Re: JSH: Nearly done

From: Nora Baron (norabaron_at_hotmail.com)
Date: 01/24/05 

Date: 24 Jan 2005 08:41:42 -0800

jstevh@msn.com wrote:
> There has been a lot of verbiage flying back and forth related to my
> theory and method for factoring that I call surrogate factoring.
>
> The mathematics though is surprisingly simple, while checking it
> thoroughly can test you to your limits. It's some of the best kind
of
> mathematics to consider as elementary methods are shown to show
> surprising results never conceived of before.
>
> At the heart of the theory are two simple quadratics:
>
> yx^2 + Ax - j^2 = T
>
> and
>
> yz^2 + Az - j^2 = 0,
>
> where all are to be rational, while A, j and T are also integers.
>
> The primary question is, do rational non-zero x, y, z exist?
>
> So what does that have to do with factoring?
>
> Well j and T are chosen such that M^2 = j^2 + T, where M is the
number
> you're trying to factor, and that means that from the first equation
> you have
>
> x(yx + A) = M^2
>
> so x is a factor of M, but it can be a fraction, so you concentrate
on
> its numerator to see if that gives a prime factor of M.
>
> So why M^2 and not M? Well that's where the theory starts pushing
you,
> as I tried M, and found out that mathematically it didn't give me
> something I could work with easily, but M^2 did.
>
> If you let b_1 b_2 = -j^2, and f_1 f_2 = T, it is easy to prove that
>
> x = (b_1 f_2 + b_2 f_1 - 2j^2)/A
>
> meaning that x is defined by the factors of j^2 and T, though it is a
> factor of M^2, which is why this is surrogate factoring. The
> surrogates are factored to try and factor M.
>

I will take the liberty to describe what Harris is doing
in a different, but I think equivalent way.

The number he wants to factor is M. In meaningful applications,
M is large and does not have any small factors. The underlying
idea is to find related numbers which more probably do have
small factors.

Harris lets T = M^2 + j^2, where he will choose trial numbers j
which are relatively small integers. He factors j^2 as j^2 = b*d,
presumably nontrivial factors.

Harris considers the quadratic in x,

(a x + b)*(c x + d) = T = M^2 + j^2 = M^2 + bd.

Now Harris tries factoring T. Unlike M, T is more likely to have
one or more small factors. Why? Because in RSA applications,
M is specifically constructed to have only large factors; T is
not. Suppose you finds a small factor f and another factor g = T/f
of T by, say, trial division. Thus you let

a x + b = f

c x + d = g.

Together with the equation above, this implies also

ac x^2 + (ad + bc)x = M^2.

At this point, M, b, d, f, and g are known. a, c,
and x are unknown. Three equations, three unknowns: you
should be able to find solutions. However, you want to end
up with *integer* factors of M. That is why Harris is looking
for *rational* a, c, and x.

Note that the key thing from the last equation is that x is a
factor of M^2, i.e.,

x * (ac x + ad + bc) = M^2.

Thus the process does have some chance of finding a factor of M.
If x is rational, at least prime factors of the numerator may be
factors of M.

Now some Q & A:

Q1. Is this guaranteed to work as a way of finding factors?

A1 Not as far as I can tell. You need to find a, c, and x that
are rational. I don't see a way that that can be guaranteed.
Second, x needs to be a nontrivial factor, i.e., not 1 or -1
or M or -M.

Q2. Will it work in polynomial time?

A2. Dunno. There are several steps affecting computing time.
First, the size of the factors of T. Second, finding rational
a, c, and x. I don't see any justification for Harris's
claim that it will work in polynomial time. Plus, even if it
did, it might not be worth doing if the polynomial has
degree 10000.

The best indication regarding its asymptotic efficiency would
come from examples of factorizations of large numbers with large
prime factors.

Q3, Is it a new method?

A3. I am by no means an expert in this area - not at all! So far
as I can tell it is not equivalent to Fermat's method or
Kraitchik's. Whether it might be related to Brillhart's
continued fraction method or quadratic sieve methods or
number field sieve methods, I don't know. I suspect it is new.
I don't see it as having much of a theoretical underpinning -
just a little low-level algebra. But if it is new, it
might provide some advance in factoring certain numbers.

Q4. Is it a breakthrough of world-shattering importance?

A4. I doubt it. Some other people with programming skills
should try implementing it and see how it performs.
Using a recursive algorithm as Harris has done may
provide terse code, but it may also make it very hard
to tell what is actually happening.

> It's a brilliant idea. No matter what any poster says in reply, what
> I've already shown is simply brilliant, as I have x, a factor of M,
> defined by factors of numbers other than M, and that is the start.
>

It's not brilliant, but it might work in cases where other
methods don't. It may not be competitive in terms of speed.
I don't think it is guaranteed to work at all in all cases.

> The first problem you face is that b_1, b_2, f_1 and f_2 may not be
> integers, but are in the field of rationals.
>
> My paper goes over methods that put f_1 and f_2 into integers, while
> allowing the mathematics to *choose* b_1 and b_2 so that they are
still
> in the field of rationals, but you get the mathematics selecting them
> out of infinity.
>
> Yup, that's why I call it a super sieve, as in picking b_1 and b_2
for
> you, the algebra checks against all rationals, the entire set, and
> that's an infinite set!
>
> Now we are beyond brilliant into the arena of almost impossible to
> imagine, with a technique for factoring, which loops through the
entire
> field of rationals in searching for a solution.
>

We are very definitely not yet beyond brilliant. As for "looping
through the entire field of rationals", nonsense. Harris is dealing
with a simple system of three equations which can be solved in
closed form. Sometimes the solutions will be rational. The
hyperbole here is really pretty revolting. I have never seen a
serious mathematician brag like this about something that might not
even work.

> So must x reveal a non-trivial factor of M?
>
> The answer, amazingly enough, depends on quadratic residues!!!
>
> The mathematics requires only elementary methods, but in the space of
a
> few paragraphs I've talked about looking for a prime factor of some
> target M, where the answer depends on the factorization of numbers
> other than M, and you pick one of those numbers, while letting the
> algebra factor the other, going through the entire field of rationals
> to pick a solution!
>
> All of that is easy to prove, and not only did I prove it in a paper,
I
> wrote a program that does it.
>
> See http://groups.yahoo.com/group/sufactor/
>

Certainly the program proves nothing, since Harris himself has
said that it only works about 50% of the time on small numbers,
and the few speeds he has quoted are not at all impressive.

I am deleting the rest here, which is mainly unsupported and
rather offensive counting-chickens-before-they-are-hatched
bragging and unjustified abuse of 'the mathematical establish-
ment'.

  Nora B.

[deleted]