summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/factor.c16
-rwxr-xr-xtests/misc/factor.pl2
2 files changed, 17 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. */
diff --git a/tests/misc/factor.pl b/tests/misc/factor.pl
index e37df9d61..ec5413745 100755
--- a/tests/misc/factor.pl
+++ b/tests/misc/factor.pl
@@ -78,6 +78,8 @@ my @Tests =
{OUT => '3401347 3861211 12099721'}],
['bug-2016-b', '222087527029934481871',
{OUT => '15601 26449 111427 4830277'}],
+ ['bug-2016-c', '12847291069740315094892340035',
+ {OUT => '5 4073 18899 522591721 63874247821'}],
);
# If we have GMP support, append tests to exercise it.