Class AQPair

  • Direct Known Subclasses:
    Partial, Smooth_Simple

    public abstract class AQPair
    extends Object
    An elementary smooth or partially smooth congruence A^2 == Q (mod N). Elementary means that only one (A,Q) pair is involved. Factoring large numbers will produce millions of partials, and their memory demands dominate the memory consumption of the whole quadratic sieve algorithm. To store them as efficiently as possible, large factors are added by subclasses. The estimated memory requirement of the fields in this class is 240 byte; adding 16 bytes for its own object header gives around 256 byte.
    Author:
    Tilman Neumann
    • Constructor Detail

      • AQPair

        public AQPair​(BigInteger A,
                      SortedIntegerArray smallFactors)
        Full constructor.
        Parameters:
        A -
        smallFactors - small factors of Q
    • Method Detail

      • getAllQFactors

        public abstract SortedMultiset<Long> getAllQFactors()
        Returns:
        all Q-factors with exponents. This method is only called in the final test of null vectors found by the smooth solver; but then it is needed for a whole bunch of AQPairs.
      • getSmallQFactors

        protected SortedMultiset<Long> getSmallQFactors()
        Building block to implement the method above.
        Returns:
        SortedMultiset containing all small factors of Q
      • getNumberOfLargeQFactors

        public abstract int getNumberOfLargeQFactors()
        Returns:
        the total number of large factors of Q in this AQPair.
      • hashCode

        public int hashCode()
        hashCode() and equals() must be based on A to avoid duplicates. Q is not required, not even in CFrac.
        Overrides:
        hashCode in class Object
      • equals

        public boolean equals​(Object obj)
        hashCode() and equals() must be based on A to avoid duplicates. Q is not required, not even in CFrac.
        Overrides:
        equals in class Object