20230221, 04:31  #12  
Sep 2002
Database er0rr
1000111000110_{2} Posts 
Quote:
Code:
? factor(2^1371) [ 32032215596496435569 1] [5439042183600204290159 1] Last fiddled with by paulunderwood on 20230221 at 04:47 

20230221, 05:12  #13 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·7·13^{2} Posts 
I am learning as I go along. It seems that there are cheaper solutions for any given base. But to get a real cheap solution (vs. a marginally cheaper one) it takes more trials than it is worth it. For M137 I assume it takes a very long time.
Here are some pointers I suspect: * if anything comes out of this it will be to sieve some special format candidates by quickly figuring out they are composites rather than PRP * Mersenne numbers are just not suitable for this use * The whole concept is to use cycles in the exponentiation to shortcut the process Take 101 (the number not the exponent). Its exponentiation for base 2 cycles at 50 meaning a saving of one out of 100. It does not fare much better for any small bases. However, there are more complex cycles that do not necessarily yield a mod 1, but occur much more frequently. I will need some time to put together a better description. 
20230221, 07:01  #14 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·7·13^{2} Posts 
FWIW:
Code:
\\EWB610ARNFERMATS by Rashid Naimi (a1call) \\This test is not expected to be usefull for Mersenne numbers \\This PARIGP code is WorkinProgress \\It's meant to be a PRP test that returns a non 0 result (the cycle) if the input is found to be a PRP \\It's based on finding cycles of equal Modular reminders (not necerrily mod 1) for 2 diffent bases \\If the cycle divides N1 then the the test is positive, else negative \\ Asis it can return both falsepositive and falsenegative (**** No cycles found (increase ranges) ****) results \\ large numbers will require extending the ranges EWD610ARNFERMATS(N) ={ my( m1, m2 ); forstep(b1=2,19^2,2, forstep(b2=3,19^2,2, if(b2==b1,next(1);); if(gcd(b2,b1)>1,next(1);); for(exp1=2,19^19, for(exp2=exp1,exp1, m1=Mod(b1,N)^exp1; m2=Mod(b2,N)^exp2; if(m1==m2, print("\nMod(",b1,",",N,")^",exp1," = ",m1); print("Mod(",b2,",",N,")^",exp2," = ",m1); if(Mod(N1,exp1)==0, return(exp1); , return(0); ); ); ); ); ); ); print("**** No cycles found (increase ranges) ****"); } EWD610ARNFERMATS(19) ## EWD610ARNFERMATS(101) ## EWD610ARNFERMATS(95) ## EWD610ARNFERMATS(2^111) ## EWD610ARNFERMATS(2^131) ## EWD610ARNFERMATS(2^(2^4)+1) ## EWD610ARNFERMATS(2^(2^5)+1) ## \\ \\ Code:
(01:53) gp > (01:53) gp > EWD610ARNFERMATS(19) Mod(2,19)^3 = Mod(8, 19) Mod(3,19)^3 = Mod(8, 19) %185 = 3 (01:53) gp > ## *** last result computed in 0 ms. (01:53) gp > EWD610ARNFERMATS(101) Mod(2,101)^25 = Mod(10, 101) Mod(3,101)^25 = Mod(10, 101) %186 = 25 (01:53) gp > ## *** last result computed in 0 ms. (01:53) gp > EWD610ARNFERMATS(95) Mod(2,95)^6 = Mod(64, 95) Mod(3,95)^6 = Mod(64, 95) %187 = 0 (01:53) gp > ## *** last result computed in 0 ms. (01:53) gp > EWD610ARNFERMATS(2^111) Mod(2,2047)^88 = Mod(1, 2047) Mod(3,2047)^88 = Mod(1, 2047) %188 = 0 (01:53) gp > ## *** last result computed in 0 ms. (01:53) gp > EWD610ARNFERMATS(2^131) Mod(2,8191)^910 = Mod(1, 8191) Mod(3,8191)^910 = Mod(1, 8191) %189 = 910 (01:53) gp > ## *** last result computed in 0 ms. (01:53) gp > EWD610ARNFERMATS(2^(2^4)+1) Mod(2,65537)^65536 = Mod(1, 65537) Mod(3,65537)^65536 = Mod(1, 65537) %190 = 65536 (01:53) gp > ## *** last result computed in 78 ms. (01:53) gp > EWD610ARNFERMATS(2^(2^5)+1) Mod(2,4294967297)^11167360 = Mod(1, 4294967297) Mod(3,4294967297)^11167360 = Mod(1, 4294967297) %191 = 0 (01:53) gp > ## *** last result computed in 18,187 ms. (01:53) gp > \\ (01:53) gp > \\ (01:53) gp > 
20230312, 01:52  #15 
"Rashid Naimi"
Oct 2015
Remote to Here/There
93E_{16} Posts 
Code:
system("cls"); \\EWJ350ABy Rashid Naimi  a1call  March 11, 2023 \\This PARI GP code generates (Fermat'sTest) PRP's to any given base (Virtually instantly) \\Unfortunately The majority are pseudoprimes (not Primes) :) b = 19 \\Choose any base here forstep(i=2,19^4,2,{ \\Controls the upper bound j=i/2; p=b^ib^j+1; if(Mod(p1,i+j)==0, print("\nPRP",length(Str(p))," = (",b,"^",i,"",b,"^",j,")+1"); \\Uncomment next line to verify Fermat's base PRP (Verification will substantially slow down the run) \\print("Mod(",b,",p)^(prp1) = ",(Mod(b,p)^(p1))); ); }) \\ 
20230317, 01:26  #16 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·7·13^{2} Posts 
Extending the concept of CyclicProbablePrimes to CyclicStrongProbablePrimes:
\\EWJ520ABy Rashid Naimi  a1call  March 16, 2023 \\This PARI GP code generates StrongProbablePrimes (SPRP) to any given base greater than 1 \\Unfortunately The majority are pseudoprimes (not Primes) :) Code:
\\EWJ520ABy Rashid Naimi  a1call  March 16, 2023 \\This PARI GP code generates StrongProbablePrimes (SPRP) to any given base greater than 1 \\Unfortunately The majority are pseudoprimes (not Primes) :) b = 19 \\Choose any base greater than 1 here lowerBound = 2 \\ Choose a positive even integer here upperBound = 19^2 \\Choose an integer greater than or equal to the lowerBound forstep(i= lowerBound, upperBound, 2,{ j=i/2; p=b^ib^j+1; \\ Constructed Candidate if(Mod(p1,(i+j))==0, \\Cyclic Fermat's PRP test v=valuation(p1,2); c = (p1)/(2^v); if(Mod(c,(i+j))==0, \\Cyclic StrongPRP test print("\nSPRP",length(Str(p))," = (",b,"^",i,"",b,"^",j,")+1"); ); ); p=b^i+b^j+1; \\ Constructed Candidate if(Mod(p1,(i+j))==0, \\Cyclic Fermat's PRP test v=valuation(p1,2); c = (p1)/(2^v); if(Mod(c,(i+j))==0, \\Cyclic StrongPRP test print("\nSPRP",length(Str(p))," = (",b,"^",i,"+",b,"^",j,")+1"); ); ); }) \\ Code:
SPRP3 = (19^219^1)+1 SPRP8 = (19^619^3)+1 SPRP24 = (19^1819^9)+1 SPRP49 = (19^3819^19)+1 SPRP70 = (19^5419^27)+1 SPRP146 = (19^11419^57)+1 SPRP208 = (19^16219^81)+1 SPRP438 = (19^34219^171)+1 Code:
SPRP1 = (3^23^1)+1 SPRP2 = (3^2+3^1)+1 SPRP3 = (3^63^3)+1 SPRP3 = (3^6+3^3)+1 SPRP9 = (3^183^9)+1 SPRP9 = (3^18+3^9)+1 SPRP21 = (3^42+3^21)+1 SPRP26 = (3^543^27)+1 SPRP26 = (3^54+3^27)+1 SPRP38 = (3^783^39)+1 SPRP61 = (3^126+3^63)+1 SPRP78 = (3^1623^81)+1 SPRP78 = (3^162+3^81)+1 SPRP112 = (3^2343^117)+1 SPRP141 = (3^294+3^147)+1 SPRP164 = (3^342+3^171)+1 ... SPRP30841 = (3^64638+3^32319)+1 SPRP32885 = (3^68922+3^34461)+1 SPRP33469 = (3^701463^35073)+1 ... SPRP46712 = (3^97902+3^48951)+1 SPRP48114 = (3^100842+3^50421)+1 SPRP49116 = (3^102942+3^51471)+1 ... SPRP126668 = (3^265482+3^132741)+1 SPRP126788 = (3^265734+3^132867)+1 ... SPRP251128 = (3^526338+3^263169)+1 ... SPRP500889 = (3^1049814+3^524907)+1 ... SPRP1000412 = (3^2096766+3^1048383)+1 SPRP1004998 = (3^2106378+3^1053189)+1 ... SPRP2371447 = (3^4970322+3^2485161)+1 ... Last fiddled with by a1call on 20230317 at 01:35 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pépin tests of Fermat numbers beyond F24  ewmayer  Computer Science & Computational Number Theory  83  20220701 22:35 
Families of cyclic cubic fields... and more  carpetpool  carpetpool  2  20200412 01:04 
Cyclic Group Problem  davar55  Homework Help  67  20170523 13:16 
What are the Primality Tests ( not factoring! ) for Fermat Numbers?  Erasmus  Math  46  20140808 20:05 
Two Primality tests for Fermat numbers  T.Rex  Math  2  20040911 07:26 