Re: Surrogate Factoring Solution

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

Date: Sun, 13 Mar 2005 00:02:13 -0500

[William Hughes]
> Indeed my predictions (I cannot speak for others)
> were based mostly on track record, but they were not quite mindless.

You don't need to defend yourself -- I'm not even writing down names for the
benefit of future prosecutors <wink>. The only thing I faulted your
predictions for were consistently overestimating(!) how long it would be
before the next iteration.

> All of James's algorithms were of the basic form:
>
> factor j^u T^v then play around a bit with these factors to
> generate nubers N_i, then calculate gcd(M,N_i) to look
> for a non-trivial factor of M. The number of N_i produced
> was at best a small factor times the number of ways of
> factoring j^u T^v.
>
> We knew (mostly due to your work) that this did not produce
> a large enough number of N_i to give a good chance of factoring
> even relatively small numbers. So whenever James came up with another
> variation on the same basic algorithm it was not much of a stretch
> to predict that his latest effort would fail. True, it could have
> been the case that some detail of the new algorithm would
> massively increase the number of N_i, or that the algorithm
> would succeed without a massive increase in the number of N_i
> (thus providing a practical way of factoring large numbers).
> I did not lose any sleep over these two possibilities.

You might have on the last one, but for a different reason <wink>: it
generated so many splittings _I_ lost a bit of sleep rewriting part of my
testing framework to make it fast enough to deliver statistically meaningful
results. Recall that it split over n^4 j^2, and n was itself M^4 - j^2:
n^4 could grow like M^16(!). n^4 j^2 was even worse. The number of splits
at M=15 was already pretty amazing:

Number of n^4 j^2 splits at M=15

    j splits
   -- ------
    1 1225
    2 225
    3 7125
    4 1125
    5 6175
    6 2625
    7 1875
    8 525
    9 3125
   10 375
   11 1425
   12 425
   13 3325
   14 75

As always, the fewer the splits, the less likely it was to work, and j=14
was the failing case there. Cases with 100,000 splits showed up already at
M=33, a million at <81, 51> (with 3,241,875 splits), and it hit 100 million
before reaching 500 (137,353,125 at <477, 237>).

I had earlier sketched a proof that no method of this general form could
work at all <M, j> pairs if it split over a power of T, but the key step in
that was cut off by splitting over powers of n and j instead.

A mildly interesting question still open is whether for every M=pq with p
and q prime, there exists a P such that

    1 < gcd(M, f-g) < M
    for some fg=P^6
    and P is the product of some initial segment of the primes

That's mildly interesting because the algorithm trying that for fixed
P=2*3*...*19 (regardless of M, and not bothering with a "j" concept) did
_almost_ best of all ever tried in tests of products of random 15- and
20-bit primes:

    nbits 15: 1000 of 1000 factored, 100%
    gcds: actual 5,189,019 expected random 11,939,687 no factor 0
    algorithm beat random-gcd 796 of 1000 factoring cases
    random - actual: min -24885
                     mean 6750.668
                     max 15573
                     median(s) [7785, 7793]

So that one was demonstrably better than random-gcd in terms of # of gcds
needed. The only one that did better was tweaking the same thing to use
Nora Baron's suggestion of computing gcd(f^2-g^2, M) instead:

    nbits 15: 1000 of 1000 factored, 100%
    gcds: actual 3,804,923 expected random 12,017,507 no factor 0
    algorithm beat random-gcd 892 of 1000 factoring cases
    random - actual: min -11524
                     mean 8212.584
                     max 15258
                     median(s) [8782, 8784]

But that was expected (trying f^2-g^2 does better than random-gcd even if f
and g are chosen at random, and for a pretty obvious reason), so I'm sorry
to say that no _really_ interesting mysteries came out of this.

Relevant Pages

  • Re: Surrogate Factoring Solution
    ... predictions for were consistently overestimatinghow long it would be ... > a large enough number of N_i to give a good chance of factoring ... > variation on the same basic algorithm it was not much of a stretch ... So that one was demonstrably better than random-gcd in terms of # of gcds ...
    (sci.math)
  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)