Talking Rationally About Surrogate Factoring

From: Proginoskes (proginoskes_at_email.msn.com)
Date: 04/17/05 

Date: 17 Apr 2005 01:23:12 -0700

As a lot of you probably know, James Harris has been talking a lot
about "surrogate factoring", an idea he has been looking at. However,
lacking the proper mathematical training (something he admits himself),
he is quite often unable to express his ideas clearly, and will
sometimes fall into traps involving infinity. I have also mentioned a
discovery (called "The Key") which could justify surrogate factoring by
providing a quick algorithm, if the Key exists. So I decided to start
this thread to answer the questions: What is Surrogate Factoring? Is
there anything in it which can be salvaged?

     (I) Preliminaries

First of all, we will start off with the factoring problem, as known to
the entire world:

PROBLEM 1: Given an integer N, factor N into the product of prime
numbers.

There is a variation of this problem, for the "RSA numbers" which is:

PROBLEM 2: Given an integer M which is the product of two (distinct)
prime numbers, find the two prime factors of M.

These problems as usually stated involve integers. James Harris
wondered about whether rational numbers could be used instead of
integers.

Now, any non-zero rational number r is a factor of an integer N in the
ring of rationals, so he wants to make a differentiation between
"trivial" rational factors (which act like the integer 1, M), and
"non-trivial" rational factors (which act like the proper divisors of
M). I have formalized the definition the following way:

DEFINITION. A non-zero rational number r = a/b (written in lowest
terms) is a non-trivial rational factor of M if a is not divisible by
M, but gcd(a,M) > 1.

Example: 5/3 is a non-trivial rational factor of N = 10, since
gcd(5,10) > 1, and 5 is not divisible by 10. 10/3 is a trivial rational
factor of 10, since 10 (the numerator of 10/3) is divisible by N.

This seems to be the definition that Harris uses; he may also insist
that no power of a prime divisor of M divides evenly into a, or he may
include the denominator in the definition, but the current definition
seems to be the simplest and most promising.

With this definition, the problem that Harris has been investigating
is:

PROBLEM 3. Given an integer M which factors into two prime numbers,
find a non-trivial rational divisor of M.

     (II) Equivalency

THEOREM. Problems 1 and 3 are equivalent; Problem 1 gives a solution to
Problem 3, and vice versa.

Proof: Clearly a positive integer divisor of M other than 1 or M is a
non-trivial divisor of M, so Problem 1, when solved, solves Problem 3.
Now, if r = a/b is a solution to Problem 3, then a is not a multiple of
M and gcd(a,M) > 1. But gcd(a,M) can only be 1, p, q, or M (where M = p
q), and it can't be 1 (by assumption) or M (since M divides into M).
Thus gcd(a,M) is a prime number which divides into M, and M / gcd(a,M)
is the other. This solves Problem 1.

     (III) The Surrogate Factoring Theorem.

The Surrogate Factoring Theorem (SF Theorem, for short) in formal
mathematical form reads as follows:

SF THEOREM. Suppose the following are true:
(1) yz^2 - Az + j^2 = 0;
(2) yx^2 - Ax + M^2 = 0;
(3) T = M^2 - j^2;
(4) k_1 k_2 = -Tj^2;
(5) b_1 b_2 = M^2; and
(6) f_1 f_2 = T.
Then
(7) b_2 f_1 = (-(Az - 2M^2)+/- sqrt((Az - 2M^2)^2 - 4TM^2))/2, where
(8) Az = Ax(Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2Ax - 2M^2) and
(9) Ax = +/- (k_1 + k_2) + 2j^2.

Period. In other words, given M, j, f_1, and k_1, he can find a factor
b_2 of M.

Now, the usual objections to this Theorem are:
(1) There may be more than one b_2. (In fact, there can be 8.)
(2) Az or b_2 might be irrational.
(3) The proof is just manipulation.

But what he's done here is to set up a function, mapping j, a factor of
T, and a factor of Tj^2, to a factor of M. In other words, he's found a
"function" f_M such that
f_M (j, f_1, k_1) = b_2.

He claims that the SF Theorem does not distinguish trivial factors from
non-trivial factors; this is true, especially when one considers the
fact that in the formal version, the words "rational", "trivial", and
"non-trivial" do not appear. He seems proud of this, in spite of the
fact that differentiating between trivial and non-trivial factors could
make Surrogate Factoring a viable possibility.

     (IV) The Key

