I know that if $(n,e)$ is the public key in RSA and we also know $d$ the private key, then there is a probabilistic algorithm to factor $n$. I'm reading the proof from Fact 1 on here.

I understand the proof until it says

"A straightforward argument shows that if $g$ is chosen at random from $\mathbb{Z}^*_N$ then with probability at least $1/2$ (over the choice of g) one of the elements in the sequence $g^{k/2}, g^{k/4}, \cdots ,g^{k/2^t} \mod N$ is a square root of unity that reveals the factorization of N."

Why is that last paragraph true?

  • $\begingroup$ Does this help you Is knowing the private key of RSA equivalent to the factorization of N? $\endgroup$
    – kelalaka
    Mar 20, 2020 at 20:23
  • $\begingroup$ @kelalaka: I wouldn't expect it would help - an answer states the algorithm, but doesn't say why it works with probability $\ge 1/2$ $\endgroup$
    – poncho
    Mar 20, 2020 at 20:26
  • $\begingroup$ @poncho last sentence of the 111's answer? $\endgroup$
    – kelalaka
    Mar 20, 2020 at 20:29
  • $\begingroup$ @kelalaka: I missed that. However, that might not satisfy Eparoh; at the very least, I see no immediate justification for the claim that "with equal probability since x is random because g is random". In particular, if N is prime, this is not true (hence any proof would need to rely on the compositeness of N) $\endgroup$
    – poncho
    Mar 20, 2020 at 20:31
  • $\begingroup$ Yes, I don't really get it from that last sentence :/ $\endgroup$
    – Eparoh
    Mar 20, 2020 at 20:34

1 Answer 1


Ok, let’s see if we can go through one line of reasoning, and see if that makes sense.

If we have the sequence:

$$g^{k/2^t} \bmod N, g^{k/2^{t-1}} \bmod N, …, g^{k/2} \bmod N, g^k \bmod N$$

We know that the last entry evaluates to 1, and we are looking at the probability (for random $g$) that the entry immediately before the first 1 is a nontrivial square root of 1.

Now, we can consider the sequences modulo $p$ and $q$, namely

$$g^{k/2^t} \bmod p, g^{k/2^{t-1}} \bmod p, …, g^{k/2} \bmod p, g^k \bmod p$$

$$g^{k/2^t} \bmod q, g^{k/2^{t-1}} \bmod q, …, g^{k/2} \bmod q, g^k \bmod q$$

Now, we might not be able to compute these values before we know the factorization, but that's OK, we're just considering them.

Both sequences end in 1, and consist of a (possibly empty) sequence of non-1 values, followed by all 1 values. In addition, $g^{k/2^i} \bmod N$ is a nontrivial square root of 1 if $g^{k/2^i} \bmod p$ is 1 and $g^{k/2^i} \bmod q$ is the last non-1 value (or versa-vica). In other words, we'll have a nontrivial square root if the two sequences turn into a 1 value at different positions in their sequences.

So, the question is: what is the probability bound on that?

Now, if $g$ is a random (equiprobable) value in $\mathbb{Z}_N^*$, then $g \bmod p$ and $g \bmod q$ are equiprobable and independently distributed values in $\mathbb{Z}_p^*$ and $\mathbb{Z}_q^*$; hence both sequences are selected from random starting values.

And, half of the values of $g$ are quadratic residues modulo $p$ and half are quadratic nonresidues modulo $p$. For a quadratic nonresidue, the mod-p sequence will become a one at step $t_p$ (where $p-1 = 2^{t_p} z_p$ for odd $z_p$; for a quadratic residue, it will be come one at an earlier step. Hence, the maximum probability for any particular step will be 0.5.

The same logic holds for $q$.

Now, $g \bmod p$ and $g \bmod q$ are independent variables, and so the maximum coincidental probability will occur if both chains have two stages with probability 0.5 each; in that case, the probability that they are difficult will be $1 - (0.5 \cdot 0.5 + 0.5 \cdot 0.5) = 0.5$.

This argument could be tightened up a bit; however it should be enough to give you some insight...

  • $\begingroup$ I don't get the end of the reasoning. I don't know why for quadratic nonresudues modulo p the sequence becomes a one at that $t_p$. I also don't understand what do you mean by the maximum probability for any particular step will be 0.5. $\endgroup$
    – Eparoh
    Mar 20, 2020 at 22:23
  • $\begingroup$ @Eparoh: if the sequence became 1 earlier than step $t_p$, then we have $(g^k)^{2^{t_p-1}} = 1$, that is, $h^{(p-1)/2} = 1$ (for $h = g^{k2^{t_p}/(p-1)}$ (and $k2^{t_p}/(p-1)$ is an odd integer). If this is the case, then $h$ is a nonQR, and if that's the case, then $g$ is one as well. Similarly, we can show that if $g$ is a QR, then it will become 1 at a step previous to the last one. $\endgroup$
    – poncho
    Mar 21, 2020 at 3:16
  • $\begingroup$ @Eparoh: as for the maximum probability of a step being 0.5, well, I believe that the probability of the last step is 0.5; that implies that the maximum probability of any other step must be, at most, 0.5 (as the probabilities must sum to 1); hence we have 0.5 as the max probability of any step $\endgroup$
    – poncho
    Mar 21, 2020 at 3:19
  • $\begingroup$ But then, all the sequences with $g$ a quadratic residue turn into $1 \mod p$ at the same point $t_p-1$, and if $g$ is a nonquadratic residue, it turns at point $t_p$. The same goes for $q$. Now, to get a non trivial square root of one we need that $t_p=t_q+1$ or $t_p=t_q-1$ but why should these values be related that way in the first place? $\endgroup$
    – Eparoh
    Mar 21, 2020 at 10:42
  • $\begingroup$ @Eparoh: no, to get a nontrivial square root, we need that the two sides turn into 1 at different steps. For a random $g \bmod p$, the $p$ side becomes 1 at step $t_p$ with probability 0.5 (because $g \bmod p$ is a nonQR with that probability), and it becomes 1 at some earlier step with probability 0.5. Hence, the probability that the $p$ side turns into 1 at some specific step is, at most, 0.5. Now, the $q$ side will become 1 at some specific step (which is independent of the $p$ side) No matter what step that happens to be, the $p$ side will happen to be that value with prob at most 0.5 $\endgroup$
    – poncho
    Mar 21, 2020 at 19:52

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.