diff options
Diffstat (limited to 'core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid')
-rw-r--r-- | core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/BigIntEuclidean.java | 54 | ||||
-rw-r--r-- | core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/IntEuclidean.java | 51 |
2 files changed, 105 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/BigIntEuclidean.java b/core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/BigIntEuclidean.java new file mode 100644 index 00000000..b5af2ec5 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/BigIntEuclidean.java @@ -0,0 +1,54 @@ +package org.bouncycastle.pqc.math.ntru.euclid; + +import java.math.BigInteger; + +/** + * Extended Euclidean Algorithm in <code>BigInteger</code>s + */ +public class BigIntEuclidean +{ + public BigInteger x, y, gcd; + + private BigIntEuclidean() + { + } + + /** + * Runs the EEA on two <code>BigInteger</code>s<br/> + * Implemented from pseudocode on <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">Wikipedia</a>. + * + * @param a + * @param b + * @return a <code>BigIntEuclidean</code> object that contains the result in the variables <code>x</code>, <code>y</code>, and <code>gcd</code> + */ + public static BigIntEuclidean calculate(BigInteger a, BigInteger b) + { + BigInteger x = BigInteger.ZERO; + BigInteger lastx = BigInteger.ONE; + BigInteger y = BigInteger.ONE; + BigInteger lasty = BigInteger.ZERO; + while (!b.equals(BigInteger.ZERO)) + { + BigInteger[] quotientAndRemainder = a.divideAndRemainder(b); + BigInteger quotient = quotientAndRemainder[0]; + + BigInteger temp = a; + a = b; + b = quotientAndRemainder[1]; + + temp = x; + x = lastx.subtract(quotient.multiply(x)); + lastx = temp; + + temp = y; + y = lasty.subtract(quotient.multiply(y)); + lasty = temp; + } + + BigIntEuclidean result = new BigIntEuclidean(); + result.x = lastx; + result.y = lasty; + result.gcd = a; + return result; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/IntEuclidean.java b/core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/IntEuclidean.java new file mode 100644 index 00000000..3ada3d4e --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/math/ntru/euclid/IntEuclidean.java @@ -0,0 +1,51 @@ +package org.bouncycastle.pqc.math.ntru.euclid; + +/** + * Extended Euclidean Algorithm in <code>int</code>s + */ +public class IntEuclidean +{ + public int x, y, gcd; + + private IntEuclidean() + { + } + + /** + * Runs the EEA on two <code>int</code>s<br/> + * Implemented from pseudocode on <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">Wikipedia</a>. + * + * @param a + * @param b + * @return a <code>IntEuclidean</code> object that contains the result in the variables <code>x</code>, <code>y</code>, and <code>gcd</code> + */ + public static IntEuclidean calculate(int a, int b) + { + int x = 0; + int lastx = 1; + int y = 1; + int lasty = 0; + while (b != 0) + { + int quotient = a / b; + + int temp = a; + a = b; + b = temp % b; + + temp = x; + x = lastx - quotient * x; + lastx = temp; + + temp = y; + y = lasty - quotient * y; + lasty = temp; + } + + IntEuclidean result = new IntEuclidean(); + result.x = lastx; + result.y = lasty; + result.gcd = a; + return result; + } +}
\ No newline at end of file |