Lemma: Sound verification of the root list

There is a deterministic polynomial-time verifier for (eq:encoding). It accepts precisely the complete correctly ordered prime lists for $N$, including the zero-padding convention.

Proof. Check that the positive entries precede all zero entries, are at least two, and are nondecreasing. Check primality of every positive entry by a deterministic polynomial-time primality test AKS,AKSErratum. Multiply the positive entries and compare with $N$.

There are at most $n$ factors, each of at most $n$ bits. Their product has at most $n^2$ bits, including on invalid guesses. Schoolbook multiplication and all comparisons therefore have polynomial bit cost. Acceptance gives a prime product equal to $N$, and unique factorization gives exactly the required list. The converse follows from the definition.