Package de.tilman_neumann.jml.factor.cfrac

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&Brillhart intending to factor the 7.th Fermat number F7 with 39 digits (~130 bits). Now this number can be factored in about three seconds. Stopping criterion for a single k: after complete period or at a maximum number of iterations. Since 2017-09 Knuth-Schroeppel multipliers have been implemented, too.

Author:

Tilman Neumann

Field Summary

Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

DEFAULT, NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit

Constructor Summary

Constructors

Constructor	Description
CFrac(boolean use_all_i, int stopRoot, float stopMult, float C, float maxQRestExponent, TDiv_CF auxFactorizer, int extraCongruences, MatrixSolver matrixSolver, int ks_adjust)	Standard constructor.

Method Summary

Modifier and Type	Method	Description
BigInteger	findSingleFactor(BigInteger N)	Test the current N.
String	getName()
static void	main(String[] args)	Standalone test.
protected void	test()

Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

factor, factor, searchFactors

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CFrac

public CFrac(boolean use_all_i,
             int stopRoot,
             float stopMult,
             float C,
             float maxQRestExponent,
             TDiv_CF auxFactorizer,
             int extraCongruences,
             MatrixSolver matrixSolver,
             int ks_adjust)

Standard constructor.

Parameters:

use_all_i -

stopRoot - order of the root to compute the maximum number of iterations

stopMult - multiplier to compute the maximum number of iterations

C - multiplier for prime base size

maxQRestExponent -

auxFactorizer - the algorithm to find smooth Q

extraCongruences - the number of surplus congruences we collect to have a greater chance that the equation system solves.

matrixSolver - matrix solver for the smooth congruence equation system

ks_adjust -

Method Detail

getName

public String getName()

Specified by:

getName in class FactorAlgorithm

Returns:

The name of the algorithm, possibly including important parameters.

findSingleFactor

public BigInteger findSingleFactor(BigInteger N)

Test the current N.

Specified by:

findSingleFactor in class FactorAlgorithm

Returns:

factor, or null if no factor was found.

test

protected void test()
             throws FactorException

Throws:

FactorException

main

public static void main(String[] args)

Standalone test. Test numbers: F7 = 340282366920938463463374607431768211457

Parameters:

args - ignored