From debbugs-submit-bounces@debbugs.gnu.org Thu Dec 08 02:50:25 2016 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. From debbugs-submit-bounces@debbugs.gnu.org Thu Dec 08 05:23:06 2016 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 From unknown Sun Jun 22 03:57:26 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Thu, 05 Jan 2017 12:24:08 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator