From 44047c3300d07192a67b1714084cc2d43b1e9bd9 Mon Sep 17 00:00:00 2001 From: Bo Xu Date: Tue, 2 Dec 2014 14:28:36 -0800 Subject: Remove unnecessary files in third_party/bigint This patch follows the initial check in of big integer library at https://pdfium.googlesource.com/pdfium/+/7504b3d87d6143661746d85c3c3e4052939b4e52 R=tsepez@chromium.org Review URL: https://codereview.chromium.org/773923002 --- third_party/bigint/BigIntegerAlgorithms.cc | 70 ------------------------------ 1 file changed, 70 deletions(-) delete mode 100644 third_party/bigint/BigIntegerAlgorithms.cc (limited to 'third_party/bigint/BigIntegerAlgorithms.cc') diff --git a/third_party/bigint/BigIntegerAlgorithms.cc b/third_party/bigint/BigIntegerAlgorithms.cc deleted file mode 100644 index 7edebda76a..0000000000 --- a/third_party/bigint/BigIntegerAlgorithms.cc +++ /dev/null @@ -1,70 +0,0 @@ -#include "BigIntegerAlgorithms.hh" - -BigUnsigned gcd(BigUnsigned a, BigUnsigned b) { - BigUnsigned trash; - // Neat in-place alternating technique. - for (;;) { - if (b.isZero()) - return a; - a.divideWithRemainder(b, trash); - if (a.isZero()) - return b; - b.divideWithRemainder(a, trash); - } -} - -void extendedEuclidean(BigInteger m, BigInteger n, - BigInteger &g, BigInteger &r, BigInteger &s) { - if (&g == &r || &g == &s || &r == &s) - throw "BigInteger extendedEuclidean: Outputs are aliased"; - BigInteger r1(1), s1(0), r2(0), s2(1), q; - /* Invariants: - * r1*m(orig) + s1*n(orig) == m(current) - * r2*m(orig) + s2*n(orig) == n(current) */ - for (;;) { - if (n.isZero()) { - r = r1; s = s1; g = m; - return; - } - // Subtract q times the second invariant from the first invariant. - m.divideWithRemainder(n, q); - r1 -= q*r2; s1 -= q*s2; - - if (m.isZero()) { - r = r2; s = s2; g = n; - return; - } - // Subtract q times the first invariant from the second invariant. - n.divideWithRemainder(m, q); - r2 -= q*r1; s2 -= q*s1; - } -} - -BigUnsigned modinv(const BigInteger &x, const BigUnsigned &n) { - BigInteger g, r, s; - extendedEuclidean(x, n, g, r, s); - if (g == 1) - // r*x + s*n == 1, so r*x === 1 (mod n), so r is the answer. - return (r % n).getMagnitude(); // (r % n) will be nonnegative - else - throw "BigInteger modinv: x and n have a common factor"; -} - -BigUnsigned modexp(const BigInteger &base, const BigUnsigned &exponent, - const BigUnsigned &modulus) { - BigUnsigned ans = 1, base2 = (base % modulus).getMagnitude(); - BigUnsigned::Index i = exponent.bitLength(); - // For each bit of the exponent, most to least significant... - while (i > 0) { - i--; - // Square. - ans *= ans; - ans %= modulus; - // And multiply if the bit is a 1. - if (exponent.getBit(i)) { - ans *= base2; - ans %= modulus; - } - } - return ans; -} -- cgit v1.2.3