mersenneforum.org a new Deterministic primality testing
 Register FAQ Search Today's Posts Mark Forums Read

2012-12-13, 13:49   #34
axn

Jun 2003

125516 Posts

Quote:
 Originally Posted by wsc812 I have found the Complete proof for N=4k+3!!!!!
The big blue text (and the exclamation marks) doesn't inspire much confidence, I'll admit. However, if it does pan out, i suspect it'll be a BIG result.

What are your plans for getting this proof verified and published?

Last fiddled with by axn on 2012-12-13 at 13:50 Reason: our->your

 2012-12-20, 03:33 #35 wsc812   Dec 2012 China 1110 Posts see my complete proof on mathoverflow http://mathoverflow.net/questions/11.../115262#115262
2013-03-01, 17:26   #36
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 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]

 2013-03-04, 06:25 #37 paulunderwood     Sep 2002 Database er0rr 5·7·97 Posts The time taken to do one Fermat Little Theorem test is "1 selfridge" by definition. A lucas test with Q=1 takes 2 selfridge. Exponentiation of (a+i*b) over x^2+1 can be achieved in 2 selfridge, by noting that the squaring operation requires two multiplications: (A-B)*(A+B) and 2*A*B*i, where A and B are intermediate values. During exponentiation, multiplication by the base is cheap. A base (a^2+b^2) Fermat test is implicit. So rather than doing Grantham's Frobenius test, which is 1+2 selfridge, one could do a base 2-prp test and then exponentiation of a+b*i, a total of 1+2 selfridge but with an extra Fermat test done for free. Please see http://www.mersenneforum.org/showpos...7&postcount=44 for more detail. (A better version of my paper is available in the file section of the Yahoo primenumbers group.) Last fiddled with by paulunderwood on 2013-03-04 at 06:38

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 194 2018-03-19 05:54 lukerichards Software 8 2018-01-24 22:30 1260 Software 17 2015-08-28 01:35 CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12 jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 05:11.

Tue Sep 22 05:11:04 UTC 2020 up 12 days, 2:22, 0 users, load averages: 1.51, 1.97, 1.83