This is where I entered the picture. I was being a "usual sci.math'er",
reading posts, posting useful responses (to threads other than JSH's),
when I realized what the phrase "surrogate factoring" meant. It meant
that, by factoring a number T, you could possibly factor M, based on
the function f_M above. But in order to guarantee that the resulting
factors were non-trivial (and rational), I realized that another
theorem -- a true theorem -- was needed. This theorem I called the Key.

I am not convinced the Key exists; in fact, after looking at the
problem, I doubt its existence. However, someone may want to take up
the search for it.

The Key is as follows:

THEOREM (THE KEY): Suppose M is the product of two prime numbers. Then
there is a rational number T, which is computable in poly-time, such
that: there is a map f_M from the rationals to the rationals, such that
the following holds: f_M(r) is a non-trivial rational factor of M if r
is an element of (some finite set).

Or maybe it's of the form:

THEOREM (ANOTHER KEY): Suppose M is the product of two prime numbers.
Then there is a rational number T, which is computable in poly-time,
such that: there is a map f_M from the rationals to the rationals, such
that the following holds: f_M(r) is a non-trivial rational factor of M
if (some condition on r requiring time bounded by p(ln(M)), where p is
a polynomial).

The Key would be a godsend to factoring. All you have to do is to set
up a map, plug in a value for r, and out comes a non-trivial factor!
The second version ("Another Key") would be more realistic; there would
be a list of possibilities, one of which would work by the fact that
the theorem can be proved.

     (V) Further Research

I tried looking at what f_1 was as a function of just M, j, b_1, and
k_1, trying to determine when it was 1 or M, but the process got messy.
Hence, I've abandoned search for The Key, but offer two possibilities:

First, in The Key, maybe we could take T = 3 * 5, the smallest integer
which is the product of two distinct odd primes, a "prototype" for
numbers like M.

Second, maybe to find the non-trivial factors of M, we have to know
about the factorization of another number T = g(M). Harris has talked
about "recursion", but this can be avoided if there is a theorem like
The Key or Another Key where T < M/2. If this is so, then the number of
recursions is ln(M), and if each step can be done in poly-time, then
the whole process can be done in poly-time, with degree one bigger.

This last issue reminds me of a private e-mail that I received, asking
about whether the calculations themselves might require time
exponential in ln(M). This doesn't seem likely; the only example I can
think of right off is of Gaussian elimination, where results of
previous row operations determine further operations. The result of the
n^3 operations on a 0-1 matrix is that one entry in the matrix has a
denominator whose size is exponential in n, the size of the matrix.
Harris's formulas don't look like this; there only seem to be a bounded
number of them, no matter how big M is.

     (V) Finale

This has been a long post! Hopefully, I have managed to capture the
idea that Harris has been working with, as well as a path towards
solving the factoring problem. If this can be done, then Surrogate
Factoring will no longer be considered the "cargo cult" that one person
called it.

     --- Christopher Heckman

Relevant Pages

  • SF: Areas of confusion, infinity
    ... One of the problems with surrogate factoring in terms of understanding ... it, is that it utilizes infinite sets, notably the set of rationals. ... Well, the surrogate factoring theorem links rational factorizations, ... The mathematics then gives you factors in exchange. ...
    (sci.crypt)
  • Re: SF: Areas of confusion, infinity
    ... One of the problems with surrogate factoring in terms of understanding ... it, is that it utilizes infinite sets, notably the set of rationals. ... Well, the surrogate factoring theorem links rational factorizations, ... The mathematics then gives you factors in exchange. ...
    (sci.crypt)
  • Re: SF: Areas of confusion, infinity
    ... > notably the set of rationals. ... choosing any integer is the same as the probability of any other ... That's what make the factoring problem interesting, i.e., not ... > is naive with the surrogate factoring theorem. ...
    (sci.crypt)
  • Re: Factoring, SF, and transforms
    ... Why not call the transform the "Surrogate Factoring Transform" instead? ... > rationals every number but 0 is a factor of every other ... > That's the power of training and education to block ...
    (sci.crypt)
  • Re: Strategy with "Uncle Al"
    ... Oh Christ - next he'll be using surrogate factoring to determine the prime ... factorization of a particle of spin 1. ... Harris is the brand name of a very popular acetylene torch. ...
    (sci.physics)