mersenneforum.org Cheap Cyclic Fermat's Tests
 Register FAQ Search Today's Posts Mark Forums Read

2023-02-21, 04:31   #12
paulunderwood

Sep 2002
Database er0rr

2·5·467 Posts

Quote:
 Originally Posted by a1call Sometimes failure is a good thing. When a candidate fails a PRP test for any given base then it is definitely a composite and not probably a composite. It is not easy (for me) to get the right base but there might just be a fast algorithm for getting these cheap bases. After all they do exist. Code: q=29 p=2^q-1 Mod(7,p)^39672 = Mod(1, 536870911) && 39672 !| M29-1 Which deduces that M29 is not PRP to base 7 obtained by exponentiating to power of 39672 rather than 536870910.
Code:

? factor(2^137-1)

[  32032215596496435569 1]

[5439042183600204290159 1]
How long would it before, using your program, would it take to find a base and an exponent M137?

Last fiddled with by paulunderwood on 2023-02-21 at 04:47

 2023-02-21, 05:12 #13 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 238010 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.
 2023-02-21, 07:01 #14 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 238010 Posts FWIW: Code: \\EWB-610-A-RN-FERMATS by Rashid Naimi (a1call) \\This test is not expected to be usefull for Mersenne numbers \\This PARI-GP code is Work-in-Progress \\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 N-1 then the the test is positive, else negative \\ As-is it can return both false-positive and false-negative (**** 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(N-1,exp1)==0, return(exp1); , return(0); ); ); ); ); ); ); print("**** No cycles found (increase ranges) ****"); } EWD610ARNFERMATS(19) ## EWD610ARNFERMATS(101) ## EWD610ARNFERMATS(95) ## EWD610ARNFERMATS(2^11-1) ## EWD610ARNFERMATS(2^13-1) ## 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^11-1) 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^13-1) 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 >
 2023-03-12, 01:52 #15 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22×5×7×17 Posts Code: system("cls"); \\EWJ-350-A-By Rashid Naimi - a1call - March 11, 2023 \\This PARI GP code generates (Fermat's-Test) 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^i-b^j+1; if(Mod(p-1,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)^(prp-1) = ",(Mod(b,p)^(p-1))); ); }) \\
 2023-03-17, 01:26 #16 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·5·7·17 Posts Extending the concept of Cyclic-Probable-Primes to Cyclic-Strong-Probable-Primes: \\EWJ-520-A-By Rashid Naimi - a1call - March 16, 2023 \\This PARI GP code generates Strong-Probable-Primes (SPRP) to any given base greater than 1 \\Unfortunately The majority are pseudoprimes (not Primes) :) Code: \\EWJ-520-A-By Rashid Naimi - a1call - March 16, 2023 \\This PARI GP code generates Strong-Probable-Primes (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^i-b^j+1; \\ Constructed Candidate if(Mod(p-1,(i+j))==0, \\Cyclic Fermat's PRP test v=valuation(p-1,2); c = (p-1)/(2^v); if(Mod(c,(i+j))==0, \\Cyclic Strong-PRP test print("\nSPRP",length(Str(p))," = (",b,"^",i,"-",b,"^",j,")+1"); ); ); p=b^i+b^j+1; \\ Constructed Candidate if(Mod(p-1,(i+j))==0, \\Cyclic Fermat's PRP test v=valuation(p-1,2); c = (p-1)/(2^v); if(Mod(c,(i+j))==0, \\Cyclic Strong-PRP test print("\nSPRP",length(Str(p))," = (",b,"^",i,"+",b,"^",j,")+1"); ); ); }) \\ Constructed SPRP's to base 19: Code: SPRP3 = (19^2-19^1)+1 SPRP8 = (19^6-19^3)+1 SPRP24 = (19^18-19^9)+1 SPRP49 = (19^38-19^19)+1 SPRP70 = (19^54-19^27)+1 SPRP146 = (19^114-19^57)+1 SPRP208 = (19^162-19^81)+1 SPRP438 = (19^342-19^171)+1 Constructed SPRP's to base 3: Code:  SPRP1 = (3^2-3^1)+1 SPRP2 = (3^2+3^1)+1 SPRP3 = (3^6-3^3)+1 SPRP3 = (3^6+3^3)+1 SPRP9 = (3^18-3^9)+1 SPRP9 = (3^18+3^9)+1 SPRP21 = (3^42+3^21)+1 SPRP26 = (3^54-3^27)+1 SPRP26 = (3^54+3^27)+1 SPRP38 = (3^78-3^39)+1 SPRP61 = (3^126+3^63)+1 SPRP78 = (3^162-3^81)+1 SPRP78 = (3^162+3^81)+1 SPRP112 = (3^234-3^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^70146-3^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 ... Thank you for your time. Last fiddled with by a1call on 2023-03-17 at 01:35

 Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Computer Science & Computational Number Theory 89 2023-06-02 22:21 carpetpool carpetpool 2 2020-04-12 01:04 davar55 Homework Help 67 2017-05-23 13:16 Erasmus Math 46 2014-08-08 20:05 T.Rex Math 2 2004-09-11 07:26

All times are UTC. The time now is 13:55.

Sat Jun 10 13:55:12 UTC 2023 up 296 days, 11:23, 0 users, load averages: 0.94, 0.84, 0.80