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

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

Expand Messages
  • 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 1 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 2 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 3 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 4 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.