diff options
author | Torbjörn Granlund <tg@gmplib.org> | 2016-12-08 10:07:29 +0000 |
---|---|---|
committer | Pádraig Brady <P@draigBrady.com> | 2016-12-08 10:10:38 +0000 |
commit | ca52f3bf3f48a1a296e70bff5fd77ff789c570f5 (patch) | |
tree | 55811fbc475f8b7b2909c785395734eb46118e47 /src/factor.c | |
parent | c44da115063bfea7ef8b2afd1c9d52737e2b7f70 (diff) | |
download | coreutils-ca52f3bf3f48a1a296e70bff5fd77ff789c570f5.tar.xz |
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.
* tests/misc/factor.pl: Add a test case.
Fixes http://bugs.gnu.org/25135
Diffstat (limited to 'src/factor.c')
-rw-r--r-- | src/factor.c | 16 |
1 files changed, 15 insertions, 1 deletions
diff --git a/src/factor.c b/src/factor.c index 115a635f9..54893ca82 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. */ |