\\ --------------- GP code --------------------------------------- \\ \\ Time-stamp: \\ \\ Description: Routines for factoring a number, using Lentra algorithm \\ \\ \\ Original Authors: Fernando Rodriguez-Villegas \\ villegas@math.utexas.edu \\ University of Texas at Austin \\ \\ Ariel Martin Pacetti \\ apacetti@math.utexas.edu \\ University of Texas at Austin \\ \\ Created: May 24 2001 \\ \\---------------------------------------------------------------------- \\ This is Lenstra algorithm for computing some non-trivial factor of \\ an integer n. The entries are the number n and the number of times to \\ run the test. There is also an extra entry (optional), which decides \\ the size of the prime factors of (p-1), where p is some prime factor \\ of n. lenstra(n,times,k)= {local(aux,ans,cont,P,E,a4); if(isprime(n),return("It's prime")); if(times==0,return("Put more times")); if((aux=gcd(n,6))!=1,return([aux,n/aux])); cont=1; if(k,,k=multilcm(vector(precprime(truncate(log(n)))))); if(k==1,k=multilcm(vector(precprime(n)))); while(aux=n^(1/cont)>=2,if(round(aux)^cont==n, return ( vector( cont,x,aux))); cont++); for(k=1,times, P=[random(n),random(n)]; a4=random(n); E=[0,0,0,a4,P[2]^2-P[1]^3-a4*P[1]]; if((aux=gcd(4*E[4]^3+27*E[5]^2,n))!=1,if(aux!=n,return([aux,n/aux]), return(lenstra(n,times-1)))); ellpowmod(E,P,k,n)); return("I failed, try more times")} \\====================================================================== \\ This is a routine for computing the addition of 2 points in an \\ elliptic curve, but looking at the equation reduced modulo some \\ number n. If the addition cannot be done, outputs some non-trivial \\ factors of n. elladdmod(e,z1,z2,n)= {local(aux,ans,lambda); if(z1==[0],return(z2),if(z2==[0],return(z1))); if(z1!=z2, aux=bezout(z2[1]-z1[1],n); if(aux[3]!=1,return([aux[3],n/aux[3]]),lambda=(z2[2]-z1[2]) * aux[1]); [aux=((lambda^2-z1[1]-z2[1])%n),(-lambda*aux-(z1[2]-lambda*z1[1]))%n], aux=4*z1[1]^3+4*E[4]*z1[1]+4*E[5]; aux=bezout(aux,n); if(aux[3]!=1,return([aux[3],n/aux[3]]),lambda=aux[1]); [ans=((z1[1]^4-2*E[4]*z1[1]^2-8*E[5]*z1[1]+E[4]^2)*lambda)%n, -((ans-z1[1])*bezout(2*z1[2],n)[1]*(3*z1[1]^2+E[4])+z1[2])%n])} \\====================================================================== \\ This is the classical algorithm for adding finding kP for a point P. ellpowmod(E,P,k,n)= {local(aux,ans,l,temp); aux=binary(k); ans=[0];l=length(aux);temp=P; for(k=1,l,if(aux[l-k+1]==1,ans=elladdmod(E,ans,temp,n)); temp=elladdmod(E,temp,temp,n)); ans} \\====================================================================== \\ This is an auxiliary routine for given a vector with integers to \\ compute the g.c.d. of all of them. multigcd(v)= {local(ans); ans=gcd(v[1],v[2]); for(k=1,length(v)-2,ans=gcd(ans,v[k+2])); ans} \\====================================================================== \\ This is an auxuliary routine for given a vector with integers to \\ compute the l.c.m. of all of them. multilcm(v)= {local(ans); ans=lcm(v[1],v[2]); for(k=1,length(v)-2,ans=lcm(ans,v[k+2])); ans} \\ Beispiel: lenstra(22222222222222222222222222223,10)