# 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

**N** is the number to factor.
**S** is the integer square root of the **N**.
**R** is the square root's remainder.
(**N = S*S + R**)
**X** is an (arbitrary) variable.
**C** is the integer cube root of **N**
**F** is the cube root's remainder.
(**N = C*C*C + F**)

## 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:

- Given:
**(S-X)**2 + R (mod X)**
- Expanding out:
**S*S - 2*S*X + X*X + R (mod X)**
- X mod X = 0:
**S*S + R (mod X)**
- And we know that
**S*S + R == N** by definition.

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**.

**S*S - 2*S*X + X*X + R = G*X**
**X*X - (2*S + G)*X + S*S + R = 0**
**X = (2*S + G + SQRT(4*S*S+4*S*G+G*G-4*S*S-4*R)))/2**
**X = (2*S + G + SQRT(4*S*G + G*G - 4*R)))/2**

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