Package de.tilman_neumann.jml.modular

Class ModularSqrt

java.lang.Object

de.tilman_neumann.jml.modular.ModularSqrt

public class ModularSqrt
extends Object

Compute modular sqrts t with t^2 == n (mod p) and u with u^2 == n (mod p^e) using Tonelli-Shanks' algorithm.

Author:

Tilman Neumann

Constructor Summary

Constructors

Constructor	Description
ModularSqrt()

Method Summary

Modifier and Type	Method	Description
int	modularSqrt(BigInteger n, int p)	Compute the modular sqrt t with t^2 == n (mod p).
int	modularSqrtModPower(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 Detail

ModularSqrt

public ModularSqrt()

Method Detail

modularSqrt

public int modularSqrt(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) = 1

p - odd prime

Returns:

the modular sqrt t

modularSqrtModPower

public int modularSqrtModPower(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^exponent

last_power - p^(exponent-1)

t - solution of t^2 == n (mod p)

Returns:

sqrt of n (mod p^exponent)