GNU bug report logs - #25135
Infinite loop in factor

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 25135 in the body.
You can then email your comments to 25135 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: nisse <at> lysator.liu.se (Niels Möller)
To: bug-coreutils <at> gnu.org
Cc: "Eggen, Bernd" <bernd.eggen <at> metoffice.gov.uk>,
 Torbjorn Granlund <tg <at> gmplib.org>
Subject: Infinite loop in factor
Date: Thu, 08 Dec 2016 08:50:06 +0100

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.

Message #10 received at 25135-done <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Niels Möller <nisse <at> lysator.liu.se>,
 25135-done <at> debbugs.gnu.org
Cc: "Eggen, Bernd" <bernd.eggen <at> metoffice.gov.uk>,
 Torbjorn Granlund <tg <at> gmplib.org>
Subject: Re: bug#25135: Infinite loop in factor
Date: Thu, 8 Dec 2016 10:23:01 +0000

On 08/12/16 07:50, Niels Möller wrote:
> Hi,
> 
> I've got an interesting bug report saying that 
> 
>   factor 158909489063877810457
> 
> is very slow (actually, I don't think it ever terminates).

Fixes pushed at:

http://git.sv.gnu.org/gitweb/?p=coreutils.git;a=commitdiff;h=v8.26-3-gc44da11
http://git.sv.gnu.org/gitweb/?p=coreutils.git;a=commitdiff;h=v8.26-4-gca52f3b

The factor tests you looked at are a bit special.
I updated a separate test and tested like:

  make TESTS=tests/misc/factor.pl SUBDIRS=. check

To run that particular test you were looking at, it's:

  make TESTS=tests/factor/t00.sh RUN_VERY_EXPENSIVE_TESTS=yes SUBDIRS=. check

thanks!
Pádraig

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.