On Tuesday 03 May 2005 22:46, you wrote:

> In Pari 2.2.8 I get the following error:

> (11:41) gp > nfs(111111)

> *** expected character: '=' instead of: primepi(i)

> ^

> (11:41) gp >

>

> Do you have a formatted version??

Here is my working version (I use a shell script to obfuscate it, but

obviously I don't try to patch it in 100% obfuscated form), already including

the fix for the coprime (a,b) pairs.

I'm not sure if I'll try to improve this, or if I should write a `serious'

implementation in C++.

Décio

nfs(n)=

{

l=log(n);

d=(3*l/log(l))^(1/3)\1;

k=3*l\log(2);

m=n^(1/d)\1;

t=d;

s=n;

H=vector(d+1,i,1);

(p(i)=prime(i));

for(i=1,d,

s-=H[i]*m^t;

H[i+1]=s\m^t--

);

(f(x)=eval(Pol(H)));

(F(x,y)=y^d*f(x/y));

(G(x,y)=x-m*y;);

(h(x)=eval(deriv(Pol(H))));

t=B=precprime(

2*exp(

(l*log(l)^2)^(1/3)

)

);

(z(i)=primepi(i));

P=z(B);

R=vector(P,i,

lift(polrootsmod(f(x),p(i)))

);

q=vector(k,i,

while(

!r=polrootsmod(f(x),t=nextprime(t+2)),

);

[t,lift(r[1])]

);

K=exp(log(n)/200);

(L(B)=log(B)/log(K)\/1);

w=vectorsmall(P,i,

L(p(i))

);

b=r=0;

A=vector(P);

for(i=2,P,

A[i]=A[i-1]+#R[i]

);

o=A[P]+#R[P];

s=o+P+k+1;

M=matrix(s,s);

N=vector(s);

while(1,

b++;

e=vectorsmall(8*B+1,a,

L(abs(F(a-4*B,b)*G(a-4*B,b))+1)

);

for(i=1,P,

t=p(i);

for(j=1,#R[i],

forstep(k=-4*B+1+b*R[i][j]%t,4*B,t,

e[k+4*B]-=w[i]

)

);

for(j=1,if(t<sqrt(B),log(B)/log(t),1),

forstep(k=-4*B+1+(-m*b)%t^j,4*B,t^j,

e[k+4*B]-=w[i]

)

)

);

for(t=1,8*B+1,

if(e[t]<L(B^2)&&gcd(a=t-4*B,b)==1,

C=factorint(abs(F(a,b)));

D=if(G(a,b),factorint(abs(G(a,b))),[]);

if(C&&D&&C[#C~,1]<=B&&D[#D~,1]<=B,

if(r++==s+1,break(2));

N[r]=[a,b];

for(i=1,#C~,

c=z(C[i,1]);

for(j=1,#R[c],

if((a-b*R[c]

[j])%C[i,1]==0,

M[r,A[c]+j]=C[i,2]

)

)

);

for(i=1,#D~,

M[r,o+z(D[i,1])]=D[i,2]

);

for(i=1,k,

M[r,o+P+i]=kronecker(a-b*q[i]

[2],q[i][1])<0;

M[r,s]=G(a,b)<0

);

)

)

)

);

S=lift(matker(Mod(M~,2)));

for(i=1,#S,

V=M~*S[,i];

v=lift(

prod(j=1,P,

Mod(p(j),n)^(V[o+j]/2)

)

);

if(

#(U=nffactor(

nfinit(f(y))

,

x^2-h(y)^2*prod(j=1,#S~,

Mod((N[j][1]-N[j][2]*y)^S[j,i],f(y))

)

))~>1

,

(u(y,x=0)=eval(

lift(U[1,1])

));

g=gcd(u(m)-h(m)*v,n);

if(g>1&&g<n,

break

)

)

);

return(g);

}

[Non-text portions of this message have been removed]