Loading ...
Sorry, an error occurred while loading the content.

An obfuscated PARI/GP implementation of NFS

Expand Messages
  • Décio Luiz Gazzoni Filho
    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
    Message 1 of 9 , May 2, 2005
    • 0 Attachment
      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
      Notepad or your favorite editor.

      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]
    • Décio Luiz Gazzoni Filho
      ... I found the problem -- I was allowing non-coprime pairs (a,b) which of course generated trivial dependencies. I ve been able to factor quite a few numbers
      Message 2 of 9 , May 2, 2005
      • 0 Attachment
        On Monday 02 May 2005 20:26, you 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.

        I found the problem -- I was allowing non-coprime pairs (a,b) which of course
        generated trivial dependencies. I've been able to factor quite a few numbers
        now, but the script is really really slow; thus I have no choice but to
        implement a large prime variant. Once I get around to that I'll post the
        final result to the list.

        Décio


        [Non-text portions of this message have been removed]
      • Hadley, Thomas H (Tom), ALABS
        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 3 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!

          Tom Hadley

          -----Original Message-----
          From: primenumbers@yahoogroups.com
          [mailto:primenumbers@yahoogroups.com]On Behalf Of Décio Luiz Gazzoni
          Filho
          Sent: Monday, May 02, 2005 6:27 PM
          To: primenumbers@yahoogroups.com
          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
          Notepad or your favorite editor.

          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/


          Yahoo! Groups Links
        • Décio Luiz Gazzoni Filho
          ... 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 4 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]
          • andrew_j_walker
            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 5 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
              > Notepad or your favorite editor.
              >
              > 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]
            • Décio Luiz Gazzoni Filho
              ... 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 6 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]
              • Paul Jobling
                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 7 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.
                • Décio Luiz Gazzoni Filho
                  ... 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 8 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]
                  • Paul Jobling
                    ... 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 9 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.