Re: Surrogate factoring, corrected algorithm

From: Bryan Olson (nameless_at_nowhere.org)
Date: 02/17/05 

Date: Thu, 17 Feb 2005 04:52:09 GMT

Tim Peters wrote:
> Sorry, it didn't work for me. I started this time with my running
example,
> M = 112554401 * 221667653 (I like that one because it's small enough so that
> the T's are easy to factor quickly by other simple methods, but its smallest
> factor is large enough that luck has scant chance of succeeding quickly).
>
> The two previous versions of this algorithm didn't factor that M at any j in
> 1 thru 623, but succeeded at j=624.
>
> This version didn't factor that M at any j in 1 thru 16, but did succeed
> once at j=17. In all, 62,320,128 gcds were tried through j=17, with 1
> success.
>
> j=17 was painfully expensive. Then T^3 j^2 =
>
> 2^9 3^6 5^3 7^3 11^3 17^2 191^3 7841^3 53633^3 56197^3
> 335417^3 14832053^3
>
> and so there are
>
> 10*7*4*4*4*3*4*4*4*4*4*4/2 = 27,525,120
>
> distinct ways to split T^3 j^2 as the product f_1 f_2 with f_1 and f_2 both
> integers >= 1, and without regard to order; and so twice as many as that =
> 55,050,240 gcds tried at j=17 alone. In comparison, all of j=1 through j=16
> computed a grand total of 7,269,888 gcds (with no success).

With the "corrected" algorithm's suggested j = floor(M/2) (+1 if even),
I get a mere 24960 gcd trials. None of them work.

> Of course the most troublesome bit is that factors still aren't found at
> some j, so at least one of {proof, algorithm, implementation} is wrong.

I never saw a proof of the claim that one of the GCD's must be a proper
factor of M.

> Implementation note: it's easiest to generate all <f_1, f_2> splittings
> without trying to weed out reversals. For example, if <3, 5> is generated,
> also generate <5, 3>. But then trying to weed out reversals later, by
> keeping track of the ones already seen, can require an enormous amount of
> memory,

How about requiring f_1 <= f_2? Just build f_1's and toss any
that get larger than the square-root of the product. 

-- 
--Bryan

Relevant Pages

  • Re: Surrogate factoring, corrected algorithm
    ... Tim Peters wrote: ... I get a mere 24960 gcd trials. ... > some j, so at least one of {proof, algorithm, implementation} is wrong. ... I never saw a proof of the claim that one of the GCD's must be a proper ...
    (sci.math)
  • Re: Library for Mocking
    ... One of the advantages of a recording mode for mocks is that you can give ... good algorithm and can check that the new algorithm exactly matches the ... because the recorder wont return the proper values). ...
    (comp.lang.ruby)
  • Re: Surrogate factoring, basic algorithm
    ... Tim Peters wrote: ... >> Well, to not be paranoid, I guess I may as well. ... of y are coprime to M, but x gives a single prime factor. ... I didn't want to complicate the algorithm, as in my opinion, that small ...
    (sci.crypt)
  • Thanks for the responces.. another question
    ... I see it uses either Rijndael, Twofish, ... or Blowfish. ... Any algorithm better than the other? ... Also what is a proper ...
    (sci.crypt)
  • Re: Flies in the ointment.
    ... "Tim Peters" wrote ... ... > Nothing wrong with the algorithm, but it's just a clumsily-stated direct ... written in the form of an *average* (shades of an "average tangent"?). ...
    (sci.math)