I recently read Squeamish Ossifrage's answer on generating RSA keys from (short) randomness where they make the following comment:

(You might want to keep the certificate secret too.)

As the answer talks about multiple primality tests, let's start with a simpler one: The Pocklington-Lehmer test.

So my question:
Assuming we are given a semiprime $n$ of unknown factorization and a Pocklington Certificate of primality for either one of $n$'s prime factors. Can we efficiently factor $n$?

Here's a summary of Pocklington's theorem / criterion:

Let $n$ be the number of which we want to prove primality. Then a list of pairs pair $(a_i,p_i)$ is the pocklington-lehmer certificate for the primality of $n$ if

  1. $\prod_i p_i>\sqrt n$ that is the product of the $p_i$ is larger than the square root of $n$
  2. $\exists B: n-1=B\cdot \prod_i p_i$, that is the product of the $p_i$ is a factor of $n-1$
  3. $\forall i: p_i\in\mathbb P$, that is, every single $p_i$ is a prime itself (this primality can be proven recursively using this theorem or a list of known primes)
  4. $\forall i:a_i^{p_i}\equiv 1\pmod n$
  5. $\forall i:\gcd(a^{(n-1)/p_i}_i-1,n)=1$

1 Answer 1


Can we efficiently factor n?

Sure can, at least with that formulation of Pocklington's theorem. From the certificate, we can obtain values $a_i, p_i$ with $a_i^{p_i} - 1 \equiv 0 \pmod p$, (where $p$ is the prime factor that the certificate applies to).

So, if we compute $a_i^{p_i} - 1 \bmod n$ (where $n = pq$), we know that that is 0 modulo $p$, but is extremely unlikely to be 0 modulo $q$ (the other prime factor). So, compute the gcd of that and $n$, and that's the factor $p$.

On the other hand, if you go to the formulation on Wikipedia, instead of the listed criteria 4, we have $a^{n-1} \equiv 1 \pmod n$. Of course, knowing a value $a$ that meets that criteria leaks nothing, as (assuming $n$ is prime) any $a$ that's between 1 and $n-1$ will meet that criteria.

If you create a certificate based on that, then it may be possible to factor, but that would depend on how the prime was generated (e.g. if the large factor $r$ of $p$ was not that much smaller than $p$, then it is easy; if it is just slightly larger than $\sqrt{p}$, then you need to hope that $(p-1)/r$ happens to be smooth (which is unlikely).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.