Re: Surrogate factoring, state of the art

From: Tim Peters (tim.one_at_comcast.net)
Date: 02/15/05 

Date: Tue, 15 Feb 2005 13:15:27 -0500

[David Kastrup]
> IIRC, 15 was the first number for which it failed. That's not really
> terribly large.

No, the latest method finds a factor of 15 regardless of which j (in 1..14)
is chosen. Here are the number of times gcd() is called at each j value if
you don't stop when you find a winner, and the number of those that return 3
or 5 (the rest return 1 or 15):

    at M=15
 j gcds winners
-- ---- -------
 1 12 5
 2 12 5
 3 24 14
 4 20 10
 5 20 10
 6 36 21
 7 30 15
 8 28 15
 9 36 23
10 18 9
11 24 12
12 36 23
13 24 12
14 18 8

There's actually no 2-digit odd composite that isn't a square of a prime
where some j fails. The smallest such failures (all odd non-prime-squared
composites M < 1004 factor for all j in 1..M-1 not listed in this table):

   M j
 --- --
 221 2
 319 2
 391 2
 451 2
 551 3
 589 2
 667 6
 671 2
 689 2
 713 4
 851 2
 893 1
 899 898
 943 4
 943 386
 943 939
 949 2
1003 1

But a conclusion that this just can't be due to luck isn't justified -- a
lot of gcds are tried, and factoring by looking at gcd(M, k) for random
integers k is in fact extremely effective for composite M this small.

When the number of distinct Tj^2 splittings (= half the number of gcds
tried) gets small compared to p+q (for a composite M=p*q with p and q both
prime), it becomes increasingly difficult to find a j that _works_. For
example, at M=988027 = 991 * 997, j=1 fails, j=2 fails, j=3 fails, j=4
fails, and then we get the first winner at j=5. But we try 128 (at j=1) +
216 (at j=2) + 240 (at j=3) + 160 (at j=4) gcds without winning first, and
744 gcds is bigger than the ~500 gcds picking candidates purely at random
would be expected to take for this M. At j=5, it tries 864 more gcds, and
gets one that works. It doesn't seem like a miracle if you know how
effective poking at random is for small M (and although this 988027 is
already in some trouble, it's tiny compared to RSA-class composites).

Relevant Pages

  • Re: Proof factoring solution is closed form
    ... In an RSA-class composite, M is so large compared to p+q this is ... JSH) has reported details about so far, the probability of factoring by pure ... rather than # of gcds, poking at random would have been _much_ more ... In other words, in this special case, the method succeeds at exactly the ...
    (sci.math)
  • Re: Proof factoring solution is closed form
    ... In an RSA-class composite, M is so large compared to p+q this is ... JSH) has reported details about so far, the probability of factoring by pure ... rather than # of gcds, poking at random would have been _much_ more ... In other words, in this special case, the method succeeds at exactly the ...
    (sci.crypt)
  • Re: Surrogate factoring, state of the art
    ... There's actually no 2-digit odd composite that isn't a square of a prime ... lot of gcds are tried, and factoring by looking at gcdfor random ...
    (sci.math)