Package de.tilman_neumann.jml.modular

Class ModularSqrt31

java.lang.Object

de.tilman_neumann.jml.modular.ModularSqrt31

public class ModularSqrt31
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
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 Detail

ModularSqrt31

public ModularSqrt31()

Method Detail

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) = 1

p - 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) = 1

power - p^exponent

last_power - p^(exponent-1)

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

Returns:

sqrt of n (mod p^exponent)