20201117, 19:07  #1 
Sep 2002
Database er0rr
3,617 Posts 
1+1 Selfridges PRP test
This script outputs no counterexamples:
Code:
{ forstep(a=3,100,1,print(a); D=a^24;E=D^24; forstep(n=4*E1,50000000*E,4*E, if(kronecker(D,n)==1&&!ispseudoprime(n), r=Mod(D,n)^((n1)/2);s=Mod(E,n)^((n1)/2); if(r==1&&s==1, print([n,r,s]))))) } 
20201117, 20:49  #2 
Feb 2017
Nowhere
4,457 Posts 

20201117, 20:54  #3  
"Sam"
Nov 2016
2·163 Posts 
Quote:
Code:
for(n=1,30000, if(n%2==1 & isprime(n)==0, for(a=1,n, if(kronecker(a^24,n)==(1) & kronecker(a^48*a^2+12,n)==(1) & Mod(a^24,n)^((n1)/2)==(1) & Mod(a^48*a^212,n)^((n1)/2)==(1), print([a,n]))))) Code:
703, 1387, 1891, 2071, 2743, 4187, 6943, 8227, 11359, 11773, 12403, 13019, 13747, 14383, 14701, 15251, 16441, 16531, 16589, 17261, 17767, 18721, 19093, 19951, 20567, 21667, 22411, 24727, 24929, 25531, 27217, 29341, 29891, ... EDIT: Code:
for(n=1,30000, if(n%2==1 & isprime(n)==0, for(a=1,n, if(kronecker(a^24,n)==(1) & kronecker(a^48*a^2+12,n)==(1) & Mod(a^24,n)^((n1)/2)==(1) & Mod(a^48*a^212,n)^((n1)/2)==(1), print([a,n]))))) Code:
259, 671, 703, 1649, 1891, 2059, 2701, 6001, 7471, 7957, 8911, 9211, 9881, 10963, 12403, 13213, 13747, 14111, 14491, 14701, 15203, 15251, 16531, 16589, 18631, 18721, 19951, 20263, 20567, 20591, 21349, 21667, 23377, 24461, 24727, 25351, 26599, 27613, 28939, 29341, 29539, 29891,... Last fiddled with by carpetpool on 20201117 at 21:03 Reason: s should be 1 not 1: 

20201117, 22:16  #4 
Sep 2002
Database er0rr
3,617 Posts 
No. "n" is the number tested, although I do not see how to make it an argument of a function.
Last fiddled with by paulunderwood on 20201117 at 22:23 
20201117, 22:18  #5  
Sep 2002
Database er0rr
3,617 Posts 
Quote:


20201117, 22:43  #6  
Sep 2002
Database er0rr
3,617 Posts 
Quote:
a even means gcd(D,E)>1. Anyway I am rerunning with some higher bounds. Last fiddled with by paulunderwood on 20201117 at 22:43 

20201117, 23:54  #7 
Feb 2017
Nowhere
4,457 Posts 
The reason I asked about the forstep() was that it was a forstep() rather than a for()
;) 
20201118, 04:02  #8 
Romulan Interpreter
Jun 2011
Thailand
3^{3}×347 Posts 
Then why the "forstep"? if the step is 1, you could just use a simple "for" which is a bit faster (internally, it uses increment instead of addition).
Edit: crosspost with Dr.S., sorry, I didn't refresh my page, from morning Last fiddled with by LaurV on 20201118 at 04:05 
20201118, 04:12  #9  
Sep 2002
Database er0rr
3,617 Posts 
Quote:
Another speed up might be had be putting !ispseudoprime() ahead of kronecker(). Anyway, I am now running with the bound 2250000000*E and have reached a=41. The only counterexample is the aforementioned one for a=4. Last fiddled with by paulunderwood on 20201118 at 04:13 

20201118, 14:48  #10  
Sep 2002
Database er0rr
3,617 Posts 
Quote:
I am now looping heavily over a with a shallow inner loop. After I will hammer a=3 to 10 to see if I can find another pseudoprime. It is remarkable that after 14 hours of computation only one pseudoprime was found. Last fiddled with by paulunderwood on 20201118 at 14:54 

20201118, 15:23  #11  
Feb 2017
Nowhere
4,457 Posts 
I checked this example, just to see if anything interesting was going on.
Code:
? factor(68368998319) %1 = [106747 1] [640477 1] ? for(i=1,#%1[,1],print(factor(%1[i,1]1))) [2, 1; 3, 1; 17791, 1] [2, 2; 3, 2; 17791, 1] Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I found the primality test, there seems to be no composite numbers that pass the test  sweety439  sweety439  7  20200211 19:49 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
Double check LL test faster than first run test  lidocorc  Software  3  20081203 15:12 
Will the torture test, test ALL available memory?  swinster  Software  2  20071201 17:54 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 