Package de.tilman_neumann.jml.gcd
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
Computes gcd, a = (1/x) mod y and b = (1/y) mod x.- Parameters:
x
-y
-- Returns:
- {gcd, a, b}
-
computeHalf
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
-