Package de.tilman_neumann.jml.factor.siqs

Class ModularSqrtsEngine

java.lang.Object

de.tilman_neumann.jml.factor.siqs.ModularSqrtsEngine

public class ModularSqrtsEngine
extends Object

Engine to compute the smallest modular sqrts for all elements of the prime base.

Author:

Tilman Neumann

Constructor Summary

Constructors

Constructor	Description
ModularSqrtsEngine()

Method Summary

Modifier and Type	Method	Description
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.

Methods inherited from class java.lang.Object

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

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