## Re: [PrimeNumbers] Re: An obfuscated PARI/GP implementation of NFS

Expand Messages
• ... 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
Message 1 of 9 , May 4, 2005
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]
• Décio, Removing the brackets around the statement z(i)=primepi(i); gets rid of the error. However, what is the routine supposed to return? It seems to
Message 2 of 9 , May 4, 2005
Décio,

Removing the brackets around the statement "z(i)=primepi(i);" gets rid of
the error. However, what is the routine supposed to return? It seems to
return 0 in all cases as far as I can tell...

Regards,

Paul.

__________________________________________________
Virus checked by MessageLabs Virus Control Centre.
• ... That s weird, because I ve been running the same file here. I recall GP complained when I _didn t_ have parentheses around function definitions; I believe
Message 3 of 9 , May 4, 2005
On Wednesday 04 May 2005 06:15, Paul Jobling wrote:
> Décio,
>
> Removing the brackets around the statement "z(i)=primepi(i);" gets rid of
> the error. However, what is the routine supposed to return? It seems to
> return 0 in all cases as far as I can tell...

That's weird, because I've been running the same file here. I recall GP
complained when I _didn't_ have parentheses around function definitions; I
believe when parentheses are stripped, GP just assumes that the function
definition goes on, which isn't what I meant. Actually you can simply get rid
of this line, search for all instances of the z() function call and replace
it by primepi() -- it was just a space-saving and obfuscation measure.

By the way, what version are you running? Mine is 2.2.9, and I successfully
ran it on a Windows box running 2.2.10 yesterday. And could you please test
it with 2^32+1, a number for which the routine is working for me? Note that
you'll need to allocatemem() some extra memory because of the linear algebra
solver; 16 MB seems to work fine here, but the default 4 MB does not.

Décio

[Non-text portions of this message have been removed]
• ... Ah, I was running on 2.2.8. I have just downloaded 2.2.10 and tried it with that, and get much more sensible behaviour with the original script. Regards,
Message 4 of 9 , May 4, 2005
> By the way, what version are you running? Mine is 2.2.9

Ah, I was running on 2.2.8. I have just downloaded 2.2.10 and tried it with
that, and get much more sensible behaviour with the original script.

Regards,

Paul.

__________________________________________________
Virus checked by MessageLabs Virus Control Centre.
Your message has been successfully submitted and would be delivered to recipients shortly.