Package de.tilman_neumann.jml.modular
Class ModularSqrt
java.lang.Object
de.tilman_neumann.jml.modular.ModularSqrt
public class ModularSqrt
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.
-
Constructor Summary
Constructors Constructor Description ModularSqrt()
-
Method Summary
Modifier and Type Method Description int
modularSqrt(java.math.BigInteger n, int p)
Compute the modular sqrt t with t^2 == n (mod p).int
modularSqrtModPower(java.math.BigInteger n, int power, int last_power, int 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].Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
ModularSqrt
public ModularSqrt()
-
-
Method Details
-
modularSqrt
public int modularSqrt(java.math.BigInteger n, int 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 modular sqrt t
-
modularSqrtModPower
public int modularSqrtModPower(java.math.BigInteger n, int power, int last_power, int 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. Implementation for arguments having int solutions.- Parameters:
n
-power
- p^exponentlast_power
- p^(exponent-1)t
- solution of t^2 == n (mod p)- Returns:
- sqrt of n (mod p^exponent)
-