Re: SF: Back to theory

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

Date: Mon, 28 Feb 2005 22:00:49 -0500

[Tim Peters]
[...]
>> f and g are generated exactly the same way in the algorithms that try
>>
>> gcd(f-g, M)
>>
>> yet those do better than random when splitting T^6. For some still-
>> unknown reason, this way of generating f and g is better than random at
>> finding f and g in the same equivalence class mod p or mod q, and
>> despite that (as above) using f or g on its own is a provably miserable
>> way to look for a factor.

[same guy]
> Ah, I suspect this is going to be funny in the end <wink>. More later,
> after a long test run ends. Suffice it for now to say that this no
> longer looks surprising, it doesn't even look interesting -- and that
> there are more effective ways to generate winning f and g without
> bothering to factor anything.

OK, I killed the test run half-way thru -- the outcome is obvious. First
the algorithm tested: Given M=p*q, the product of two primes. Let p_i be a
0-indexed list of all primes, p_0=2, p_1=3, p_2=5, and so on.

1. Let S be the empty set.
2. for j=0, 1, 2, ...:
3. Add p_j to S.
4. Let T = the product of the primes in S.
5. if T**2 < M:
6. continue # skip the rest of this and advance to the next j
7. for all ways to express T**6 as the product f*g, where
               f and g are integers >= 1, and f >= g:
8. Let g = gcd(f-g, M).
9. if 1 < g < M:
10. return g

Lines 5+6 aren't essential. They're just trying to skip futile attempts
with teensy T, like T=2, T=2*3, and T=2*3*5. Following the intuition that
earlier algorithms were "really" obscured ways to come up with T having a
variety of prime factors, this one stuffs a variety of primes into T
directly.

I'm not going to say much more about it! Think about it, and in particular
try to guess how big j is likely to get when M is the product of 20-bit
primes. Everything will either be obvious or very surprising when you
ponder the test results:

    nbits 20: 561 of 561 factored, 100%
    gcds: actual 98,757,807 expected random 215,807,639 no factor 0
    algorithm beat random-gcd 456 of 561 factoring cases
    random - actual: min -1292661
                     mean 208644.976827
                     max 481993
                     median(s) [256748]

Smallest winning j; one '*' per 10 (or fraction thereof) cases

  7 *********************************************************

LOL! At the size of these products, lines 5 and 6 skipped the rest until
j=7, so that T was the product of the first 8 primes, T=2*3*...*19 = 9699690
(that's why there's no output for j < 7). It never had to add 23 to that
set too (that's why there's no output for j > 7 either): all products tried
factored for some f*g = 9699690^6.

Example:

M = 687389 * 592133 = 407025710737
T = 2*3*...*19 = 9699690
f = 91024295004372586106250 = 2* 3**3* 5**5* 7**4* 11**5* 13**6* 17**2
g = 9149340767991288480 = 2**5* 3**3* 5* 7**2* 11* 17**4* 19**6
check that f*g = T**6 yup
gcd(f-g, M) = 687389 bingo
gcds tried 19,259

Well, that was fun <wink>.

Relevant Pages

  • Re: Factoring problem and the SFT
    ... you and Nora _both_ lying to James about this, ... of 20-bit primes, and toward the end cut that to 15-bit primes as the ... algorithms got ever more expensive to try). ... The set of all integers divisible by 101 is infinite. ...
    (sci.math)
  • Re: SF: Back to theory
    ... >> f and g are generated exactly the same way in the algorithms that try ... Let T = the product of the primes in S. ... variety of prime factors, this one stuffs a variety of primes into T ... algorithm beat random-gcd 456 of 561 factoring cases ...
    (sci.crypt)
  • Re: Confusing performance results for prime
    ... > various data structures to cache primes and the like. ... > If you want to test primality quickly, using the sieve of erotosthenes ... > better is to use Miller-Rabin pseudoprimality tests (well, ... understand algorithms. ...
    (comp.lang.python)
  • Re: SF: Any other research out there?
    ... > couldn't afford to pay for the kinds of verification, ... You knowingly posted incorrect algorithms. ... Well, knowing the value of A is provably unimportant, and that doesn't ... even bigger primes depending on special circumstances. ...
    (sci.crypt)
  • Re: SF: Generalized SFTs
    ... I don't know if I can describe the feeling, ... He knows darned well too that his previous rounds of "proven correct" factoring algorithms were proved wrong by trying examples, ...
    (sci.math)