summaryrefslogtreecommitdiff
path: root/third_party/bigint/BigIntegerAlgorithms.cc
diff options
context:
space:
mode:
authorBo Xu <bo_xu@foxitsoftware.com>2014-12-02 13:06:22 -0800
committerBo Xu <bo_xu@foxitsoftware.com>2014-12-02 13:06:22 -0800
commit7504b3d87d6143661746d85c3c3e4052939b4e52 (patch)
tree3baa8695a001c3226719409b666db31c3153f039 /third_party/bigint/BigIntegerAlgorithms.cc
parent4643533ca3dabe945fd174caf892a3ccb6cf2fd6 (diff)
downloadpdfium-7504b3d87d6143661746d85c3c3e4052939b4e52.tar.xz
Initial check in of big integer library, v2010.04.30
R=tsepez@chromium.org Review URL: https://codereview.chromium.org/773443004
Diffstat (limited to 'third_party/bigint/BigIntegerAlgorithms.cc')
-rw-r--r--third_party/bigint/BigIntegerAlgorithms.cc70
1 files changed, 70 insertions, 0 deletions
diff --git a/third_party/bigint/BigIntegerAlgorithms.cc b/third_party/bigint/BigIntegerAlgorithms.cc
new file mode 100644
index 0000000000..7edebda76a
--- /dev/null
+++ b/third_party/bigint/BigIntegerAlgorithms.cc
@@ -0,0 +1,70 @@
+#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;
+}