Re: I was right, surrogate factoring proof

jstevh_at_msn.com
Date: 02/14/05 

Date: 13 Feb 2005 15:46:43 -0800

Tim Peters wrote:
> [ođin]
> >> Factor T and j? How do you do it and hop long dos it take? You
have not
> >> proved that it is easier than factoring M.
>
> [Décio Luiz Gazzoni Filho]
> > If every valid j is allowed (other than requiring j to be even, JSH
> > claims that any j will do),
>
> Sorry, JSH fooled you this time: the algorithm he posted actually
requires
> j to be odd:
>
> Select j. ...
>
> If j is even, add 1.
>
> So that destroys any method for finding M+j and M-j both prime, and
in
> particular nullifies your RSA2048 example (which used even j, as that

> approach must use).
>
> The smallest composite I found for which his new algorithm fails is
M=25
> with j=13 (the j he suggested using). But it does better than the
last
> method overall, presumably because it's trying twice as many gcd
candidates.
>
> If there's some reason for why squares "can't work", another small
example
> of failure is at M = 551 = 19*29 with j=3, where I get gcd=1 92 times
and
> gcd=551 4 times.
>

Oh yeah, it won't factor squares.

It's trivial to prove why, but I'll leave it as an exercise.

I'm more curious about the second.

James Harris

Relevant Pages

  • Re: Surrogate factoring, basic algorithm
    ... Tim Peters wrote: ... >> Well, to not be paranoid, I guess I may as well. ... of y are coprime to M, but x gives a single prime factor. ... I didn't want to complicate the algorithm, as in my opinion, that small ...
    (sci.crypt)
  • Re: Surrogate factoring, corrected algorithm
    ... Tim Peters wrote: ... I get a mere 24960 gcd trials. ... > some j, so at least one of {proof, algorithm, implementation} is wrong. ... I never saw a proof of the claim that one of the GCD's must be a proper ...
    (sci.math)
  • Re: Surrogate factoring, corrected algorithm
    ... Tim Peters wrote: ... I get a mere 24960 gcd trials. ... > some j, so at least one of {proof, algorithm, implementation} is wrong. ... I never saw a proof of the claim that one of the GCD's must be a proper ...
    (sci.crypt)
  • Re: Flies in the ointment.
    ... "Tim Peters" wrote ... ... > Nothing wrong with the algorithm, but it's just a clumsily-stated direct ... written in the form of an *average* (shades of an "average tangent"?). ...
    (sci.math)
  • Re: Not complicated, weird situation
    ... of squares in some way that involves factoring a number you get to ... This is a faaaaantastic algorithm. ... > better than 50% success rate, which is a claim you made but didn't ... > hard work, Harris' work broke into society with the help of Justin, ...
    (sci.crypt)
Quantcast