Re: Proof factoring solution is closed form

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

Date: 11 Feb 2005 17:55:21 -0800

Décio Luiz Gazzoni Filho wrote:
> Nora Baron wrote:
>
> > Tim Peters wrote:
> > <snip>
> >
> >> Pick any odd j, 0 < j < M, and both halves are even, and the
largest
> >> remaining piece (after dividing out 2s) is smaller than M. Pick
an
> > even j
> >> s.t. M+j and M-j are both prime (a strong argument was made by
Décio
> > Luiz
> >> Gazzoni Filho that this can probably be done efficiently),
> >>
> >
> > I would think so, with an efficient prime-testing routine.
> >
>
> It goes beyond just having an efficient prime-testing routine. You
need to
> bound the interval where a prime would be found. I have reason to
believe
> that on average, an interval of size ~0.6 log^2 M around M has a pair
M + j
> and M - j such that both are prime. The reasoning is laid out in
> http://groups.yahoo.com/group/primenumbers/message/16075.
>
> So it doesn't matter whether you PRP-test using an O(log^3 M)
routine, or
> whether you certify it with fastECPP at O(log^5 M), or whatever. The
point
> is, you have to sift through at most O(log^2 M) candidates, and apply
a
> test which is itself polynomial time in each of them. So the reason
that
> one can find primes efficiently has much more to do with the primes
> themselves than with your primality test.
>
> > <snip>
> >
> >> [...]
> >> > Two is the possibility that T has a great many small prime
factors.
> >> > In that case, the number of possible integer divisors of T could
be
> >> > very large, and searching through all of them might take as much
> >> > time as factoring M in the first place, and may not work anyway.
> >>
> >> "May not work anyway" is the rub, of course. I'm not sure exactly
> > which of
> >> JSH's methods you have in mind, but the one Rick wrote about
(which
> > is no
> >> longer the current one) definitely doesn't succeed for many <M, j>
> > pairs,
> >> and empirical evidence suggests it's harder to find a j that works
> > the
> >> larger M gets. Factoring by random trial gcd appears at least as
> > effective.
> >> JSH recently even seemed to agree that method doesn't always work.
> >>
> >
> > I don't think random trial division has much chance when you are
> > dealing with an RSA number, unless I am missing something.
>
> And since JSH's method appears to perform worse than trial division,
then
> neither does JSH's method. What's your point? Did you actually
believe for
> a second that his method might indeed factor an RSA challenge?
>

  I certainly do not claim expertise in this. My guess is that on
average Harris's method will do very badly. However if T has the
right distribution of prime factors, his method might get lucky.
Of course you could similarly argue that random trial division
could similarly get lucky.

> > <snip>
> >
> >> Not yet, but soon. Very soon. This time it's "easily
implemented"
> > (not
> >> sure what that means, since the algorithm Rick gave was in fact
very
> > easy to
> >> implement -- the only part that required any thought was
generating
> > all the
> >> unique splittings of -j^2*T's factors efficiently in all cases).
And
> > this
> >> time "the math is childishly simple" (not sure how that differs
from
> > the
> >> claim for the last one either).
> >>
> >
> > I do not discount the possibility that his idea might lead to
> > a quick factorization of some fraction of RSA numbers. However,
> > he has now let so much of the cat out of the bag that it may well
> > be someone else who gets there first - someone who can program
> > more efficiently and make use of shortcuts, etc.. If I were him
> > right now I would be very worried that I had said too much.
> >
> > Conceivably it can be shown that his scheme is a variant of trial
> > division and has no advantage over it. I don't see an obvious
> > proof of that, but it is possible. I would guess not.
>
> Tim Peters argued in another post that his method looks like adding a
> constant to two pseudo-random integers. I would go further and say
that all
> three of them are pseudo-random, since j is variable as well, and it
also
> behaves randomly -- you just pick the j that's easiest to factor M +
j and
> M - j, and there's nothing special about that.
>
> Tim's comment makes even more sense in light of Rick's assertion that
`if p
> is a prime dividing M, then g_1 + g_2 + 2j^2 = 0 mod p iff g_1 = g_2
= -j^2
> mod p^2.' I just don't see a reason why, except out of sheer luck,
that
> these conditions would be met.
>
> >
> >> [...]
> >>
> >> > You made a barbarically rude comment to Rick Decker. He has
> >> > been unfailingly polite and reasonsble and has done a far
> >> > better job than you have yourself of explaining what you are
> >> > trying to do. You pay him back with sheer meanness. You
> >> > should be ashamed, and you owe him an apology.
> >>
> >> 100% agreed on 100% of that.
> >
> > This too is a test. If someone else beats him to the factoring
> > punch and he is denied all the credit or at least the monetary
prize,
> > it will be partly because he is so incredibly spiteful.
>
> You speak as though there's the slightest chance that his method will
lead
> to anything.

  Certainly from what you say and what we have seen so far, it is a
long shot.

> I didn't follow sci.crypt at the time, but were you guys also
> pondering the consequences of The Neo Project figuring out a factor
of an
> RSA challenge?
>

  I haven't followed sci.crypt at all.

  Nora B.

> Décio

Relevant Pages

  • Re: Proof factoring solution is closed form
    ... It goes beyond just having an efficient prime-testing routine. ... I have reason to believe ... And since JSH's method appears to perform worse than trial division, ... a second that his method might indeed factor an RSA challenge? ...
    (sci.crypt)
  • Re: Proof factoring solution is closed form
    ... It goes beyond just having an efficient prime-testing routine. ... I have reason to believe ... And since JSH's method appears to perform worse than trial division, ... a second that his method might indeed factor an RSA challenge? ...
    (sci.math)
  • Re: JSH: Nearly done
    ... > My prototype program already does that to a certain extent, ... But unlike trial division that gives the correct result ... > potentially chew through even an RSA challenge type number in minutes. ... Define what polynomial time means to you. ...
    (sci.math)
  • Re: Easy test of surrogate factoring
    ... but the population of primes is much denser from 2 to the factor than ... > more practical than trial division for an RSA challenge. ... I was not wondering whether attacking a RSA ...
    (sci.crypt)
  • Re: JSH: Hyperbolic factoring method
    ... Was there a reason people ... Remember that if you post a factor of an RSA challenge number, nobody can ... Besides, if only you have The Answer, current investors and future ...
    (sci.crypt)