Package de.tilman_neumann.jml.factor.tdiv

Class TDiv63Inverse

  • public class TDiv63Inverse
extends FactorAlgorithm
    Trial division factor algorithm replacing division by multiplications. Instead of dividing N by consecutive primes, we store the reciprocals of those primes, too, and multiply N by those reciprocals. Only if such a result is near to an integer we need to do a division. Assuming that we want to identify "near integers" with a precision of 2^-d. Then the approach works for primes p if bitLength(p) >= bitLength(N) - 53 + d. For some unknown reason, storing and reusing the quotient q = (long) (N*r + DISCRIMINATOR) only helps in TDiv31Inverse but not in TDiv63Inverse.

    • Constructor Detail

      • TDiv63Inverse

        public TDiv63Inverse​(int factorLimit)
        Create a trial division algorithm that is capable of finding factors up to factorLimit.
        Parameters:
        factorLimit -

    • Method Detail

      • getName

        public String getName()
        Specified by:
        getName in class FactorAlgorithm
        Returns:
        The name of the algorithm, possibly including important parameters.

      • setTestLimit

        public TDiv63Inverse setTestLimit​(int pLimit)
        Set the upper limit of primes to be tested.
        Parameters:
        pLimit - the limit; must be smaller than the factorLimit parameter passed to the constructor
        Returns:
        this
        Throws:
        IllegalStateException - if pLimit > factorLimit

      • findSingleFactor

        public BigInteger findSingleFactor​(BigInteger N)
        Find a single factor of the given N, which is composite and odd. This implementation will return 1 if the smallest factor of N is greater than pLimit.
        Specified by:
        findSingleFactor in class FactorAlgorithm
        Returns:
        factor

      • findSingleFactor

        public int findSingleFactor​(long N)

      • main

        public static void main​(String[] args)
        Test.
        Parameters:
        args - ignored