zkdocs
zkdocs copied to clipboard
Short factoring proofs: Addition of phi(N)
In the short factoring proof, there is the line $y = r + (N - \varphi(N))e$. In the vanilla protocol, the verifier checks $x \overset{?}{\equiv} z^{y - eN} \mod N$. Because $\varphi(N)$ is the order of the multiplicative group of integers modulo $N$, taking the exponent of a multiple of $\varphi(N)$ gives you the identity 1 for all group elements, so $z^{\varphi(N)e} \equiv 1 \mod N$. This is my understanding how the protocol works.
I was wondering, can we define $y = r + (N + \varphi(N))e$ instead? The minus sign seems redundant to me and the above argument should still work, shouldn't it?