Re: JSH: Nearly done

From: *** T. Winter (***.Winter_at_cwi.nl)
Date: 01/25/05 

Date: Tue, 25 Jan 2005 01:29:24 GMT

In article <1106584902.512209.138010@f14g2000cwb.googlegroups.com> "Nora Baron" <norabaron@hotmail.com> writes:
...
> 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.

As Rick Decker already noticed, it is T = M^2 - j^2 (and I think this
confused some people...)

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

I think this is true.

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

While T may will probably have some small factors, as James noted, you need
a complete factorisation of T because most splits will not result in a
factorisation of M. But as T is much larger than M, it is likely that
you will end up with a number larger than M that does not contain small
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.

Contrary what somebody else said, it is neither equivalent to Format,
nor to the quadratic sieve or number field sieve methods. All three
attempt to find two numbers p and q such that p^2 = q^2 mod M (with
Fermat actually p^2 - q^2 = M). They differ only in the way they search.
Fermat simply starts with p = ceil(sqrt(M)), and calculates q as
floor(sqrt(p^2 - M)), when this is not a solution, p is increased.
The quadratic sieve method calculates numbers n, such that n^2 mod M is
easily factored in a (predefined) set of primes. Once you have sufficient
such relations (and you know beforehand how many you need), you can come
up with a final relation p^2 = q^2 mod M, and have (probably) factored
the number. The only problem is that p+q or p-q might be divisible by M,
but if M has only 2 factors, that probability is only 1/2. The number
field sieve attempts something similar, but in some quadratic field.
Neither of these is similar to the given method, which attempts to
factor a number M^2 - j^2, for some j.

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

There are other methods that attempt a factoring by first factoring another
number. The p-1 method is one. The major difference is that in James'
method the number to be factored is *larger* than the original number.

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

Most current other methods do work always. The only limits are memory and
time. E.g. in the number field sieve you will end up with a Gaussian
elimination of a *huge* matrix over GF(2). But given enough memory and
time, the method will succeed.

> I don't think it is guaranteed to work at all in all cases.

And this is one of the problems. It is an inefficient method that will
work in some of the cases. Preliminary timings by me shows that where
it works, simple trial division methods outperform it by a huge margin,
and they always do succeed.

One other unsupported claim by James:

> > So must x reveal a non-trivial factor of M?
> >
> > The answer, amazingly enough, depends on quadratic residues!!!

There is *no* reason to suspect this is indeed true, at least I do
not know what this means. 

-- 
*** t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~***/
Quantcast