Subject: bug#25135: closed (Re: bug#25135: Infinite loop in factor)

From: [email-masked] (GNU bug Tracking System)
Date: Thu, 08 Dec 2016 10:24:02 +0000

Your bug report

#25135: Infinite loop in factor

which was filed against the coreutils package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
25135: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=25135
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#25135: Infinite loop in factor
From: Pádraig Brady <[email-masked]>
To: Niels Möller <[email-masked]>, [email-masked]
Cc: "Eggen, Bernd" <[email-masked]>, Torbjorn Granlund <[email-masked]>
Date: Thu, 8 Dec 2016 10:23:01 +0000
List-Id: <debbugs-submit.debbugs.gnu.org>

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

Subject: Infinite loop in factor
From: [email-masked] (Niels Möller)
To: [email-masked]
Cc: "Eggen, Bernd" <[email-masked]>, Torbjorn Granlund <[email-masked]>
Date: Thu, 08 Dec 2016 08:50:06 +0100
List-Id: <debbugs-submit.debbugs.gnu.org>

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 <[email-masked]>
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 <[email-masked]>
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.