COMPOSITES is in NP · certificate is a divisor

COMPOSITES = {n : n is composite}. Certificate for n: a non-trivial divisor d (1 < d < n). Verifier: confirm n mod d = 0. Polynomial in log n.

• "Polynomial" is polynomial in the bit length of n, not in n itself. Input size is |n| ≈ log n. A divisor's bit length is (log n)/2 — polynomial.
• 1 and n are trivial divisors and don't count. The certificate is a divisor strictly between 1 and n. Without this restriction, every number would have a "divisor" and the problem would collapse.
• PRIMES vs COMPOSITES. PRIMES is the complement of COMPOSITES (modulo 0, 1). Both are in NP. Both are in P (AKS 2002). For decades only NP membership was known.

• Q1. Why is the certificate "small"?
  A non-trivial divisor d satisfies d ≤ √n, so its bit length is at most (log n)/2 — half the bit length of n. Polynomial in input size.
• Q2. Is the verifier polynomial?
  Yes — dividing n by d using school long division takes O((log n)²) bit operations. Verifying n mod d = 0 fits easily in P.
• Q3. How does AKS achieve P?
  AKS (Agrawal–Kayal–Saxena 2002) uses a polynomial identity test over (Z/nZ)[x] — checks whether (x − a)ⁿ ≡ xⁿ − a (mod x^r − 1, n) for many a. Not a divisor at all — entirely different witness structure. The algorithm runs in O((log n)⁶) bit operations.
• Q4. What's the historical lesson?
  "NP but maybe not P" doesn't mean "actually outside P." PRIMES sat in NP for 25+ years before AKS placed it in P. The same could happen to other natural NP problems — although for NP-complete problems, that would require P = NP.

Sipser: §7.3 (NP examples). AKS paper. Lecture notes: Module 5 slide 2. Companion problems: P21 (verifier vs solver), P22 (SAT).