View Single Post
2013-03-01, 17:26   #36
akruppa

"Nancy"
Aug 2002
Alexandria

46408 Posts

Quote:
 Originally Posted by wsc812 we know that if $q=4k+3$ ($q$ is a prime), then $(a+bI)^q=a^q+b^q(I)^{4k+3}(mod q) =a -bI$ for every gaussian integer $(a+bi)$ ,Now consider a composite $N=4k+3$ satisfies this condistion for $a+bi=3+2i$, I use Mathematica8 and find no solutison$less than$5\cdot 10^7, can someone find a lager number for the condition . I guess it's impossible for a composite N.So this can be use for Primality test .
This is in fact a particular case of the Frobenius test, explained in Crandall and Pomerance, among others. You are working in Fp[x]/(x^2+1) which is a proper quadratic extension for a prime p ≡ 3 (mod 4). Then the Frobenius automorphism maps (a+bi) to its conjugate (a+bi)p = (a-bi). Testing that this condition holds is the basic idea behind Grantham's Frobenius test, which he also generalized to higher-degree extension fields. The Frobenius test is quite a strong probabilistic primality test, but there is no proof as far as I know that it is deterministic with any polynomial, and the idea is not new, either.

Last fiddled with by akruppa on 2013-03-01 at 20:19 Reason: [x]