Class CFrac
java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.cfrac.CFrac
public class CFrac extends FactorAlgorithm
CFrac = Shanks' SQUFOF algorithm + carry along continuant recurrence + collect smooth relations + LinAlg solver.
The original CFrac was implemented by Morrison and Brillhart intending to factor the 7.th Fermat number F7 with 39 digits (~130 bits). Now this number can be factored single-threaded in a second or a few. Since 2017-09 Knuth-Schroeppel multipliers have been implemented, too. Stopping criterion for a single multiplier k: after complete period or at a maximum number of iterations. Switching multipliers seems to improve performance for small factor arguments (<60 bits) only; nonetheless we keep the code for possible further experiments.
The original CFrac was implemented by Morrison and Brillhart intending to factor the 7.th Fermat number F7 with 39 digits (~130 bits). Now this number can be factored single-threaded in a second or a few. Since 2017-09 Knuth-Schroeppel multipliers have been implemented, too. Stopping criterion for a single multiplier k: after complete period or at a maximum number of iterations. Switching multipliers seems to improve performance for small factor arguments (<60 bits) only; nonetheless we keep the code for possible further experiments.
-
Field Summary
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
-
Constructor Summary
Constructors Constructor Description CFrac(boolean use_all_i, int stopRoot, float stopMult, float C, float smoothBoundExponent, TDiv_CF auxFactorizer, MatrixSolver matrixSolver, int ks_adjust)
Standard constructor. -
Method Summary
Modifier and Type Method Description java.math.BigInteger
findSingleFactor(java.math.BigInteger N)
Test the current N.java.lang.String
getName()
static void
main(java.lang.String[] args)
Standalone test.protected java.math.BigInteger
test()
Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
factor, factor, getDefault, searchFactors
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
CFrac
public CFrac(boolean use_all_i, int stopRoot, float stopMult, float C, float smoothBoundExponent, TDiv_CF auxFactorizer, MatrixSolver matrixSolver, int ks_adjust)Standard constructor.- Parameters:
use_all_i
-stopRoot
- order of the root to compute the maximum number of iterationsstopMult
- multiplier to compute the maximum number of iterationsC
- multiplier for prime base sizesmoothBoundExponent
-auxFactorizer
- the algorithm to find smooth QmatrixSolver
- matrix solver for the smooth congruence equation systemks_adjust
-
-
-
Method Details
-
getName
public java.lang.String getName()- Specified by:
getName
in classFactorAlgorithm
- Returns:
- The name of the algorithm, possibly including important parameters.
-
findSingleFactor
public java.math.BigInteger findSingleFactor(java.math.BigInteger N)Test the current N.- Specified by:
findSingleFactor
in classFactorAlgorithm
- Parameters:
N
- number to be factored.- Returns:
- factor, or null if no factor was found.
-
test
protected java.math.BigInteger test() -
main
public static void main(java.lang.String[] args)Standalone test. Test numbers: F7 = 340282366920938463463374607431768211457- Parameters:
args
- ignored
-