Re: I was right, surrogate factoring proof

From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/13/05 

Date: Sun, 13 Feb 2005 19:20:33 -0200

jstevh@msn.com wrote:
> <snip>
>
> 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.

As promised, here's my implementation in PARI/GP, which as you may know you
can download from http://pari.math.u-bordeaux.fr:

jsh(M,j) =
{
  T = M^2 - j^2;
  fordiv(M-j,Mmj,
    fordiv(M+j,Mpj,
      fordiv(j^2,myf1,
        f1 = myf1*Mmj*Mpj;
        f2 = T*j^2/f1;
        Ax1 = (f1 - f2) + 2*j^2;
        Ax2 = (f2 - f1) + 2*j^2;
        write("results","\nf1 = "f1"\nf2 = "f2);
        write("results","Ax1 = "Ax1"\ngcd(Ax1,M) = "gcd(Ax1,M));
        write("results","Ax2 = "Ax2"\ngcd(Ax2,M) = "gcd(Ax2,M));
      );
    );
  );
}

If M + j and M - j are easily factorable (say, they're either prime, or
divisible by small primes except for a single large prime), then this
should run very quickly. The reason I do three nested fordiv calls is
because although we know the factorization of M + j and M - j, the
factorization of T = (M + j)(M - j) is generally very difficult without
this knowledge, since it has at least 2 large prime factors.

Anyway, by running this, a file will be created in your working directory
named `results'. This file will contain, for each combination of f1 and f2,
a printout of f1, f2, (f1 - f2) + 2j^2, (f2 - f1) + 2j^2 and the gcds of
the Ax's with M. Using M = RSA2048, j = 1232424, all gcds are either 1 or
RSA2048 itself (in which case Ax was equal to RSA2048^2.)

You are advised to explain why your method failed to produce nontrivial
factors in this case, before claiming again that

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

Décio

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)
Quantcast