Package de.tilman_neumann.jml.modular
Class ModularSqrt31
java.lang.Object
de.tilman_neumann.jml.modular.ModularSqrt31
public class ModularSqrt31
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 ModularSqrt31()
-
Method Summary
Modifier and Type Method Description int
modularSqrt(int n, int p)
Compute the modular sqrt t with t^2 == n (mod p).int
modularSqrtModPower(int 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
-
ModularSqrt31
public ModularSqrt31()
-
-
Method Details
-
modularSqrt
public int modularSqrt(int 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 smaller) sqrt of n (mod p)
-
modularSqrtModPower
public int modularSqrtModPower(int 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
- a positive integer having Jacobi(n|p) = 1power
- p^exponentlast_power
- p^(exponent-1)t
- solution of t^2 == n (mod p)- Returns:
- sqrt of n (mod p^exponent)
-