The quadratic sieve is a general purpose factoring method invented by Carl Pomerance in 1981. Invention of quadratic sieve greatly advanced the science of factorization of integers, particularly those considered difficult, those large integers containing exactly two prime factors of approximately the same precision.

Running time of quadratic sieve is dependent on size of integer to be factored, and the quadratic sieve has accomplished some impressive records in the field of factorization of integers.

This page presents some simple examples of the factorization of small integers. Although using the quadratic sieve on small integers is like driving a thumb tack with a sledge hammer, the examples illustrate how the quadratic sieve is implemented.

Introduction

edit

The quadratic sieve attempts to build quadratic congruences of form   where   is number to be factored.


Many congruences are created:

 

 

 

 

 


Suitable congruences are combined to produce congruent squares:

  where

 

 


Then   and, with a little luck,

  and

  where   is function  

Implementation

edit

This exercise calculates prime factors of  

Build Factor base

edit

Let the Factor Base contain 40 small primes, the first 40 for which   is a quadratic residue.

[2, 11, 13, 17, 19, 23, 37, 41, 43, 59, 73, 103, 107, 113, 127, 131, 137, 149, 163, 179, 181, 
191, 197, 199, 211, 223, 233, 241, 251, 271, 281, 293, 307, 311, 317, 347, 367, 373, 379, 383]

Dictionary with logarithms of primes

edit

Create a table or dictionary containing primes and logarithms of primes. Logarithms to base 2 are calculated. The reason for choosing base   will become apparent later.

   
                  
   
   
   
   
   
    
   
   
   
   
   
   
   
   
    
   
   
   
   
   
   
   
   
   
   
   
   
   
    
   
   
   
   
   
    
   
   
   
   

Initialize sieve

edit

In a regular sieve fine material falls through sieve and coarse material is retained. In this sieve coarse material falls through sieve and fine material is retained.

The expression "coarse material" refers to integers containing a small number of large primes, the great majority of integers.

The expression "fine material" refers to integers containing a large number of small primes, primes that are members of this factor base, or "smooth" according to this factor base.

The base or root of operations is the smallest value of   for which   is a positive number.

 

# python code:

root = 71679

sieve = dict()

sieve[root] = [2]

for prime in factorBase[1:] :
    count = 0
    for x in range (root, root+2*(prime+2)) :
        y = x**2 - N
        if (y % prime) == 0 :
            if x in sieve : sieve[x] += [prime]
            else :  sieve[x] = [prime]
            count += 1
        if count >= 2 : break
    if count != 2 : print ('Internal error 1.')

L1 = sorted([p for p in sieve])

print()
print ('Initialized sieve contains', len(sieve),
       'keys in range from', L1[0], 'through', L1[-1],
       'or', L1[-1]-L1[0]+1, 'possibilities.')
Initialized sieve contains 65 keys in range from 71679 through 71954 or 276 possibilities.
for key in L1[::-1] :
    print (key, '|', sieve[key])
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

Activate sieve

edit

While information in table above is accurate, it is incomplete. Processing of sieve attempts to find values for which information is complete.

Processing locations in sequence

edit
Step 1
edit

The code examines location 71679. Product of factors 2,11 = 22, not enough to provide complete factorization of  

Location 71679+2 or 71681 is initialized with [2] and location 71679+11 or 71690 is appended by [11]. Location 71679 is deleted.

   
   
   
   
   
   
   
   
   
   
   
   
   
Step 2
edit

The code examines location 71680. Factor 13 is not enough to provide complete factorization of  

Location 71680+13 or 71693 is initialized with [13]. Location 71680 is deleted.

   
   
   
   
   
   
   
   
   
   
   
   
   
Step 3
edit

The code examines location 71681. Factor 2 is not enough to provide complete factorization of  

Location 71681+2 or 71683 is initialized with [2]. Location 71681 is deleted.

   
   
   
   
   
   
   
   
   
   
   
   
   
Step 4
edit

Location 71682 does not exist in sieve. The code examines location 71683. Factor 2 is not enough to provide complete factorization of  

Location 71683+2 or 71685 is appended by [2]. Location 71683 is deleted.

   
   
   
   
   
   
   
   
   
   
   
   

