mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-12-06, 09:55   #12
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-12-06, 10:03   #13
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216468 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2012-12-06, 11:07   #14
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×5×47 Posts
Default

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
R. Gerbicz is offline   Reply With Quote
Old 2012-12-06, 11:29   #15
wsc812
 
Dec 2012
China

11 Posts
Exclamation

Quote:
Originally Posted by R. Gerbicz View Post
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
wsc812 is offline   Reply With Quote
Old 2012-12-06, 11:43   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

344610 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2012-12-06, 16:36   #17
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

212448 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-12-06, 18:31   #18
wsc812
 
Dec 2012
China

138 Posts
Default

2465=5*17*29
10585=5*29*73
162401=17*41*233
wsc812 is offline   Reply With Quote
Old 2012-12-06, 19:49   #19
wsc812
 
Dec 2012
China

11 Posts
Default

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
wsc812 is offline   Reply With Quote
Old 2012-12-06, 21:09   #20
wsc812
 
Dec 2012
China

11 Posts
Default

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
wsc812 is offline   Reply With Quote
Old 2012-12-07, 01:49   #21
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2012-12-07, 02:10   #22
wsc812
 
Dec 2012
China

11 Posts
Post

123

Last fiddled with by wsc812 on 2012-12-07 at 02:34
wsc812 is offline   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 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

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.