Class ModularSqrt_BB

java.lang.Object
de.tilman_neumann.jml.modular.ModularSqrt_BB

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

    Constructors
    Constructor Description
    ModularSqrt_BB()  
  • Method Summary

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

    • ModularSqrt_BB

      public ModularSqrt_BB()
  • Method Details

    • modularSqrt

      public java.math.BigInteger modularSqrt​(java.math.BigInteger n, java.math.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 java.math.BigInteger modularSqrtModSquare_v01​(java.math.BigInteger n, java.math.BigInteger p, java.math.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 java.math.BigInteger modularSqrtModSquare_v02​(java.math.BigInteger n, java.math.BigInteger p, java.math.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 java.math.BigInteger modularSqrtModPower​(java.math.BigInteger n, java.math.BigInteger power, java.math.BigInteger last_power, java.math.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)