Re: I was right, surrogate factoring proof

jstevh_at_msn.com
Date: 02/13/05 

Date: 13 Feb 2005 12:34:38 -0800

Décio Luiz Gazzoni Filho wrote:
> jstevh@msn.com wrote:
> > <snip>
> >
> > You made the claim that finding A is an issue, and I showed that it
is
> > not.
>
> No you didn't. I'm still waiting for a formal algorithm and/or a
worked
> example. Preferably both.
>
> > Actually, you find Ax and Az--integers--as can easily be seen from
the
> > square roots to be defined by the factorizations of Tj^2 and TM^2.
> >
> > I was answering your objection.
> >
> >>
> >> You should be able to, as it's so painfully obvious.
> >>
> >> Décio
> >
> > I just worked this out today, when it should have occurred to me
before
> > to just multiply both sides by A, but well, it didn't.
> >
> >>From the theory to an implementation that can handle really big
numbers
> > is, however, not trivial.
>
> No it's not, at least according to you. The only step of your method
that
> you've admitted to being difficult is finding the factorization of M
+ j
> and M - j. I provided an efficient algorithm to find that, and I went
> further, I gave an actual value of j that works for RSA-2048. If the
> remaining steps are trivial, why haven't you found the factorization
of
> RSA-2048 yet?
>
> Again, I'll go out of my way to try to help you. I'm somewhat
acquaintanced
> with number theoretical software, in which one could easily program a
> solution to the remaining steps of your method. If finding Ax and Az
is so
> painfully obvious, then you'll have no problem with stating it as a
formal
> algorithm. In exchange for that, I'll readily give you an efficient
> implementation which can handle `really big numbers.' Failure to
provide me
> with a formal algorithm will be interpreted as an admission that
finding
> the missing parameters is difficult (and rightly so.)
>
> Décio

Ok. An algorithm is easy.

Given an odd natural number M to be factored.

Select j. Simplest is to let j = floor(M/2).

If j is even, add 1.

Calculate T.

T = M^2 - j^2.

Factor T, and j.

Iterate through integer f_1 and f_2 such that f_1 f_2 = Tj^2.

For each f_1 and f_2 calculate Ax using

Ax = (f_1 - f_2) + 2j^2

and

Ax = (f_2 - f_1) + 2j^2

to handle plus or minus, and take the gcd of Ax with M.

The gcd of Ax with M will be a single prime factor of M, for at least
one set of f_1 and f_2.

James Harris

Relevant Pages

  • Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting Dik ...)
    ... the Fermat-Maas algorithm to prove it's really prime, ... the known factorization of p-1 that you got when you directly ... Back to the RSA page: ... So somebody buys 80 high-speed computers, ...
    (sci.math)
  • Re: Spectral Matrix Factorization via Wilson Method
    ... inner-outer factorization of a spectral density matrix, S, (where ... Factorization of Matricial Spectral Densities, ... algorithm does not quite converge on the correct solution. ...
    (comp.dsp)
  • Simple answer, surrogate factoring
    ... where M is the target to be factored, j is some non-zero natural ... Az is related to the factorization of T and M. ... So the full algorithm, which splits up A and x requires that you solve ... And then for at least one case, it must be true that the denominator ...
    (sci.math)
  • Simple answer, surrogate factoring
    ... where M is the target to be factored, j is some non-zero natural ... Az is related to the factorization of T and M. ... So the full algorithm, which splits up A and x requires that you solve ... And then for at least one case, it must be true that the denominator ...
    (sci.crypt)
  • Re: Surrogate factoring demonstrated
    ... > Will Twentyman wrote: ... >>or success wise? ... > Initial Factorization: ... be a sharp increase in factoring efficiency depending on what algorithm ...
    (sci.crypt)