Re: Surrogate factoring, complete theory

From: Tim Peters (tim.one_at_comcast.net)
Date: 03/07/05 

Date: Sun, 6 Mar 2005 20:18:45 -0500

[JSH]
[...]
> and now multiplying the top by d_1, I have that
>
> T^2 j^2/(d_2 n - Tj^2)
>
> must include cases where n is given as you consider integers f_1 and
> f_2, such that
>
> f_1 f_2 = T^2 j^2, and take the gcd of
>
> f_1 + Tj^2
>
> with M, to get a prime factor.

Is this the algorithm?: Given odd composite M not the square of a prime (or
does the square-of-a-prime business not matter anymore?):

1. Pick an integer j with 0 < j < M. Maybe gcd(j, M)=1 is required too?

2. Let T = M^2 - j^2.

3. For each integer f (positive or negative) dividing T^2 j^2,
   compute g = gcd(f + Tj^2, M). Report that g is a factor if
   1 < g < M.

If so, the smallest counterexample is M=851 at j=2. The smallest
counterexample with odd j is M=1537 at j=1.

I'll just spell out the last one:

M = 1537 = 29 * 53
j = 1
T = M^2 - j^2 = 2362368 = 2^10 * 3 * 769
Tj^2 = T = 2362368
T^2 j^2 = T^2 = 2^20 * 3^2 * 769^2

There are 21*3*3*2 = 378 different integer f (the "*2" at the end was for
positive and negative) dividing T^2 j^2 then, and I won't show them here --
suffice it to say that gcd(f + 2362368, 1537) returns 1 for 366 of them, and
returns 1537 for the other 12.

Across 1000 products of two randomly chosen 15-bit primes (the success rate
with 20-bit primes was too low to justify burning the time), always using
j=1:

   nbits 15: 300 of 1000 factored, 30%
   gcds: actual 4,037,494 expected random 3,560,373 no factor 11,988,072
   algorithm beat random-gcd 141 of 300 factoring cases
   random - actual: min -81192
                    mean -1590.40333333
                    max 14875
                    median(s) [2644, 2668]

Relevant Pages

  • Re: Surrogate factoring, complete theory
    ... Is this the algorithm?: Given odd composite M not the square of a prime (or ... does the square-of-a-prime business not matter anymore?): ... the smallest counterexample is M=851 at j=2. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... This is a variation of my earlier counterexample: ... My counterexample graphs have D=2. ... > I have no counterexample to the lazy version of the algorithm, ... You've shown 2*ID iterations are not always sufficient. ...
    (sci.crypt)
  • Re: An algorithm with Minimum vertex cover without considering its performance
    ... thinking of as a counterexample to the OP's new broken algorithm is ... The OP's new algorithm, AIUI, would take ... random graphs to check if there are any violations: ... Randomly generate a graph; ...
    (comp.programming)
  • Re: A Definition of an Algorithm
    ... the algorithms be written explicitly as primitive recursive functions ... doesn't match the usually meaning of algorithm, ... for one algorithm (insertion sort, say) to be written in many different ... see whether there is a counterexample to Fermat's Last ...
    (sci.math)
  • Re: ------------------ Relat
    ... Let t be an odd composite. ... Then x= t-2, y = 2 gives ... a counterexample. ... What am I missing? ...
    (sci.math)