Processing continues in this way until location 71690 is examined. Factors [17, 23, 373, 11] are complete factorization of   Values [ 71690 , [17, 23, 373, 11] ] are appended to array "smooth."


Sieving continues until array "smooth" contains 45 members, at which time sieving is complete.

To improve speed

edit

There are very few values of   that are smooth. Therefore code is designed to discard unsuitable values of   quickly, and to make other decisions quickly.

Decisions to discard unsuitable candidates are:

  • if x does not exist in sieve.
  • if there is only 1 prime for location x. Complete factorization of y requires at least 2 primes.

Code intended to reduce processing time:

 

 

 

 

 

Multiplication in last statement above is of smaller numbers than calculation of   As size of   increases, last statement above becomes more efficient.

Divisions and multiplications are time consuming. Instead of multiplying primes or dividing   to determine smoothness, logarithms of primes are added and compared to   Calculation of   or   to base   is time consuming. Because   is type   a good approximation of   to base   can be calculated quickly. As it happens, in this application "close enough" is good enough.


  for example:

As binary,  

Length of   is   Therefore  


  for example:

As binary,  

Length of   is   Therefore  

However, second most significant bit is set. Therefore  

   
   
   
   
   
   
   
   
   

Sieving complete

edit

Python code that accomplishes the sieving is:

# python code.

limit = 10000
rootSquaredMinusN = root**2 - N
twoRoot = root << 1
notin = count1 = count = 0
smooth = []
numberOfSmoothDesired = 45
for x in range (root, root+limit) :
    if x & 0xFF == 0 :
        '''
This code is added to provide information about sieve
during sieving.
'''
        L1 = sorted([ p for p in sieve ])
        range_ = L1[-1] - L1[0] + 1
        print ('For x =',x, 'Range of sieve =',range_, 'number of empty locations =', range_ - len(L1) )
    if x not in sieve :
        notin += 1
        continue

    primes = sieve[x]
    for prime in primes :
        v = x + prime
        if v in sieve : sieve[v] += [prime]
        else : sieve[v] = [prime]
    del (sieve[x])

    if len(primes) == 1 :
        count1 += 1 ; continue                 
    a = x - root
    y = rootSquaredMinusN + a*(twoRoot + a)

    sumOfLogs = log[primes[0]] + log[primes[1]]
    for prime in primes[2:] : sumOfLogs += log[prime]

    log_y = logBase2(y)
    if sumOfLogs >= 0.95*log_y :
        count += 1
        product = primes[0] * primes[1]
        for prime in primes[2:] : product *= prime
        if y == product :
            smooth += [[x,primes]]
            if len(smooth) >= numberOfSmoothDesired : break
            
print ('Range of values of x =', x-root+1)
print ('Number of empty locations in sieve =', notin)
print ('Number of locations with only 1 prime =', count1)
print ('Number of locations tested =', x-root+1-notin-count1)
print ('Number of locations chosen for close examination =', count)
print ('Number of values of x retained after close examination =', len(smooth))
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

Thousands of values of   are tested. At any one time the range of values of   in sieve is   and sieve is mostly empty.

Range of values of x = 3922
Number of empty locations in sieve = 585
Number of locations with only 1 prime = 1331
Number of locations tested = 2006
Number of locations chosen for close examination = 45
Number of values of x retained after close examination = 45

Array of smooth values

edit

Array "smooth" contains 45 members:

