Class ModularSqrtsEngine


  • public class ModularSqrtsEngine
    extends Object
    Engine to compute the smallest modular sqrts for all elements of the prime base.
    Author:
    Tilman Neumann
    • Constructor Detail

      • ModularSqrtsEngine

        public ModularSqrtsEngine()
    • Method Detail

      • computeTArray

        public int[] computeTArray​(int[] primesArray,
                                   int primeBaseSize,
                                   BigInteger kN)
        For all primes p in the prime base, find the modular sqrt's of kN (mod p), i.e. the t such that t^2 == kN (mod p). Since t^2 == kN (mod p) equals t^2 == (kN%p) (mod p), we can compute Tonelli-Shanks in all-integer arguments. For SIQS this is no big improvement though, because Tonelli-Shanks is not time-critical anyway.
        Parameters:
        primesArray -
        primeBaseSize -
        kN -
        Returns:
        the array of modular sqrt's t with t^2 == kN (mod p) for all p of the prime base