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 <tg <at> 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 <nisse <at> 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.
This bug report was last modified 8 years and 223 days ago.