[71690, [17, 23, 373, 11]]
[71706, [137, 199, 13, 11]]
[71733, [113, 137, 251, 2]]
[71771, [233, 59, 37, 13, 2]]
[71800, [271, 307, 19, 11]]
[71824, [163, 103, 73, 17]]
[71849, [223, 383, 13, 11, 2]]
[71876, [211, 307, 23, 19]]
[72030, [103, 41, 37, 19, 17]]
[72066, [379, 131, 59, 19]]
[72071, [271, 59, 43, 41, 2]]
[72237, [233, 211, 43, 19, 2]]
[72268, [241, 163, 127, 17]]
[72372, [271, 43, 41, 19, 11]]
[72425, [367, 191, 59, 13, 2]]
[72509, [241, 211, 107, 11, 2]]
[72659, [211, 41, 37, 17, 13, 2]]
[72750, [241, 113, 23, 19, 13]]
[72809, [373, 281, 41, 19, 2]]
[72863, [149, 113, 23, 17, 13, 2]]
[73246, [163, 113, 59, 19, 11]]
[73279, [197, 179, 23, 13, 11, 2]]
[73322, [317, 179, 19, 17, 13]]
[73411, [307, 293, 127, 11, 2]]
[73472, [113, 107, 103, 19, 11]]
[73576, [347, 73, 43, 23, 11]]
[73868, [233, 131, 73, 13, 11]]
[73898, [163, 137, 37, 23, 17]]
[73900, [131, 107, 59, 23, 17]]
[73968, [293, 271, 19, 17, 13]]
[74176, [73, 41, 37, 23, 13, 11]]
[74427, [311, 127, 23, 17, 13, 2]]
[74435, [281, 181, 107, 37, 2]]
[74544, [127, 59, 23, 17, 13, 11]]
[74583, [293, 137, 37, 13, 11, 2]]
[74671, [127, 113, 73, 19, 11, 2]]
[74890, [199, 181, 179, 73]]
[75052, [271, 197, 127, 73]]
[75247, [251, 163, 149, 43, 2]]
[75252, [233, 211, 181, 59]]
[75365, [379, 163, 107, 41, 2]]
[75433, [293, 181, 127, 41, 2]]
[75462, [293, 113, 43, 23, 17]]
[75554, [223, 199, 43, 23, 13]]
[75600, [191, 37, 23, 19, 17, 11]]

If you look closely at contents of array "smooth," you notice that primes   are used exactly 1 time for each prime. Therefore, locations   are not usable.

This section removes members containing these values of   from array "smooth." Unfortunately, the removal of these values of   causes other members to become unusable. The process continues until array "smooth" is ready, meaning that each prime in array "smooth" appears at least 2 times.

Removing unusable primes from smooth:
unusable = [383, 367, 317, 347, 311]
unusable = [223, 191]
len(smooth) = 38

The final version of array "smooth" contains 38 members:

[71690, [17, 23, 373, 11]]
[71706, [137, 199, 13, 11]]
[71733, [113, 137, 251, 2]]
[71771, [233, 59, 37, 13, 2]]
[71800, [271, 307, 19, 11]]
[71824, [163, 103, 73, 17]]
[71876, [211, 307, 23, 19]]
[72030, [103, 41, 37, 19, 17]]
[72066, [379, 131, 59, 19]]
[72071, [271, 59, 43, 41, 2]]
[72237, [233, 211, 43, 19, 2]]
[72268, [241, 163, 127, 17]]
[72372, [271, 43, 41, 19, 11]]
[72509, [241, 211, 107, 11, 2]]
[72659, [211, 41, 37, 17, 13, 2]]
[72750, [241, 113, 23, 19, 13]]
[72809, [373, 281, 41, 19, 2]]
[72863, [149, 113, 23, 17, 13, 2]]
[73246, [163, 113, 59, 19, 11]]
[73279, [197, 179, 23, 13, 11, 2]]
[73411, [307, 293, 127, 11, 2]]
[73472, [113, 107, 103, 19, 11]]
[73868, [233, 131, 73, 13, 11]]
[73898, [163, 137, 37, 23, 17]]
[73900, [131, 107, 59, 23, 17]]
[73968, [293, 271, 19, 17, 13]]
[74176, [73, 41, 37, 23, 13, 11]]
[74435, [281, 181, 107, 37, 2]]
[74544, [127, 59, 23, 17, 13, 11]]
[74583, [293, 137, 37, 13, 11, 2]]
[74671, [127, 113, 73, 19, 11, 2]]
[74890, [199, 181, 179, 73]]
[75052, [271, 197, 127, 73]]
[75247, [251, 163, 149, 43, 2]]
[75252, [233, 211, 181, 59]]
[75365, [379, 163, 107, 41, 2]]
[75433, [293, 181, 127, 41, 2]]
[75462, [293, 113, 43, 23, 17]]

The Matrix

edit

Prime factors of y = x^2 - N

edit

