Package de.tilman_neumann.jml.modular
Class ModularSqrt_BB
java.lang.Object
de.tilman_neumann.jml.modular.ModularSqrt_BB
public class ModularSqrt_BB
extends java.lang.Object
Compute modular sqrts t with t^2 == n (mod p) and u with u^2 == n (mod p^e) using Tonelli-Shanks' algorithm.
Implementation for all-BigInteger arguments.
-
Constructor Summary
Constructors Constructor Description ModularSqrt_BB()
-
Method Summary
Modifier and Type Method Description java.math.BigInteger
modularSqrt(java.math.BigInteger n, java.math.BigInteger p)
Compute the modular sqrt t with t^2 == n (mod p).java.math.BigInteger
modularSqrtModPower(java.math.BigInteger n, java.math.BigInteger power, java.math.BigInteger last_power, java.math.BigInteger t)
General solution of u^2 == n (mod p^exponent), well explained in [http://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power, Gottfried Barthel].java.math.BigInteger
modularSqrtModSquare_v01(java.math.BigInteger n, java.math.BigInteger p, java.math.BigInteger pSquare)
Simplest algorithm to compute solutions u of u^2 == n (mod p^2).java.math.BigInteger
modularSqrtModSquare_v02(java.math.BigInteger n, java.math.BigInteger p, java.math.BigInteger pSquare)
A faster version to compute solutions u of u^2 == n (mod p^2), doing modular arithmetics (mod p) only, which is an application of lifting via Hensels lemma.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
ModularSqrt_BB
public ModularSqrt_BB()
-
-
Method Details
-
modularSqrt
public java.math.BigInteger modularSqrt(java.math.BigInteger n, java.math.BigInteger p)Compute the modular sqrt t with t^2 == n (mod p). Uses Tonelli-Shanks algorithm for p==1 (mod 8), Lagrange's formula for p==3, 7 (mod 8) and another special formula for p==5 (mod 8).- Parameters:
n
- a positive integer having Jacobi(n|p) = 1p
- odd prime- Returns:
- (the smaller) sqrt of n (mod p)
-
modularSqrtModSquare_v01
public java.math.BigInteger modularSqrtModSquare_v01(java.math.BigInteger n, java.math.BigInteger p, java.math.BigInteger pSquare)Simplest algorithm to compute solutions u of u^2 == n (mod p^2). This is the first proposition in [Pomerance 1985: The Quadratic Sieve Factoring Algorithm, p. 178]. Works only for p==3 (mod 4).- Parameters:
n
- a positive integer having Jacobi(n|p) = 1p
- an odd prime with p==3 (mod 4)pSquare
- p^2- Returns:
- (the smaller) sqrt of n (mod p^2)
-
modularSqrtModSquare_v02
public java.math.BigInteger modularSqrtModSquare_v02(java.math.BigInteger n, java.math.BigInteger p, java.math.BigInteger pSquare)A faster version to compute solutions u of u^2 == n (mod p^2), doing modular arithmetics (mod p) only, which is an application of lifting via Hensels lemma. This is the second proposition in [Pomerance 1985], but not fully out-formulated there. This implementation was accomplished following [Silverman 1987: The Multiple Polynomial Quadratic Sieve, p. 332]. Works only for p==3 (mod 4).- Parameters:
n
- a positive integer having Jacobi(n|p) = 1p
- an odd prime with p==3 (mod 4)pSquare
- p^2- Returns:
- (the smaller) sqrt of n (mod p^2)
-
modularSqrtModPower
public java.math.BigInteger modularSqrtModPower(java.math.BigInteger n, java.math.BigInteger power, java.math.BigInteger last_power, java.math.BigInteger t)General solution of u^2 == n (mod p^exponent), well explained in [http://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power, Gottfried Barthel]. Works for any odd p with t^2 == n (mod p) having solution t>0.- Parameters:
n
-power
- p^exponentlast_power
- p^(exponent-1)t
- solution of t^2 == n (mod p)- Returns:
- sqrt of n (mod p^exponent)
-