View Single Post
Old 2019-01-23, 22:10   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Carried out on an idle Pi Zero W:

Code:
? gettime();p=21701;n=2^p-1;e=n;r=Mod(3,n)^((e))-3;print([length(e),lift(r)]);gettime()
[679, 0]
54996
? gettime();p=21701;n=2^p-1;e=lift(Mod(2,n-1)^(p-1));r=Mod(3,n)^((e))+3;print([length(e),lift(r)]);gettime()
[679, 0]
54455
Not surprising, in the 1st case e=2^p-1, while in the 2nd case e=2^(p-1) and that enables a simple repeated squaring at powmod. Actually we're doing the 2nd variant with error checking, probably it is better to do 3^(2^p) mod mp to allow a fast space efficient cofactor test for mp/d.
R. Gerbicz is offline   Reply With Quote