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

Puzzle re factorization

Expand Messages
  • ronhallam@lineone.net
    Hi Following on from the emails relating to factorization, here is a little brain teaser. Work out the difference mod 6, 7 and 11 on the following number:
    Message 1 of 8 , Nov 25, 2012
    • 0 Attachment
      Hi
      Following on from the emails relating to factorization, here is a
      little brain teaser.
      Work out the difference mod 6, 7 and 11 on the following
      number:


      2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411.



      You should only need to use a computer to calculate the sqare root
      and the initial values for the modular values, the rest can be done
      using pencil and paper!! (back to the old days)





      Ron
    • djbroadhurst
      ... 2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411. Help! I can t do
      Message 2 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.

        Help! I can't do that. For n = p*q = 1 mod 11, there are
        10 solutions modulo 11, namely p = 1/q mod 11, for
        q = 1 to 10. And then the difference q - p may
        have 5 distinct values, mod 11:

        print(vecsort(eval(Set(vector(10,q,(q-1/q)%11)))));
        [0, 1, 4, 7, 10]

        David (missing something important?)
      • ronhallam@lineone.net
        David A clue would be phi(N). The number mod 11 gives 1, and the squareroot mod 11 is 4. (1 4 1 8 5 ** 5 4 0 10 9 6) (5 3 1 6 0 ** 0 9 1 10 8 2) (0 2 1 4
        Message 3 of 8 , Nov 25, 2012
        • 0 Attachment
          David
          A clue would be phi(N).

          The number mod 11 gives 1, and the squareroot mod 11 is 4.
          (1 4 1 8 5 '**' 5 4 0 10 9 6)
          (5 3 1 6 0 '**' 0 9 1 10 8 2)
          (0 2 1 4 8 '**' 8 5 4 1 9 0)
          (8 1 1 2 7 '**' 7 3 9 5 1 0)
          (7 0 1 0 8 '**' 8 3 5 0 6 2)
          (8 10 1 9 0 '**' 0 5 3 8 2 6)
          (0 9 1 7 5 '**' 5 9 3 7 0 1)
          (5 8 1 5 1 '**' 1 4 5 8 0 9)
          (1 7 1 3 10 '**' 10 1 9 0 2 8)
          (10 6 1 1 10 '**' 10 0 4 5 6 9)
          (10 5 1 10 1 '**' 1 1 1 1 1 1))

          The values after the asterixes are arrived at by deleting the
          follwing values mod 11 (0 1 5 6 7 10) from {5, 0,8, 7 ...} the missing
          values do not give any zeros.

          Looking at the values after the '**' the ones of interest are the
          values preceding a zero, so we have in the first column 5 and 8; the
          second column only gives a single value 1; the third colum gives a
          single value of 1; the fourth column give a 5 and 8; the fifth column
          gives a 2 and 0; whilst that last column also gives a 2 and 0.



          Putting these values together gives (5 8 1 2 0) the final twist is
          that the differences mod 11 are given by subtracting 1 from each value
          -->> (4 7 0 1 10 )mod 11.



          Proof: The possible factors mod 11 are (1 1) (2 6) (3 4) (5 9) (7
          8) (10 10).





          Ron









          >----Original Message----

          >From: d.broadhurst@...

          >Date: 25/11/2012 12:52

          >To: <primenumbers@yahoogroups.com>

          >Subj: [PrimeNumbers] Re: Puzzle re factorization

          >

          >

          >

          >--- In primenumbers@yahoogroups.com,

          >"ronhallam@..." <ronhallam@...> wrote:

          >

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

          >

          >2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411.

          >

          >Help! I can't do that. For n = p*q = 1 mod 11, there are

          >10 solutions modulo 11, namely p = 1/q mod 11, for

          >q = 1 to 10. And then the difference q - p may

          >have 5 distinct values, mod 11:

          >

          > print(vecsort(eval(Set(vector(10,q,(q-1/q)%11)))));

          >[0, 1, 4, 7, 10]

          >

          >David (missing something important?)

          >

          >

          >

          >

          >
        • djbroadhurst
          ... No. 4^2 is not equal to 1 mod 11. David
          Message 4 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 5 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 6 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 7 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 8 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.