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

Illustration of the quadratic part of the quadratic sieve factoring algorithm, using small integer

Expand Messages
  • Kermit Rose
    The quadratic part of the quadratic sieve factoring algorithm illustrated with a small integer. Let z = 33 = 3 * 11 We know that it is trivial to factor such a
    Message 1 of 2 , Feb 5, 2010
    • 0 Attachment
      The quadratic part of the quadratic sieve factoring algorithm
      illustrated with a small integer.

      Let z = 33 = 3 * 11

      We know that it is trivial to factor such a small integer
      by trial division.

      However, 33 also can be used to illustrate one of the principles used in
      the quadratic sieve algorithm.

      The largest square < 33 is 25 = 5**2.

      25 = -8 mod 33.

      5**2 = -8 mod 33.

      2 * 33 = 66.

      The largest square < 66 is 64 = 8**2.

      64 = -2 mod 33.

      8**2 = -2 mod 33

      (5**2) * (8**2) = (-8)*(-2) mod 33.

      The (5**2) * (8**2) ensures we have an integer square,
      for which we already know the square root.

      The (-8)*(-2) is selected from among the squares
      mod z, to ensure that the product is also an integer
      square, for which we already know the square root by
      the selection process.


      (5 * 8)**2 = 16 mod 33

      40**2 = 4**2 mod 33

      40 = 7 mod 33

      7**2 = 4**2 mod 33

      7**2 - 4**2 = 0 mod 33

      (7-4)*(7+4) = 0 mod 33

      3 * 11 = 0 mod 33.




      Kermit
    • aldrich617
      ... Another pattern that leads to the determination of factors by the above method begins with: 14**2 = 2 mod 33; 8**2 = -2 mod 33; In a closely related
      Message 2 of 2 , Feb 12, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Kermit Rose <kermit@...> wrote:
        >
        >
        >
        > 5**2 = -8 mod 33.
        >
        > 8**2 = -2 mod 33
        >
        > (5**2) * (8**2) = (-8)*(-2) mod 33.
        >
        > (5 * 8)**2 = 16 mod 33
        >
        > 40**2 = 4**2 mod 33
        >
        > 40 = 7 mod 33
        >
        > 7**2 = 4**2 mod 33
        >
        > 7**2 - 4**2 = 0 mod 33
        >
        > (7-4)*(7+4) = 0 mod 33
        >
        > 3 * 11 = 0 mod 33.
        >

        Another pattern that leads to the determination of factors
        by the above method begins with:
        14**2 = 2 mod 33;
        8**2 = -2 mod 33;

        In a closely related method
        we start with an integer Q such that Q**2 > 33 and Q**2 mod 33
        equals a perfect square:
        7**2 mod 33 = 16; 7 +/- 4 has factors of 33
        10**2 mod 33 = 1; 10 +/- 1 has factors of 33
        13**2 mod 33 = 4; 13 +/- 2 has factors of 33
        16**2 mod 33 = 25; 16 +/- 5 has factors of 33

        There are many additional variations of quadratic sieve factoring
        ideas. The problem really is to find an extremely efficient search
        pattern good for very large integers.
      Your message has been successfully submitted and would be delivered to recipients shortly.