mersenneforum.org PPP Extended test -- based on François Olivier Raoul Perrin's Sequence
 Register FAQ Search Today's Posts Mark Forums Read

 2023-09-16, 04:16 #23 paulunderwood     Sep 2002 Database er0rr 3·1,601 Posts Cubic calculation Recall the cubic route is given by the test: Code: {kill(x);TPPPC(n)=my(a=0,f,X=x); while(X==x,a++;f=x^3-x-a; while(gcd(a,n)!=1||kronecker(poldisc(f),n)!=1,a++;f=x^3-x-a); X=Mod(Mod(x,n),f)^n); gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0;} For exponentiation of x consider the intermediate value s*x^2+t*x+u. Squaring: Code: Mod(s*x^2+t*x+u,x^3-x-a)^2 Mod((s^2 + 2*u*s + t^2)*x^2 + (a*s^2 + 2*t*s + 2*u*t)*x + (2*a*t*s + u^2), x^3 - x - a) Which can be calculated as ((s + t)^2-2*s*t + 2*u*s)*x^2 + (a*s^2 + 2*t*s + 2*u*t)*x + (2*a*t*s + u^2). Totting up the different multiplications (and discounting multiplication by small a) gives 6 selfridges. There may be other ways to arrange this calculation or just leave it as PARI/GP has shown: 3 squares plus 3 mults (which all have to be modularly reduced over n). Multiplying by the base, x, when the bit is one: Code: Mod(s*x^2+t*x+u,x^3-x-a)*x Mod(t*x^2 + (s + u)*x + a*s, x^3 - x - a) Simple enough. Here it is: Code: {Cubo(n,a)=my(s=Mod(0,n),t=Mod(1,n),u=Mod(0,n),s2,t2,u2,st,tu,us,k,LEN=#digits(n,2)-2,tmp); forstep(k=LEN,0,-1,s2=sqr(s);t2=sqr(t);u2=sqr(u);st=s*t;tu=t*u;us=u*s;s=s2+2*us+t2;t=a*s2+2*st+2*tu;u=2*a*st+u2; if(bittest(n,k),tmp=s;s=t;t=tmp+u;u=a*tmp)); Mod(s*x^2+t*x+u,x^3-x-a)} {kill(x);TPPPC(n)=my(a=0,f,X=x); while(X==x,a++;f=x^3-x-a; while(gcd(a,n)!=1||kronecker(poldisc(f),n)!=1,a++;f=x^3-x-a); X=Cubo(n,a)); gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0;} Timings: Code: ? n=2^44497-1;Mod(Mod(x,n),x^3-x-1)^n; ? ## *** last result: cpu time 3min, 2,654 ms, real time 3min, 3,078 ms. ? n=2^44497-1;Cubo(n,1); ? ## *** last result: cpu time 1min, 59,033 ms, real time 1min, 59,127 ms. Time for some verification of the cubic "route"! Something like this will do: Code: {for(n=11,1000000,if(!ispseudoprime(n), for(a=1,n, if(gcd(a,n)==1&&kronecker(poldisc(x^3-x-a),n)==1&& (X=Cubo(n,a))&&X!=x&&gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0, print([n,a])))))} Last fiddled with by paulunderwood on 2023-09-16 at 06:52
 2023-09-16, 15:48 #24 paulunderwood     Sep 2002 Database er0rr 3·1,601 Posts Note that poldisc(x^3-1-a) is 4-27*a^2. Also working over x^3-x-a is the same as x^3-x+a. Code: {for(n=11,1000000,if(!ispseudoprime(n), for(a=1,(n-1)/2,if(gcd(a,n)==1&&kronecker(4-27*a^2,n)==1&& (X=Cubo(n,a))&&X!=x&&gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0, print([n,a])))))} I'll convert this all to The C Language over the coming week. Last fiddled with by paulunderwood on 2023-09-16 at 16:08
2023-09-25, 21:06   #25
paulunderwood

Sep 2002
Database er0rr

3×1,601 Posts

Quote:
 Originally Posted by paulunderwood I'll convert this all to The C Language over the coming week.
The C program is attached which verifies the cubic version.
Attached Files
 perrin-cubic.cpp (3.0 KB, 0 views)

Last fiddled with by paulunderwood on 2023-09-25 at 22:24

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 3 2022-10-13 20:02 sweety439 sweety439 6 2022-04-16 23:55 MathDoggy Miscellaneous Math 8 2019-04-17 03:04 ktpn2011 Software 56 2019-01-17 06:11 carpetpool Miscellaneous Math 5 2018-02-05 05:20

All times are UTC. The time now is 04:02.

Tue Sep 26 04:02:13 UTC 2023 up 13 days, 1:44, 0 users, load averages: 1.68, 1.14, 1.00