Package de.tilman_neumann.jml.gcd

Class EEA63

  • public class EEA63
extends 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.
    Author:
    Tilman Neumann

    • Constructor Detail

      • EEA63

        public EEA63()

    • Method Detail

      • 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