Assign a unique bit to each prime number in factor base:

   
     
    
    
    
    
    
   
   
   
   
   
   
   

Values of x in smooth array

edit

Assign a unique bit to each value of   in smooth array:

   
   
   
   
   
   
   
   
   
   
   
   
   
   

Create Matrix

edit

The matrix contains patterns representing values of   and patterns representing the corresponding prime factors of  

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

Process matrix

edit
                   Pattern representing values of x   |           Pattern representing factors of y
------------------------------------------------------|--------------------------------------------------
Line 1:   x1 = 00000000000000000000000000000000000001 |  f1 = 001000000000000000000000000000000010 1 010
               00000000000000000000000000000000000010 |       000000000000000010000001000000000000 0 110
               00000000000000000000000000000000000100 |       000000000001000000000001001000000000 0 001
               00000000000000000000000000000000001000 |       000000000000010000000000000000100100 0 101
               00000000000000000000000000000000010000 |       000000010010000000000000000000000001 0 010
Line 2:   x2 = 00000000000000000000000000000000100000 |  f2 = 000000000000000000000100000011000000 1 000
               00000000000000000000000000000001000000 |       000000010000000100000000000000000011 0 000
Line 3:   x3 = 00000000000000000000000000000010000000 |  f3 = 000000000000000000000000000010001101 1 000
               00000000000000000000000000000100000000 |       010000000000000000000000100000100001 0 000
               00000000000000000000000000001000000000 |       000000000010000000000000000000111000 0 001
               00000000000000000000000000010000000000 |       000000000000010100000000000000010001 0 001
Line 4:   x4 = 00000000000000000000000000100000000000 |  f4 = 000000000000100000000100010000000000 1 000
               00000000000000000000000001000000000000 |       000000000010000000000000000000011001 0 010
               00000000000000000000000010000000000000 |       000000000000100100000000000100000000 0 011
Line 5:   x5 = 00000000000000000000000100000000000000 |  f5 = 000000000000000100000000000000001100 1 101
               00000000000000000000001000000000000000 |       000000000000100000000000001000000011 0 100
               00000000000000000000010000000000000000 |       001000000100000000000000000000001001 0 001
Line 6:   x6 = 00000000000000000000100000000000000000 |  f6 = 000000000000000000000010001000000010 1 101
               00000000000000000001000000000000000000 |       000000000000000000000100001000100001 0 010
               00000000000000000010000000000000000000 |       000000000000000001001000000000000010 0 111
               00000000000000000100000000000000000000 |       000000011000000000000000010000000000 0 011
               00000000000000001000000000000000000000 |       000000000000000000000000001110000001 0 010
               00000000000000010000000000000000000000 |       000000000000010000000000100001000000 0 110
Line 7:   x7 = 00000000000000100000000000000000000000 |  f7 = 000000000000000000000101000000000110 1 000
Line 8:   x8 = 00000000000001000000000000000000000000 |  f8 = 000000000000000000000000100100100010 1 000
Line 9:   x9 = 00000000000010000000000000000000000000 |  f9 = 000000001010000000000000000000000001 1 100
               00000000000100000000000000000000000000 |       000000000000000000000000000001001110 0 110
               00000000001000000000000000000000000000 |       000000000100000000010000000100000100 0 001
Line 10: x10 = 00000000010000000000000000000000000000 | f10 = 000000000000000000000000010000100010 1 110
               00000000100000000000000000000000000000 |       000000001000000000000001000000000100 0 111
               00000001000000000000000000000000000000 |       000000000000000000000000011001000001 0 011
               00000010000000000000000000000000000000 |       000000000000000010011000000001000000 0 000
               00000100000000000000000000000000000000 |       000000000010000001000000010001000000 0 000
               00001000000000000000000000000000000000 |       000000000001000000000110000000010000 0 001
               00010000000000000000000000000000000000 |       000000000000010100010000000000100000 0 000
               00100000000000000000000000000000000000 |       010000000000000000000100000100001000 0 001
               01000000000000000000000000000000000000 |       000000001000000000010000010000001000 0 001
Line 11: x11 = 10000000000000000000000000000000000000 | f11 = 000000001000000000000000001000010010 1 000
                                                                                                   ^
                                           Lines designated with a line number all have bit 3 set: ^

