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.
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:
- 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$.
- 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.