Class EEA31

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

public class EEA31
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. This int implementation is quite fast.
  • Nested Class Summary

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

    Constructors
    Constructor Description
    EEA31()  
  • Method Summary

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

    Methods inherited from class java.lang.Object

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

    • EEA31

      public EEA31()
  • Method Details

    • computeAll

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

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

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

      public int modularInverse​(int a, int 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