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

Re: Puzzle re factorization

Expand Messages
  • djbroadhurst
    ... No. 4^2 is not equal to 1 mod 11. David
    Message 1 of 8 , Nov 25, 2012
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "ronhallam@..." <ronhallam@...> wrote:

      > The number mod 11 gives 1, and the squareroot mod 11 is 4.

      No. 4^2 is not equal to 1 mod 11.

      David
    • djbroadhurst
      ... ronhallam@... wrote, after many lines of working, ... Thus we are unable to solve the puzzle without obtaining the complete
      Message 2 of 8 , Nov 25, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "ronhallam@..." <ronhallam@...> wrote,

        after many lines of working,
        > (4 7 0 1 10 )mod 11

        in agreement with my previous one-line derivation:
        > print(vecsort(eval(Set(vector(10,q,(q-1/q)%11)))));
        > [0, 1, 4, 7, 10]

        Thus we are unable to solve the "puzzle" without obtaining
        the complete factorization of a 133-digit target.

        A small example illustrates this. With
        n = 1110187 = 1 mod 11, we may write n = p*q
        with q > p > 1 in 7 different ways and obtain
        all 5 of the distinct possible values of q-p modulo 11:

        {n=1110187;fordiv(n,p,q=n/p;if(q>p&&p>1,print1((q-p)%11" ")));}

        4 0 1 4 4 7 10

        where 10 happens to be the residue of (q-p) that
        would be obtained from the first factorization
        produced by Fermat's method, namely n = 1027*1081.

        David
      • djbroadhurst
        ... 2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411 In this case, n = p*q
        Message 3 of 8 , Nov 25, 2012
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          "ronhallam@" <ronhallam@> wrote:

          > Work out the difference mod 6, 7 and 11 on the following number:

          2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411

          In this case, n = p*q with (q-p) divisible by the primes
          2, 3, 5, 7, 11, 4590011 and 186453571036492667910025371580824511.

          Puzzle: Use these data to find another prime that divides (q-p).

          Comment: This puzzle may be solved, systematically, in less
          than 3 CPU-seconds, without appealing to extraneous data.

          David
        • Peter Kosinar
          ... The answer is: 5558358186556723282830357110595686293 And here s the (ugly) code which found it: n= v=[2, 3, 5, 7, 11, 4590011,
          Message 4 of 8 , Nov 27, 2012
          • 0 Attachment
            > --- In primenumbers@yahoogroups.com,
            > "ronhallam@" <ronhallam@> wrote:
            >
            > > Work out the difference mod 6, 7 and 11 on the following number:
            >
            > 2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411
            >
            > In this case, n = p*q with (q-p) divisible by the primes
            > 2, 3, 5, 7, 11, 4590011 and 186453571036492667910025371580824511.
            >
            > Puzzle: Use these data to find another prime that divides (q-p).

            The answer is: 5558358186556723282830357110595686293
            And here's the (ugly) code which found it:

            n=<the long number>
            v=[2, 3, 5, 7, 11, 4590011, 186453571036492667910025371580824511]

            vv=[Mod(0,1)];for(k=1,#v,s=sqrt(Mod(n,v[k])); \
            vv=concat(apply(x->[chinese(x,s),chinese(x,-s)],vv))); \
            m=prod(k=1,#v,v[k]);vv=lift(vv); \
            for(k=1,#vv,r=vv[k];s=(n-r^2)/m;apb=lift(Mod(s,m)/r); \
            atb=(s-apb*r)/m; if(issquare(apb^2-4*atb), \
            d=sqrtint(apb^2-4*atb); print(factor(d))))

            Mat([5558358186556723282830357110595686293, 1])
            Mat([5558358186556723282830357110595686293, 1])

            (the answer is printed twice due to Mod(1,2) being equal to Mod(-1,2); if
            you want to get rid of it, start the first loop with k=2 and initialize vv
            to [Mod(1,2)] instead of [Mod(0,1)]).

            > Comment: This puzzle may be solved, systematically, in less
            > than 3 CPU-seconds, without appealing to extraneous data.

            Puzzle solved? Check.
            Systematically? Check.
            Less than 3 CPU-seconds? Check.
            Extraneous data? Unsure.
            Elegant: Certainly not!

            Peter
          • djbroadhurst
            ... Nice work, Peter. Here is my version, using OpenLenstra: {read( OpenLenstra.gp ); http://tech.groups.yahoo.com/group/primeform/message/2492
            Message 5 of 8 , Nov 27, 2012
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              Peter Kosinar <goober@...> wrote:

              > The answer is: 5558358186556723282830357110595686293

              Nice work, Peter. Here is my version, using OpenLenstra:

              {read("OpenLenstra.gp");
              \\ http://tech.groups.yahoo.com/group/primeform/message/2492
              n=3^240*polcyclo(770,4/3)/(2311*512053081);
              v=[2,3,5,7,11,4590011,186453571036492667910025371580824511];
              d=prod(k=1,#v,v[k]);v=vector(#v,k,sqrt(Mod(n,v[k])));u=[v[1]];
              for(j=2,#v,w=vector(#u,k,chinese(u[k],v[j]));
              u=concat(w,vector(#u,k,chinese(u[k],-v[j]))));u=lift(u);
              for(k=1,#u,t=Lenstra(n,u[k],d)[3];if(#t,t=factor((t[2]-t[1])/d);
              print("Solution: "t[1,1]" in "gettime" ms");break()));}

              Solution: 5558358186556723282830357110595686293 in 42 ms

              Comment: The complete factorization of the cyclotomic
              number was given by Paul Leyland:
              http://www.leyland.vispa.com/numth/factorization/anbn/4+3.txt
              385 2311.512053081.200512409435077328148952740169875706164009384669091. P83

              David
            Your message has been successfully submitted and would be delivered to recipients shortly.