Hi, I've got an interesting bug report saying that
factor 158909489063877810457 is very slow (actually, I don't think it ever terminates). With below patch to gcd2_odd (the important part is checking if the <a1, a0> input is zero; deleting the unneeded handling of even <b1, b0> makes sense but is not essential), factor terminates instantly, $ ./src/factor 158909489063877810457 158909489063877810457: 3401347 3861211 12099721 Then there's another problem: It may happen that the first Pollard rho attempt fails and produces only a trivial factorization. In this case, factor (with the first fix applied) attemps to factor the number 1 and crashes. The other patch, by Torbjörn, fixes this problem. Input numbers of interest are 158909489063877810457 (above), 222087527029934481871 (same problem) and 12847291069740315094892340035 (second problem). I had a look at extending the test suite, but I gave up after spending at least half an hour trying to find out how to run individual tests (I had expected either ./tests/factor/t00.sh or make check TESTS=tests/factor/t00.sh to do the trick, possible after also setting RUN_VERY_EXPENSIVE_TESTS, but I couldn't get it to work). Best regards, /Niels commit e4a7c55cc585c07358c00bff42a6ebf65f73136d Author: Torbjörn Granlund <t...@gmplib.org> Date: Wed Dec 7 21:01:03 2016 +0100 factor: Retry properly if Pollard rho gives a trivial factorization * src/factor.c (factor_using_pollard_rho): Handle trivial factor g = n. (factor_using_pollard_rho2): Handle trivial factor g1 = n1, g0 = n0. diff --git a/src/factor.c b/src/factor.c index 115a635..54893ca 100644 --- a/src/factor.c +++ b/src/factor.c @@ -1522,6 +1522,13 @@ factor_using_pollard_rho (uintmax_t n, unsigned long int a, } while (g == 1); + if (n == g) + { + /* Found n itself as factor. Restart with different params. */ + factor_using_pollard_rho (n, a + 1, factors); + return; + } + n = n / g; if (!prime_p (g)) @@ -1607,7 +1614,7 @@ factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n0, unsigned long int a, if (g1 == 0) { - /* The found factor is one word. */ + /* The found factor is one word, and > 1. */ divexact_21 (n1, n0, n1, n0, g0); /* n = n / g */ if (!prime_p (g0)) @@ -1621,6 +1628,13 @@ factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n0, unsigned long int a, to trigger. Please be careful before you change this code! */ uintmax_t ginv; + if (n1 == g1 && n0 == g0) + { + /* Found n itself as factor. Restart with different params. */ + factor_using_pollard_rho2 (n1, n0, a + 1, factors); + return; + } + binv (ginv, g0); /* Compute n = n / g. Since the result will */ n0 = ginv * n0; /* fit one word, we can compute the quotient */ n1 = 0; /* modulo B, ignoring the high divisor word. */ commit 1bdf193895da010daf95260158c1eba5b9377b30 Author: Niels Möller <ni...@lysator.liu.se> Date: Wed Dec 7 18:50:20 2016 +0100 factor: Fix infinite loop in gcd2_odd * src/factor.c (gcd2_odd): Fix the case a1 == 0, a0 == 0. diff --git a/src/factor.c b/src/factor.c index d271de9..115a635 100644 --- a/src/factor.c +++ b/src/factor.c @@ -480,10 +480,16 @@ gcd_odd (uintmax_t a, uintmax_t b) static uintmax_t gcd2_odd (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t b1, uintmax_t b0) { + assert (b0 & 1); + + if ( (a0 | a1) == 0) + { + *r1 = b1; + return b0; + } + while ((a0 & 1) == 0) rsh2 (a1, a0, a1, a0, 1); - while ((b0 & 1) == 0) - rsh2 (b1, b0, b1, b0, 1); for (;;) { -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance.