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

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

Expand Messages
  • 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 1 of 9 , May 3, 2005
      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 2 of 9 , May 3, 2005
        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 3 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]
        • 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 4 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.
          • 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 5 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]
            • 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 6 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.