From unknown Sat Aug 16 16:23:21 2025 X-Loop: help-debbugs@gnu.org Subject: bug#25135: Infinite loop in factor Resent-From: nisse@lysator.liu.se (Niels =?UTF-8?Q?M=C3=B6ller?=) Original-Sender: "Debbugs-submit" Resent-CC: bug-coreutils@gnu.org Resent-Date: Thu, 08 Dec 2016 07:51:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 25135 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: 25135@debbugs.gnu.org Cc: "Eggen, Bernd" , Torbjorn Granlund X-Debbugs-Original-To: bug-coreutils@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.148118342519758 (code B ref -1); Thu, 08 Dec 2016 07:51:02 +0000 Received: (at submit) by debbugs.gnu.org; 8 Dec 2016 07:50:25 +0000 Received: from localhost ([127.0.0.1]:60702 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cEtTE-00058c-T1 for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:25 -0500 Received: from eggs.gnu.org ([208.118.235.92]:43665) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cEtTC-00058O-CN for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:22 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cEtT5-0008Ac-Se for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:17 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:57533) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cEtT5-00089o-PQ for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:15 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:34625) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cEtT4-0007Lj-6u for bug-coreutils@gnu.org; Thu, 08 Dec 2016 02:50:15 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cEtT2-00083N-Ul for bug-coreutils@gnu.org; Thu, 08 Dec 2016 02:50:14 -0500 Received: from mail.lysator.liu.se ([2001:6b0:17:f0a0::3]:56290) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cEtT2-0007t1-NP for bug-coreutils@gnu.org; Thu, 08 Dec 2016 02:50:12 -0500 Received: from mail.lysator.liu.se (localhost [127.0.0.1]) by mail.lysator.liu.se (Postfix) with ESMTP id C6D0840031; Thu, 8 Dec 2016 08:50:07 +0100 (CET) Received: from armitage.lysator.liu.se (armitage.lysator.liu.se [IPv6:2001:6b0:17:f0a0::83]) by mail.lysator.liu.se (Postfix) with SMTP id 8EA9640005; Thu, 8 Dec 2016 08:50:06 +0100 (CET) Received: by armitage.lysator.liu.se (sSMTP sendmail emulation); Thu, 08 Dec 2016 08:50:06 +0100 From: nisse@lysator.liu.se (Niels =?UTF-8?Q?M=C3=B6ller?=) Date: Thu, 08 Dec 2016 08:50:06 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (berkeley-unix) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Virus-Scanned: ClamAV using ClamSMTP X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.4 (----) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.4 (----) Hi, I've got an interesting bug report saying that=20 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=20 input is zero; deleting the unneeded handling of even 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=C3=B6rn, fixes this problem. Input numbers of interest are 158909489063877810457 (above), 222087527029934481871 (same problem) and 12847291069740315094892340035 (second problem).=20 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=3Dtests/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=C3=B6rn Granlund Date: Wed Dec 7 21:01:03 2016 +0100 factor: Retry properly if Pollard rho gives a trivial factorization =20=20=20=20 * src/factor.c (factor_using_pollard_rho): Handle trivial factor g =3D = n. (factor_using_pollard_rho2): Handle trivial factor g1 =3D n1, g0 =3D 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 =3D=3D 1); =20 + if (n =3D=3D g) + { + /* Found n itself as factor. Restart with different params. */ + factor_using_pollard_rho (n, a + 1, factors); + return; + } + n =3D n / g; =20 if (!prime_p (g)) @@ -1607,7 +1614,7 @@ factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n0= , unsigned long int a, =20 if (g1 =3D=3D 0) { - /* The found factor is one word. */ + /* The found factor is one word, and > 1. */ divexact_21 (n1, n0, n1, n0, g0); /* n =3D n / g */ =20 if (!prime_p (g0)) @@ -1621,6 +1628,13 @@ factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n= 0, unsigned long int a, to trigger. Please be careful before you change this code! = */ uintmax_t ginv; =20 + if (n1 =3D=3D g1 && n0 =3D=3D 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 =3D n / g. Since the result = will */ n0 =3D ginv * n0; /* fit one word, we can compute the quot= ient */ n1 =3D 0; /* modulo B, ignoring the high divisor w= ord. */ commit 1bdf193895da010daf95260158c1eba5b9377b30 Author: Niels M=C3=B6ller Date: Wed Dec 7 18:50:20 2016 +0100 factor: Fix infinite loop in gcd2_odd =20=20=20=20 * src/factor.c (gcd2_odd): Fix the case a1 =3D=3D 0, a0 =3D=3D 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) =3D=3D 0) + { + *r1 =3D b1; + return b0; + } + while ((a0 & 1) =3D=3D 0) rsh2 (a1, a0, a1, a0, 1); - while ((b0 & 1) =3D=3D 0) - rsh2 (b1, b0, b1, b0, 1); =20 for (;;) { --=20 Niels M=C3=B6ller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. From unknown Sat Aug 16 16:23:21 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: nisse@lysator.liu.se (Niels =?UTF-8?Q?M=C3=B6ller?=) Subject: bug#25135: closed (Re: bug#25135: Infinite loop in factor) Message-ID: References: <2fb822dc-831b-645f-880c-75cded45b628@draigBrady.com> X-Gnu-PR-Message: they-closed 25135 X-Gnu-PR-Package: coreutils Reply-To: 25135@debbugs.gnu.org Date: Thu, 08 Dec 2016 10:24:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1481192642-778-1" This is a multi-part message in MIME format... ------------=_1481192642-778-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 25135@debbugs.gnu.org. --=20 25135: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D25135 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1481192642-778-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 25135-done) by debbugs.gnu.org; 8 Dec 2016 10:23:06 +0000 Received: from localhost ([127.0.0.1]:60769 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cEvr0-0000BP-BQ for submit@debbugs.gnu.org; Thu, 08 Dec 2016 05:23:06 -0500 Received: from mail.magicbluesmoke.com ([82.195.144.49]:38682) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cEvqx-0000BG-Rr for 25135-done@debbugs.gnu.org; Thu, 08 Dec 2016 05:23:04 -0500 Received: from [192.168.1.80] (unknown [109.79.95.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.magicbluesmoke.com (Postfix) with ESMTPSA id 3AA4D244; Thu, 8 Dec 2016 10:23:02 +0000 (GMT) Subject: Re: bug#25135: Infinite loop in factor To: =?UTF-8?Q?Niels_M=c3=b6ller?= , 25135-done@debbugs.gnu.org References: From: =?UTF-8?Q?P=c3=a1draig_Brady?= Message-ID: <2fb822dc-831b-645f-880c-75cded45b628@draigBrady.com> Date: Thu, 8 Dec 2016 10:23:01 +0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 25135-done Cc: "Eggen, Bernd" , Torbjorn Granlund X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.0 (/) 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 ------------=_1481192642-778-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 8 Dec 2016 07:50:25 +0000 Received: from localhost ([127.0.0.1]:60702 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cEtTE-00058c-T1 for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:25 -0500 Received: from eggs.gnu.org ([208.118.235.92]:43665) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cEtTC-00058O-CN for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:22 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cEtT5-0008Ac-Se for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:17 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:57533) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cEtT5-00089o-PQ for submit@debbugs.gnu.org; Thu, 08 Dec 2016 02:50:15 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:34625) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cEtT4-0007Lj-6u for bug-coreutils@gnu.org; Thu, 08 Dec 2016 02:50:15 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cEtT2-00083N-Ul for bug-coreutils@gnu.org; Thu, 08 Dec 2016 02:50:14 -0500 Received: from mail.lysator.liu.se ([2001:6b0:17:f0a0::3]:56290) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cEtT2-0007t1-NP for bug-coreutils@gnu.org; Thu, 08 Dec 2016 02:50:12 -0500 Received: from mail.lysator.liu.se (localhost [127.0.0.1]) by mail.lysator.liu.se (Postfix) with ESMTP id C6D0840031; Thu, 8 Dec 2016 08:50:07 +0100 (CET) Received: from armitage.lysator.liu.se (armitage.lysator.liu.se [IPv6:2001:6b0:17:f0a0::83]) by mail.lysator.liu.se (Postfix) with SMTP id 8EA9640005; Thu, 8 Dec 2016 08:50:06 +0100 (CET) Received: by armitage.lysator.liu.se (sSMTP sendmail emulation); Thu, 08 Dec 2016 08:50:06 +0100 From: nisse@lysator.liu.se (Niels =?utf-8?Q?M=C3=B6ller?=) To: bug-coreutils@gnu.org Subject: Infinite loop in factor Date: Thu, 08 Dec 2016 08:50:06 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (berkeley-unix) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Virus-Scanned: ClamAV using ClamSMTP X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.4 (----) X-Debbugs-Envelope-To: submit Cc: "Eggen, Bernd" , Torbjorn Granlund X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.4 (----) Hi, I've got an interesting bug report saying that=20 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=20 input is zero; deleting the unneeded handling of even 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=C3=B6rn, fixes this problem. Input numbers of interest are 158909489063877810457 (above), 222087527029934481871 (same problem) and 12847291069740315094892340035 (second problem).=20 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=3Dtests/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=C3=B6rn Granlund Date: Wed Dec 7 21:01:03 2016 +0100 factor: Retry properly if Pollard rho gives a trivial factorization =20=20=20=20 * src/factor.c (factor_using_pollard_rho): Handle trivial factor g =3D = n. (factor_using_pollard_rho2): Handle trivial factor g1 =3D n1, g0 =3D 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 =3D=3D 1); =20 + if (n =3D=3D g) + { + /* Found n itself as factor. Restart with different params. */ + factor_using_pollard_rho (n, a + 1, factors); + return; + } + n =3D n / g; =20 if (!prime_p (g)) @@ -1607,7 +1614,7 @@ factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n0= , unsigned long int a, =20 if (g1 =3D=3D 0) { - /* The found factor is one word. */ + /* The found factor is one word, and > 1. */ divexact_21 (n1, n0, n1, n0, g0); /* n =3D n / g */ =20 if (!prime_p (g0)) @@ -1621,6 +1628,13 @@ factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n= 0, unsigned long int a, to trigger. Please be careful before you change this code! = */ uintmax_t ginv; =20 + if (n1 =3D=3D g1 && n0 =3D=3D 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 =3D n / g. Since the result = will */ n0 =3D ginv * n0; /* fit one word, we can compute the quot= ient */ n1 =3D 0; /* modulo B, ignoring the high divisor w= ord. */ commit 1bdf193895da010daf95260158c1eba5b9377b30 Author: Niels M=C3=B6ller Date: Wed Dec 7 18:50:20 2016 +0100 factor: Fix infinite loop in gcd2_odd =20=20=20=20 * src/factor.c (gcd2_odd): Fix the case a1 =3D=3D 0, a0 =3D=3D 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) =3D=3D 0) + { + *r1 =3D b1; + return b0; + } + while ((a0 & 1) =3D=3D 0) rsh2 (a1, a0, a1, a0, 1); - while ((b0 & 1) =3D=3D 0) - rsh2 (b1, b0, b1, b0, 1); =20 for (;;) { --=20 Niels M=C3=B6ller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. ------------=_1481192642-778-1--