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

 2012-12-06, 09:55 #12 LaurV Romulan Interpreter     Jun 2011 Thailand 22·3·739 Posts Yes, the algorithm has the same complexity as a Sarus test (2-PRP 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 2012-12-06 at 10:08 Reason: links
 2012-12-06, 10:03 #13 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 216468 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.
 2012-12-06, 11:07 #14 R. Gerbicz     "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: (3-2*I)^n==3-2*I mod n multiple them (notice that the modulus is the same here): 13^n==13 mod n So the counter-examples are also base-13 pseudo primes. Last fiddled with by R. Gerbicz on 2012-12-06 at 11:08
2012-12-06, 11:29   #15
wsc812

Dec 2012
China

11 Posts

Quote:
 Originally Posted by R. Gerbicz Hm, another interesting property: (3+2*I)^n==3+2*I mod n then conjugate it: (3-2*I)^n==3-2*I mod n multiple them (notice that the modulus is the same here): 13^n==13 mod n So the counter-examples are also base-13 pseudo primes.
sorry! R. Gerbicz .I'm not good at English ,I don't understand your meaning .now my proof is in progress,and at first we can conclude there is no $4k+1$ factors for
$N=4k+3$ if a counter-examples exists.

Last fiddled with by wsc812 on 2012-12-06 at 12:18

 2012-12-06, 11:43 #16 paulunderwood     Sep 2002 Database er0rr 344610 Posts R. Gerbicz is right. For 2+i you can use a 5-prp test. In general, for a+b*i you can do a base (a^2+b^2) prp test, where kronecker((2*a)^2-4*(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 2012-12-06 at 12:42
 2012-12-06, 16:36 #17 LaurV Romulan Interpreter     Jun 2011 Thailand 212448 Posts Yeah, I also figured this out and I was playing with something identical. The chances are quite high to find one 13-PRP 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))==13||z==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 2012-12-06 at 16:44
 2012-12-06, 18:31 #18 wsc812   Dec 2012 China 138 Posts 2465=5*17*29 10585=5*29*73 162401=17*41*233
 2012-12-06, 19:49 #19 wsc812   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
 2012-12-06, 21:09 #20 wsc812   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
 2012-12-07, 01:49 #21 LaurV Romulan Interpreter     Jun 2011 Thailand 22·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 "hiden-base" 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.
 2012-12-07, 02:10 #22 wsc812   Dec 2012 China 11 Posts 123 Last fiddled with by wsc812 on 2012-12-07 at 02:34

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

Sun Oct 25 19:51:26 UTC 2020 up 45 days, 17:02, 0 users, load averages: 1.65, 1.77, 1.62