faster than LL?

[paulunderwood]

? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^N);gettime()
6132

? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^q);gettime()
6125

The result of Mod(3,n)^q is a power of 2 less than 2^p-1 -- but only for Prime Mp?

[science_man_88]

Originally Posted by paulunderwood

? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^N);gettime()
6132

? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^q);gettime()
6125

The result of Mod(3,n)^q is a power of 2 less than 2^p-1 -- but only for Prime Mp?

it will depend on which version or coding of the LL test you use to test it against on my system for exponent 110503 your code runs for 1min, 29,975 ms. the lucas example takes about 2min, 17,097 ms. and the code from http://mersenneforum.org/showpost.ph...86&postcount=2 runs in under 29 seconds.

[axn]

gp > p=44497;
gp > N=2^p-1;
gp > q=(N-1)/p;
gp > r=N+1;
gp > #
   timer = 1 (on)
gp > lift(Mod(3,N)^N);
time = 18,095 ms.
gp > lift(Mod(3,N)^q);
time = 18,032 ms.
gp > lift(Mod(3,N)^r);
time = 17,986 ms.
gp >

lift(Mod(3,N)^(N+1)) is, of course, 9, for primes.

[paulunderwood]

Originally Posted by science_man_88

it will depend on which version or coding of the LL test you use to test it against on my system for exponent 110503 your code runs for 1min, 29,975 ms. the lucas example takes about 2min, 17,097 ms. and the code from http://mersenneforum.org/showpost.ph...86&postcount=2 runs in under 29 seconds.

29 seconds is because of the special mod 2^p==1 has been used. Try applying that to my fractional power Fermat PRP test!

The LL tests uses p-2 squarings and subtractions by 2 all mod 2^p-1. The test I give requires fewer squarings and some multiplications by 3 all mod 2^p-1.

[science_man_88]

Originally Posted by paulunderwood

29 seconds is because of the special mod 2^p==1 has been used. Try applying that to my fractional power Fermat PRP test!

The LL tests uses p-2 squarings and subtractions by 2 all mod 2^p-1. The test I give requires fewer squarings and some multiplications by 3 all mod 2^p-1.

other than the fact I know x%(2^p-1) = x/(2^p)+x%(2^p) until there's at most p bits I'm not sure how to best do that here. edit: all I can think of is a loop like it's done for the LL code however if N is prime eulerphi(N) =N-1 so the exponent can be reduced to 1 I think as it's usually done mod eulerph if I remember correctly.

[paulunderwood]

Originally Posted by axn

gp > p=44497;
gp > N=2^p-1;
gp > q=(N-1)/p;
gp > r=N+1;
gp > #
   timer = 1 (on)
gp > lift(Mod(3,N)^N);
time = 18,095 ms.
gp > lift(Mod(3,N)^q);
time = 18,032 ms.
gp > lift(Mod(3,N)^r);
time = 17,986 ms.
gp >

lift(Mod(3,N)^(N+1)) is, of course, 9, for primes.

Yes. All squarings. Pari maybe is not the best program to use to see the true differences.

[axn]

Originally Posted by paulunderwood

Yes. All squarings. Pari maybe is not the best program to use to see the true differences.

Yes. But even in a properly optimized program (like P95 or PFGW), all squaring will be slightly faster than modular exponentiation with exponents containing lots of 1 bits (I think). Also, all the tests are still probable-primality only (unlike LL test). And the saving of log(p) bits (about 25 bits at current GIMPS LL tests) is just rounding error in the grand scheme of things. One extra OS interrupt, and you won't be able to tell the difference.

EDIT:- Not to mention the cost of computing q=(N-1)/p.

[paulunderwood]

Originally Posted by axn

Yes. But even in a properly optimized program (like P95 or PFGW), all squaring will be slightly faster than modular exponentiation with exponents containing lots of 1 bits (I think). Also, all the tests are still probable-primality only (unlike LL test). And the saving of log(p) bits (about 25 bits at current GIMPS LL tests) is just rounding error in the grand scheme of things. One extra OS interrupt, and you won't be able to tell the difference.

EDIT:- Not to mention the cost of computing q=(N-1)/p.

I see. Thanks for your analysis.

I coded it up by hacking Robert's script:

myfermat(p)=mp=2^p-1;q=(mp-1)/p;res=3;len=length(binary(q));forstep(i=len-2,0,-1,res=sqr(res);hi=shift(res,-p);lo=bitand(res,mp);res=lo+hi;if(bittest(q,i),res*=3);while(res>=mp,res-=mp);while(res<0,res+=mp))

? gettime();myfermat(110503);gettime()
time = 18,232 ms.
18232
? gettime();mylucas(110503);gettime()
time = 18,096 ms.
18096

[science_man_88]

Originally Posted by paulunderwood

I see. Thanks for your analysis.

I coded it up by hacking Robert's script:

myfermat(p)=mp=2^p-1;q=(mp-1)/p;res=3;len=length(binary(q));forstep(i=len-2,0,-1,res=sqr(res);hi=shift(res,-p);lo=bitand(res,mp);res=lo+hi;if(bittest(q,i),res*=3);while(res>=mp,res-=mp);while(res<0,res+=mp))

? gettime();myfermat(110503);gettime()
time = 18,232 ms.
18232
? gettime();mylucas(110503);gettime()
time = 18,096 ms.
18096

see on my machine your code starts out at 33 seconds but I have been able to shave that to roughly <30 using some of the things I also posted in that LL thread I made ( at least on my system).

myfermat(p)=mp=2^p-1;q=mp\p;res=3;len=length(binary(q));forstep(i=len-2,0,-1,res=sqr(res);hi=res>>p;lo=bitand(res,mp);res=lo+hi;if(bittest(q,i),res*=3);while(res>=mp,res-=mp);while(res<0,res+=mp))

[science_man_88]

okay I may have been testing with a virus scanner going that may explain things somewhat but I still get mine as faster with just chrome going. okay maybe I just think this is faster for some reason. never midn I quit I am never really helpful too many ways to play with codes.

[paulunderwood]

Originally Posted by science_man_88

okay I may have been testing with a virus scanner going that may explain things somewhat but I still get mine as faster with just chrome going. okay maybe I just think this is faster for some reason. never midn I quit I am never really helpful too many ways to play with codes.

Your's is marginally faster, modulo system activity,