Class EEA63

java.lang.Object
de.tilman_neumann.jml.gcd.EEA63

public class EEA63
extends java.lang.Object
Extended Euclidean algorithm, mostly used to compute the modular inverse of x (mod y). Extends [Crandall/Pomerance 2005: "Prime numbers", algorithm 2.1.4] to let modInverse(x, y) work on negative x, too. Long version.
  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    static class  EEA63.Result  
  • Constructor Summary

    Constructors
    Constructor Description
    EEA63()  
  • Method Summary

    Modifier and Type Method Description
    EEA63.Result computeAll​(long x, long y)
    Computes gcd, a = (1/x) mod y and b = (1/y) mod x.
    EEA63.Result computeHalf​(long x, long y)
    Computes only gcd and a = (1/x) mod y.
    long modularInverse​(long a, long p)
    Compute the modular inverse x of a mod p, i.e.
    long modularInverse_v1​(long x, long y)
    Computes only the modular inverse a = (1/x) mod y.
    long modularInverse_v2​(long a, long modulus)
    Slightly faster modular inverse initializing variables with first iteration and needing one step less at the end.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • EEA63

      public EEA63()
  • Method Details

    • computeAll

      public EEA63.Result computeAll​(long x, long y)
      Computes gcd, a = (1/x) mod y and b = (1/y) mod x.
      Parameters:
      x -
      y -
      Returns:
      {gcd, a, b}
    • computeHalf

      public EEA63.Result computeHalf​(long x, long y)
      Computes only gcd and a = (1/x) mod y.
      Parameters:
      x -
      y -
      Returns:
      {gcd, a, b=-1 (undefined)}
    • modularInverse_v1

      public long modularInverse_v1​(long x, long y)
      Computes only the modular inverse a = (1/x) mod y.
      Parameters:
      x -
      y -
      Returns:
      (1/x) mod y
    • modularInverse_v2

      public long modularInverse_v2​(long a, long modulus)
      Slightly faster modular inverse initializing variables with first iteration and needing one step less at the end. Adapted from R.D.Silverman's single_modinv2(), see http://www.mersenneforum.org/showthread.php?t=12963&page=2, post #16.
      Parameters:
      a -
      modulus -
      Returns:
      (1/a) mod modulus
    • modularInverse

      public long modularInverse​(long a, long p)
      Compute the modular inverse x of a mod p, i.e. x = (1/a) mod p. Taken from Ben Buhrow's tinyecm.c and modified to work for a<0 and a>=p, too. Optimal performance is achieved by 6 "if's" in Java, compared to 9 "if's" in C. Significantly faster than the versions above.
      Parameters:
      a -
      p - modulus
      Returns:
      (1/a) mod p