# Why is $\phi(N) = (p^2 -1) (q^2 - 1)$ here?

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 :)

• digitalcommons.northgeorgia.edu/cgi/… – kelalaka Apr 11 at 9:51
• 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$ – kelalaka Apr 11 at 9:54

## 1 Answer

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.

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