20121206, 09:55  #12 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·3·739 Posts 
Yes, the algorithm has the same complexity as a Sarus test (2PRP test), except you do few more multiplications and two modular reductions after each powering (real and imag), but the complexity is the same. This is very fast test, but the question is if the only numbers to pass it are prime, or there are also "pseudoprimes" passing it. As people said already (and I also believe that), this seems to be only a disguised form of "multiple base" PRP test. It does not guarantee the "primality" (grrr, underlined again ). And the preliminary tests for different (complex) bases shows that generally carmichael numbers and euler pseudoprimes pass it with brio. Therefore, "heuristic" suggests that 3+2i (or other) base could be just a "tougher" one, but not guarantee primality unless you can prove so. I can't prove.
Here is where some expert adviser like RDS would be really welcomed. Last fiddled with by LaurV on 20121206 at 10:08 Reason: links 
20121206, 10:03  #13 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
21646_{8} Posts 
Now he is laughing at y'all! "Take this, MFers!"
P.S. Homoscedacity is even worse, come to think about it. __________ *by MFers I (he) obviously meant mersenneforumers. 
20121206, 11:07  #14 
"Robert Gerbicz"
Oct 2005
Hungary
2×3×5×47 Posts 
Hm, another interesting property:
(3+2*I)^n==3+2*I mod n then conjugate it: (32*I)^n==32*I mod n multiple them (notice that the modulus is the same here): 13^n==13 mod n So the counterexamples are also base13 pseudo primes. Last fiddled with by R. Gerbicz on 20121206 at 11:08 
20121206, 11:29  #15  
Dec 2012
China
11 Posts 
Quote:
if a counterexamples exists. Last fiddled with by wsc812 on 20121206 at 12:18 

20121206, 11:43  #16 
Sep 2002
Database er0rr
3446_{10} Posts 
R. Gerbicz is right. For 2+i you can use a 5prp test. In general, for a+b*i you can do a base (a^2+b^2) prp test, where kronecker((2*a)^24*(a^2+b^2),n)==1 i.e n==3 (mod 4). The logical converse does not hold: (a^2+b^2)prp does not imply (a+b*i)^(n+1)==a^2+b^2 (mod n)
Last fiddled with by paulunderwood on 20121206 at 12:42 
20121206, 16:36  #17 
Romulan Interpreter
Jun 2011
Thailand
21244_{8} Posts 
Yeah, I also figured this out and I was playing with something identical. The chances are quite high to find one 13PRP which verifies the complex base too. For example, there are 53 pseudoprimes base 13 which verifies the condition under 10^7, unfortunately all are 1 (mod 4). I let this program running since I arrived home (about 5 hours ago) and it is close to 10^9 now, still no counterexample for 3 (mod 4). I will let it run overnight (in one core).
Code:
gp > b=3+2*I; cnt=0; nr=0; n=2; while((n=nextPSP(n++,13))<=10^7, if(((z=cpowmod(b,n+1,n))==13z==5+12*I)&&!i sprime(n),nr++; print(n" : "n%4" ")); if(n>cnt, cnt+=1000; printf("...%d...%c",n,13))); print(" ") ; nr 2465 : 1 10585 : 1 162401 : 1 252601 : 1 278545 : 1 294409 : 1 340033 : 1 410041 : 1 459709 : 1 488881 : 1 493697 : 1 636641 : 1 694153 : 1 1042417 : 1 1194285 : 1 1461241 : 1 1615681 : 1 1683969 : 1 1703677 : 1 1735841 : 1 1755001 : 1 1909001 : 1 1987021 : 1 2113921 : 1 2134277 : 1 2433601 : 1 2704801 : 1 2899801 : 1 3075521 : 1 3581761 : 1 4082653 : 1 4335241 : 1 4408321 : 1 4561481 : 1 4567837 : 1 5148001 : 1 5265937 : 1 5308181 : 1 5444489 : 1 6054985 : 1 6157601 : 1 6189121 : 1 6313681 : 1 6976201 : 1 7207201 : 1 7519441 : 1 7648033 : 1 7982129 : 1 8134561 : 1 8231653 : 1 8719921 : 1 8725753 : 1 9131401 : 1 (nr) = 53 gp > Last fiddled with by LaurV on 20121206 at 16:44 
20121206, 18:31  #18 
Dec 2012
China
13_{8} Posts 
2465=5*17*29
10585=5*29*73 162401=17*41*233 
20121206, 19:49  #19 
Dec 2012
China
11 Posts 
these numbers are all psp(13) and have no 4k+3 factors ,we may decompose it by using extraction squre root constantly until it become a complex.
e.g (3+2i)^20300=80852+1631i (mod 192401 ) calculate GCD[1631,162401]=233 or GCD[80852,162401]=41 
20121206, 21:09  #20 
Dec 2012
China
11 Posts 
I found all these psp(3+2i) are not spsp(13), so we can find its factors easily. now whether we can give a certanty primality test no matter what it's 4k+1 or 4k+3

20121207, 01:49  #21 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·3·739 Posts 
There are another 73 of them, to 10^8, all being 1 (mod 4). And more if you go higher. No 3 (mod 4) yet, I think I will stop to 10^9 (did not reach it yet, when I left in the morning it looked like it still had few hours left to go; it goes slower as the numbers grow). Do we really need another PRP test? How does proving primality goes? :D We would fell much better if someone can crack it theoretically. Till then I am still holding to my opinion that we have a "hidenbase" PRP test, and a counterexample should appear sooner or later. This would not be so useful, we "know" how to test small numbers for primality. A "sure primality" test that would be easy to apply for large numbers in their general form, would be totally other story.

20121207, 02:10  #22 
Dec 2012
China
11 Posts 
123
Last fiddled with by wsc812 on 20121207 at 02:34 
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 