Last line of matrix   becomes the source of the next operation.   has   set. Targets of the operation are all other lines with   set, lines designated as   through  

  is combined in turn with   by means of operation exclusive or, thus:

x10 = x10 ^ x11
f10 = f10 ^ f11

x9 = x9 ^ x11
f9 = f9 ^ f11

...............

x1 = x1 ^ x11
f1 = f1 ^ f11

  is deleted and   has been removed from all values on Right Hand Side of matrix.

The process is repeated. When a zero value is found on Right Hand Side of matrix, it means that this value is a perfect square.

Produce factors of N

edit

Processing the matrix revealed 7 values of X that produce a perfect square on Right Hand Side of congruence.

Perfect square #1

edit

00000000010000000001001000100000000000

The 4 bits set in this pattern represent values of x : [72268, 72750, 73246, 74544]

X = 72268 * 72750 * 73246 * 74544 = 28706195569530528000


These 4 values of x produce a value on RHS of congruence containing factors:

[11, 11, 13, 13, 17, 17, 19, 19, 23, 23, 59, 59, 113, 113, 127, 127, 163, 163, 241, 241]

Every factor in this list appears an even number of times.

Therefore, Y is product of factors: [11, 13, 17, 19, 23, 59, 113, 127, 163, 241]

Y = 35335010025681509


Using   and  

p1,p2 = 1, 5137851827


This congruence produced trivial factors of N.

Perfect square #2

edit

01010000010010001000001111010010000000

The 11 bits set in this pattern represent values of x :

[72030, 72237, 72372, 72509, 72659, 72750, 73472, 73968, 74544, 75252, 75433]

X = product of values of x = 331906592471738688342554821695566634067059049758720000


From these 11 values of x:

Y = product of factors:

[2, 2, 11, 11, 13, 13, 17, 17, 19, 19, 19, 23, 37, 41, 41, 43, 
59, 103, 107, 113, 127, 181, 211, 211, 233, 241, 271, 293]

Y = 3343990074727707345948316157765706289327953268


Using   and  

p1,p2 = 89123, 57649


This congruence produced non-trivial factors of N.

Example #2

edit

This example presents a more advanced implementation of the quadratic sieve because it includes the following features:

  • Use of powers of primes.
  • Use of primes not in factor base, "large" primes.
  • Participation in a distributed computing effort.

Past attempts to factor large integers were successful only because many computers contributed to the production of "smooth" values of  

One way to organize a distributed computing effort is to assign different tasks to many different computers so that no computer duplicates the work of another. For example, different computers can be assigned the following tasks:

  • Smooth values for   with   positive.
  • Smooth values for   with   negative.
  • Smooth values for   with   positive.
  • Smooth values for   with   negative.


This example assumes the role of computer assigned:

Smooth values for   with   negative.

To ensure that this task does not duplicate other work, values of   are all odd.


Let  

Then  

  where   is an odd integer very close to  

Because   is even and   is always odd,   is always odd.

Consequently, prime number   is not in factor base.

Factor base

edit

Create the factor base, a list containing 230 small primes for which   is a quadratic residue:

 

You may notice that primes   do not exist in this factor base.

Tables of logarithms

edit

Create a dictionary of logarithms, called  :

   
         
         
       
       
   
   
   
   
   

For example,  


Create a dictionary of antilogarithms, called  :

   
           
           
         
         
   
   
   
   
   

For example, desired prime  

Create sieve

edit

Preparation

edit

The following code adds to sieve information concerning powers of primes.

A closer look at this information will be presented later.

# python code

sieve = dict()

def powers_of_primes (p,power,L1) :
    '''
x1,x2 = powers_of_primes (p,power,[xa,xb])
This function may return None.

If power == 2 :
L1 contains 2 values of x that satisfy: x**2 /// N (mod p)
This function calculates the values of x for which:
x**2 /// N (mod (p**2))

If power == 3 :
L1 contains 2 values of x that satisfy: x**2 /// N (mod (p**2))
This function calculates the values of x for which:
x**2 /// N (mod (p**3))

and so on.

The method presented here, while simple and accurate, is
suitable for only small primes. As the size of p increases,
this method becomes impractical.
'''
    thisName = 'powers_of_primes() :'
    P_ = p**(power-1)
    P = P_ * p

    if P > 1_000_000 : return None

    L2 = []
    for x_ in L1 :
