20121205, 13:21  #1 
Dec 2012
China
11 Posts 
a new Deterministic primality testing
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 .
__________ We know that if ( is a prime), then for every gaussian integer , Now consider a composite satisfies this condistion for , I use Mathematica8 and find no solution less than , can someone find a larger number for the condition? I guess it's impossible for a composite N. So this can be use for Primality test. Last fiddled with by Batalov on 20121206 at 02:30 Reason: (original message kept, tex'ed version added) 
20121205, 15:07  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I haven't found counterexamples up to 10^7, except powers of 3 with odd exponent.
However, I suspect that this might be a kind of combined p1 and p+1 test in disguise, and for those there are pairs of parameters known for which there is no known counterexample, but no proof of deterministicness (is that a word?), either. See for example http://mathworld.wolfram.com/Baillie...alityTest.html Last fiddled with by akruppa on 20130118 at 10:36 Reason: now>no 
20121205, 15:32  #3 
Sep 2002
Database er0rr
2·3^{2}·11·19 Posts 
Earlier this year, I tested 2+i for n==3 (mod 4) up to 10^13 without finding a counterexample
Last fiddled with by paulunderwood on 20121205 at 15:37 
20121205, 18:46  #4 
"Robert Gerbicz"
Oct 2005
Hungary
2·743 Posts 
This would be an AKS type test: n=4k+3 is prime iff (2*x+3)^n==32*x mod (x^2+1,n)
To see this notice that the minimal polynom of I is x^2+1 (and not x^41). This subject is an old topic not to use that many polynom tests for AKS, only a few. Here it would mean only one polynom. 
20121205, 21:24  #5 
∂^{2}ω=0
Sep 2002
República de California
19×613 Posts 
My guess would be that the appropriate "suffixing to imply the property of being ___" here is analogous to the one for e.g. "domestic". I love words that, even when spelled correctly, just sound plain wrong: coolth ... gruntled ... "deterministicity" seems a fine addition to this distinguished pantheon.
 Edit: Of course using the alternative analogy with e.g. optimistic/pessimistic one arrives at the accepted suffixing here, "determinism"  but where's the fun in that? Last fiddled with by ewmayer on 20121205 at 22:09 
20121206, 03:58  #6 
Romulan Interpreter
Jun 2011
Thailand
25BF_{16} Posts 
[offtopic]
related to that I really have a problem with "primality" because is always underlined red by the spellchecker and that "piss me off" for such a simple word. I tried different forms, even using "r" or "double l" in all variations, but all ended up in being underlined, and I concluded that either there is no word like that, either I am dumb, or the speller is not so clever, therefore I continued to use "primality". So, what is the correct form? [/offtopic] Last fiddled with by LaurV on 20121206 at 04:00 Reason: [ot] tags 
20121206, 04:26  #7  
∂^{2}ω=0
Sep 2002
República de California
11647_{10} Posts 
Quote:


20121206, 04:38  #8  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,497 Posts 
Quote:
Have you tried: rightclick on the word primality, and "add to dictionary"? Same with heteroscedacity, pseudomarkers, telomeric ...and an endless score of biological and statistical terms. Add them once and never be bothered again. Maybe. Last fiddled with by Batalov on 20121206 at 04:39 Reason: (I need a spellchecker, too) 

20121206, 07:36  #9 
Romulan Interpreter
Jun 2011
Thailand
9663_{10} Posts 
Did that for colleagues' names (never remember Thai names!) and other common words which I know they are not English, and even some technical words (same as your biology stuff, but for me is microcontroller, photodiode, etc) which I don't give a darn if they are English or not, as long as I need to use them and everybody understand them. Including my family name, which the autosubstitute was always replacing it with a bad English word, hehe. Those are all complex** words! But primality? grrr.
** That to stay on topic with complex numbers Now to really stay on topic, for every odd prime is easy to show that according with its modularity to 4, the expression (3+2i)^n is either 3+2i, either 32i. Putting this in a pari line: Code:
gp > n=3; a=3+2*I; while((n+=2)<10^6, if(n%4==3, c=32*I; b=real(d=a^n)%n(nimag(d))%n*I, c=3+2*I; b=real(d=a^n)%n+imag(d)%n*I); if(b==c&&!isprime(n), print(n))) 1105 2465 10585 29341 41041 46657 115921 etc Now, all that appear in the list are 1 (mod 4), but there is no reason why 3 (mod 4) numbers won't appear if we go higher. We also can change the complex base, to get some other numbers which "pass". We can see this works right, by removing the "&&!isprime()" call then it prints all primes. For example, with 2+i, there are the same as above, plus few additional: 15841 is one of them. Last fiddled with by LaurV on 20121206 at 07:41 
20121206, 07:56  #10 
Romulan Interpreter
Jun 2011
Thailand
3·3,221 Posts 
It turned out there is no big deal to implement this. No idea if pari has one already. I made it recursive, if power is even, call the function with power>>1, square, if power is odd multiply, take mod at the end. I put that in a "cIsPrime(b,n)" function, which will return 1 if n is probable prime base b, with b being a complex number.
The nicer part is that now, a complex number can be one with the imaginary part being zero . Do you recognize these numbers? (please scroll down into the code section) Code:
gp> forstep(n=3,10^6,2, if(cIsPrime(2,n)&&!isprime(n),print(n))) 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 *** <break, snip, this is very fast anyhow> *** gp > forstep(n=3,10^6,2, if(cIsPrime(3+2*I,n)&&!isprime(n),print(n))) 1105 2465 10585 29341 41041 46657 *** <break, snip, this is very fast anyhow> *** // <This is a beautiful one!> : gp > forstep(n=3,10^6,2, if(cIsPrime(1+I,n)&&!isprime(n),print(n))) 561 1105 1729 1905 2047 2465 3277 4033 4681 6601 8321 8481 10585 12801 15841 16705 <etc> Last fiddled with by LaurV on 20121206 at 08:01 Reason: cut the lists, too long code section, bolded, red color 
20121206, 08:48  #11 
Dec 2012
China
11 Posts 
is algorithm complexity For ? we may not select base , for effectively testing, and calculate
instead of Last fiddled with by wsc812 on 20121206 at 09:07 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test  a1call  Miscellaneous Math  194  20180319 05:54 
Primality testing nonMersennes  lukerichards  Software  8  20180124 22:30 
Testing an expression for primality  1260  Software  17  20150828 01:35 
Testing Mersenne cofactors for primality?  CRGreathouse  Computer Science & Computational Number Theory  18  20130608 19:12 
a new primality testing method  jasong  Math  1  20071106 21:46 