Can we efficiently factor if we are given a Pocklington certificate of one of the prime factors?

Question

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$

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).