- 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 - --- In primenumbers@yahoogroups.com, Kermit Rose <kermit@...> wrote:
>

Another pattern that leads to the determination of factors

>

>

> 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.

>

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.