Add GCD testing infrastructure.

This commit adds testing and Known Answer Tests (KATs) to OpenSSL for
the `BN_gcd` function.

(cherry picked from commit b75d6310857bc44ef2851bde68a1979c18bb4807)

Reviewed-by: Paul Dale <paul.dale@oracle.com>
Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/10122)

3 files changed, 17235 insertions, 3 deletions

diff --git a/test/bntest.c b/test/bntest.c
index 0bd9a06f72..9f63ec121c 100644
--- a/test/bntest.c
+++ b/test/bntest.c
@@ -1634,6 +1634,30 @@ static int file_modsqrt(STANZA *s)
     return st;
 }
 
+static int file_gcd(STANZA *s)
+{
+    BIGNUM *a = NULL, *b = NULL, *gcd = NULL, *ret = NULL;
+    int st = 0;
+
+    if (!TEST_ptr(a = getBN(s, "A"))
+            || !TEST_ptr(b = getBN(s, "B"))
+            || !TEST_ptr(gcd = getBN(s, "GCD"))
+            || !TEST_ptr(ret = BN_new()))
+        goto err;
+
+    if (!TEST_true(BN_gcd(ret, a, b, ctx))
+            || !equalBN("gcd(A,B)", gcd, ret))
+        goto err;
+
+    st = 1;
+ err:
+    BN_free(a);
+    BN_free(b);
+    BN_free(gcd);
+    BN_free(ret);
+    return st;
+}
+
 static int test_bn2padded(void)
 {
 #if HAVE_BN_PADDED
@@ -2352,6 +2376,34 @@ static int test_ctx_consttime_flag(void)
     return st;
 }
 
+static int test_gcd_prime(void)
+{
+    BIGNUM *a = NULL, *b = NULL, *gcd = NULL;
+    int i, st = 0;
+
+    if (!TEST_ptr(a = BN_new())
+            || !TEST_ptr(b = BN_new())
+            || !TEST_ptr(gcd = BN_new()))
+        goto err;
+
+    if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL)))
+            goto err;
+    for (i = 0; i < NUM0; i++) {
+        if (!TEST_true(BN_generate_prime_ex(b, 1024, 0,
+                                            NULL, NULL, NULL))
+                || !TEST_true(BN_gcd(gcd, a, b, ctx))
+                || !TEST_true(BN_is_one(gcd)))
+            goto err;
+    }
+
+    st = 1;
+ err:
+    BN_free(a);
+    BN_free(b);
+    BN_free(gcd);
+    return st;
+}
+
 static int file_test_run(STANZA *s)
 {
     static const FILETEST filetests[] = {
@@ -2366,6 +2418,7 @@ static int file_test_run(STANZA *s)
         {"ModExp", file_modexp},
         {"Exp", file_exp},
         {"ModSqrt", file_modsqrt},
+        {"GCD", file_gcd},
     };
     int numtests = OSSL_NELEM(filetests);
     const FILETEST *tp = filetests;
@@ -2454,6 +2507,7 @@ int setup_tests(void)
 #endif
         ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
         ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
+        ADD_TEST(test_gcd_prime);
     } else {
         ADD_ALL_TESTS(run_file_tests, n);
     }
diff --git a/test/recipes/10-test_bn.t b/test/recipes/10-test_bn.t
index a663009ce9..4e38c8f8b4 100644
--- a/test/recipes/10-test_bn.t
+++ b/test/recipes/10-test_bn.t
@@ -16,9 +16,8 @@ use OpenSSL::Test qw/:DEFAULT data_file/;
 
 setup("test_bn");
 
