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

Expand Messages
• Decio, Does Pari-GP really allow you to break up things like a function name into parts? For instance, on line 3 you have f(x)=ev al(Pol( . Does Pari know
Message 1 of 9 , May 2, 2005
• 0 Attachment
Decio,
Does Pari-GP really allow you to break up things like a function name
into parts? For instance, on line 3 you have "f(x)=ev al(Pol(". Does
Pari know to remove the space between "ev" and "al"? I don't know much
about Pari-GP but an interpreted language that ignores white space like
this seems unusual. Then again, Pari seems to be an exceptional language!

-----Original Message-----
[mailto:primenumbers@yahoogroups.com]On Behalf Of Décio Luiz Gazzoni
Filho
Sent: Monday, May 02, 2005 6:27 PM
Subject: [PrimeNumbers] An obfuscated PARI/GP implementation of NFS

I've been working since yesterday on an implementation of the number field
sieve in PARI/GP. This isn't meant to the fast or anything, just a curiosity.
It almost works (the only problem is that the congruent squares x^2 == y^2
mod n generated always have x == y mod n, but I'm working on it.) However,
99% of the work is done.

Sorry about the last line being too short. Once the program is fully working
I'll just rename some variables to obtain perfect alignment. Also, if someone
has a more creative suggestion for the background drawing, I'd love to know.

Needless to say, this is best viewed with a monospaced font on an 80-column
or larger terminal. If Yahoo! breaks up the message, just reassemble it in

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=vect
or(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)=ev al(Pol( H)));(F(x,y)=y^d*f(x /y));(G(x,y)=x-m*y;);(h
(x)=eval(d e riv(Pol(H)))) ;t=B=pr ecprime(exp((l*log( l)^2)^(1/3)));(z(i)=prim
epi(i));P= z( B);R=vector( P,i,lif t(polrootsmod(f(x) ,p(i))));q=vector(k,i,whi
le(!r=polr oot smod(f(x),t =nextpr ime(t+2)),);[t,lif t(r[1])]);K=exp(log(n)/20
0);(L(B)=l og(B )/log(K)\/ 1);w=ve ctorsmall(P,i,L(p( i)));b=r=0;A=vector(P);fo
r(i=2,P,A[ i]=A[ i-1]+#R[i ]);o=A[ P]+#R[P];s=o+P+k+1; M=matrix(s+8,s);N=vector
(s+8);whil e(1,b+ +;e=vect orsmall (B+1,a,L(abs(F(a,b)* G(a,b))));for(i=1,P,t=p
(i);for(j= 1,#R[i] ,forste p(k=b*R [i][j]%t,B,t, e[k+1]-=w[i]))
;for(j=1,i f(t<sqrt (B),lo g(B)/lo g(t),1),forstep(k=-m*b%t^j,B,t ^j,e[k+1]-=w[
i])));for( t=1,B+1,i f(e[t ]<L(B^2 ),a=t-1;C=factorint(F(a,b));D=f actorint(abs
(G(a,b))); if(C[#C~,1 ]<=B &&D[#D~ ,1]<=B,if(r++==s+9,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]=kronec
ker(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(pr od(j=1,P,Mod(p(j),n)^(V[o+j]/2 )));if(#(U=nf
factor(nfi nit(f(y)),x^2-h (y)^2*p rod(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]

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/

• ... Yes, PARI/GP effectively has no concept of whitespace (except in strings). For instance, a quote from the manual: `As explained above, the general way to
Message 2 of 9 , May 3, 2005
• 0 Attachment
On Tuesday 03 May 2005 00:24, you wrote:
> Decio,
> Does Pari-GP really allow you to break up things like a function name
> into parts? For instance, on line 3 you have "f(x)=ev al(Pol(". Does
> Pari know to remove the space between "ev" and "al"? I don't know much
> about Pari-GP but an interpreted language that ignores white space like
> this seems unusual. Then again, Pari seems to be an exceptional language!

Yes, PARI/GP effectively has no concept of whitespace (except in strings). For
instance, a quote from the manual: `As explained above, the general way to
input a string is to enclose characters between quotes ". This is the only
input construct where whitespace characters are significant: the string will
contain the exact number of spaces you typed
in.' (http://pari.math.u-bordeaux.fr/pub/pari/manuals/unstable/users.pdf,
section 2.67).

That's why I like writing obfuscated programs. You really learn a lot about
the language by writing them.

Décio

[Non-text portions of this message have been removed]
• 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
Message 3 of 9 , May 3, 2005
• 0 Attachment
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??

Andrew

--- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
<decio@d...> wrote:
> I've been working since yesterday on an implementation of the number
field
> sieve in PARI/GP. This isn't meant to the fast or anything, just a
curiosity.
> It almost works (the only problem is that the congruent squares x^2
== y^2
> mod n generated always have x == y mod n, but I'm working on it.)
However,
> 99% of the work is done.
>
> Sorry about the last line being too short. Once the program is fully
working
> I'll just rename some variables to obtain perfect alignment. Also,
if someone
> has a more creative suggestion for the background drawing, I'd love
to know.
>
> Needless to say, this is best viewed with a monospaced font on an
80-column
> or larger terminal. If Yahoo! breaks up the message, just reassemble
it in
>
> 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=vect
> or(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)=ev al(Pol( H)));(F(x,y)=y^d*f(x
/y));(G(x,y)=x-m*y;);(h
> (x)=eval(d e riv(Pol(H)))) ;t=B=pr ecprime(exp((l*log(
l)^2)^(1/3)));(z(i)=prim
> epi(i));P= z( B);R=vector( P,i,lif t(polrootsmod(f(x)
,p(i))));q=vector(k,i,whi
> le(!r=polr oot smod(f(x),t =nextpr ime(t+2)),);[t,lif
t(r[1])]);K=exp(log(n)/20
> 0);(L(B)=l og(B )/log(K)\/ 1);w=ve ctorsmall(P,i,L(p(
i)));b=r=0;A=vector(P);fo
> r(i=2,P,A[ i]=A[ i-1]+#R[i ]);o=A[ P]+#R[P];s=o+P+k+1;
M=matrix(s+8,s);N=vector
> (s+8);whil e(1,b+ +;e=vect orsmall (B+1,a,L(abs(F(a,b)*
G(a,b))));for(i=1,P,t=p
> (i);for(j= 1,#R[i] ,forste p(k=b*R [i][j]%t,B,t,
e[k+1]-=w[i]))
> ;for(j=1,i f(t<sqrt (B),lo g(B)/lo g(t),1),forstep(k=-m*b%t^j,B,t
^j,e[k+1]-=w[
> i])));for( t=1,B+1,i f(e[t ]<L(B^2 ),a=t-1;C=factorint(F(a,b));D=f
actorint(abs
> (G(a,b))); if(C[#C~,1 ]<=B &&D[#D~ ,1]<=B,if(r++==s+9,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]=kronec
> ker(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(pr od(j=1,P,Mod(p(j),n)^(V[o+j]/2
)));if(#(U=nf
> factor(nfi nit(f(y)),x^2-h (y)^2*p rod(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]
• ... 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 4 of 9 , May 4, 2005
• 0 Attachment
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 5 of 9 , May 4, 2005
• 0 Attachment
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 6 of 9 , May 4, 2005
• 0 Attachment
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 7 of 9 , May 4, 2005
• 0 Attachment
> 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.