Go Back > Math Stuff > Computer Science & Computational Number Theory

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

3·17·101 Posts

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 offline   Reply With Quote
Old 2012-12-20, 03:33   #35
Dec 2012

11 Posts

see my complete proof on mathoverflow
wsc812 is offline   Reply With Quote
Old 2013-03-01, 17:26   #36
akruppa's Avatar
Aug 2002

2,467 Posts

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's Avatar
Sep 2002
Database er0rr

387310 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 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

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 07:19.

Mon Oct 25 07:19:04 UTC 2021 up 94 days, 1:48, 0 users, load averages: 1.15, 0.94, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.