A sieve attempts to separate desired things from other things. In this case, we seek to remove steps from the Fermat Method of Prime Factorization
which do not lead to a solution from those which might lead to a
solution. The method of finding whether the a's and b's are odd or even
in: a2−b2=N when we are trying to factorize
N using Fermat's Method is a method of sieving, because when we find
that a, for instance, is even, we do not need to test the odd values,
and this reduces the work involved by one half, because we remove all
the odd a's.
Here, we attempt to remove more a's from our procedure in the following way.
We recall:
a2−b2=N [1.1] Where a, b and N are positive integers, and N is odd. We seek to factor N by seeking a's and b's which satisfy equation 1.1, so: (a+b)(a−b)=N, giving us factors of N. By considering 1.1 modulo 10, we can simplify the arithmetic and discover some properties of our a's. By rearranging 1.1, we get: a2−N=b2 [1.2] Or a2−N≡b2 (mod 10) [1.3] That is: a2−N≡a perfect square (mod 10) [1.4] So: a2≡N+a perfect square (mod 10) [1.5]
Perfect Squares Modulo 10
The following integers are perfect squares modulo 10: 0, 1, 4, 5, 6, 9 [2.1] That is any integer, modulo 10 when squares produces one of the six numbers above.
The square roots of each of these numbers (modulo 10) are: √0=0 √1=1 or 9 √4=2, or 8 √5=5 √6=4, or 6, and √9=3 or 7 [ List 2.2]
Computing the a's modulo 10
Let us consider the number 4633, for which we seek to find its factors (or if it is prime). √(4633) ≤69
4633 (mod 10)≡3
Using formula 1.5: a2≡N+a perfect square (mod 10) [1.5, repeated] And noting the perfect squares modulo 10: 0, 1, 4, 5, 6, 9 [2.1, repeated]
We can copy the perfect squares from 2.1 into 1.5, substituting 3 for N, so possible values of a2 are: 0+3=3 (not a perfect square) 1+3=4 (perfect square, mod 10) 4+3=7 (not a perfect square) 5+3=8 (not a perfect square) 6+3=9 (perfect square, mod 10) 9+3=2 (mod 10)
So, a2 as 1 or 9 is a perfect square (modulo 10) Using odd/even , we note that 4633=-1 (mod 4), so N is of the form 4m+1, which means a and a2 are odd numbers. So a2=1, or 9 (mod 10) √1=1, or 9 (mod 10) and √9=3 or 7
So a ends in the digit 1, 9, 3 or 7. In fact, 772−362=4633 What
this means is that we would have to check the numbers from 69 to 77, or
8 numbers. Using the odd/even, and noting that a is odd, we would have
to check 69, 71, 73 and 77, or perhaps just 71, 73 and 77 if we have
checked the number isn't divisible by small numbers such as 3. With the
above information, we need to begin our search with 77, which in this
case, gives us the answer we seek: 4633=41•113
Which in this
case, we could have discovered much faster by applying Fermat to 8
numbers, 69-77, or even faster using trial division of about 15
numbers. However, with slightly larger numbers, trial division can
become extremely tedious, as can the Fermat Method.
For instance let N=6,747,883
Factorizing N=6,747,883
Without wishing to spoil the plot, it would take about 1000 trial divisions to factorize this number. N=6747883 √(6,747,883)<2598
The number is of the form 4m-1, so the a's are even numbers.
We recall: a2≡N+a perfect square (mod 10) [1.5, repeated] And the perfect squares, mod 10 are: 0, 1, 4, 5, 6, 9 [2.1, repeated]
And note that: 6747883=3 (mod 10)
So we search for possible a's modulo 10: 3+0=3 3+1=4 3+4=7 3+5=8 3+6=9 3+9=2 So a2 could be 1 or 6, but because it is even, then a2=6 √6=4 or 6 (mod 10)
The a's will therefore end in 2 or 8 or 4 or 6. In fact: 26782-6512=6747883 So the factors are (2678+651) and (2678-651), or 3329, and 2027 (see Fermat Method)
This means we would have to check using the Fermat Method (2678-2598 + 1)=81 terms, and using odd/even, 41 terms.
Using our perfect squares, we would have to check 17 terms. (Of course, with an actual problem, we would not know this.)
Let us consider modulo 30, to see if we can reduce the number of items to check.
Perfect Squares Modulo 30
The following are perfect squares modulo 30: 0, 1, 4, 6, 9, 10, 15, 16, 19 21, 24, 25
