mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2012-12-13, 13:49   #34
axn
 
axn's Avatar
 
Jun 2003

125516 Posts
Default

Quote:
Originally Posted by wsc812 View Post
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
axn is online now   Reply With Quote
Old 2012-12-20, 03:33   #35
wsc812
 
Dec 2012
China

1110 Posts
Smile

see my complete proof on mathoverflow
http://mathoverflow.net/questions/11.../115262#115262
wsc812 is offline   Reply With Quote
Old 2013-03-01, 17:26   #36
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by wsc812 View Post
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]
akruppa is offline   Reply With Quote
Old 2013-03-04, 06:25   #37
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·7·97 Posts
Default

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
paulunderwood is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test a1call Miscellaneous Math 194 2018-03-19 05:54
Primality testing non-Mersennes lukerichards Software 8 2018-01-24 22:30
Testing an expression for primality 1260 Software 17 2015-08-28 01:35
Testing Mersenne cofactors for primality? CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12
a new primality testing method 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.