bug#25135: Infinite loop in factor

[Niels Möller]

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 <address@hidden>
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 <address@hidden>
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.