# Verify that x_ is valid.
        y = x_**2 - N
        if y % P_ :
            print (thisName,'Error 1 for x,p =',x_,p)
            return None
        for k in range(0,p) :
            x = x_ - k * P_
            y = x**2-N
            if y%P : continue
            if not (x&1) : x -= P # x must be odd.
            if not (x&1) :
                print ('error1a') ; continue
            y = x**2 - N
            if y%P :
                print ('error2') ; continue
# Every increment that goes into sieve must be even because:
# Odd x + even increment gives odd x.
            if x in sieve :
# Value of prime p is not included here. It will be recovered later.
# Hence the requirement for dictionary aLogs.
                sieve[x] += [(P<<1,logs[p])]
            else :
                sieve[x] = [(P<<1,logs[p])]
            L2 += [x]
            break
    if len(L2) != 2 :
        print (thisName, 'error2a, len(L2) =', len(L2))
        return None
    return L2

Initialize sieve

edit
# python code

for p in factorBase :
    modulo = N%p
    for q in range (p>>1, 0, -1) :
        y = q**2 - modulo
        if y%p : continue

        base1 = base - (base%p)
        L1 = []
        for x in (base1 + q, base1 - q) :
            if not (x&1) : x -= p # Make x odd.
            if not (x&1) : print ('error3')
            y = x**2 - N
            if y%p :
                print ('error4') ; continue
# Every increment that goes into sieve must be even because:
# Odd x + even increment gives odd x.
            if x in sieve :
                sieve[x] += [(p<<1,logs[p])]
            else :
                sieve[x] = [(p<<1,logs[p])]
            L1 += [x]
        break
        
    last = L1
    for power in range (2,14) :
        this = powers_of_primes(p,power,last)
        if this == None : break
        last = this

Initialized sieve contains 624 valid locations.

Check sieve

edit

It is wise to check entries in sieve because an error in initialized sieve can cause many problems later.


First entry in sieve is :

 

Value   and  

Value   is the decrement, always even.

Decrement must be exactly divisible by associated prime.

Value   and   must be  


The other entry containing this prime is:

 

There must be exactly 2 instances of each decrement, and difference between associated values of   must not be exactly divisible by decrement.


Here is an entry for prime  

  Value  

Decrement   and  

This decrement appears in the sieve exactly 2 times, at   and   and   is non-zero, correct.

Check:   This calculation   which is correct.


In this way, all entries in sieve are checked.

Activate sieve

edit
# python code.
print ('''
Activate sieve
''')
log_of_maximum_prime2 = 0.9*2*logs[factorBase[-1]]
smooth = []
last_log = 0

# (x_ + a)**2 = x_**2 + 2ax_ + a**2
# (x_ + a)**2 - N = x_**2-N + 2ax_ + a**2
# (x_ + a)**2 - N = x_**2-N + a(2x_ + a)
# x_ = base
base_squared_minus_N = base**2 - N
two_times_base = 2*base

count1 = count2 = count3 = 0

for x in range (max, max-(2*(10**5)), -2) :
    if (x & 0x7FFF) == 1 :
# This piece of code is not normally required.
# It is included here to provide some statistics about sieve during sieving.
        L1 = sorted([ p for p in sieve ])
        min_ = L1[0] ; max_ = L1[-1] ; used = len(L1)
        print ('''
max = {}
min = {}
range of sieve = {}
number of values used = {}
'''.format(max_, min_, 1+max_-min_, len(sieve))
)

    if x not in sieve :
        count1 += 1 ; continue

    values = list(sieve[x]) ; del (sieve[x])

    sum_of_logs = 0
    for v in values :
        increment, log2_ = v
        next = x-increment
        if next in sieve : sieve[next] += [v]
        else : sieve[next] = [v]
        sum_of_logs += log2_

    if sum_of_logs < last_log :
        count2 += 1 ; continue

    a = x - base ;
    y = base_squared_minus_N + a*(two_times_base + a)
    logy = logBase2 (abs(y))
