Find Gaussian prime with a given norm in effective way

[Bodigrim]

There are three kinds of Gaussian primes (see Math.NumberTheory.GaussianIntegers.primes):

• 1 + i,
• p + 0i, where p is an integer prime and p = 4k+3,
• a + bi, where a^2+b^2 is an integer prime and p = 4k+1.

In the third case it is non-trivial how to find a and b, satisfying a^2+b2 = p for a given p. Currently Math.NumberTheory.GaussianIntegers.findPrime' does it via brute force.

We should rather employ the Hermite-Serret algorithm. Resources: https://math.stackexchange.com/a/5883 http://www.ams.org/journals/mcom/1972-26-120/S0025-5718-1972-0314745-6/S0025-5718-1972-0314745-6.pdf

[rockbmb]

@Bodigrim

a + bi, where a^2+b^2 is an integer prime and p = 4k+1.

Don't you mean

a + bi, where a^2+b^2 is an integer prime p and p = 4k+1.

?

I'm revisiting this issue because it seems there is no such algorithm for Eisenstein integers as there is for Gaussian integers, at least from what I've seen. It seems someone will have to discover it.

[Bodigrim]

Yes, I meant a^2+b^2 = p = 4k + 1.

Basically, findPrime for Gaussian integers consists of two steps:

• Find one of roots of the quadratic equation norm (z :+ 1) = 0 (mod p).
• Return gcd (p :+ 0) (z :+ 1), which is a Gaussian prime.

Since for Gaussian integers norm (z :+ 1) = z^2 + 1, we have z = sqrt(-1) (mod p). For Eisenstein integers it is not that straightforward, but I believe one can solve a quadratic equation as usual, employing modular square root and modular division instead of real ones.

[rockbmb]

@Bodigrim so, for Eisenstein integers, what we need is to

• Find one of the roots of the quadratic equation norm (z :+ 1) = 0 (mod p) <=> z^2 - z + 1 = 0 (mod p).

I'll look into this.

[rockbmb]

@Bodigrim

For Eisenstein integers it is not that straightforward

I forgot to ask, did this mean the two steps you described in this issue's first post will not be enough? Or that they are enough, but some parts of them will not be so simple as they were for Gaussian integers? I.e. Having to solve a not-so-trivial z^2 - z + 1 = 0 (mod p)?

[Bodigrim]

Well, I have not tested it and I do not know any references, but I believe that the only difference is to solve z^2 - z + 1 = 0 (mod p) instead of z^2 + 1 = 0 (mod p).

[rockbmb]

@Bodigrim well, I guess we'll just have to see if findPrimes for Eisenstein integers will produce what we want or not, after it's written.