Package de.tilman_neumann.jml.factor.base.congruence

Class AQPair

java.lang.Object
de.tilman_neumann.jml.factor.base.congruence.AQPair
Direct Known Subclasses:
Partial, Smooth_Simple
public abstract class AQPair
extends java.lang.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.

  • Constructor Summary

    Constructors
    Constructor Description
    AQPair​(java.math.BigInteger A, SortedIntegerArray smallFactors)
    Full constructor.

  • Method Summary

    Modifier and Type Method Description
    boolean equals​(java.lang.Object obj)
    hashCode() and equals() must be based on A to avoid duplicates.
    java.math.BigInteger getA()  
    abstract SortedMultiset<java.lang.Long> getAllQFactors()  
    abstract int getNumberOfLargeQFactors()  
    protected SortedMultiset<java.lang.Long> getSmallQFactors()
    Building block to implement the method above.
    int hashCode()
    hashCode() and equals() must be based on A to avoid duplicates.
    java.lang.String toString()  

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • AQPair

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

  • Method Details

    • getA

      public java.math.BigInteger getA()

    • getAllQFactors

      public abstract SortedMultiset<java.lang.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<java.lang.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 java.lang.Object

    • equals

      public boolean equals​(java.lang.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 java.lang.Object

    • toString

      public java.lang.String toString()
      Overrides:
      toString in class java.lang.Object