2
$\begingroup$

I read in this paper (see page 1 paragraph 3) that Gaussian integers arithmetic $\pmod{p}$, where $p\in\mathbb{Z}^+$ is a prime, requires that $p \equiv 3 \pmod{4}$.

I have some doubts here that I hope one can clarify:

1- Why is this necessary?

2- What about primes $\equiv 1 \pmod{4}$? don't they support Gaussian integers arithmetic (I tired some examples and it works fine for +,-,*)?

3- Which operations are not supported specifically (division, remainder, or what)?

4- Is there any trick that can be used to support Gaussian integers arithmetic using these primes $\equiv 1 \pmod{4}$?

$\endgroup$
5
  • $\begingroup$ The main thing is that your notion of something being "prime" is relative to what ring (ordinary integers, Gaussian integers, etc.) you're working in. Ordinary prime numbers from $\mathbb{Z}$ which are congruent to $3$ mod $4$ remain prime when you consider them as Gaussian integers, other primes do not. $\endgroup$
    – D_S
    Commented Jan 18, 2017 at 2:27
  • $\begingroup$ I don't really need to work with $p$ in the Gaussian integers domain. I just wan't to perform that Discrete Galois Transform mentioned in the same paper but modulo a prime congruent to 1 $\pmod{p}$ $\endgroup$
    – caesar
    Commented Jan 18, 2017 at 2:33
  • $\begingroup$ Isn't the paper only about Mersenne primes? They are always congruent to $3$ mod $4$. $\endgroup$
    – D_S
    Commented Jan 18, 2017 at 2:38
  • $\begingroup$ Yes, but I am trying to perform the transform over a non-Mersenne prime. I understood that the transform can be computed using a Mersenne prime or any other prime congruent to $3 \pmod{4}$ which includes the Mersenne primes as well. The prime number I am working with is congruent to $1 \pmod{4}$. So, I am just worried that the transform may not work as intended for. $\endgroup$
    – caesar
    Commented Jan 18, 2017 at 2:43
  • $\begingroup$ I see, you should have mentioned you were working in a finite field. $\endgroup$
    – D_S
    Commented Jan 18, 2017 at 2:44

1 Answer 1

Reset to default
2
$\begingroup$

As I understand, $p$ is a prime number, and you are working in a field $F$ with $p^2$ elements. This field contains the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ with $p$ elements as a subfield.

Assuming $p$ is congruent to $3$ modulo $4$, it is possible to write the elements of $F$ in a similar way to Gaussian integers: namely, there some is element of $F$, let's call it $i$, with the property that $i^2 = -1$. Such an element $i$ will not be in $\mathbb{F}_p$. Then

$$F = \{ a+ bi : a, b \in \mathbb{F}_p \}$$

You can't do this if $p \equiv 1 \pmod{4}$, because in this case, the square roots of $-1$ already lie in $\mathbb{F}_p$. For example, if $p = 5$, then $-1$ is equal to $2^2$. Therefore, the set

$$\{ a + bi : a, b \in \mathbb{F}_p\}$$

just gets you $\mathbb{F}_p$, not all of $F$.

$\endgroup$
1
  • 1
    $\begingroup$ That was a great help @D_S. Thank you. $\endgroup$
    – caesar
    Commented Jan 18, 2017 at 2:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .