Class ModularSqrt

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

public class ModularSqrt
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
    ModularSqrt()  
  • Method Summary

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

    • ModularSqrt

      public ModularSqrt()
  • Method Details

    • modularSqrt

      public int modularSqrt​(java.math.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​(java.math.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)