# Zero knowledge of two factor

Here I overconfident in myself state that I can show, that n has two factors.

This is not completely true, can possibly show $n$ is composite - prover generates RSA key with modulo $n$, and gives $e$ to verifier.

Verifier takes random number $x$, and checks if $x^{e*d}=x$, where $d*e=1$ (mod $n-1$). If it is, then $n$ is prime, if not $n$ is composite and has factors.

Verifier sends $x^e$ to prover, and if prover sends back $x$ we can be sure that prover has factors of $n$. This doesnt, however garanties that there is just two factors.

How to prove-verify that there is only two factors in $n$?

UPDATE: This is not zeroproof, it is interactive here as was pointed in comments. Well, then. Question becomes more broader - can (duh) show that $n$ is not a prime. How to show it has two factors, zero knowledge, without interactivity?

• "This doesnt, however garanties that there is just two factors." It's also not zero knowledge: a simulator without access to the prover would be unable to compute $x$. – fkraiem Mar 27 '15 at 17:54
• yea, had a feeling i miss interactivity here, thanks – Timo Junolainen Mar 27 '15 at 17:57
• Actually, there is no need for a ZKP that $n$ is not prime; anyone can verify that directly in polynomial time. – poncho Mar 27 '15 at 18:01
• yes, but to show that there is no more, no less than two factors? – Timo Junolainen Mar 27 '15 at 18:03

1. Firstly, convince the verifier that $$n$$ is not a prime number. (Prime is in P)

2. Use Zero-Knowledge Proof to make sure that $$n$$ has no square factor (no $$p^2|n$$)

See this paper Practical zero-knowledge proofs: Giving hints and using deficiencies for details.

3. Showing that $$n$$ has exactly two factors: if not, the number of quadratic residues is roughly less than $$1/8*n$$. Verifier just randomly chooses a value y and ask prover to prove whether y is quadratic residue.

If the probability is roughly $$1/4$$, then accept. Verifier can't cheat since he can only compute the quadratic residue, and let the probability raise, but not decrease below $$1/8$$.

• How one does the 1. – kelalaka Nov 5 '18 at 11:45
• Since it's in P, the simulator of zero-knowledge proof can perfectly simulate step 1. But step 3 is incorrect. Zero-knowledge proof requires if it's true, then verifier can accept it with probability 1, but in my proof, we can only do it with high probability. – mignonjia Nov 6 '18 at 12:13
• this is not zero knowledge, verifier learns if y is quqdratic residue for many y – Meir Maor Nov 6 '18 at 19:43