# Factoring $n$ in RSA knowing $e$ and $d$

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?

• Does this help you Is knowing the private key of RSA equivalent to the factorization of N? Commented Mar 20, 2020 at 20:23
• @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$ Commented Mar 20, 2020 at 20:26
• @poncho last sentence of the 111's answer? Commented Mar 20, 2020 at 20:29
• @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) Commented Mar 20, 2020 at 20:31
• Yes, I don't really get it from that last sentence :/ Commented Mar 20, 2020 at 20:34

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

• 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. Commented Mar 20, 2020 at 22:23
• @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. Commented Mar 21, 2020 at 3:16
• @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 Commented Mar 21, 2020 at 3:19
• 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? Commented Mar 21, 2020 at 10:42
• @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 Commented Mar 21, 2020 at 19:52