I was reading a paper on attacks on RSA variants, and the paper equates $\phi(N) = (p^2-1)(q^2-1)$. Before, I have always seen $\phi(N) = (p-1)(q-1)$ and don't understand why it is different here.

I have added a screenshot of one part where they mention this below. Thanks :) enter image description here

  • $\begingroup$ digitalcommons.northgeorgia.edu/cgi/… $\endgroup$ – kelalaka Apr 11 at 9:51
  • $\begingroup$ Isn't clear? Gaussian integers are $Z[i]$ and the Euler Totient is given. $|P|$ is the norm with $P = a+bi$ and $|P| = a^2 + b^2$, if there is no imaginary part then $|P| = p^2$ $\endgroup$ – kelalaka Apr 11 at 9:54

Gaussian integers are numbers of the form $a+bi$, where $i$ is such that $i^2=-1$. If you consider them modulo a prime integer $p$, then:

  1. If $p=4k+1$, then $i$ exists in $GF(p)$ and so Gaussian integers simply reduce to $GF(p)$ when working modulo $p$, with the size of the multiplicative group equal to $p-1$.
  2. If $p=4k+3$, then $i$ does not exist in $GF(p)$ but does exist in $GF(p^2)$ (that's actually a common way to construct $GF(p^2)$ - to introduce such $i$), so Gaussian integers reduce to $GF(p^2)$ when working modulo $p$. The size of the multiplicative group is $p^2-1$.

Note that $p-1|p^2-1$ so using $p^2-1$ in the first case (as a multiple of the group order) also works for RSA. Although, for the scheme it probably matters to use primes of the form $p=4k+3$ to avoid degeneration to the basic RSA.

  • $\begingroup$ I think this answer will be great if you talk about UFD of Gaussian Integers and prime definition and How Euler Totient is defined. $\endgroup$ – kelalaka Apr 11 at 11:46
  • $\begingroup$ I specifically did not write $\phi$ but "size of the multiplicative group" because that's what matters for RSA. $\endgroup$ – Fractalice Apr 11 at 12:50
  • $\begingroup$ I see your point, I've considered it from the educative perspective. $\endgroup$ – kelalaka Apr 11 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.