Package de.tilman_neumann.jml.modular

Class ModularSqrt_BB

java.lang.Object

de.tilman_neumann.jml.modular.ModularSqrt_BB

public class ModularSqrt_BB
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. Implementation for all-BigInteger arguments.

Author:

Tilman Neumann

Constructor Summary

Constructors

Constructor	Description
ModularSqrt_BB()

Method Summary

Modifier and Type	Method	Description
BigInteger	modularSqrt(BigInteger n, BigInteger p)	Compute the modular sqrt t with t^2 == n (mod p).
BigInteger	modularSqrtModPower(BigInteger n, BigInteger power, BigInteger last_power, 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].
BigInteger	modularSqrtModSquare_v01(BigInteger n, BigInteger p, BigInteger pSquare)	Simplest algorithm to compute solutions u of u^2 == n (mod p^2).
BigInteger	modularSqrtModSquare_v02(BigInteger n, BigInteger p, 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 Detail

ModularSqrt_BB

public ModularSqrt_BB()

Method Detail

modularSqrt

public BigInteger modularSqrt(BigInteger n,
                              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) = 1

p - odd prime

Returns:

(the smaller) sqrt of n (mod p)

modularSqrtModSquare_v01

public BigInteger modularSqrtModSquare_v01(BigInteger n,
                                           BigInteger p,
                                           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) = 1

p - an odd prime with p==3 (mod 4)

pSquare - p^2

Returns:

(the smaller) sqrt of n (mod p^2)

modularSqrtModSquare_v02

public BigInteger modularSqrtModSquare_v02(BigInteger n,
                                           BigInteger p,
                                           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) = 1

p - an odd prime with p==3 (mod 4)

pSquare - p^2

Returns:

(the smaller) sqrt of n (mod p^2)

modularSqrtModPower

public BigInteger modularSqrtModPower(BigInteger n,
                                      BigInteger power,
                                      BigInteger last_power,
                                      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^exponent

last_power - p^(exponent-1)

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

Returns:

sqrt of n (mod p^exponent)