Factoring by Modular Constraints.

Modular Constraints is not really a factoring method. It is a method of reducing the search space of other methods. It is also useful as a combiner over several different methods.

Given: a factoring method that involves a defining relation (such as Fermat's Y*Y - X*X = N),

If one evaluates this modulo a small number, one finds that not all values of the variables are possible.

For example, consider N=187. The only possibilities that work mod 2 are X=1,Y=0, and X=0,Y=1. The possibilities of X=1,Y=1 and X=0,Y=0 fail mod 2.

We will write the working possibilities as: (X,Y,2) = ({1,0}, {0,1})

Note that if there were three independent variables, there would be three numbers in each item. If there was only one number each item would have only one element. [If you know any with only one variable, I want to hear about it.]

Formal Description

If the indices of two rows have no common factors, then there is not much that can be said about them. (There are always going to be numbers that can match the constraints of any relations taken from both.)

If, on the other hand, the indices of both have a common factor, the two sets of constraints can (possibly) be used to cut down on the size of the relations.

Consider two rows with indices A and B which share a common factor K, where K is not equal to 1.

For each pair in each row, form the image of the pair as the pair mod the common factor. Remember which pair generated them.

Since each row describes all possible working pairs, and the images also describe all working pairs, any image appearing in one set and not the other can't belong to a possible working pair.

So... any pair with such an orphan image can be removed from the original row.

Example Data

For the example 187, with Fermat's relation, we get:

(X,Y, 2) = ({0,1}, {1,0})
(X,Y, 3) = ({0,1}, {0,2})
(X,Y, 4) = ({1,0}, {1,2}, {3,0}, {3,2})
(X,Y, 5) = ({2,1}, {2,4}, {3,1}, {3,4})
(X,Y, 6) = ({0,1}, {0,5}, {3,2}, {3,4})
...
(X,Y, 8) = ({1,2},{1,6},{3,2},{3,6},{5,2},{5,6},{7,2},{7,6})
(X,Y, 9) = ({0,4}, {0,5}, {3,4}, {3,5}, {6,4}, {6,5})
(X,Y,10) = ({2,1}, {2,9}, {3,4}, {3,6}, {7,4}, {7,6}, {9,4}, {9,6})
...
(X,Y,12) = ({3,2},{3,4},{3,8},{3,10},{9,2},{9,4},{9,8},{9,10})
...
(X,Y,15) = ({3,1}, {3,4}, {3,11}, {3,14}, {12,1}, {12,4}, {12,11}, {12,14})

Back Elimination Example

In the 187 example, we can pick rows 2 and four.

Picking rows 2 and 4.  K = 2.
(X,Y,2) = ({0,1} -> [0 mod 2, 1 mod 2], {1, 0} -> [1 mod 2, 0 mod 2])
which reduces to 
(X,Y,2) = ({0,1} -> [0,1], {1,0} -> [1,0])
and row 4 is
(X,Y,4) = ({1,0} -> [1,0], {1,2} -> [1,0], {3,0} -> [1,0], {3,2} => [1,0])

Note that the image [0,1] in row 2 never appears in row 4's images.

Since row four covers all possible solutions, and doesn't have the [0,1] image, then the [0,1] can't possibly be a solution in row 2 either.

So, row two is now: (X,Y, 2) = ({1,0})

Forward elimination Example

Consider the (new) row 2 and row 6, K=2...

(X,Y, 2) = ({1,0} -> [1,0])
(X,Y, 6) = ({0,1} -> [0,1], {0,5} -> [0,1], {3,2} -> [1,0], {3,4} -> [1,0] )

Since [0,1] doesn't appear in 2, but doesn't appear in 6, it can't really be an example for 6 either.

So the new 6 is (X, Y, 6) = ({3,2}, {3,4})

More examples

Rehash of new table.

(X,Y, 2) = ({1,0})
(X,Y, 3) = ({0,1}, {0,2})
(X,Y, 4) = ({1,0}, {1,2}, {3,0}, {3,2})
(X,Y, 5) = ({2,1}, {2,4}, {3,1}, {3,4})
(X,Y, 6) = ({3,2}, {3,4})
...
(X,Y, 8) = ({1,2},{1,6},{3,2},{3,6},{5,2},{5,6},{7,2},{7,6})
(X,Y, 9) = ({0,4}, {0,5}, {3,4}, {3,5}, {6,4}, {6,5})
(X,Y,10) = ({2,1}, {2,9}, {3,4}, {3,6}, {7,4}, {7,6}, {9,4}, {9,6})
...
(X,Y,12) = ({3,2},{3,4},{3,8},{3,10},{9,2},{9,4},{9,8},{9,10})
...
(X,Y,15) = ({3,1}, {3,4}, {3,11}, {3,14}, {12,1}, {12,4}, {12,11}, {12,14})

Using rows 4 and 8 (K=4) we get images of

4 = ([1,0], [1,2], [3,0], [3,2]) 
  and
8 = ([1,2], [1,2], [3,2], [3,2], [1,2], [1, 2], [3,2], [3,2]

The images [1,0], and [3,0] never appear in 8, so are not valid solutions for 4 either.

So the new 4 is (X,Y, 4) = ({1,2}, {3,2})

Using the new row 4, and the row 12 we get:

 4 = ([1,2], [3,2])
12 = ([3,2], [3,0], [3,0], [3,2], [1,2], [1,0], [1,0], [1,2])

Since no terms [1,0] or [3,0] exist in row 4, they can't reasonably be expected to be real solutions to row 12 either.

So the new row 12 is: (X,Y,12) = ({3,2},{3,10},{9,2},{9,10})

Comparing row 5 with row 10, we get a new row 10 of (X,Y,10) = ({2,1}, {2,9}, {3,4}, {3,6}, {7,4}, {7,6})

Comparing the new row 2 with row 10 gives a new row 10 of (X,Y,10) = ({3,4}, {3,6}, {7,4}, {7,6})

Comparing row 10 and row 15

   (X,Y,15) = ({3,1}, {3,4}, {3,11}, {3,14}, {12,1}, {12,4}, {12,11}, {12,14})
               [3,1]  [3,4]  [3,1]   [3,4]   [2,1]   [2,4]   [2,1]    [2,4]
   (X,Y,10) = ({3,4}, {3,6}, {7,4}, {7,6})
               [3,4]  [3,1]  [2,4]  [2,1]

As you can see above, not everything reduces.

But we have made some progress... as we can see comparing old and new.

(X,Y, 2) = ({0,1}, {1,0})
(X,Y, 2) = (       {1,0})

(X,Y, 3) = ({0,1}, {0,2})
(X,Y, 3) = ({0,1}, {0,2})

(X,Y, 4) = ({1,0}, {1,2}, {3,0}, {3,2})
(X,Y, 4) = (       {1,2},        {3,2})

(X,Y, 5) = ({2,1}, {2,4}, {3,1}, {3,4})
(X,Y, 5) = ({2,1}, {2,4}, {3,1}, {3,4})

(X,Y, 6) = ({0,1}, {0,5}, {3,2}, {3,4})
(X,Y, 6) = (              {3,2}, {3,4})

...

(X,Y, 8) = ({1,2},{1,6},{3,2},{3,6},{5,2},{5,6},{7,2},{7,6})
(X,Y, 8) = ({1,2},{1,6},{3,2},{3,6},{5,2},{5,6},{7,2},{7,6})

(X,Y, 9) = ({0,4}, {0,5}, {3,4}, {3,5}, {6,4}, {6,5})
(X,Y, 9) = ({0,4}, {0,5}, {3,4}, {3,5}, {6,4}, {6,5})

(X,Y,10) = ({2,1}, {2,9}, {3,4}, {3,6}, {7,4}, {7,6}, {9,4}, {9,6})
(X,Y,10) = (              {3,4}, {3,6}, {7,4}, {7,6}              )

...

(X,Y,12) = ({3,2},{3,4},{3,8},{3,10},{9,2},{9,4},{9,8},{9,10})
(X,Y,12) = ({3,2},            {3,10},{9,2},            {9,10})

...

(X,Y,15) = ({3,1}, {3,4}, {3,11}, {3,14}, {12,1}, {12,4}, {12,11}, {12,14})
(X,Y,15) = ({3,1}, {3,4}, {3,11}, {3,14}, {12,1}, {12,4}, {12,11}, {12,14})

But we have made some progress.

Summary

The amount of progress one can make depends on both N and the relation one is using. For example, when applied to Fermat's method it only reduces even numbers (although some reduce quite far).

If one can limit choices before applying this method then many more reductions are usually possible.

This can't be used as a factoring method on its own, but can be used with some methods to usefully reduce the search space.


Go to ...


This page is:  http://www.cc.utah.edu/~nahaj/factoring/constrain.html
© Copyright 2001 by John Halleck, All Rights Reserved.
This page was last modified on January 18th, 2001