A note on using complex numbers as a field

[weikengchen]

This note is left here for information purposes for someone else who may plan to change the prime number for certain applications.

The current implementation uses the complex number for the extension field F_{p^2}. This works if x^2+1 is an irreducible polynomial in F_p.

For all the Mersenne primes except 2, using the Rabin Irreducibility Test, complex numbers work fine. This is also the case considered by Virgo.

For all the primes p where p-1 has two-arity greater than 1, complex numbers would not work.

in conclusion, if one wants to change the prime number, such as for high two-arity, a different irreducible polynomial needs to be chosen. Luckily, one can try from x^2 + {-1, 0, 1} x + {-1, 1} to see if there is an easily computable one. If not, x^2 + 2, x^2 + 3 are also not hard to compute.