Cheap Cyclic Fermat's Tests - Page 2

paulunderwood · 2023-02-21, 04:31

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?

a1call · 2023-02-21, 05:12

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.

a1call · 2023-02-21, 07:01

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 >

a1call · 2023-03-12, 01:52

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)));
    );
})
\\

a1call · 2023-03-17, 01:26

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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Pépin tests of Fermat numbers beyond F24	ewmayer	Computer Science & Computational Number Theory	89	2023-06-02 22:21
Families of cyclic cubic fields... and more	carpetpool	carpetpool	2	2020-04-12 01:04
Cyclic Group Problem	davar55	Homework Help	67	2017-05-23 13:16
What are the Primality Tests ( not factoring! ) for Fermat Numbers?	Erasmus	Math	46	2014-08-08 20:05
Two Primality tests for Fermat numbers	T.Rex	Math	2	2004-09-11 07:26

2023-02-21, 05:12	#13
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 41·59 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.