# this_log is < logy to allow inclusion of "large" prime.
    last_log = this_log = logy-log_of_maximum_prime2
    if sum_of_logs < this_log :
        count3 += 1 ; continue
    smooth += [[x,values]]

The following data are representative of statistics collected during sieving.

max = 24295997441
min = 24294230499
range of sieve = 1766943
number of values used = 601

Range of values in sieve was about 1.75 million, and number of entries in sieve at any time was about 600.

Within this range of values of   only odd values are used.

# python code.

print ('''
Sieving complete:

not in sieve = count1 = {}
(sum_of_logs < last_log) = count2 = {}
(sum_of_logs >= last_log), but (sum_of_logs < this_log) =  count3 = {}
length of ( smooth ) = {}
total = {}
'''.format(count1,count2,count3,len(smooth), count1+count2+count3+len(smooth))
)
Sieving complete:

not in sieve = count1 = 8238
(sum_of_logs < last_log) = count2 = 89543
(sum_of_logs >= last_log), but (sum_of_logs < this_log) =  count3 = 2
length of ( smooth ) = 2217
total = 100000
  • 8,238 values of   were discarded because they did not exist in sieve.
  • 89,543 values of   were discarded because they were not "smooth." Note that decision to discard did not depend on calculation of   or  
  • 2,219 values of   were examined for smoothness. Of these, 2 were discarded.
  • Array "smooth" contains 2,217 members.

Process array "smooth."

edit

Array "smooth" contains entries similar to this example:

[
24296003881, 
[(106, 5.72792), (386, 7.59246), (562, 8.13443), (54, 1.58496), (18, 1.58496), (14, 2.80735), (6, 1.58496)]
]

  is value of  

Antilogs are replaced by the corresponding prime.

[(106, 53), (386, 193), (562, 281), (54, 3), (18, 3), (14, 7), (6, 3)]
  • decrement  
  • decrement  
  • decrement  
  • decrement  
  • decrement  
  • decrement  
  • decrement  
  • If there is entry for   there must be entry for  
  • If there is entry for   there must be entry for  
# python code.
>>> N,x
(590295810358705651708, 24296003881)
>>> y = abs(x**2 - N) ; y
5773138589547
>>> q,remainder = divmod (y, 53*193*281*3*3*7*3);q,remainder
(10627, 0)
>>>

Product   divides   exactly.

Quotient   is a "large" prime. Without the powers of   this entry may have been missed.

This entry becomes :

[
24296003881, 
[53, 193, 281, 3, 7, 10627]
]

When a prime is included here, it was used an odd number of times above.

Here is an example of a smooth value of  

[24295805845, [3203, 641, 577, 547, 127, 13, 3, 3]]

There is no large prime. This entry becomes:

[24295805845, [3203, 641, 577, 547, 127, 13]]

Prime   is not used. It did not appear an odd number of times.

The smooth array is processed as necessary to eliminate any entry containing a prime used only once. Any prime in smooth is used at least twice.

Here is an example deleted because the large prime was used only once:

[24295822145, [619, 181, 157, 83, 3], 2017529]

Here is an example retained because the large prime was used twice:

[24296002963, [797, 83, 3, 3, 23, 3, 3], 408803]

This entry becomes:

[24296002963, [797, 83, 23, 408803]]

Recall that the range of values of   examined by the sieve was 200,000.

Yet, here we see large prime 408,803 used twice. How is this possible?

Because prime   was found twice, the same question can be asked for these entries:

[24295960025, [863, 547, 67, 13, 3, 1732331]]
[24295924525, [1277, 857, 97, 7, 3, 1732331]]

Here is an example of a large prime used 3 times:

[24295844383, [1259, 983, 863, 67, 12043]]
[24295854167, [2179, 1093, 443, 191, 3, 12043]]
[24295964813, [2347, 661, 641, 53, 3, 12043]]

If you look closely,   Why only 3 entries for prime  


Result is array smooth containing 286 entries. Of these 96 are smooth. 190 contain large primes.

The total number of primes is 281. Of these 91 are large primes. You can see that large primes are almost a third of all primes used.

