Equivalent Function Factoring

The task of factoring an integer N can be looked at as the task of finding the values of X for which the function N mod X has the value of zero.

Unfortunately, N mod X doesn't have a lot of structure to exploit. Fortunately, there are other functions with structure that produce the same values.

Terminology Rehash

Constant Slope

[Under Construction]

[Geometric interpretation]

Parabolas

The function (S-X)**2 + R (mod X) has exactly the same zeros as the function N (mod X).

Proof:

So we know that the given Parabola, and the original function, must give the same results mod X.

What does this really mean?

(S-X)**2 + R must be equal to some multiple of X at any point where N mod X is going to be zero. So, for some g (S-X)**2 + R = gX (In general, not mod X)

This leads to a form for X in terms of g.

This form has lots of exploitable structure, and has a much reduced search space. Knowing that sub-expressions must be integer allows quite a bit of search space reduction.

In cases of interest (N odd, product of two primes) one can show that G is even. This reduces the expression to
X = S + G + SQRT(2*S*G + G*G - R)
Which you will find explicit in several other methods on these pages.

Cubic Curves

Using the same techniques as above, one can show that
(C-X)**3 + F (mod X)
also has the same zero's as N (mod X)

However the solution to the general cubic is extremely grim... (And I'm not going to bother to give it here.) It does have a lot of structure, and a number of constraints on the values that make intermediate results integer.

Higher order functions

With higher order functions, there is usually not any closed form for the solution. There are some tricks that can be used because of special structure of the problem. But it is uglier than I'm willing to put up with.

Equation Constraint Combination

[Under Construction]


Go to ...


This page is: http://www.cc.utah.edu/~nahaj/factoring/equivalent.html
This page was last modified on August 18th, 1998