QuadSieveEx.html

Quadratic Sieve Examples

>

In the context of RSA, factoring the product of a pair of prime numbers is an important problem. One of the current methods of solving this problem is with a quadratic sieve. It is a difficult enough process that we would like to look at an example in detail.

We would like to look at using a quadratic sieve to factor a product of two primes. We start with an n that is a product of two primes.

Example 1, n = 9091*3271

> isprime(3271);
isprime(9091);
n := 9091*3271;

We want to look at numbers whose squares that will be a product of small primes mod n. For our example we will consider a prime to be small if it is less than 20. We will also cheat a bit on checking if a number is a product of small primes. Instead we will check if it divides the tenth power of the product of small primes.

> smallprime := 2*3*5*7*11*13*17*19;

To find numbers whose square is a product of small primes we look for numbers whose square is small mod n. We find candidates by taking the square root of n*i and rounding up. If the result is a factor of (smallprime)^10, we factor it and store the result.

>    for i from 1 to 100 do
   t1 := ceil(sqrt(n*i)):
   t2 := t1^2 mod n:
   t3 := irem(smallprime^10, t2):
   if (t3 = 0) then print(i, t1, t2, ifactors(t2)) fi;
end do:

A line of output lists the i from the square root of n*i, the value m this rounds up to, the square mod n, and the prime factors with multiplicity of M=m^2mod n. We look for products of m's where the product of the M's is a perfect square. The rows corresponding to 11 and 14 work. They tell us that (18086*36172)^2 = (2*5^3)^2 mod n. This means n divides (18086*36172-2*5^3)(18086*36172+2*5^3). Hopefully one of the factors of n divides each of these factors.

> igcd(18086*36172-2*5^3,n);

Unfortunately, that is not true so we need to try more numbers to get more relations.

>    for i from 1 to 400 do
   t1 := ceil(sqrt(n*i)):
   t2 := t1^2 mod n:
   t3 := irem(smallprime^10, t2):
   if (t3 = 0) then print(i, t1, t2, ifactors(t2)) fi;
end do:

We can look at the product of the rows corresponding to 31, 278, and 396, or rows 11 and 275, or row 225 all by itself.

> igcd(30362*90922*108653-2^2*3^2*7^3*11*17,n);
igcd(18086*90430-5^4,n);
igcd(81797-22,n);

Two of these three sets of relations yield a prime factorization of n.

Example 2: n= 3701*3571

> p := 3701;
q := 3571;
n := p*q;

> smallprime := 2*3*5*7*11*13*17*19;

> for i from 1 to 400 do
t1 := ceil(sqrt(n*i)):
t2 := t1^2 mod n:
t3 := irem(smallprime^10, t2):
if (t3 = 0) then print(i, t1, t2, ifactors(t2)) fi;
od: