bug#59636: prime [ factor ] utility very slow in factoring the square of a prime

[Jason C. Kwan]

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