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

Expand Messages
• 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
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 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
• ... 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
--- 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