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

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

Expand Messages
  • 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 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!

      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 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]
      • 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 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
          > 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 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]
          • 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 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.
            • 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 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]
              • 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 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.