Note that number of entries is more than number of primes. This indicates that the probability of finding perfect squares is good.

Although this array is called "smooth," the numbers show that it is not smooth. Perhaps a name such as "useful" would be better.


  less than   containing large primes. This shows that some large primes must be used at least   times.

Produce results

edit

Create and process matrix as in example above.

Remember that all values of   are negative. Use last entry of matrix as source and combine this source with all other lines in matrix. This eliminates factor   from matrix.

6 exact squares were produced:

0x441c794316262b96cba6611846d4d08f140a9112094634a0a4005ca0a55049f3242a9a
0x191d545b83a46c88439a5c3aca122ec85583100679c867ecb95c568398b33ae37c35f49
0x2108304080466a0a6b086014a1d2fb252586943d48ac34aa938041431a58210034283a4
0x421979c5e5689e36142c1b3ee2158332eab3a2f21ba1ba9bab1fff1ce2cabeec565245d
0x89e6c569cd412504035f785fb66f3cb43542eb37a09f8572451618e98153cc889520475
0x1093981134aa745002d0c560f80a3686d00c76b3d3e7e44aefbf81350998e106ad09d833

First exact square produced the trivial solution. All others produced the non-trivial solution.

Here are details about solution number 2:

0x191d545b83a46c88439a5c3aca122ec85583100679c867ecb95c568398b33ae37c35f49

Bits in this solution represent values of  

24295805611  24295808157  24295809107  24295810993  24295813401  24295814777
24295815203  24295815539  24295817177  24295817523  24295818143  24295822355
24295822809  24295823345  24295823809  24295824387  24295826851  24295829685
24295834427  24295834433  24295834903  24295835917  24295836679  24295840049
24295840069  24295842793  24295845053  24295850555  24295851025  24295852037
24295856707  24295856797  24295858601  24295859223  24295860675  24295864007
24295868039  24295869383  24295870685  24295872787  24295874983  24295875361
24295875395  24295877125  24295882233  24295887633  24295888671  24295889123
24295889763  24295891739  24295891827  24295894117  24295896665  24295897715
24295897757  24295898563  24295898639  24295900473  24295900529  24295902379
24295903131  24295903735  24295903845  24295906899  24295907743  24295909587
24295909633  24295915013  24295915591  24295925549  24295928591  24295928827
24295933043  24295933489  24295935911  24295937075  24295938625  24295941777
24295944341  24295946505  24295947657  24295947869  24295948051  24295949051
24295950065  24295950821  24295955895  24295956829  24295958335  24295959525
24295960117  24295962247  24295963279  24295963477  24295965661  24295965791
24295965927  24295966189  24295967757  24295969127  24295970477  24295972089
24295972745  24295973099  24295976427  24295978303  24295981347  24295981883
24295982671  24295982999  24295983685  24295984517  24295985429  24295985575
24295987391  24295987487  24295992373  24295993279  24295993381  24295994227
24295994959  24295996271  24295997723  24295997941  24295998495  24295998895
24296000299  24296001081  24296001127  24296002045  24296002715  24296002963

  integer containing   decimal digits.


  integer containing   decimal digits.

# python code.
    gcd1 = iGCD (x+y,n)
    print ('gcd1 =',gcd1)
    gcd2 = iGCD (x-y,n)
    print ('gcd2 =',gcd2)
gcd1 = 193707721
gcd2 = 761838257287

Review

edit

Example #2 above began with 100,000 simple operations on the sieve. Yes, the range of the sieve was about 1.75 million. This means that there were entries in bottom of sieve that were never used.

The 100,000 simple operations produced about 2,000 items of data worth investigating, This investigation produced a matrix of length 286 from which 5 non-trivial congruences were derived.

The original factor base contained 230 primes. Of these, 190 were used, leaving 40 unused.


If it seems that there was "too much data," this is not a problem. If you find yourself with not enough data, this really is a problem.

  is in fact   called   a number made famous by Professor Frank Nelson Cole in 1903.

Before the era of computers he produced the factors of   with pencil on paper, a magnificent achievement.

edit

Professor Cole's Paper

Mersenne prime

Carl Pomerance

Quadratic sieve

RSA-129