q: Improved |
initial writing: 2004-12-31 last updated: 2005-02-22 |
q: has been improved to succeed much more often. The algorithm is based on the work of Cliff Reiter on elliptic curve and other auxiliary factoring techniques as detailed in http://ww2.lafayette.edu/~reiterc/j/vector/factor_ecj.html. The algorithm starts to lose effectiveness on hard factorizations (that is, involving just two primes) of numbers with 25 digits. For example:
x=: 8191068869406862657520989247075401x q: x 8191068869406862657520989247075401 q: x* p: 1e7 179424691 8191068869406862657520989247075401 q: x*x |break | q:x*x
The last example q: x*x ran for a very long time and was interrupted by ctrl-break.
y=: 5726527968877x q: y 5726527968877 q: y*y |nonce error | q:y*y
A nonce error is signalled if a composite number can not be factored by the current implementation.