# 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? – kelalaka Mar 20 '20 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$ – poncho Mar 20 '20 at 20:26
• @poncho last sentence of the 111's answer? – kelalaka Mar 20 '20 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) – poncho Mar 20 '20 at 20:31
• Yes, I don't really get it from that last sentence :/ – Eparoh Mar 20 '20 at 20:34

Ok, lets 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 squareroot 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 squareroot 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 squareroot if the two sequences turn into a 1 value at different positions in their sequences. So, the question is: what is the probability bounds 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. – Eparoh Mar 20 '20 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. – poncho Mar 21 '20 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 – poncho Mar 21 '20 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? – Eparoh Mar 21 '20 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 – poncho Mar 21 '20 at 19:52