Re: misc/43192: games/factor takes forever on some large inputs

[David Holland <dholland-bugs%netbsd.org@localhost>]

The following reply was made to PR misc/43192; it has been noted by GNATS.

From: David Holland <dholland-bugs%netbsd.org@localhost>
To: gnats-bugs%NetBSD.org@localhost
Cc: 
Subject: Re: misc/43192: games/factor takes forever  on some large inputs
Date: Thu, 22 Apr 2010 17:32:46 +0000

 On Thu, Apr 22, 2010 at 02:30:01AM +0000, lhf%impa.br@localhost wrote:
  > While this works fine
  >         factor 123456789012345678901234567890
  >         123456789012345678901234567890: 2 3 3 3 5 7 13 31 37 211 241 2161 
3607 3803 2906161
  > 
  > this goes on forever:
  >         factor 1234567890123456789012345678901
  > (32 hours and no output yet)
  > 
  > Pollard p-1 seems to have a hard time with 
1234567890123456789012345678901...
 
 It looks to me like the code we have is a mixture of the Pollard p-1
 algorithm and the Pollard rho algorithm, and it appears to be, if not
 actually incorrect, at least suboptimal. Compare for example
 
 http://modular.math.washington.edu/edu/2007/spring/ent/ent-html/node81.html
 
 I am not sufficiently up on the finer points to want to try to correct
 it without putting in some time on the math, which is not likely to
 happen anytime soon.
 
 ISTM also, though, that we ought to identify values that are labeled
 prime based on statistical primality testing rather than on exhaustive
 (non-)factoring. The error rate is very small, but it's not zero, and
 the people running this program are nonspecialists who won't in
 general be already aware of this issue.
 
 -- 
 David A. Holland
 dholland%netbsd.org@localhost