-my @files = (
-    "bnexp.txt", "bnmod.txt", "bnmul.txt", "bnshift.txt", "bnsum.txt"
-    );
+my @files = qw( bnexp.txt bnmod.txt bnmul.txt bnshift.txt bnsum.txt bngcd.txt );
+
 plan tests => 1 + scalar(@files);
 
 foreach my $f ( @files ) {
diff --git a/test/recipes/10-test_bn_data/bngcd.txt b/test/recipes/10-test_bn_data/bngcd.txt
new file mode 100644
index 0000000000..ea19336b5d
--- /dev/null
+++ b/test/recipes/10-test_bn_data/bngcd.txt
@@ -0,0 +1,17179 @@
+# Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+#
+# Licensed under the Apache License 2.0 (the "License").  You may not use
+# this file except in compliance with the License.  You can obtain a copy
+# in the file LICENSE in the source distribution or at
+# https://www.openssl.org/source/license.html
+
+# GCD tests.
+#
+# These test vectors satisfy gcd(A, B) = GCD.
+# They were generated with sage, independent of OpenSSL.
+
+A = 0
+B = 0
+GCD = 0
+
+# gcd(1,0) = 1
+A = 1
+B = 0
+GCD = 1
+
+# gcd(1,1) = 1
+A = 1
+B = 1
+GCD = 1
+
+# gcd(0,a) = a
+A = 0
+B = 70030ffeeea3deaea19387f4f1d0f460a6954a2a9cb98290602ac09036143ef8eb9692f3eac22961811083e073ee0be1506c24d7b0d4eb0089406758828f7c99dc01692846f88aafb58b2d56a6dd1157b781eeaf807d59496aac6ca754f8830b743ea938ce16cbe03c8fd8675c78ba2420d502f2227a9bbe3979865cd154cbb2
+GCD = 70030ffeeea3deaea19387f4f1d0f460a6954a2a9cb98290602ac09036143ef8eb9692f3eac22961811083e073ee0be1506c24d7b0d4eb0089406758828f7c99dc01692846f88aafb58b2d56a6dd1157b781eeaf807d59496aac6ca754f8830b743ea938ce16cbe03c8fd8675c78ba2420d502f2227a9bbe3979865cd154cbb2
+
+# gcd(-a,0) = |a|
+A = -231f16458c487346cf50a17beec83632f25d19abeea1097c746533cd3e35207b7efd75dc3e9c663a64b6861e88579dad08649f107a13edf2ad43d0056f9240ad2a08c4aba20f05cc4aad23eb47e77cc8031df5b1c735b55103e164ca6c07bd040e12616df28064e5895a8903a26dfde7e88229a8d29fc4cb77711bf81bd04db9
+B = 0
+GCD = 231f16458c487346cf50a17beec83632f25d19abeea1097c746533cd3e35207b7efd75dc3e9c663a64b6861e88579dad08649f107a13edf2ad43d0056f9240ad2a08c4aba20f05cc4aad23eb47e77cc8031df5b1c735b55103e164ca6c07bd040e12616df28064e5895a8903a26dfde7e88229a8d29fc4cb77711bf81bd04db9
+
+# for even i, test:
+# gcd(2**i - 1, 2**(i/2) - 1) = 2**(i/2) - 1
+# gcd(2**i - 1, 2**(i/2) + 1) = 2**(i/2) + 1
+A = f
+B = 3
+GCD = 3
+
+A = f
+B = 5
+GCD = 5
+
+A = 3f
+B = 7
+GCD = 7
+
+A = 3f
+B = 9
+GCD = 9
+
+A = ff
+B = f
+GCD = f
+
+A = ff
+B = 11
+GCD = 11
+
+A = 3ff
+B = 1f
+GCD = 1f
+
+A = 3ff
+B = 21
+GCD = 21
+
+A = fff
+B = 3f
+GCD = 3f
+
+A = fff
+B = 41
+GCD = 41
+
+A = 3fff
+B = 7f
+GCD = 7f
+
+A = 3fff
+B = 81
+GCD = 81
+
+A = ffff
+B = ff
+GCD = ff
+
+A = ffff
+B = 101
+GCD = 101
+
+A = 3ffff
+B = 1ff
+GCD = 1ff
+
+A = 3ffff
+B = 201
+GCD = 201
+
+A = fffff
+B = 3ff
+GCD = 3ff
+
+A = fffff
+B = 401
+GCD = 401
+
+A = 3fffff
+B = 7ff
+GCD = 7ff
+
+A = 3fffff
+B = 801
+GCD = 801
+
+A = ffffff
+B = fff
+GCD = fff
+
+A = ffffff
+B = 1001
+GCD = 1001
+
+A = 3ffffff
+B = 1fff
+GCD = 1fff
+
+A = 3ffffff
+B = 2001
+GCD = 2001
+
+A = fffffff
+B = 3fff
+GCD = 3fff
+
+A = fffffff
+B = 4001
+GCD = 4001
+
+A = 3fffffff
+B = 7fff
+GCD = 7fff
+
+A = 3fffffff
+B = 8001
+GCD = 8001
+
+A = ffffffff
+B = ffff
+GCD = ffff
+
+A = ffffffff
+B = 10001
+GCD = 10001
+
+A = 3ffffffff
+B = 1ffff
+GCD = 1ffff
+
+A = 3ffffffff
+B = 20001
+GCD = 20001
+
+A = fffffffff
+B = 3ffff
+GCD = 3ffff
+
+A = fffffffff
+B = 40001
+GCD = 40001
+
+A = 3fffffffff
+B = 7ffff
+GCD = 7ffff
+
+A = 3fffffffff
+B = 80001
+GCD = 80001
+
+A = ffffffffff
+B = fffff
+GCD = fffff
+
+A = ffffffffff
+B = 100001
+GCD = 100001
+
+A = 3ffffffffff
+B = 1fffff
+GCD = 1fffff
+
+A = 3ffffffffff
+B = 200001
+GCD = 200001
+
+A = fffffffffff
+B = 3fffff
+GCD = 3fffff
+
+A = fffffffffff
+B = 400001
+GCD = 400001
+
+A = 3fffffffffff
+B = 7fffff
+GCD = 7fffff
+
+A = 3fffffffffff
+B = 800001
+GCD = 800001
+
+A = ffffffffffff
+B = ffffff
+GCD = ffffff
+
+A = ffffffffffff
+B = 1000001
+GCD = 1000001
+
+A = 3ffffffffffff
+B = 1ffffff
+GCD = 1ffffff
+
+A = 3ffffffffffff
+B = 2000001
+GCD = 2000001
+
+A = fffffffffffff
+B = 3ffffff
+GCD = 3ffffff
+
+A = fffffffffffff
+B = 4000001
+GCD = 4000001
+
+A = 3fffffffffffff
+B = 7ffffff
+GCD = 7ffffff
+
+A = 3fffffffffffff
+B = 8000001
+GCD = 8000001
+
+A = ffffffffffffff
+B = fffffff
+GCD = fffffff
+
+A = ffffffffffffff
+B = 10000001
+GCD = 10000001
+
+A = 3ffffffffffffff
+B = 1fffffff
+GCD = 1fffffff
+
+A = 3ffffffffffffff
+B = 20000001
+GCD = 20000001
+
+A = fffffffffffffff
+B = 3fffffff
+GCD = 3fffffff
+
+A = fffffffffffffff
+B = 40000001
+GCD = 40000001
+
+A = 3fffffffffffffff
+B = 7fffffff
+GCD = 7fffffff
+
+A = 3fffffffffffffff
+B = 80000001
+GCD = 80000001
+
+A = ffffffffffffffff
+B = ffffffff
+GCD = ffffffff
+
+A = ffffffffffffffff
+B = 100000001
+GCD = 100000001
+
+A = 3ffffffffffffffff
+B = 1ffffffff
+GCD = 1ffffffff
+
+A = 3ffffffffffffffff
+B = 200000001
+GCD = 200000001
+
+A = fffffffffffffffff
+B = 3ffffffff
+GCD = 3ffffffff
+
+A = fffffffffffffffff
+B = 400000001
+GCD = 400000001
+
+A = 3fffffffffffffffff
+B = 7ffffffff
+GCD = 7ffffffff
+
+A = 3fffffffffffffffff
+B = 800000001
+GCD = 800000001
+
+A = ffffffffffffffffff
+B = fffffffff
+GCD = fffffffff
+
+A = ffffffffffffffffff
+B = 1000000001
+GCD = 1000000001
+
+A = 3ffffffffffffffffff
+B = 1fffffffff
+GCD = 1fffffffff
+
+A = 3ffffffffffffffffff
+B = 2000000001
+GCD = 2000000001
+
+A = fffffffffffffffffff
+B = 3fffffffff
+GCD = 3fffffffff
+
+A = fffffffffffffffffff
+B = 4000000001
+GCD = 4000000001
+
+A = 3fffffffffffffffffff
+B = 7fffffffff
+GCD = 7fffffffff
+
+A = 3fffffffffffffffffff
+B = 8000000001
+GCD = 8000000001
+
+A = ffffffffffffffffffff
+B = ffffffffff
+GCD = ffffffffff
+
+A = ffffffffffffffffffff
+B = 10000000001
+GCD = 10000000001
+
+A = 3ffffffffffffffffffff
+B = 1ffffffffff
+GCD = 1ffffffffff
+
+A = 3ffffffffffffffffffff
+B = 20000000001
+GCD = 20000000001
+
+A = fffffffffffffffffffff
+B = 3ffffffffff
+GCD = 3ffffffffff
+
+A = fffffffffffffffffffff
+B = 40000000001
+GCD = 40000000001
+
+A = 3fffffffffffffffffffff
+B = 7ffffffffff
+GCD = 7ffffffffff
+
+A = 3fffffffffffffffffffff
+B = 80000000001
+GCD = 80000000001
+
+A = ffffffffffffffffffffff
+B = fffffffffff
+GCD = fffffffffff
+
+A = ffffffffffffffffffffff
+B = 100000000001
+GCD = 100000000001
+
+A = 3ffffffffffffffffffffff
+B = 1fffffffffff
+GCD = 1fffffffffff
+
+A = 3ffffffffffffffffffffff
+B = 200000000001
+GCD = 200000000001
+
+A = fffffffffffffffffffffff
+B = 3fffffffffff
+GCD = 3fffffffffff
+
+A = fffffffffffffffffffffff
+B = 400000000001
+GCD = 400000000001
+
+A = 3fffffffffffffffffffffff
+B = 7fffffffffff
+GCD = 7fffffffffff
+
+A = 3fffffffffffffffffffffff
+B = 800000000001
+GCD = 800000000001
+
+A = ffffffffffffffffffffffff
+B = ffffffffffff
+GCD = ffffffffffff
+
+A = ffffffffffffffffffffffff
+B = 1000000000001
+GCD = 1000000000001
+
+A = 3ffffffffffffffffffffffff
+B = 1ffffffffffff
+GCD = 1ffffffffffff
+
+A = 3ffffffffffffffffffffffff
+B = 2000000000001
+GCD = 2000000000001
+
+A = fffffffffffffffffffffffff
+B = 3ffffffffffff
+GCD = 3ffffffffffff
+
+A = fffffffffffffffffffffffff
+B = 4000000000001
+GCD = 4000000000001
+
+A = 3fffffffffffffffffffffffff
+B = 7ffffffffffff
+GCD = 7ffffffffffff
+
+A = 3fffffffffffffffffffffffff
+B = 8000000000001
+GCD = 8000000000001
+
+A = ffffffffffffffffffffffffff
+B = fffffffffffff
+GCD = fffffffffffff
+
+A = ffffffffffffffffffffffffff
+B = 10000000000001
+GCD = 10000000000001
+
+A = 3ffffffffffffffffffffffffff
+B = 1fffffffffffff
+GCD = 1fffffffffffff
+
+A = 3ffffffffffffffffffffffffff
+B = 20000000000001
+GCD = 20000000000001
+
+A = fffffffffffffffffffffffffff
+B = 3fffffffffffff
+GCD = 3fffffffffffff
+
+A = fffffffffffffffffffffffffff
+B = 40000000000001
+GCD = 40000000000001
+
+A = 3fffffffffffffffffffffffffff
+B = 7fffffffffffff
+GCD = 7fffffffffffff
+
+A = 3fffffffffffffffffffffffffff
+B = 80000000000001
+GCD = 80000000000001
+
+A = ffffffffffffffffffffffffffff
+B = ffffffffffffff
+GCD = ffffffffffffff
+
+A = ffffffffffffffffffffffffffff
+B = 100000000000001
+GCD = 100000000000001
+
+A = 3ffffffffffffffffffffffffffff
+B = 1ffffffffffffff
+GCD = 1ffffffffffffff
+
+A = 3ffffffffffffffffffffffffffff
+B = 200000000000001
+GCD = 200000000000001
+
+A = fffffffffffffffffffffffffffff
+B = 3ffffffffffffff
+GCD = 3ffffffffffffff
+
+A = fffffffffffffffffffffffffffff
+B = 400000000000001
+GCD = 400000000000001
+
+A = 3fffffffffffffffffffffffffffff
+B = 7ffffffffffffff
+GCD = 7ffffffffffffff
+
+A = 3fffffffffffffffffffffffffffff
+B = 800000000000001
+GCD = 800000000000001
+
+A = ffffffffffffffffffffffffffffff
+B = fffffffffffffff
+GCD = fffffffffffffff
+
+A = ffffffffffffffffffffffffffffff
+B = 1000000000000001
+GCD = 1000000000000001
+
+A = 3ffffffffffffffffffffffffffffff
+B = 1fffffffffffffff
+GCD = 1fffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffff
+B = 2000000000000001
+GCD = 2000000000000001
+
+A = fffffffffffffffffffffffffffffff
+B = 3fffffffffffffff
+GCD = 3fffffffffffffff
+
+A = fffffffffffffffffffffffffffffff
+B = 4000000000000001
+GCD = 4000000000000001
+
+A = 3fffffffffffffffffffffffffffffff
+B = 7fffffffffffffff
+GCD = 7fffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffff
+B = 8000000000000001
+GCD = 8000000000000001
+
+A = ffffffffffffffffffffffffffffffff
+B = ffffffffffffffff
+GCD = ffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffff
+B = 10000000000000001
+GCD = 10000000000000001
+
+A = 3ffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffff
+GCD = 1ffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffff
+B = 20000000000000001
+GCD = 20000000000000001
+
+A = fffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffff
+GCD = 3ffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffff
+B = 40000000000000001
+GCD = 40000000000000001
+
+A = 3fffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffff
+GCD = 7ffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffff
+B = 80000000000000001
+GCD = 80000000000000001
+
+A = ffffffffffffffffffffffffffffffffff
+B = fffffffffffffffff
+GCD = fffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffff
+B = 100000000000000001
+GCD = 100000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffff
+GCD = 1fffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffff
+B = 200000000000000001
+GCD = 200000000000000001
+
+A = fffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffff
+GCD = 3fffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffff
+B = 400000000000000001
+GCD = 400000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffff
+GCD = 7fffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffff
+B = 800000000000000001
+GCD = 800000000000000001
+
+A = ffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffff
+GCD = ffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffff
+B = 1000000000000000001
+GCD = 1000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffff
+GCD = 1ffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffff
+B = 2000000000000000001
+GCD = 2000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffff
+GCD = 3ffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffff
+B = 4000000000000000001
+GCD = 4000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffff
+GCD = 7ffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffff
+B = 8000000000000000001
+GCD = 8000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffff
+GCD = fffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffff
+B = 10000000000000000001
+GCD = 10000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffff
+GCD = 1fffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffff
+B = 20000000000000000001
+GCD = 20000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffff
+GCD = 3fffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffff
+B = 40000000000000000001
+GCD = 40000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffffff
+GCD = 7fffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffff
+B = 80000000000000000001
+GCD = 80000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffffff
+GCD = ffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffff
+B = 100000000000000000001
+GCD = 100000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffffff
+GCD = 1ffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffff
+B = 200000000000000000001
+GCD = 200000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffffff
+GCD = 3ffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffff
+B = 400000000000000000001
+GCD = 400000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffffff
+GCD = 7ffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffff
+B = 800000000000000000001
+GCD = 800000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffffff
+GCD = fffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffff
+B = 1000000000000000000001
+GCD = 1000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffffff
+GCD = 1fffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffff
+B = 2000000000000000000001
+GCD = 2000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffffff
+GCD = 3fffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffff
+B = 4000000000000000000001
+GCD = 4000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffffffff
+GCD = 7fffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffff
+B = 8000000000000000000001
+GCD = 8000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffffffff
+GCD = ffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffff
+B = 10000000000000000000001
+GCD = 10000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffffffff
+GCD = 1ffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffff
+B = 20000000000000000000001
+GCD = 20000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffffffff
+GCD = 3ffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffff
+B = 40000000000000000000001
+GCD = 40000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffffffff
+GCD = 7ffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffff
+B = 80000000000000000000001
+GCD = 80000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffffffff
+GCD = fffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffff
+B = 100000000000000000000001
+GCD = 100000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffffffff
+GCD = 1fffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffff
+B = 200000000000000000000001
+GCD = 200000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffffffff
+GCD = 3fffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffff
+B = 400000000000000000000001
+GCD = 400000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffffffffff
+GCD = 7fffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffff
+B = 800000000000000000000001
+GCD = 800000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffffffffff
+GCD = ffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1000000000000000000000001
+GCD = 1000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffffffffff
+GCD = 1ffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffff
+B = 2000000000000000000000001
+GCD = 2000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffffffffff
+GCD = 3ffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffff
+B = 4000000000000000000000001
+GCD = 4000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffffffffff
+GCD = 7ffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffff
+B = 8000000000000000000000001
+GCD = 8000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffffffffff
+GCD = fffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 10000000000000000000000001
+GCD = 10000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffffffffff
+GCD = 1fffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 20000000000000000000000001
+GCD = 20000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffffffffff
+GCD = 3fffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 40000000000000000000000001
+GCD = 40000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffffffffffff
+GCD = 7fffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 80000000000000000000000001
+GCD = 80000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffffffffffff
+GCD = ffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 100000000000000000000000001
+GCD = 100000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffffffffffff
+GCD = 1ffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 200000000000000000000000001
+GCD = 200000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffffffffffff
+GCD = 3ffffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 400000000000000000000000001
+GCD = 400000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffffffffffff
+GCD = 7ffffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 800000000000000000000000001
+GCD = 800000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffffffffffff
+GCD = fffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1000000000000000000000000001
+GCD = 1000000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffffffffffff
+GCD = 1fffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 2000000000000000000000000001
+GCD = 2000000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffffffffffff
+GCD = 3fffffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 4000000000000000000000000001
+GCD = 4000000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffffffffffffff
+GCD = 7fffffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 8000000000000000000000000001
+GCD = 8000000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffffffffffffff
+GCD = ffffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 10000000000000000000000000001
+GCD = 10000000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffffffffffffff
+GCD = 1ffffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 20000000000000000000000000001
+GCD = 20000000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffffffffffffff
+GCD = 3ffffffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 40000000000000000000000000001
+GCD = 40000000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffffffffffffff
+GCD = 7ffffffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 80000000000000000000000000001
+GCD = 80000000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffffffffffffff
+GCD = fffffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 100000000000000000000000000001
+GCD = 100000000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffffffffffffff
+GCD = 1fffffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 200000000000000000000000000001
+GCD = 200000000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffffffffffffff
+GCD = 3fffffffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 400000000000000000000000000001
+GCD = 400000000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffffffffffffffff
+GCD = 7fffffffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 800000000000000000000000000001
+GCD = 800000000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffffffffffffffff
+GCD = ffffffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1000000000000000000000000000001
+GCD = 1000000000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffffffffffffffff
+GCD = 1ffffffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 2000000000000000000000000000001
+GCD = 2000000000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffffffffffffffff
+GCD = 3ffffffffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 4000000000000000000000000000001
+GCD = 4000000000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffffffffffffffff
+GCD = 7ffffffffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 8000000000000000000000000000001
+GCD = 8000000000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffffffffffffffff
+GCD = fffffffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 10000000000000000000000000000001
+GCD = 10000000000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffffffffffffffff
+GCD = 1fffffffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 20000000000000000000000000000001
+GCD = 20000000000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffffffffffffffff
+GCD = 3fffffffffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 40000000000000000000000000000001
+GCD = 40000000000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7fffffffffffffffffffffffffffffff
+GCD = 7fffffffffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 80000000000000000000000000000001
+GCD = 80000000000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = ffffffffffffffffffffffffffffffff
+GCD = ffffffffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 100000000000000000000000000000001
+GCD = 100000000000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1ffffffffffffffffffffffffffffffff
+GCD = 1ffffffffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 200000000000000000000000000000001
+GCD = 200000000000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3ffffffffffffffffffffffffffffffff
+GCD = 3ffffffffffffffffffffffffffffffff
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 400000000000000000000000000000001
+GCD = 400000000000000000000000000000001
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 7ffffffffffffffffffffffffffffffff
+GCD = 7ffffffffffffffffffffffffffffffff
+
+A = 3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 800000000000000000000000000000001
+GCD = 800000000000000000000000000000001
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = fffffffffffffffffffffffffffffffff
+GCD = fffffffffffffffffffffffffffffffff
+
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1000000000000000000000000000000001
+GCD = 1000000000000000000000000000000001
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 1fffffffffffffffffffffffffffffffff
+GCD = 1fffffffffffffffffffffffffffffffff
+
+A = 3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 2000000000000000000000000000000001
+GCD = 2000000000000000000000000000000001
+
+A = fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+B = 3fffffffffffffffffffffffffffffffff
+GCD = 3fffffffffffffffffffffffffffffffff
+