Re: Factoring problem, my assertion revisited

From: Nora Baron (norabaron_at_hotmail.com)
Date: 02/08/05 

Date: 8 Feb 2005 09:06:48 -0800

Rick Decker wrote:
> rupertmccallum@yahoo.com wrote:
>
> > jstevh@msn.com wrote:
> >
> >>Well I can at least give some idea why I figured I'd solved the
> >>factoring problem, and kept talking about theoretically, while my
> >>attempts at implementing the theory have so far failed to live up
to
> >>even my expectations:
> >>
> >>There are the two quadratics:
> >>
> >>yx^2 + Ax - M^2 = 0 [1]
> >>
> >>and
> >>
> >>yz^2 + Az - j^2 = 0 [2]
> >>
> >>where A, j, and M are integers greater than 0 chosen, where M is
the
> >>target to be factored, and that is done through factoring the
> >
> > surrogate
> >
> >>T, which is
> >>
> >>T = M^2 - j^2
> >>
> >>and substituting out y to solve for x and z gives
> >>
> >>x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)
> >>
> >>and
> >>
> >>z = x(-Ax +/- sqrt((Ax - 2j^2)^2 - 4Tj^2))/(2M^2 - 2Ax)
> >>
> >
> >
> > I'm sorry, I don't follow this step. Could you explain it in a bit
more
> > detail?
> >
> James is using y = (M^2 - Ax) / x^2 from what I've called [1], using
> that value in what I've called [2], and then looking at the result as
> a quadratic in z and solving it.
>
> > Also, could you tell me: when you say you think you've solved the
> > factoring problem, do you mean you think you've found an algorithm
> > which you can prove will factor an arbitrary positive integer in
> > polynomial time?
> >
> It almost surely won't, even in the cases where it finds a factor
> at all. In simple terms, James' method factors M by factoring
> -4(M^2 - j^2)j^2, a number which is almost certainly at least as
> hard to factor as M itself.
>

  I don't agree on this. In the applications of interest, M is
chosen to have two very large factors and no small factors. That
is what makes the factorization difficult. There is no reason to
think that M^2 - j^2 also has no small factors. There is a good
chance that it has several of them. "Most" numbers have more
small factors than RSA numbers do. Similarly for j itself.

  I have a different perspective on the whole problem here.
Harris's proposed method of factoring does not have to be
100% certain to be important. If he could factor even 1% of RSA
numbers in a reasonable amount of time, he would have added
significantly to the arsenal of code-cracking algorithms. People
using RSA cryptography could no longer assume that their encryption
schemes were safe. At a minimum RSA numbers would have to be chosen
which were 'Harris-resistant' - provided this can be defined in
some way other than just by running Harris's algorithm against M.
Harris need not prove that he can factor numbers in polynomial
time. All he has to do is show that he can factor some (small)
percent of RSA-type numbers M quickly. What he should be doing is
testing his program against some large RSA numbers, i.e., numbers
of 100 digits or more which are the product of two 50-digit primes.
If he can factor even 1 out of 100 such numbers quickly, his algorithm
is a threat to encryption. There may, however, still be theoretical
reasons that his algorithm probably cannot do this.

  Nora B.

>
> Regards,
>
> Rick

Relevant Pages