From debbugs-submit-bounces@debbugs.gnu.org Sun May 18 03:39:54 2025 Received: (at submit) by debbugs.gnu.org; 18 May 2025 07:39:54 +0000 Received: from localhost ([127.0.0.1]:54791 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uGYcj-00084G-Pf for submit@debbugs.gnu.org; Sun, 18 May 2025 03:39:54 -0400 Received: from lists.gnu.org ([2001:470:142::17]:43498) by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1uGYch-00083m-5d for submit@debbugs.gnu.org; Sun, 18 May 2025 03:39:51 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1uGYcb-0005Mm-SD for bug-coreutils@gnu.org; Sun, 18 May 2025 03:39:45 -0400 Received: from mail.cs.ucla.edu ([131.179.128.66]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1uGYcZ-0004Ca-Qe for bug-coreutils@gnu.org; Sun, 18 May 2025 03:39:45 -0400 Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id 7BDA13C01086E; Sun, 18 May 2025 00:39:41 -0700 (PDT) Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10032) with ESMTP id gBNCiLuBjKCE; Sun, 18 May 2025 00:39:41 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id 4FF573C01087D; Sun, 18 May 2025 00:39:41 -0700 (PDT) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.cs.ucla.edu 4FF573C01087D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.ucla.edu; s=9D0B346E-2AEB-11ED-9476-E14B719DCE6C; t=1747553981; bh=IG6xlnJrUsUZhn4C9jVkQZWhQmbKQRuX4tJqNuFYzGw=; h=Message-ID:Date:MIME-Version:To:From; b=QxNX9Bf/RHPZ4+tjaMIK2oUa+PlSVoWeYsn2pnvvHIndELT5lhy5+tcckiyMpQCC7 RQ2XkEFoPrj0qbWKdpLXbA2GBx4XBIE55g5EeU32ZxMIBQaNcP73OGhcHlmZyLHzzv TfaJslV3XrBKTi/3bNpIuH8HAs8qL7bim6uZNQoPJBRe0hmZyesg0PwY5XobYY0Vpl ITXBh6dCUrefFZwAVNRdGOtlJJ92gpj5CSrdyQ9XMnON1hhx8NqduCRyJK6qmSQiln hfTpdRrC+x7xtRjwN/cHZ0RFYeRnCYJH+2nbje78IFzoJYrNsdg1hi0k8LNOSvPeFc 1Bo64lULAHDDw== X-Virus-Scanned: amavis at mail.cs.ucla.edu Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10026) with ESMTP id pNjdq10aWKTj; Sun, 18 May 2025 00:39:41 -0700 (PDT) Received: from [192.168.254.12] (47-147-225-25.fdr01.snmn.ca.ip.frontiernet.net [47.147.225.25]) by mail.cs.ucla.edu (Postfix) with ESMTPSA id 2C4243C01086E; Sun, 18 May 2025 00:39:41 -0700 (PDT) Message-ID: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> Date: Sun, 18 May 2025 00:39:38 -0700 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Content-Language: en-US To: Coreutils bugs From: Paul Eggert Subject: GNU 'factor' problems with 128-bit word Organization: UCLA Computer Science Department Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: quoted-printable Received-SPF: pass client-ip=131.179.128.66; envelope-from=eggert@cs.ucla.edu; helo=mail.cs.ucla.edu X-Spam_score_int: -19 X-Spam_score: -2.0 X-Spam_bar: -- X-Spam_report: (-2.0 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_VALIDITY_RPBL_BLOCKED=0.001, RCVD_IN_VALIDITY_SAFE_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: submit Cc: 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 (/) I recently found out that GNU coreutils 'factor' misbehaves if its=20 internal word is 128 bits rather than the usual 64. This could happen if=20 one builds Coreutils 9.7 on a platform with 128-bit uintmax_t, something=20 that POSIX allows (though it's only theoretical now as far as I know). The problem occurs when src/factor.c's prime_p function assumes that as=20 a quick test, its argument N must be prime if N is less than=20 FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME. I guess this quick-test=20 assumption is true for 64-bit uintmax_t, but not for 128-bit. I worked around the bug by installed a patch=20 .=20 This patch changes prime_p to rely on the quick-test assumption only=20 when the internal word size is 64 bits. On platforms with wider words,=20 the code now tests smaller numbers for primes too; this works around the=20 bug, but is slower. It'd be nice if the underlying problem were fixed, so that the code is=20 more portable to 128-bit word. The issue might be related to Bug#25135 "Infinite loop in factor"=20 so I am cc'ing this to Torbj=C3=B6rn. The=20 current factor.c is not the same as what Torbj=C3=B6rn contributed years = ago=20 so it is of course possible that I or someone else introduced the bug=20 more recently. To reproduce the problem on Fedora 42 x86-64: git clone https://git.savannah.gnu.org/git/coreutils.git cd coreutils git checkout fe51b33859d2e7286425d6d5600288ce9ae43bd1 ./bootstrap ./configure make CFLAGS=3D'-DUSE_INT128 -DEXHIBIT_INT128_BUG' WERROR_CFLAGS=3D echo 340282366920938463463374607431768211355 | src/factor The output is: 340282366920938463463374607431768211355: 155=20 2195370109167344925570158757624311041 which is wrong, as 155 is not prime. From debbugs-submit-bounces@debbugs.gnu.org Sun May 18 05:07:18 2025 Received: (at submit) by debbugs.gnu.org; 18 May 2025 09:07:18 +0000 Received: from localhost ([127.0.0.1]:55475 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uGZzJ-00056y-La for submit@debbugs.gnu.org; Sun, 18 May 2025 05:07:17 -0400 Received: from lists.gnu.org ([2001:470:142::17]:53200) by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1uGZzH-00056S-N0 for submit@debbugs.gnu.org; Sun, 18 May 2025 05:07:16 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1uGZzA-0001xi-TR for bug-coreutils@gnu.org; Sun, 18 May 2025 05:07:10 -0400 Received: from martin.gmplib.org ([130.242.124.102] helo=shell.gmplib.org) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1uGZz8-0008Mx-R3 for bug-coreutils@gnu.org; Sun, 18 May 2025 05:07:08 -0400 Received: by shell.gmplib.org (Postfix, from userid 1001) id AB8249552; Sun, 18 May 2025 11:07:01 +0200 (CEST) From: =?utf-8?Q?Torbj=C3=B6rn_Granlund?= To: Paul Eggert Subject: Re: GNU 'factor' problems with 128-bit word In-Reply-To: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> (Paul Eggert's message of "Sun, 18 May 2025 00:39:38 -0700") References: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> Date: Sun, 18 May 2025 11:07:01 +0200 Message-ID: <868qmuthhm.fsf@shell.gmplib.org> User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Received-SPF: none client-ip=130.242.124.102; envelope-from=tg@gmplib.org; helo=shell.gmplib.org X-Spam_score_int: -14 X-Spam_score: -1.5 X-Spam_bar: - X-Spam_report: (-1.5 / 5.0 requ) BAYES_00=-1.9, KHOP_HELO_FCRDNS=0.399, RCVD_IN_VALIDITY_RPBL_BLOCKED=0.001, RCVD_IN_VALIDITY_SAFE_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: submit Cc: Coreutils bugs 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: -1.0 (-) Just a quick note. I don't think is makes much sense to handle two 128-bit words in this code. In fact, the use of uintmax_t was a mistake, it should use "unsigned long" or "unsigned long long" whichever is efficiently supported directly by the hardware. While uintmax_t could be made to work also for the cases you report, it will be inefficient. A few months ago, I contributed a suggested new core factoring function to GNU coreutils, which is, IIRC, 2-3 times faster than the current code for the bignum range. It uses GMP's mpn functions with "Montgomery multiplication". There were two problems with my new core code: 1. It will not work with mini-GMP, which I think is undesiable. 2. It did not optimise for smaller factoring tasks. The fix for this would be to merge that from the current coreutils factor.c. --=20 Torbj=C3=B6rn Please encrypt, key id 0xC8601622 From debbugs-submit-bounces@debbugs.gnu.org Mon May 19 15:27:37 2025 Received: (at 78476) by debbugs.gnu.org; 19 May 2025 19:27:37 +0000 Received: from localhost ([127.0.0.1]:45141 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uH69B-0008QL-DN for submit@debbugs.gnu.org; Mon, 19 May 2025 15:27:37 -0400 Received: from mail.cs.ucla.edu ([131.179.128.66]:53102) by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1uH698-0008Pj-4y for 78476@debbugs.gnu.org; Mon, 19 May 2025 15:27:34 -0400 Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id 474103C0140A0; Mon, 19 May 2025 12:27:28 -0700 (PDT) Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10032) with ESMTP id t7NWSWvfKZdi; Mon, 19 May 2025 12:27:28 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id 20C5B3C0149D1; Mon, 19 May 2025 12:27:28 -0700 (PDT) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.cs.ucla.edu 20C5B3C0149D1 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.ucla.edu; s=9D0B346E-2AEB-11ED-9476-E14B719DCE6C; t=1747682848; bh=JtPNaW5QGBkhez1Uw9qnr9E8bBU2udMD9MzS2oPWJys=; h=Message-ID:Date:MIME-Version:To:From; b=dGl4RYPrDXcCETIcu3ycH+6eJM7QNZ9mDJzmPOpxaXdu/9D0nv0L1g1TAxttY4vlc zTlYTcGYh4R6ZIfjSbzi8o4mS10UkSM4LPt/1a3sxYgjYF6aW+2J+hp8NkVl0U5Q19 RmI8OdIq39akUmsh0EpVJrhsRy95PTG9OsemqpdiTGt6KxYq8wOrTpGms2ltPXlj2X osWi13Qr9UVi7LTTW4lPD7f/uAllkVynvHO2qAmF+nmBAcUASxwyhsOWP5zxxCuwVW lCFmF7i/e/k1b28ACxbP8B0WJ6LuEarazARxc5XNlGQk4CR3v6i8Lxw3IL1Rf/l1Qe UJXpgDSyBY8Qg== X-Virus-Scanned: amavis at mail.cs.ucla.edu Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10026) with ESMTP id nkHbxciAx2V2; Mon, 19 May 2025 12:27:28 -0700 (PDT) Received: from [192.168.254.12] (unknown [47.147.225.25]) by mail.cs.ucla.edu (Postfix) with ESMTPSA id 017E03C0140A0; Mon, 19 May 2025 12:27:27 -0700 (PDT) Message-ID: <5fe8b1c3-1dc6-4863-9892-ab4fef74fb8e@cs.ucla.edu> Date: Mon, 19 May 2025 12:27:27 -0700 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: bug#78476: GNU 'factor' problems with 128-bit word To: =?UTF-8?Q?Torbj=C3=B6rn_Granlund?= References: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> <868qmuthhm.fsf@shell.gmplib.org> Content-Language: en-US From: Paul Eggert Organization: UCLA Computer Science Department In-Reply-To: <868qmuthhm.fsf@shell.gmplib.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 78476 Cc: 78476@debbugs.gnu.org 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: -1.0 (-) On 2025-05-18 02:07, Torbj=C3=B6rn Granlund wrote: > I don't think is makes much sense to handle two 128-bit words in this > code. In fact, the use of uintmax_t was a mistake, it should use > "unsigned long" or "unsigned long long" whichever is efficiently > supported directly by the hardware. Fine, but the 128-bit bug is independent of uintmax_t. Suppose we change=20 factor.c to never use uintmax_t, and suppose we have a (theoretical but=20 allowed) platform where unsigned long is 128 bits and where factor.c=20 uses that type for its words. Then before my Saturday coreutils=20 commit[1], this code in prime_p: /* We have already cast out small primes. */ if (n < (wide_uint) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME) return true; was incorrect. The problem is that when given 2**128 - 101,=20 factor_using_pollard_rho generates 155 and tests it with prime_p, and=20 the above code causes prime_p to incorrectly report that 155 is prime. > While uintmax_t could be made to work also for the cases you report, it > will be inefficient. >=20 > A few months ago, I contributed a suggested new core factoring function > to GNU coreutils, which is, IIRC, 2-3 times faster than the current cod= e > for the bignum range. It uses GMP's mpn functions with "Montgomery > multiplication". >=20 > There were two problems with my new core code: >=20 > 1. It will not work with mini-GMP, which I think is undesiable. >=20 > 2. It did not optimise for smaller factoring tasks. The fix for this > would be to merge that from the current coreutils factor.c. Thanks, I didn't know about all that. I plan to take a look at it. [1]:=20 https://git.savannah.gnu.org/cgit/coreutils.git/commit/?id=3Dfe51b33859d2= e7286425d6d5600288ce9ae43bd1 From debbugs-submit-bounces@debbugs.gnu.org Mon May 19 18:23:56 2025 Received: (at 78476) by debbugs.gnu.org; 19 May 2025 22:23:56 +0000 Received: from localhost ([127.0.0.1]:46965 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uH8to-0003bv-7d for submit@debbugs.gnu.org; Mon, 19 May 2025 18:23:56 -0400 Received: from martin.gmplib.org ([130.242.124.102]:61438 helo=shell.gmplib.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uH8tk-0003bQ-HU for 78476@debbugs.gnu.org; Mon, 19 May 2025 18:23:53 -0400 Received: by shell.gmplib.org (Postfix, from userid 1001) id 698A49568; Tue, 20 May 2025 00:23:50 +0200 (CEST) From: =?utf-8?Q?Torbj=C3=B6rn_Granlund?= To: Paul Eggert Subject: Re: bug#78476: GNU 'factor' problems with 128-bit word In-Reply-To: <5fe8b1c3-1dc6-4863-9892-ab4fef74fb8e@cs.ucla.edu> (Paul Eggert's message of "Mon, 19 May 2025 12:27:27 -0700") References: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> <868qmuthhm.fsf@shell.gmplib.org> <5fe8b1c3-1dc6-4863-9892-ab4fef74fb8e@cs.ucla.edu> Date: Tue, 20 May 2025 00:23:50 +0200 Message-ID: <86iklwutmx.fsf@shell.gmplib.org> User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.4 (/) X-Debbugs-Envelope-To: 78476 Cc: 78476@debbugs.gnu.org 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: -1.0 (-) Paul Eggert writes: Fine, but the 128-bit bug is independent of uintmax_t. Suppose we change factor.c to never use uintmax_t, and suppose we have a (theoretical but allowed) platform where unsigned long is 128 bits and where factor.c uses that type for its words. Then before my Saturday coreutils commit[1], this code in prime_p: /* We have already cast out small primes. */ if (n < (wide_uint) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME) return true; was incorrect. Why is it incorrect? I read you change, and I strongly disgree with it. I actually find it extremely worrying that a change is motivated by "We don't know why the code misbehaves when wide_uint is wider;" and then the presumed bug is masked with a pretty questionable change. Really? How about debugging it? Furthernorem tinkering with mature code for porting it to something with does not exist and likely will never exist, is a bad idea. No, we are very unlikely to see systems with 128x128->256 bit hardware multiply support, which is the only case where forcing factor.c to do 128-bit arithmetic. Let's use our time and effort on improving things for the word we live in. --=20 Torbj=C3=B6rn Please encrypt, key id 0xC8601622 From debbugs-submit-bounces@debbugs.gnu.org Mon May 19 18:51:25 2025 Received: (at 78476) by debbugs.gnu.org; 19 May 2025 22:51:25 +0000 Received: from localhost ([127.0.0.1]:47254 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uH9KO-0000nu-Nz for submit@debbugs.gnu.org; Mon, 19 May 2025 18:51:25 -0400 Received: from mail.cs.ucla.edu ([131.179.128.66]:54550) by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1uH9KL-0000nA-9G for 78476@debbugs.gnu.org; Mon, 19 May 2025 18:51:22 -0400 Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id CD4C73C0149EF; Mon, 19 May 2025 15:51:13 -0700 (PDT) Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10032) with ESMTP id EK2Z2j2pdPXH; Mon, 19 May 2025 15:51:13 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id A60353C0149F3; Mon, 19 May 2025 15:51:13 -0700 (PDT) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.cs.ucla.edu A60353C0149F3 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.ucla.edu; s=9D0B346E-2AEB-11ED-9476-E14B719DCE6C; t=1747695073; bh=J9lG5BvxOj1H7t6CzUBTVXh3UY+91f5/8lJGcCkfTeA=; h=Message-ID:Date:MIME-Version:To:From; b=eeBurBaIDZdqHYBZ5O/lzVml1zdPizo2tdOhfnTi32xJHgUznN1tK/XngUTOREAPO umomzKbWnqdMREfrSKnJcQbRWO+lkDQ5wDzrfH9aMk+kx/ATyDGr7EMD5yhdlZ+Kif QmRGqyHU45W/xmJ7UjCF8Fedvk21uJTMpXEXdEpF5vNS8zkRDIFZUoSkWs46sQ6p3m FocYIfkSHSI6PcQz7F5izPwrfRjLSilJI+R8C1bFXWuWQlWWY74HgDhuuHeV8yevPB GOdLXO8XjWU58ss0wzQSixNtT2opGaXjPpLPRn8pIuw4k67tmjAV/8AFnR7FX0PUfC dXv3Z1qJ1leBQ== X-Virus-Scanned: amavis at mail.cs.ucla.edu Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10026) with ESMTP id sSh93FaWRU3x; Mon, 19 May 2025 15:51:13 -0700 (PDT) Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by mail.cs.ucla.edu (Postfix) with ESMTPSA id 8DD023C0149EF; Mon, 19 May 2025 15:51:13 -0700 (PDT) Message-ID: <7bbe9797-48c0-435a-8334-85c2ef817955@cs.ucla.edu> Date: Mon, 19 May 2025 15:51:12 -0700 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: bug#78476: GNU 'factor' problems with 128-bit word To: =?UTF-8?Q?Torbj=C3=B6rn_Granlund?= References: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> <868qmuthhm.fsf@shell.gmplib.org> <5fe8b1c3-1dc6-4863-9892-ab4fef74fb8e@cs.ucla.edu> <86iklwutmx.fsf@shell.gmplib.org> Content-Language: en-US From: Paul Eggert Autocrypt: addr=eggert@cs.ucla.edu; keydata= xsFNBEyAcmQBEADAAyH2xoTu7ppG5D3a8FMZEon74dCvc4+q1XA2J2tBy2pwaTqfhpxxdGA9 Jj50UJ3PD4bSUEgN8tLZ0san47l5XTAFLi2456ciSl5m8sKaHlGdt9XmAAtmXqeZVIYX/UFS 96fDzf4xhEmm/y7LbYEPQdUdxu47xA5KhTYp5bltF3WYDz1Ygd7gx07Auwp7iw7eNvnoDTAl KAl8KYDZzbDNCQGEbpY3efZIvPdeI+FWQN4W+kghy+P6au6PrIIhYraeua7XDdb2LS1en3Ss mE3QjqfRqI/A2ue8JMwsvXe/WK38Ezs6x74iTaqI3AFH6ilAhDqpMnd/msSESNFt76DiO1ZK QMr9amVPknjfPmJISqdhgB1DlEdw34sROf6V8mZw0xfqT6PKE46LcFefzs0kbg4GORf8vjG2 Sf1tk5eU8MBiyN/bZ03bKNjNYMpODDQQwuP84kYLkX2wBxxMAhBxwbDVZudzxDZJ1C2VXujC OJVxq2kljBM9ETYuUGqd75AW2LXrLw6+MuIsHFAYAgRr7+KcwDgBAfwhPBYX34nSSiHlmLC+ KaHLeCLF5ZI2vKm3HEeCTtlOg7xZEONgwzL+fdKo+D6SoC8RRxJKs8a3sVfI4t6CnrQzvJbB n6gxdgCu5i29J1QCYrCYvql2UyFPAK+do99/1jOXT4m2836j1wARAQABzSBQYXVsIEVnZ2Vy dCA8ZWdnZXJ0QGNzLnVjbGEuZWR1PsLBlQQTAQgAPwIbAwYLCQgHAwIGFQgCCQoLBBYCAwEC HgECF4AWIQR+N5Kp2Kz31jO8FYjtl+kOYqp+NAUCZiLOewUJHWQLDAAKCRDtl+kOYqp+NHGE D/9Wmbk+cAaQsYLPGBvyzIjZIRzo/V2p3ZwckVA1VEQivx5azu1cs86qDoVIe45AtwmKOvdV wTQd/QeglkZR6D2YPW7UR/7emajyJZZcy+etVTDKoaw1i6/hmd/CpGjUeUSvgoPs6nYR+1lo pSXTpaGrh1W0qQHalSkOOwCHG3HtGk9Ve2AERDUYxmcn8/eZHb7xpUJEJMBBI1bx/zcw1EtB rjsQ1R1faJ/r/7LPAyV36RLvnbX69PylHKQEbJoaY9aUb2Vpm63ni3FeTA7/3jpPvaSRWHJh vPYx6Fm2Ln8pI0Yf/W2B8QMiPTnF/LnH2kvUcf9VXm+1mQJ3fBFU25HZwBhuqZ24IeKymPEt BUMQAum97Dto0jSgR2OUvX7z+twhpQEgRGBzPHYwDi4SxF5Z4Q5Y7B7a++HP9tIxG6CVFIwI 4xVaZud18bPa0YBL+cISmMgxq7h7yoVXl6u3pm9Yiv+W6Lp9QGN8Rw1VuJMOoFCYuoxG8mXO TA5b1jvlQ32gHFFhqErDAhNJRsfgrpe9Gok4Ycp+rWljbvS5Wrl0uth5MP7FbaHN2kmTZibq KXAd//IqczhDyU6qnW6ao+h4iDBDgYgRbQjmToX/vmIdEMzvPGqWXKhe/q1TYMuOO+IfP+bI fyPFH29nVN/o9c4J7myeKvv3HKSXdSVjlh2V787BTQRMgHJkARAApoXrvxP3DIfjCNOtXU/P dwMShKdX/RlSs5PfunV1wbKP8herXHrvQdFVqECaTSxmlhzbk8X0PkY9gcVaU2O49T3qsOd1 cHeF52YFGEt0LhsBeMjgNX5uZ1V76r8gyeVlFpWWb0SIwJUBHrDXexF67upeRb2vdHBjYDNe ySn+0B7gFEqvVmZu+LadudDp6kQLjatFvHQHUSGNshBnkkcaTbiI9Pst0GCc2aiznBiPPA2W QxAPlPRh3OGTsn5THADmbjqY6FEMLasVX8DSCblMvLwNeO/8SxziBidhqLpJCqdQRWHku5Xx gIkGeKOz5OLDvXHWJyafrEYjjkS6Ak6B5z6svKliClWnjHQcjlPzyoFFgKTEfcqDxCj4RY0D 0DgtFD0NfyeOidrSB/SzTe2hwryQE3rpSiqo+0cGdzh4yAHKYJ+UrXZ4p93ZhjGfKD1xlrNY DlWyW9PGmbvqFuDmiIAQf9WD/wzEfICc+F+uDDI+uYkRxUFp92ykmdhDEFg1yjYsU8iGU69a Hyvhq36z4zctvbqhRNzOWB1bVJ/dIMDvsExGcXQVDIT7sDNXv0wE3jKSKpp7NDG1oXUXL+2+ SF99Kjy753AbQSAmH617fyBNwhJWvQYg+mUvPpiGOtses9EXUI3lS4v0MEaPG43flEs1UR+1 rpFQWVHo1y1OO+sAEQEAAcLBfAQYAQgAJgIbDBYhBH43kqnYrPfWM7wViO2X6Q5iqn40BQJm Is58BQkdZAsMAAoJEO2X6Q5iqn40Q68QAJ9GubS/ej30Vc4idoZdc0IyMcL7kQJbMohF+Tyn ZE+TGn9WvzP10yLyzoI0vNlcNfP92d2MS//pFjOuANb5mwyiEYA+rDZIdS4ZZpHxCs2sxMC4 afLCf3kv4aMnTeBvb9na403dlczz9cAacvsmniSFdpb1+BzMpYbybglU5oYMGhYT2nnCRjXN 6S2nKYt4mjJeeOuxHrdeqQQdVBNYeNfTcPePeqvZ2+bD6u9yxZtaV+wxdpqglosQvjqhOYz7 h50/ZTSq70/npoCq44TzdJKttaYvlW6ziRz0g4RRAqZyoxjYXiy5qj8r8zXJuB11ApZCGuKn /usbji9RYbflAhxFeh4LMmpDVi6BrF30b73Md59K7PuEKN1NxzlWiqqQHZZ9momN0GXLPcGq 4uyfq7yVEy7wP5PMOh6oqscKklE3gFQtq0P1Ki0xqdF6Fq5LPJc+0Db2CYkVIy7Xaa/f74I3 sOfQfEeDylVXR5iDfUJEYv/0DYhOr7q5/0b1kh3M4wkrB4C5jVNHjIIj+RsAK90c3t38OhAl jiSN7Bkwy24Afy8eIu6wWzvhnsQGpZPB+IffmxT1wkTy8UxZKjUWV0C82iphVgCUUi2f9sDV Q/tNcwVWmOS+gdv9Wk6tdGeM+Ee+Qs6YG05jcSoajzF0TL07ajLcayRq2j1Os2CtQ8qu Organization: UCLA Computer Science Department In-Reply-To: <86iklwutmx.fsf@shell.gmplib.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 78476 Cc: 78476@debbugs.gnu.org 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: -1.0 (-) On 5/19/25 15:23, Torbj=C3=B6rn Granlund wrote: > Paul Eggert writes: >=20 > before my Saturday coreutils commit[1], this code in prime_p: >=20 > /* We have already cast out small primes. */ > if (n < (wide_uint) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME) > return true; >=20 > was incorrect. >=20 > Why is it incorrect? Because when you run it on a machine with 128-bit unsigned long (or=20 whatever type is being used for the word size), N can be 155 and 155 is=20 not prime. > I actually find it extremely worrying that a change is motivated by "We > don't know why the code misbehaves when wide_uint is wider;" and then > the presumed bug is masked with a pretty questionable change. Really? The change is questionable only because it hurts performance when the=20 word size exceeds 64 bits. It's not questionable on correctness grounds.=20 And it doesn't affect performance in the usual 64-bit case. > How about debugging it? Yes, that'd be better and that's why I filed the bug report. However,=20 what's a good way to debug it? My *guess* is that prime_p is sometimes called in a context where it's=20 already guaranteed that we have cast out small primes, and it's=20 sometimes called in a context where there is no such guarantee. The=20 latter context is the bug. It appears that this context can occur in=20 factor_using_pollard_rho (n, a, factors), which contains this code after=20 the "factor_found:" label: if (!prime_p (g)) factor_using_pollard_rho (g, a + 1, factors); else factor_insert (factors, g); If I understand things correctly, there's no guarantee here that G=20 cannot be a small prime, which means factor_insert can be called even=20 when G is not prime, and that is a bug. > Let's use our time and effort on improving things for the word we live > in. That would be reasonable if we knew that the existing code works for all=20 cases in 64 bits. Is there some way to show that? (We can't exhaustively=20 test it.) Even a comment would be helpful. And, if the code is not designed to=20 work with any word size other than 64 bits, there should be a static=20 check to that effect. (There's already a static check that words must be=20 at least 64 bits.) From debbugs-submit-bounces@debbugs.gnu.org Tue May 20 03:04:29 2025 Received: (at 78476) by debbugs.gnu.org; 20 May 2025 07:04:29 +0000 Received: from localhost ([127.0.0.1]:52855 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uHH1Y-0006OM-QQ for submit@debbugs.gnu.org; Tue, 20 May 2025 03:04:29 -0400 Received: from martin.gmplib.org ([130.242.124.102]:64242 helo=shell.gmplib.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uHH1W-0006OC-4P for 78476@debbugs.gnu.org; Tue, 20 May 2025 03:04:26 -0400 Received: by shell.gmplib.org (Postfix, from userid 1001) id 595D1957D; Tue, 20 May 2025 09:04:24 +0200 (CEST) From: =?utf-8?Q?Torbj=C3=B6rn_Granlund?= To: Paul Eggert Subject: Re: bug#78476: GNU 'factor' problems with 128-bit word In-Reply-To: <7bbe9797-48c0-435a-8334-85c2ef817955@cs.ucla.edu> (Paul Eggert's message of "Mon, 19 May 2025 15:51:12 -0700") References: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> <868qmuthhm.fsf@shell.gmplib.org> <5fe8b1c3-1dc6-4863-9892-ab4fef74fb8e@cs.ucla.edu> <86iklwutmx.fsf@shell.gmplib.org> <7bbe9797-48c0-435a-8334-85c2ef817955@cs.ucla.edu> Date: Tue, 20 May 2025 09:04:24 +0200 Message-ID: <86sekzvk3r.fsf@shell.gmplib.org> User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.4 (/) X-Debbugs-Envelope-To: 78476 Cc: 78476@debbugs.gnu.org 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: -1.0 (-) Paul Eggert writes: > if (n < (wide_uint) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME) > return true; > was incorrect. > Why is it incorrect? Because when you run it on a machine with 128-bit unsigned long (or whatever type is being used for the word size), N can be 155 and 155 is not prime. I thought you said that test was wrong, and I asked what was wrong with it, and why did you make that test return false. Now I understand that you made the test return false in order to mask an underlying bug. Please don't do that! The change is questionable only because it hurts performance when the word size exceeds 64 bits. It's not questionable on correctness grounds. I cannot tell for sure that you change cannot coase other problems. Say, an infinite loop? (I will not lose sleep over that until somebody creates a computer with native 128-bit multiply hardware.) However, what's a good way to debug it? As a last resort, compare the execution for a working base type with one which fails? When do they diverge? Why do they diverge? I am too busy to take care of this. Sorry. The current factor.c code is becoming insanely complex. Contructs masking bugs triggered on hypothetical systems doesn't help with managing complexity. Preferably, this problem should be fully understood. If it can be argued that it is a real bug which affects real systems, it needs a clean fix. --=20 Torbj=C3=B6rn Please encrypt, key id 0xC8601622 From debbugs-submit-bounces@debbugs.gnu.org Fri May 23 03:07:49 2025 Received: (at 78476) by debbugs.gnu.org; 23 May 2025 07:07:49 +0000 Received: from localhost ([127.0.0.1]:44536 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uIMVR-0005IY-5M for submit@debbugs.gnu.org; Fri, 23 May 2025 03:07:49 -0400 Received: from mout.kundenserver.de ([212.227.126.133]:55463) by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1uIMVN-0005I0-Ae for 78476@debbugs.gnu.org; Fri, 23 May 2025 03:07:46 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bernhard-voelker.de; s=s1-ionos; t=1747984047; x=1748588847; i=mail@bernhard-voelker.de; bh=60bSQW8h9SA6W9eHH+kizzJQJ9Er9QVfgKQAwB3eil0=; h=X-UI-Sender-Class:Message-ID:Date:MIME-Version:Subject:To:Cc: References:From:In-Reply-To:Content-Type: Content-Transfer-Encoding:cc:content-transfer-encoding: content-type:date:from:message-id:mime-version:reply-to:subject: to; b=XrBd8hULeiuHd9UJg4YCT8UCm2xJIbzDHEFOiYzLqP2Hu3h0xdpSdoAQRJGjGnV/ GkAwDMs1pLoabY2hM8168mgAYokw5fomgMGdNhOLf6QahvJY6jXGoVcmw3cMO/2ZS vd6LFCpyS+iL4b8r3u9TCz6bTRCXtQq5yqQLs0AK+e+xZ3EM4NWfHSzOCSy1AFyN/ whvVqLqtntF8c/XZUrbT4rJhzVrpmSOCNYcuw7zgkwUm0Gle0DkqVWz1KYSy94S3z /mbp8sqdYn16+H2Fq85N84fa2aLrETKJaegCz9/1ilajRBGMt2Xb/0W0zksC+hPM3 4h9dMkm3GYScIgw0iw== X-UI-Sender-Class: 55c96926-9e95-11ee-ae09-1f7a4046a0f6 Received: from [192.168.101.10] ([91.49.79.180]) by mrelayeu.kundenserver.de (mreue010 [212.227.15.167]) with ESMTPSA (Nemesis) id 1MGzI3-1u60IG2dAx-004BXi; Fri, 23 May 2025 09:07:27 +0200 Message-ID: <3076bb4f-c857-40b1-9521-417b9d6955d6@bernhard-voelker.de> Date: Fri, 23 May 2025 09:07:26 +0200 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: bug#78476: GNU 'factor' problems with 128-bit word To: =?UTF-8?Q?Torbj=C3=B6rn_Granlund?= , Paul Eggert References: <567bb67d-7365-4709-b56c-5b0731bb1189@cs.ucla.edu> <868qmuthhm.fsf@shell.gmplib.org> <5fe8b1c3-1dc6-4863-9892-ab4fef74fb8e@cs.ucla.edu> <86iklwutmx.fsf@shell.gmplib.org> <7bbe9797-48c0-435a-8334-85c2ef817955@cs.ucla.edu> <86sekzvk3r.fsf@shell.gmplib.org> Content-Language: en-US From: Bernhard Voelker In-Reply-To: <86sekzvk3r.fsf@shell.gmplib.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: quoted-printable X-Provags-ID: V03:K1:KJBNgrbuMvGTwUQyhD97k2EiCPQ39+bPimg8Z5E/y9n18qko8Mu spnTJuX0mFgdgytBAuyIgk2NK8GCS+LMcJY8PlFZ6NNOjzWhoup+c3+3cMM/CSqj0v/JEKb ZTTXADWPm+G/dtInh39YQbVNFWCdk8YosSOMJKrm6h+WrXGe1qgu5Rj8nJDsERNdxlGQzvO ASvJFbJ4XCTLhzUhvCAjQ== X-Spam-Flag: NO UI-OutboundReport: notjunk:1;M01:P0:Ir9WRZNDb0Q=;2fsYToqklydopAEffusnZBoHlds i7eqIV5zn9a5aeZBb739wD9EYNruFKlkYUL2EB4ZKTmUzwOkQpJvDGDr/1KVyk7ohoTrP3Mi0 9SXMTRhf7oWCdzKNG4OAyvns4MS45MYiZvyqLvmyrFVzqIf2n3N82gaMLrIudV9CWBXmNtDbC 3Sw2UAIAns3kJClmLH21dAFNibAN9mW5JsKVcQAy8ZRIr6zboXoEp5QeaMwA+rhThLZh3O9/8 ZFxAMOJO2dhKtooe+EWk/Iy3thh0kSWeftkSCYQJ2N4DizSf5YIYtjQvbT9+z1QNEJxtirV8S y+Eqru1XmIhgWDUG6MbAqSCb1yZohYDjCmLRodudiQ+mJHmCR9329QzHKShz+JzSEq7KJ7z29 6c5q5enErQq5GDLWbe1brKd4GAVFrbapQiFB2gUFCNLNn79OKj/A3qNjX4xJ73Ei35gnttXLr 9id4iXPJrZyFWiuzsuJsVxjTrTVeqkcRIGvnMSjJNMsux8fk6IIQpk9XsAENJsYwmIGoYZBk7 mEWXJuGoMC7ns+htVwdTJahHPM4Iiy0G8YU6Th4WtiJK4PDkTWk2vyFmfC6RD9er7ef3/1OrB 9g3s6Jk7JMh2lzE8yEO+jCpMEX/Ixzt2wqzg2HbmPMzLr/c0En7PvJvULKrTboi17bqvNCLYk mJFSc0GuZuqZ9pjLYqmaMQEud7gk7WW6xRfLHLUsIRI4ZBgB6SQm8sbJ/EoI3TcQhMKUht9zk +gQN9POnyzqmebPg4vkl20TUM1fl6x73rdyYFvkPcAcEiCxG3QQAyocWFW/V7onkXjf7rJwwk cUEJ009SyPB4SlyLEaLg7OJd5GVWBj8pdEW+SlIVaKRx1HYudAUs+DEcR9UbBPtzgkFwAJSvE RPV8hhzTPruF4P0QWU79Mc+Av8ACLLO+qFzEuUja+3BdKz1mZ1UcDFYwi5QLVUHXXAg8xtjTj ch4frHfOSyQ0TlVX6K/0f44qAwUpQU8HrSYLWozyw9wgTyOQsoWrIv4ceYtg37ydKIeZ4QA3J MZ6UtZ4o5DPeQRfjkNFnYyrc88DJ3g4bzKNmbnyp33NPXlXt0BsZZYY6SbQxyge9n5nqcNng4 VPXlSnKBNuCbzPMiokfTxNFrfsPzZ2niU4SoAjxvBO2220BiFZ6THrf9WoBHwOOp9/d+eJzKk cG7sY/3hXZ4O3Zj9eMulYOLqyZ9SiDgJFzuTO9ufkfIbFsTHKGEG9RODcjdIV6AhaqIvJc5uQ jgK+WXRX+Sm1pJm4F8JVY9IUvt8eTWsEwbQ3cl5wl78zAkXuZlSYsrwmjVEiKihuXZK+jcpyu hW4vWHWyN2p3KxuN5cfR/Eo4SoihQ6LbfSzOJo2HX0tFW2iLkm8Oa06Fs5VwPP8GrywDFHHxH kIER8S6ImoPD0aUAJe+k0DFx8dBN/fjf4c3alhAf8WU+7K4XtyyrarrExx X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 78476 Cc: 78476@debbugs.gnu.org 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: -1.0 (-) On 5/20/25 09:04, Torbj=C3=B6rn Granlund wrote: > The current factor.c code is becoming insanely complex. Contructs > masking bugs triggered on hypothetical systems doesn't help with > managing complexity. If such hardware seems to be quite some time away, what about guarding the code for the ranges we know it to work, and throw an error - no matter whether at compile time or runtime - with a diagnostic to revisit the problem once such hardware will be available? Have a nice day, Berny