GNU bug report logs - #59636
prime [ factor ] utility very slow in factoring the square of a prime

Previous Next

To reply to this bug, email your comments to 59636 AT debbugs.gnu.org.

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

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

From: "Jason C. Kwan" <jasonckwan <at> yahoo.com>
To: bug-coreutils <at> gnu.org
Subject: prime [ factor ] utility very slow in factoring the square of a prime
Date: Sun, 27 Nov 2022 14:48:16 +0000 (UTC)

[Message part 1 (text/plain, inline)]

The test case is 
      49,456,902,806,087,647,575,555,655,201
a prime that is approx. 95.3-bits in size, plus the direct squaring of it, ascalculated by gnu-bc 
    (see full text below for host system info,      versioning details, and command line      statements used to perform this test. 
      xargs used is macOS 12.6 built-in one instead of GNU one)
The base prime has a hex representation is 
      0x 9FCD CA89 5696 76C0 0B03 4621

The issue being that while it took the [ factor ] utility just shy of 4.8ms to complete its primality checks, and confirmed the first input is indeed prime, 
attempting to factor the direct squaring of the same prime resultedin the task being timed out after 1200 seconds, or 20 minutes.
Perhaps there is an opportunity to optimize it by    
   - performing a quick square/square-root check for large inputs   

     (e.g. >= 2^127, per "info factor") 
before routing it to what "info factor" refers to as "the slower algorithm" ?
Maybe also add one more cube/cube-root quick check if the relative cost to system resources isn't particularly material ?

RegardsJason

% uname -mrsv 
      Darwin 21.6.0 Darwin Kernel Version 21.6.0:       Mon Aug 22 20:19:52 PDT 2022; 
      root:xnu-  8020.140.49~2/RELEASE_ARM64_T6000 arm64
% gdate  gfactor --version       bc --version

      Sun Nov 27 03:34:47 EST 2022
---------------------------------------------
factor (GNU coreutils) 9.1Copyright (C) 2022 Free Software Foundation, Inc.License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>.This is free software: you are free to change and redistribute it.There is NO WARRANTY, to the extent permitted by law.
---------------------------------------------
Written by Paul Rubin, Torbjörn Granlund, and Niels Möller.bc 1.06Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
---------------------------------------------
  echo ' x = 49456902806087647575555655201 ; x^1 ; x^2 ; ' |   bc                                                       |   xargs -t -n 1 -P 2 timeout --foreground 1200 gfactor     | 
  awk '  function ep16(__,_,___) {       return substr("",        (___ = RS) * (RS = "\n") * \           ( (__ = " gdate +\"%s%6N\" ") | getline _),        close( __) ^ (RS = ___))_   }
  function timer(_,__) {       return \      +_ < (__= ep16())^(_<_) \      ?   __\      : (__-_) /\        ( ( (_+=_^=_<_)+_*_*_)^(_ +_+  _)*\            ( _++^!++_ +    _^-(_ +_+--_) ) )  }  BEGIN {  __ = timer(_ = _<_)        OFMT = "%.25g"     CONVFMT = "%.250g"          _^=_  }  ($++NF = sprintf("%.13f", timer(__)))^!_ +\     ($++NF =        log( $_ ) / log(_+_))^!_' 
---------------------------------------------
timeout --foreground 1200 gfactor 49456902806087647575555655201timeout --foreground 1200 gfactor 2445985235170800228886882843536511572299116327852398350401
49456902806087647575555655201: 49456902806087647575555655201 0.0047909999999 95.320158551927676171544590033590793609619140625

[Message part 2 (text/html, inline)]

Previous Next

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