diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index 41b0066..2ee6a16 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -372,6 +372,10 @@
   ASSERT_TRUE(BN_lshift(ret.get(), a.get(), n));
   EXPECT_BIGNUMS_EQUAL("A << N", lshift.get(), ret.get());
 
+  ASSERT_TRUE(BN_copy(ret.get(), a.get()));
+  ASSERT_TRUE(BN_lshift(ret.get(), ret.get(), n));
+  EXPECT_BIGNUMS_EQUAL("A << N (in-place)", lshift.get(), ret.get());
+
   ASSERT_TRUE(BN_rshift(ret.get(), lshift.get(), n));
   EXPECT_BIGNUMS_EQUAL("A >> N", a.get(), ret.get());
 
@@ -562,9 +566,31 @@
   ASSERT_TRUE(BN_add(ret.get(), ret.get(), remainder.get()));
   EXPECT_BIGNUMS_EQUAL("Quotient * B + Remainder", a.get(), ret.get());
 
+  // The remaining division variants only handle a positive quotient.
+  if (BN_is_negative(b.get())) {
+    BN_set_negative(b.get(), 0);
+    BN_set_negative(quotient.get(), !BN_is_negative(quotient.get()));
+  }
+
+  bssl::UniquePtr<BIGNUM> nnmod(BN_new());
+  ASSERT_TRUE(nnmod);
+  ASSERT_TRUE(BN_copy(nnmod.get(), remainder.get()));
+  if (BN_is_negative(nnmod.get())) {
+    ASSERT_TRUE(BN_add(nnmod.get(), nnmod.get(), b.get()));
+  }
+  ASSERT_TRUE(BN_nnmod(ret.get(), a.get(), b.get(), ctx));
+  EXPECT_BIGNUMS_EQUAL("A % B (non-negative)", nnmod.get(), ret.get());
+
+  // The remaining division variants only handle a positive numerator.
+  if (BN_is_negative(a.get())) {
+    BN_set_negative(a.get(), 0);
+    BN_set_negative(quotient.get(), 0);
+    BN_set_negative(remainder.get(), 0);
+  }
+
   // Test with |BN_mod_word| and |BN_div_word| if the divisor is small enough.
   BN_ULONG b_word = BN_get_word(b.get());
-  if (!BN_is_negative(b.get()) && b_word != (BN_ULONG)-1) {
+  if (b_word != (BN_ULONG)-1) {
     BN_ULONG remainder_word = BN_get_word(remainder.get());
     ASSERT_NE(remainder_word, (BN_ULONG)-1);
     ASSERT_TRUE(BN_copy(ret.get(), a.get()));
@@ -580,17 +606,9 @@
     }
   }
 
-  // Test BN_nnmod.
-  if (!BN_is_negative(b.get())) {
-    bssl::UniquePtr<BIGNUM> nnmod(BN_new());
-    ASSERT_TRUE(nnmod);
-    ASSERT_TRUE(BN_copy(nnmod.get(), remainder.get()));
-    if (BN_is_negative(nnmod.get())) {
-      ASSERT_TRUE(BN_add(nnmod.get(), nnmod.get(), b.get()));
-    }
-    ASSERT_TRUE(BN_nnmod(ret.get(), a.get(), b.get(), ctx));
-    EXPECT_BIGNUMS_EQUAL("A % B (non-negative)", nnmod.get(), ret.get());
-  }
+  ASSERT_TRUE(bn_div_consttime(ret.get(), ret2.get(), a.get(), b.get(), ctx));
+  EXPECT_BIGNUMS_EQUAL("A / B (constant-time)", quotient.get(), ret.get());
+  EXPECT_BIGNUMS_EQUAL("A % B (constant-time)", remainder.get(), ret2.get());
 }
 
 static void TestModMul(BIGNUMFileTest *t, BN_CTX *ctx) {
@@ -855,9 +873,11 @@
   bssl::UniquePtr<BIGNUM> a = t->GetBIGNUM("A");
   bssl::UniquePtr<BIGNUM> b = t->GetBIGNUM("B");
   bssl::UniquePtr<BIGNUM> gcd = t->GetBIGNUM("GCD");
+  bssl::UniquePtr<BIGNUM> lcm = t->GetBIGNUM("LCM");
   ASSERT_TRUE(a);
   ASSERT_TRUE(b);
   ASSERT_TRUE(gcd);
+  ASSERT_TRUE(lcm);
 
   bssl::UniquePtr<BIGNUM> ret(BN_new());
   ASSERT_TRUE(ret);
@@ -870,6 +890,16 @@
     EXPECT_FALSE(BN_mod_inverse(ret.get(), b.get(), a.get(), ctx))
         << "B^-1 (mod A) computed, but it does not exist";
   }
+
+  int is_relative_prime;
+  ASSERT_TRUE(
+      bn_is_relatively_prime(&is_relative_prime, a.get(), b.get(), ctx));
+  EXPECT_EQ(is_relative_prime, BN_is_one(gcd.get()));
+
+  if (!BN_is_zero(gcd.get())) {
+    ASSERT_TRUE(bn_lcm_consttime(ret.get(), a.get(), b.get(), ctx));
+    EXPECT_BIGNUMS_EQUAL("LCM(A, B)", lcm.get(), ret.get());
+  }
 }
 
 class BNTest : public testing::Test {
diff --git a/crypto/fipsmodule/bn/bn_tests.txt b/crypto/fipsmodule/bn/bn_tests.txt
index 88f8011..7f85a02 100644
--- a/crypto/fipsmodule/bn/bn_tests.txt
+++ b/crypto/fipsmodule/bn/bn_tests.txt
@@ -11150,204 +11150,280 @@
 
 # GCD tests.
 #
-# These test vectors satisfy gcd(A, B) = GCD.
+# These test vectors satisfy gcd(A, B) = GCD and lcm(A, B) = LCM.
 
 GCD = 0
 A = 0
 B = 0
+# Just to appease the syntax-checker.
+LCM = 0
 
 GCD = 1
 A = 92ff140ac8a659b31dd904161f9213706a08a817ae845e522c3af0c9096699e059b47c8c2f16434b1c5766ebb384b79190f2b2a62c2378f45e116890e7bb407a
 B = 2f532c9e5902b0d68cd2ed69b2083bc226e8b04c549212c425a5287bb171c6a47fcb926c70cc0d34b8d6201c617aee66af865d31fdc8a2eeb986c19da8bb0897
+LCM = 1b2c97003e520b0bdd59d8c35a180b4aa36bce14211590435b990ad8f4c034ce3c77899581cb4ee1a022874203459b6d53859ab1d99ff755efa253fc0e5d8487bb000c13c566e8937f0fe90b95b68bc278610d4f232770b08d1f31bee55a03da47f2d0ebb9e7861c4f16cc22168b68593e9efcde00f54104b4c3e1a0b294d7f6
 
 GCD = a
 A = faaffa431343074f5c5d6f5788500d7bc68b86eb37edf166f699b4d75b76dae2cb7c8f6eccae8f18f6d510ef72f0b9633d5740c0bebb934d3be796bd9a53808e
 B = 2f48ec5aa5511283c2935b15725d30f62244185573203b48c7eb135b2e6db5c115c9446ac78b020574665b06a75eb287e0dbeb5da7c193294699b4c2129d2ac4
+LCM = 4a15f305e9622aa19bd8f39e968bfc16d527a47f7a5219d7b02c242c77ef8b608a4a6141f643ca97cedf07c0f1f3e8879d2568b056718aa15c0756899a08ccbe0a658bae67face96fa110edb91757bfa4828e8ff7c5d71b204f36238b12dd26f17be8ba9771f7068d63e41d423671f898f054b1187605754bc5546f2b02c5ac
 
 GCD = 16
 A = cf0b21bde98b41b479ac8071086687a6707e9efaacd4e5299668ce1be8b13290f27fd32ae68df87c292e8583a09d73ec8e8a04a65a487380dcd7dacca3b6e692
 B = 3be3f563f81d5ad5c1211db7eff430aa345e830ce07b4bde7d4d32dba3ac618d2034351e5435fd6c7f077971fb4a1e83a7396a74fdff7fce1267112851db2582
+LCM = 233a2188de2c017235024b182286f17562b2ee5ab9fdfe4efa2f61c4ff99fa44e1ead5bf6cde05bd7502ce78373c83e3f9dbab0c9bb8620a87c2640bce5d12c685af656df789bb3d0ba1edbaa98cf4f0166d422ab17aa6706f8132264d45b72827d6671a00a9186e723379e3a3bb7902d08865f357c74100059f83800241976
 
 GCD = 1
 A = dd7b7597d7c1eb399b1cea9b3042c14bd6022d31b1d2642a8f82fc32de6eadaf012fbbf349eaec4922a8468740ca73c6090833d6a69a380ed947b39c2f9b0b76
 B = 8e0dc8654e70eec55496038a8d3fff3c2086bc6dbfc0e2dbdf5bd7de03c5aef01a3982556ac3fc34fd5f13368be6cdc252c82367b7462e210f940f847d382dd9
+LCM = 7ae667df4bd4dd35bbec28719a9f1b5e1f396a9ab386c086742a6ab3014a3386d39f35b50624d0c5b4e6b206c2635c7de5ea69e2faa85dd616a7e36622962a07632839857aa49332942feccff2aee1c962e2f4e8ccfd738a5da5bf528b4c5a2440409350f5a17a39d234403e8482ccf838e0d2758ccfb8018198a51dbb407506
 
 GCD = 1
 A = 0
 B = 1
+LCM = 0
 
 GCD = 1
 A = 1
 B = 0
+LCM = 0
 
 GCD = 1
 A = 1
 B = 1
+LCM = 1
 
 GCD = 2b2
 A = dfccaa3549c1b59ab3e114fe87dc5d187719abad58c51724e972741eb895ab79a49f385f61d531ec5c88dbb505ae375093fa848165f71a5ed65e7832a42ade191a
 B = fa58a81f43088da45e659fc1117d0f1cd015aa096c8e5377cf1832191baf7cc28b5c24998b93b64f8900a0973faedb9babaaf1854345f011739da8f1175d9684c
+LCM = 5132f7ab7a982b9dc55114bd96800b7637f9742cf8a7a00a0d69d5e4574fc85792c89a1c52bcfc74b9d7f3f6164819466c46b2d622e280ced7ad1211604084a15dc1fd1951a05c8ce37122c0ec15891d818a70d3763670ea3195098de9b1ca50ea89893a9753fb9ea801541058f44801f7f50967124abfc864a2b01c41f94193c
 
 GCD = 8e
 A = 248d96a8a4cab0a1b194e08c1146868b094597cadbc35531f0ed2d77cba9f15cb5cc7c10e64ce054bf93396d25259d750b3de3aba65073db1fd2b852a6454ac1a
 B = 4c7bad8e1844901fd6a2ce2edc82e698d28ec95d6672ca148d85b49ecc78dd0a8b870e202244210bc98592b99ff6abbd20630f9eee7d46b15ccfae8d08b86799de
+LCM = 13b01f9d9c6c13e90c97e3d95bbce5a835c631b3de3bd4ff5df13ad850f5223dbdf71c53912275d0397df9335ef3a3ba8e4684c6b25962bb7b18bc74144cb5edf0196f79863a7ff032619a71646a92281f7baace7f223d254cb4d05ec19bf8d4c8ce4455a9d770daec89c0d3cf338cbdae39cf982b3c4568f5c9def4e1133d28a
 
 GCD = 3e55
 A = 2fa97382f46676b7a4cc2b8153f17b58792d24660e187d33ce55c81cc193ccb6e1e2b89feea1d5fd8faa36e13bf947fb48635e450a4d1488d0978324194a1f43c6
 B = ab08ad074139963bc18e5d87ba68db64ca6f4c279616c64039b02c55f2375b3bc04114e8e05e1ba92fb6470768f61d123845aea36774c18612736a220934561faf
+LCM = 82c7c377ecda2cb9228604cd287df5eff94edd4a539c3eb3b3fdd4b4a79d2f4eaf2b22f8286272d3dad2e370cfcd9ea4d93ebb3f049c52b8fa23b68a5bf79af989822e2cfb978f68c6a5058f47319dffcb455b089b06ae6db9e5c8a2b6e951d6e118bd2b4cd08b6e5733476a446a57387d940d1289ec00e24315821ed3a5daf2
 
 GCD = a7a
 A = 923706dfed67834a1e7e6c8e8e9f93bfbc0b43ca1f324886cf1f1380fb9b77109275d4b50af1b7689802fe9b3623ac46c7ba0e17e908c20278127b07a5c12d86ec
 B = 64473e878a29021fac1c1ce34a63eae1f4f83ee6851333b67213278b9a4a16f005cba0e8cdb410035bb580062f0e486c1a3a01f4a4edf782495f1dc3ebfa837d86
+LCM = 57785ca45b8873032f1709331436995525eed815c55140582ce57fd852116835deac7ca9d95ce9f280e246ea4d4f1b7140ab7e0dd6dc869de87f1b27372098b155ad0a1828fd387dff514acc92eae708609285edaab900583a786caf95153f71e6e6092c8c5ee727346567e6f58d60a5e01c2fa8ebcf86da9ea46876ecc58e914
 
 GCD = 42
 A = 0
 B = 42
+LCM = 0
 
 GCD = 42
 A = 42
 B = 0
+LCM = 0
 
 GCD = 42
 A = 42
 B = 42
+LCM = 42
 
 GCD = f60d
 A = ef7886c3391407529d5cf2e75ed53e5c3f74439ad2e2dc48a79bc1a5322789b4ced2914b97f8ff4b9910d212243b54001eb8b375365b9a87bd022dd3772c78a9fd63
 B = d1d3ec32fa3103911830d4ec9f629c5f75af7039e307e05bc2977d01446cd2cbeeb8a8435b2170cf4d9197d83948c7b8999d901fe47d3ce7e4d30dc1b2de8af0c6e4
+LCM = cc376ed2dc362c38a45a719b2ed48201dab3e5506e3f1314e57af229dc7f3a6a0dad3d21cfb148c23a0bbb0092d667051aa0b35cff5b5cc61a7c52dec4ed72f6783edf181b3bf0500b79f87bb95abc66e4055f259791e4e5eb897d82de0e128ecf8a091119475351d65b7f320272db190898a02d33f45f03e27c36cb1c45208037dc
 
 GCD = 9370
 A = 1ee02fb1c02100d1937f9749f628c65384ff822e638fdb0f42e27b10ee36e380564d6e861fcad0518f4da0f8636c1b9f5124c0bc2beb3ca891004a14cd7b118ddfe0
 B = 67432fd1482d19c4a1c2a4997eab5dbf9c5421977d1de60b739af94c41a5ad384cd339ebfaa43e5ad6441d5b9aaed5a9f7485025f4b4d5014e1e406d5bd838a44e50
+LCM = 159ff177bdb0ffbd09e2aa7d86de266c5de910c12a48cbe61f6fa446f63a2151194777555cd59903d24cb30965973571fb1f89c26f2b760526f73ded7ee8a34ebcecd1a3374a7559bcdb9ac6e78be17a62b830d6bb3982afdf10cf83d61fd0d588eab17d6abef8e6a7a5763fcb766d9a4d86adf5bb904f2dd6b528b9faec603987a0
 
 GCD = c5f
 A = 5a3a2088b5c759420ed0fb9c4c7685da3725b659c132a710ef01e79435e63d009d2931ea0a9ed9432f3d6b8851730c323efb9db686486614332c6e6ba54d597cf98
 B = 1b1eb33b006a98178bb35bbcf09c5bebd92d9ace79fa34c1567efa8d6cf6361547807cd3f8e7b8cd3ddb6209dccbae4b4c16c8c1ec19741a3a57f61571882b7aed7
+LCM = c5cbbbe9532d30d2a7dd7c1c8a6e69fd4fa4828a844d6afb44f3747fef584f7f1f3b835b006f8747d84f7699e88f6267b634e7aef78d6c7584829537d79514eec7d11219721f91015f5cefdc296261d85dba388729438991a8027de4827cd9eb575622e2912b28c9ce26d441e97880d18db025812cef5de01adeaec1322a9c9858
 
 GCD = e052
 A = 67429f79b2ec3847cfc7e662880ab1d94acdf04284260fcfffd67c2862d59704ed45bcc53700c88a5eea023bc09029e9fd114fc94c227fd47a1faa1a5ef117b09bd2
 B = 39faa7cbdeb78f9028c1d50ab34fbe6924c83a1262596f6b85865d4e19cc258b3c3af1ee2898e39e5bee5839e92eac6753bbbb0253bd576d1839a59748b778846a86
+LCM = 1ab071fb733ef142e94def10b26d69982128561669e58b20b80d39cf7c2759d26b4a65d73b7f940c6e8fc417180ef62d7e52ac24678137bd927cd8d004ad52b02affe176a1ecde903dbc26dcc705678f76dd8cd874c0c3fe737474309767507bbe70dd7fb671bbb3694cedf0dcdaa0c716250ddd6dfec525261572fa3e1387f7b906
 
 GCD = 3523
 A = 0
 B = 3523
+LCM = 0
 
 GCD = 3523
 A = 3523
 B = 0
+LCM = 0
 
 GCD = 3523
 A = 3523
 B = 3523
+LCM = 3523
 
 GCD = f035a941
 A = 16cd5745464dfc426726359312398f3c4486ed8aaeea6386a67598b10f744f336c89cdafcb18e643d55c3a62f4ab2c658a0d19ea3967ea1af3aee22e11f12c6df6e886f7
 B = 74df09f309541d26b4b39e0c01152b8ad05ad2dfe9dd2b6706240e9d9f0c530bfb9e4b1cad3d4a94342aab309e66dd42d9df01b47a45173b507e41826f24eb1e8bcc4459
+LCM = b181771d0e9d6b36fdfcbf01d349c7de6b7e305e1485ea2aa32938aa919a3eee9811e1c3c649068a7572f5d251b424308da31400d81ac4078463f9f71d7efd2e681f92b13a6ab3ca5c9063032dcbdf3d3a9940ce65e54786463bbc06544e1280f25bc7579d264f6f1590cf09d1badbf542ce435a14ab04d25d88ddbac7d22e8cae1c91f
 
 GCD = 33ad1b8f
 A = 1af010429a74e1b612c2fc4d7127436f2a5dafda99015ad15385783bd3af8d81798a57d85038bcf09a2a9e99df713b4d6fc1e3926910fbbf1f006133cb27dc5ebb9cca85
 B = 92a4f45a90965a4ef454f1cdd883d20f0f3be34d43588b5914677c39d577a052d1b25a522be1a656860a540970f99cbc8a3adf3e2139770f664b4b7b9379e13daf7d26c
+LCM = 4c715520ed920718c3b2f62821bc75e3ff9fd184f76c60faf2906ef68d28cd540d3d6c071fa8704edd519709c3b09dfaee12cb02ab01ad0f3af4f5923d5705ce6d18bcab705a97e21896bb5dd8acb36ee8ec98c254a4ddc744297827a33c241f09016a5f109248c83dd41e4cea73ce3eabb28d76678b7e15545b96d22da83c111b6b624
 
 GCD = dc0429aa
 A = ccb423cfb78d7150201a97114b6644e8e0bbbb33cadb0ef5da5d3c521a244ec96e6d1538c64c10c85b2089bdd702d74c505adce9235aa4195068c9077217c0d431de7f96
 B = 710786f3d9022fc3acbf47ac901f62debcfda684a39234644bac630ab2d211111df71c0844b02c969fc5b4c5a15b785c96efd1e403514235dc9356f7faf75a0888de5e5a
+LCM = 6929af911850c55450e2f2c4c9a72adf284fe271cf26e41c66e1a2ee19e30d928ae824f13d4e2a6d7bb12d10411573e04011725d3b6089c28d87738749107d990162b485805f5eedc8f788345bcbb5963641f73c303b2d92f80529902d3c2d7899623958499c8a9133aae49a616c96a2c5482a37947f23af18c3247203ac2d0e760340e6
 
 GCD = 743166058
 A = 16cd476e8031d4624716238a3f85badd97f274cdfd9d53e0bd74de2a6c46d1827cc83057f3889588b6b7ca0640e7d743ed4a6eaf6f9b8df130011ecc72f56ef0af79680
 B = 86eba1fc8d761f22e0f596a03fcb6fe53ad15a03f5b4e37999f60b20966f78ba3280f02d3853f9ace40438ccfaf8faed7ace2f2bf089b2cdd4713f3f293bf602666c39f8
+LCM = 1a7a1b38727324d6ba0290f259b8e2b89c339b2445cada38a5a00ded1468ab069f40678ce76f7f78c7c6f97783cc8a49ef7e2a0c73abbac3abc66d1ce99566ce7f874a8949ca3442051e71967695dc65361184748c1908e1b587dc02ed899a524b34eb30b6f8db302432cfa1a8fbf2c46591e0ab3db7fd32c01b1f86c39832ee9f0c80
 
 GCD = 6612ba2c
 A = 0
 B = 6612ba2c
+LCM = 0
 
 GCD = 6612ba2c
 A = 6612ba2c
 B = 0
+LCM = 0
 
 GCD = 6612ba2c
 A = 6612ba2c
 B = 6612ba2c
+LCM = 6612ba2c
 
 GCD = 2272525aa08ccb20
 A = 11b9e23001e7446f6483fc9977140d91c3d82568dabb1f043a5620544fc3dda233b51009274cdb004fdff3f5c4267d34181d543d913553b6bdb11ce2a9392365fec8f9a3797e1200
 B = 11295529342bfb795f0611d03afb873c70bd16322b2cf9483f357f723b5b19f796a6206cf3ae3982daaeafcd9a68f0ce3355a7eba3fe4e743683709a2dd4b2ff46158bd99ff4d5a0
+LCM = 8d4cbf00d02f6adbaa70484bcd42ea932000843dcb667c69b75142426255f79b6c3b6bf22572597100c06c3277e40bf60c14c1f4a6822d86167812038cf1eefec2b0b19981ad99ad3125ff4a455a4a8344cbc609e1b3a173533db432bd717c72be25e05ed488d3970e7ed17a46353c5e0d91c8428d2fec7a93210759589df042cab028f545e3a00
 
 GCD = 3480bf145713d56f9
 A = 8cf8ef1d4f216c6bcec673208fd93b7561b0eb8303af57113edc5c6ff4e1eeae9ddc3112b943d947653ba2179b7f63505465126d88ad0a0a15b682f5c89aa4a2a51c768cd9fdeaa9
 B = a6fd114023e7d79017c552a9051ca827f3ffa9f31e2ee9d78f8408967064fcdc9466e95cc8fac9a4fa88248987caf7cf57af58400d27abd60d9b79d2fe03fad76b879eceb504d7f
+LCM = 1c05eee73a4f0db210a9007f94a5af88c1cdd2cba456061fd41de1e746d836fa4e0e972812842e0f44f10a61505f5d55760c48ba0d06af78bb6bde7da8b0080b29f82b1161e9c0b5458e05ac090b00f4d78b1cc10cf065124ba610e3acab092a36fe408525e21c0ddc7c9696ed4e48bd2f70423deecfe62cecc865c6088f265da0e5961d3f3a84f
 
 GCD = 917e74ae941fcaae
 A = 652f8a92d96cbf0a309629011d0fbaceb1266bc2e8243d9e494eead4cf7100c661b537a8bea93dec88cfc68597d88a976c125c3b4de19aba38d4ea9578202e59848d42652518348a
 B = 32e07b71979d57e8344e97c39680a61e07d692d824ae26b682156890792d8a766ee29a4968f461aaced5bf049044fba2f4120b1c1f05985676f975d4582e9e82750d73c532cd07b2
+LCM = 23620c7b897dc26c7717e32f3517ac70bf09fbe08f7255ab010cf4cf946f4e96304c425043452c5d5a0e841d3a3cfd9c2d84d9256f3b5974fe3ebfa9255fe20a710d3e6511606c0d85970381101c7f4986d65ad6a73a71507f146b11f903043cfa805cc0b14d4f3072da98bf22282f7762040406c02d5b3ef9e7587f63bab8b29c61d8e30911aa96
 
 GCD = 2b9adc82005b2697
 A = 19764a84f46045ef1bca571d3cbf49b4545998e64d2e564cc343a53bc7a0bcfbe0baa5383f2b346e224eb9ce1137d9a4f79e8e19f946a493ff08c9b423574d56cbe053155177c37
 B = 1bbd489ad2ab825885cdac571a95ab4924e7446ce06c0f77cf29666a1e20ed5d9bc65e4102e11131d824acad1592075e13024e11f12f8210d86ab52aa60deb250b3930aabd960e5a
+LCM = 1032a0c5fffc0425e6478185db0e5985c645dd929c7ebfeb5c1ee12ee3d7b842cfab8c9aa7ff3131ac41d4988fb928c0073103cea6bb2cc39808f1b0ad79a6d080eac5a0fc6e3853d43f903729549e03dba0a4405500e0096b9c8e00510c1852982baec441ed94efb80a78ed28ed526d055ad34751b831b8749b7c19728bf229357cc5e17eb8e1a
 
 GCD = 8d9d4f30773c4edf
 A = 0
 B = 8d9d4f30773c4edf
+LCM = 0
 
 GCD = 8d9d4f30773c4edf
 A = 8d9d4f30773c4edf
 B = 0
+LCM = 0
 
 GCD = 8d9d4f30773c4edf
 A = 8d9d4f30773c4edf
 B = 8d9d4f30773c4edf
+LCM = 8d9d4f30773c4edf
 
 GCD = 6ebd8eafb9a957a6c3d3d5016be604f9624b0debf04d19cdabccf3612bbd59e00
 A = 34dc66a0ffd5b8b5e0ffc858dfc4655753e59247c4f82a4d2543b1f7bb7be0e24d2bbf27bb0b2b7e56ee22b29bbde7baf0d7bfb96331e27ba029de9ffdff7bdb7dc4da836d0e58a0829367ec84ea256833fd4fe1456ad4dd920557a345e12000
 B = 1f3406a20e20ebf96ccb765f898889a19b7636608fd7dc7c212607b641399543f71111d60e42989de01eaa6ff19a86ea8fbde1a3d368c0d86dc899e8e250fc764090f337958ca493119cbb4ad70cbfae7097d06d4f90ec62fbdd3f0a4496e600
+LCM = ee502c50e3667946e9089d0a9a0382e7fd0b75a17db23b56a0eec997a112c4dbd56d188808f76fe90451e5605550c9559ef14a95014c6eb97e9c1c659b98515c41470142843de60f72fb4c235faa55b0a97d943221003d44e2c28928f0b84bf071256254897ed31a7fd8d174fc962bc1311f67900ac3abcad83a28e259812f1ee229511ab1d82d41f5add34693ba7519babd52eb4ec9de31581f5f2e40a000
 
 GCD = ef7399b217fc6a62b90461e58a44b22e5280d480b148ec4e3b4d106583f8e428
 A = 7025e2fe5f00aec73d90f5ad80d99ca873f71997d58e59937423a5e6ddeb5e1925ed2fd2c36a5a9fc560c9023d6332c5d8a4b333d3315ed419d60b2f98ccf28bbf5bf539284fd070d2690aeaac747a3d6384ee6450903a64c3017de33c969c98
 B = df0ac41dbabce1deeb0bceb1b65b1079850052ecf6534d0cff84a5a7fb5e63baee028d240f4419925154b96eaa69e8fbb1aae5102db7916234f290aa60c5d7e69406f02aeea9fe9384afbff7d878c9ac87cd31f7c35dff243b1441e09baff478
+LCM = 687669343f5208a6b2bb2e2efcac41ec467a438fde288cc5ef7157d130139ba65db9eb53e86a30c870bd769c0e0ab15a50f656cd9626621ae68d85eaff491b98da3ea5812062e4145af11ea5e1da457084911961ef2cd2ac45715f885ba94b4082aa76ffd1f32461f47c845b229d350bf36514c5ce3a7c782418746be342eca2721346ade73a59475f178c4f2448e1326110f5d26a0fef1a7a0c9288489e4dc8
 
 GCD = 84b917557acf24dff70cb282a07fc52548b6fbbe96ca8c46d0397c8e44d30573
 A = 81dbb771713342b33912b03f08649fb2506874b96125a1ac712bc94bfd09b679db7327a824f0a5837046f58af3a8365c89e06ff4d48784f60086a99816e0065a5f6f0f49066b0ff4c972a6b837b63373ca4bb04dcc21e5effb6dfe38271cb0fa
 B = 1da91553c0a2217442f1c502a437bb14d8c385aa595db47b23a97b53927b4493dd19f1bc8baf145bc10052394243089a7b88d19b6f106e64a5ab34acad94538ab504d1c8ebf22ac42048bbd1d4b0294a2e12c09fe2a3bd92756ba7578cb34b39
+LCM = 1d0530f8142754d1ee0249b0c3968d0ae7570e37dadbe4824ab966d655abf04cd6de5eb700eba89d8352dec3ae51f2a10267c32fbd39b788c7c5047fe69da3d7ad505435a6212f44899ba7e983bb780f62bcdee6f94b7dba8af7070a4cc008f351ae8be4579bc4a2e5c659ce000ad9c8cdc83723b32c96aeb0f5f4127f6347353d05525f559a8543cd389ad0af6f9d08a75b8c0b32419c097e6efe8746aee92e
 
 GCD = 66091477ea3b37f115038095814605896e845b20259a772f09405a8818f644aa
 A = cedac27069a68edfd49bd5a859173c8e318ba8be65673d9d2ba13c717568754ed9cbc10bb6c32da3b7238cff8c1352d6325668fd21b4e82620c2e75ee0c4b1aff6fb1e9b948bbdb1af83cecdf356299b50543b72f801b6a58444b176e4369e0
 B = 5f64ca1ba481f42c4c9cf1ffa0e515b52aa9d69ceb97c4a2897f2e9fa87f72bae56ee6c5227f354304994c6a5cc742d9f09b2c058521975f69ca5835bce898cf22b28457cd7e28870df14e663bb46c9be8f6662f4ff34d5c4ae17a888eba504e
+LCM = c163cb28642e19a40aa77887c63180c2c49fc10cda98f6f929c8131752ea30b5283a814a81681b69b9d1762e6c1a9db85f480bc17f998d235fd7e64c1caa70ef170c9e816d3e80f516b29f2c80cfb68bf208b4d5082ef078da4314b3f20c7d6c54b0aeb378096b029a7b61c0a4cd14aeddc01004c53915a4f692d2291752e5af46b23d7fa6dd61f2d56c6f4bf8e6119688abac8fd7aba80e846a7764bb3fca0
 
 GCD = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
 A = 0
 B = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
+LCM = 0
 
 GCD = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
 A = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
 B = 0
+LCM = 0
 
 GCD = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
 A = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
 B = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
+LCM = bb80bf51757ba696c700fa4e4c0132b3151d2bf9ebff8382f808ded78be67182
 
 GCD = 120451d8307219aa0c96f328ad653ccd462e92423ca93ed8a3dde45bf5cb9b13cdaf9800e4d05dd71c4db6a129fb3280ee4ec96ec5297d881c1a8b5efccbd91fef21f5c5bf5fba42a4c8eaa358f620a074b7a17054527bdaa58d5acaa0dfdc48ecba1a10ebf4d57bb4215de406e6be13fed3fe493b1cd1e2d11a8d4ac03c47756
 A = 3f8179a8e1f0b342475a855c3e1bae402dd41424cf24a0b4d2e263c8efb08bde7d92eae8607fb5e88b1378f0f1bd0733f229a35be6b1383a48d32749d5d6b32427d26323b7ab05bb5781289e96bfbc21971439319b15f6c0fe93fdb35d0b67ec41443c59a081dd3cef047ac797fccb45bece84c0bb0bb7e1797259526d8ec9cc63ba4d32cfc692ccd3d243cb2b53ac216312f3a8e8c0daa09d21b6150d697639a5e52059414a417c607be8ec0eee2e708219cadbaf37a369c4485b01ed87bbc2
 B = 2c474e396a2dd9cd10b9d7313f69d3b4ca123e9fd853edd488339236d14c56453a1381958864a04d2624e81995dabcdd0ccf60db9917813f887de68da075d0ea4440001e18f470e43b38ee3440b49be651d709fbdef980e3e4149913f4ae2681124f54523f4881376ddb533b5219e804cc26f4c2e577be4e02613c4da80ba1215775b0a5178a965ad47bd2befb32493943ded1004ef66347b4983f8d1ba990d4a943505dfce6debcfb322842ed88106cd6dee9aa592ff0d2274bc727a6e1f14c
+LCM = 9c129cf649555bfd2d3d9c64dc6d6f022295e53bca5d2f218adaa66aa60eb4694429b7e83bf81b6df4459c5104023ab9a33f006ffcd8114507baa17e2ef6fe23ebdd4740f66879033da2041f2cb7ba517ad3526ffe75614ea9432c085f71b2d65a736bac7ba42b639e330b82733372083843dcb78b6a273ab20e0d4b7c8998a14048aa15bb20a0a0bd997917107274c89b4cec175fb98043d52e6c555bd9e0036566d052a6d4e7e276d1e8835e1f06e3ca46d47747ba586e95fb1a790d992834b7c3e136141eb8a434e6c12067246ac3c0a81c69e03b1ed28aa0b3173d6eff83d278c2f461a47a416f3f9a5dae3bb410fd18817bd4115e7f1e84b936cc02364
 
 GCD = 95aa569a2c76854300d7660847dd20fe0b8c445fdbcaa98465cee61aee76ad6a438e75a8c573198570ffb62bc07ec3a2be0ae0a1f631670fa88d6f75f3161e8b9a4d44b6801ffc884c7f469c5ed1f27b1edecce9f2977f9e92d1a3b230492fea7e6f2af739dc158a7fbd29856cbedb57b4119e64b27ab09eb1c2df01507d6e7fd
 A = 4c653b5bfec44e9be100c064dffe5d8cd59b0cf4cc56b03eabb4ef87cfda6506c9a756b811907fe9d8b783eb7a0b9e129773bf1da365ddb488d27b16fb983e89345d1ccdb4f06a67a11925c3f266373be5d7b0075189c6f3c2157e2da197058fe0a7bcc50adc34e99e254a29abbe2d5948d3157e1b0c3fca3d641760f7b9862843b63abef0b3d83fd486f4526b30382fda355575da30e9a106718a3921774c4d69f5311f8d737fe618f5236b4763fe1b2ee7f13184db67367d3903c535ff6d7b
 B = 2dcca83c99a28e9fd2f84e78973699baf2f04fd454094730948b22477834a0064817b86e0835e6d7b26e5b0b1dcf4ad91a07ac0780d6522df1fcac758cf5db6c2a5623d7c0f1afefd5718f7b6de639867d07a9ec525991304e9355d1635104bea837f74758d6aa2aab4e4afbb606af1d98de7417505e4710cd0589bdff9a0bf38a857cc59a5f1781043e694fc2337fd84bdeb28b13a222bb09328a81ec409ad586e74236393d27398cc24d412135e34247c589149e134b97f4bd538ac9a3424b
+LCM = 1760c0b0066aa0695767099e87e9388729ea89b8e8c36bddcd04d257591e741613c07b0e69447c0a468c33a745084171e06523d987d8db40a1433bf435325e8a724a0876503b34495170ff3671d42117a2e4f3a75b1d9dd809a34fa0fb26fe50d84f80a9b02e40190e5efb927a5a61a03f13edbce2e666af6c3a2a9bcb84e47e3090008753ff27c4b8cf06480f471379a93f5230923623a83b286b71a555cd5e5347282f664ed90b14b2c4de84a70375e488211a7b3931119ef3bbe029b712389fe784818a0bf29d80733ce9cc940c547aa1eb3f06d492eb676bf37802283c82ce76156dfaab5c2d5107e08062681b5fa169f6eb68e1ab8bd9b2005e90bd4fd
 
 GCD = 244b9b1290cf5b4ba2f810574c050651489f2d3a2b03e702b76ebfaf4e33de9bbe5da24c919e68d3a72eadd35982b3a89c6b18b38ff7082ac65263e52b6ec75a5717b971c98257b194c828bff0216a99536603b41a396ea2fb50f5ea7cf3edf10bb0d039123e78593ae9ffcbbba02e51e038533e83b6bc73c70551d6467f39809
 A = 41a0b1310669500681cdf888836f6c556758750f562d743ac780dd4c0d161856380e44fdbb1f8a2786bf45be6b0e7f1cb2cd85f6b9e50acc72793d92383c7d7fb796fc74d32e8fac8225bdc19ae47546d9c9c75f5f06ca684f07daccaf89ccf2cddeb7ec255d530c7dd1e71daf44cafdc9d30fbcb1cbaefae3480585f79f4177e3834a5bc91845e2e8cd8aeb27f484e5e5b2c3c076dbb6c23e91303f0a0fdde83cd33a8ea6ed1549e727b4d766c1017c169710fd98e1585d60f66e121f9180b3
 B = 251f5aeaa60b3959285f49540cdaf8e21451110bbddb9933bbbcaea3112f4eb45e435a3ba37c52d2ab79ce997a8f6c829b3aa561f2852924b8effb52396d09d2bf257ebb4fb56c7aa25648f69b06d2cd01e876c9f9c0679de9e6fffa79eb7e603723e5af7de46ee405a5a079229577b5b6fffb8d43e391fe6f4eb89638e64d6eff8026249aaa355a91625eb0bfd14caa81e4c3586aaa2e94fde143a44f223a91e226661d12f55dfcdb4215e5a64e14e968005733be6a71c465de312ca109b34a
+LCM = 431f918b274f3e43f446e4e85567883d6536a0332db662cef088f5a36b0f4b68372048174ba10fee94b9f8f1c2e189c974be2e6e8ae8e2ae108445326d40f63e38d8d4e2e46174589a3cbc9583e0036dc8146e79eee9e96f4436313b3f143dd0f5aceab05243def7f915169c360f55ef123977cf623c5ba432c3259c62fb5e37d5adab0f24b825aa4ada99ec4e83e9ca4698399e1ed633091ce5f9844c540a642cd264201116ed4168aa2105a5159f5df064f845830c469140f766c7319052ce59bd1ad7c3f2d8c30e54f147f6aeb5586c70c984302ba18d854a60aec01b394c7d66fa33fe18fe4a8cfb3238df219294e6e42190a30d28b10049a1b75853a4e
 
 GCD = 206695d52bc391a4db61bf8cb6ea96188333a9c78f477ee76976c2346dad682cf56ca6f176d86ef67d41ff5921b6162b0eca52359975872430dd14c45643eacdf028d830770714c033fd150669705851b2f02de932322d271d565d26768530c3f6cb84f0b3356f970b9070b26c050ead0417152c324c8ffe266d4e8b5b7bef3a
 A = 1114eb9f1a9d5947eb1399e57f5c980833489685023ed2fe537fe1276c1e026b9a19e6fff55aa889d6c4e977b6e6f3111e2ad463138637b50f42cf32e57d83f282de9e72f813e5969195159a666d74dcd689bd527c60199ae327f7bd548ac36868fea5fdf6f35d19b921e7c10b6448ca480de6826478cd0642d72f05af3f8e65ce42409fbd49f56e81946e89c8e83962c4edc0ed54600600a305e52d081aed3c351e450e11f8fb0ce5754c92cf765b71393b2b7a89c95df79b9ea1b3cb600862
 B = 1d8f3179ca7b5cc7119360c10de939ffa57c9043da2f2b0ca3009c9bdad9f19ed16e3c2c197bef4b527fa1bf2bbab98b77e26c329911db68bd63d3d0fbfc727a977395b9ad067106de3094d68e097830858c5ccfa505fc25e972bdee6f347e7d1163efacd3d29a791ec2a94ffeed467884ae04896efc5e7e5f43d8d76c147e3c9951a1999173bc4e5767d51268b92cc68487ba1295372143b538711e0a62bf0ac111cc750ca4dd6c318c9cbe106d7fc492261404b86a1ba728e2d25b1976dc42
+LCM = f9570211f694141bfb096560551080cbe02a80271b4505591aaea9e3b99ea1d5ac1c1f2378fd72799e117ac2a73381b1ad26314e39972164d93971479ee3ba21a4d98cef0bd299d540ce5826995dcee0de420dff73d30b23cbf3188c625c7696df517535bc5675d71faa00807efbebdca547933f4a37849d1c014484a77da6df0670c4974bcc91eb5f5fe5faf9dd095ef195ec32ad9eeebf0e63288b4032ed9e70b888afc642f4ff96f0b4c0a68787301c12e4527fe79bdfe72dd3844ab5e094a9295df6616f24d1b9eeebc2116177dacf91969dda73667bc421ef3ccd8d5c23dddc283f5d36568d31f2654926be67f78e181075bdc148f2b39c630b141ae8a
 
 GCD = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
 A = 0
 B = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
+LCM = 0
 
 GCD = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
 A = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
 B = 0
+LCM = 0
 
 GCD = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
 A = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
 B = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
+LCM = 3d319c42d872f21131ce5ff3ab8bec94339308e620316dda218e85fedcd511cd62f0b2f3448d5e58fd3520ae8118abd54ead9ad9e8ec3890365c6b2cca2172d4b8839b2d2c5ab02f65180826cb0cd5c9798f5d6261efe6e6ec31dea047da7c486b0590359e6f333557f67ceebf9ea9cd5dd986a999a8c88bdbd0ca21816b2423
+
+GCD = 2
+A = 14e95a85e59ade9ef39e2f400c65db18702fa5fc485b9bba479a5282b2206129160e54f73ef4917983c17b4c5ebff7be112a886de069706eee29ba902515cb038
+B = ddcfff1d39c90c599f55495bf71c1e7597c6b08b7430707f360c6a6e5137bbc7b403c6d9e2c34f3d2f29d5d32b869346853c2de239cc35381bdfb4a01569211a
+LCM = 90f38564ee72e55d362c04599e7d74f068c75f541b84e97abba2841f1a9f66b06b5c9009f6a4c2e319fced85270588de03ccebddbd9279aaecb13bdc1dbea7f42acaee751cb7da83779b8785cc86f41b94b13b54964208ca287d981634778d1096f20e76ca636c0717fd27e0800c43f599a5eded807421b502eaf9990a8c8ed8
+
+GCD = 4
+A = 3c719c1c363cdeb7b57c2aabb71f425da4c3e6d3e447204d555e7cf0f3d372bdda906f36078045044978dafc20171767c8b1464d52dfdf3e2ba8a4906da033a8
+B = 30fe0ef151ac51404e128c064d836b191921769dc02d9b09889ed40eb68d15bfdd2edea33580a1a4d7dcee918fefd5c776cbe80ca6131aa080d3989b5e77e1b24
+LCM = 2e4526157bbd765b0486d90bcd4728f890bc6dbd9a855c67ca5cb2d6b48f8e74e1d99485999e04b193afca58dbf282610185d6c0272007744ff26e00dbdc813929b47940b137dc56ba974da07d54a1c50ec4a5c2b26e83f47cf17f4ccce8c3687e8d1e91d7c491a599f3d057c73473723ce9eee52c20fe8ae1595447552a7ee8
+
+GCD = 10
+A = 44e04071d09119ea9783a53df35de4a989200133bb20280fdca6003d3ca63fdd9350ad1a1673d444d2f7c7be639824681643ec4f77535c626bd3ee8fa100e0bb0
+B = ca927a5a3124ce89accd6ac41a8441d352a5d42feb7f62687a5ebc0e181cc2679888ecc2d38516bdc3b3443550efccac81e53044ae9341ecace2598fe5ce67780
+LCM = 36805ba9b2412a0cb3fe4ed9bdabfa55515c9d615a3d0af268c45c5f6098d2de4a583f3791f1e3883c55d51ce23c5658fd0e8faa9a3709a1cfbd6a61dbab861690f27c86664f084c86cfd4a183b24aaadf59a6f8cbec04f1b0ded8a59b188cb46ae920052e3e099a570540dbc00f7d4a571eef08aa70d2d189a1804bf04e94a80
+
+GCD = 100
+A = 73725032b214a677687c811031555b0c51c1703f10d59b97a4d732b7feaec5726cb3882193419d3f057583b2bc02b297d76bb689977936febaae92638fdfc46a00
+B = 979f4c10f4dc60ad15068cedd62ff0ab293aeaa1d6935763aed41fe3e445de2e366e8661eadf345201529310f4b805c5800b99f351fddab95d7f313e3bb429d900
+LCM = 4460439b4be72f533e9c7232f7e99c48328b457969364c951868ceab56cb2cbbeda8be2e8e3cae45c0758048468b841fdb246b2086d19b59d17b389333166ab82ed785860620d53c44f7aaaff4625ee70fb8072df10fb4d1acb142eadc02978ff2bb07cea9f434e35424b3323a7bda3a1a57aa60c75e49ebb2f59fb653aa77da00
+
+GCD = 100000000
+A = f8b4f19e09f5862d79fb2931c4d616a1b8e0dd44781ca52902c8035166c8fca52d33a56ff484c365ec1257de7fa8ed2786163cfc051d5223b4aad859a049e8ba00000000
+B = 6e54cb41b454b080e68a2c3dd0fa79f516eb80239af2be8250ca9cd377ba501aabafc09146fad4402bdc7a49f2c3eec815e25f4c0a223f58e36709eefd92410500000000
+LCM = 6b3020a880ddeff9d17d3dc234da8771962de3322cd15ba7b1e4b1dd4a6a2a802a16c49653865c6fdf6c207cbe0940f8d81ef4cb0e159385fd709d515ee99d109ad9ad680031cbae4eab2ed62944babdade4e3036426b18920022f737897c7d751dce98d626cdda761fec48ad87a377fb70f97a0a15aa3d10d865785719cc5a200000000
diff --git a/crypto/fipsmodule/bn/check_bn_tests.go b/crypto/fipsmodule/bn/check_bn_tests.go
index abb4ca5..bf05e75 100644
--- a/crypto/fipsmodule/bn/check_bn_tests.go
+++ b/crypto/fipsmodule/bn/check_bn_tests.go
@@ -265,7 +265,7 @@
 				}
 			}
 		case "GCD":
-			if checkKeys(test, "A", "B", "GCD") {
+			if checkKeys(test, "A", "B", "GCD", "LCM") {
 				a := test.Values["A"]
 				b := test.Values["B"]
 				// Go's GCD function does not accept zero, unlike OpenSSL.
@@ -278,6 +278,11 @@
 					g = new(big.Int).GCD(nil, nil, a, b)
 				}
 				checkResult(test, "GCD(A, B)", "GCD", g)
+				if g.Sign() != 0 {
+					lcm := new(big.Int).Mul(a, b)
+					lcm = lcm.Div(lcm, g)
+					checkResult(test, "LCM(A, B)", "LCM", lcm)
+				}
 			}
 		default:
 			fmt.Fprintf(os.Stderr, "Line %d: unknown test type %q.\n", test.LineNumber, test.Type)
diff --git a/crypto/fipsmodule/bn/div.c b/crypto/fipsmodule/bn/div.c
index f58f3dc..2a3bcdd 100644
--- a/crypto/fipsmodule/bn/div.c
+++ b/crypto/fipsmodule/bn/div.c
@@ -454,6 +454,92 @@
   bn_select_words(r, carry, tmp /* r < 0 */, r /* r >= 0 */, num);
 }
 
+int bn_div_consttime(BIGNUM *quotient, BIGNUM *remainder,
+                     const BIGNUM *numerator, const BIGNUM *divisor,
+                     BN_CTX *ctx) {
+  if (BN_is_negative(numerator) || BN_is_negative(divisor)) {
+    OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
+    return 0;
+  }
+  if (BN_is_zero(divisor)) {
+    OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO);
+    return 0;
+  }
+
+  // This function implements long division in binary. It is not very efficient,
+  // but it is simple, easy to make constant-time, and performant enough for RSA
+  // key generation.
+
+  int ret = 0;
+  BN_CTX_start(ctx);
+  BIGNUM *q = quotient, *r = remainder;
+  if (quotient == NULL || quotient == numerator || quotient == divisor) {
+    q = BN_CTX_get(ctx);
+  }
+  if (remainder == NULL || remainder == numerator || remainder == divisor) {
+    r = BN_CTX_get(ctx);
+  }
+  BIGNUM *tmp = BN_CTX_get(ctx);
+  if (q == NULL || r == NULL || tmp == NULL ||
+      !bn_wexpand(q, numerator->width) ||
+      !bn_wexpand(r, divisor->width) ||
+      !bn_wexpand(tmp, divisor->width)) {
+    goto err;
+  }
+
+  OPENSSL_memset(q->d, 0, numerator->width * sizeof(BN_ULONG));
+  q->width = numerator->width;
+  q->neg = 0;
+
+  OPENSSL_memset(r->d, 0, divisor->width * sizeof(BN_ULONG));
+  r->width = divisor->width;
+  r->neg = 0;
+
+  // Incorporate |numerator| into |r|, one bit at a time, reducing after each
+  // step. At the start of each loop iteration, |r| < |divisor|
+  for (int i = numerator->width - 1; i >= 0; i--) {
+    for (int bit = BN_BITS2 - 1; bit >= 0; bit--) {
+      // Incorporate the next bit of the numerator, by computing
+      // r = 2*r or 2*r + 1. Note the result fits in one more word. We store the
+      // extra word in |carry|.
+      BN_ULONG carry = bn_add_words(r->d, r->d, r->d, divisor->width);
+      r->d[0] |= (numerator->d[i] >> bit) & 1;
+      // tmp = r - divisor. We use |bn_sub_words| to perform the bulk of the
+      // subtraction, and then apply the borrow to |carry|.
+      carry -= bn_sub_words(tmp->d, r->d, divisor->d, divisor->width);
+      // |r| was previously fully-reduced, so we know:
+      //
+      //    2*0 - divisor <= tmp <= 2*(divisor-1) + 1 - divisor
+      //         -divisor <= tmp < divisor
+      //
+      // If 0 <= |tmp| < |divisor|, |tmp| fits in |divisor->width| and |carry|
+      // is zero. We then wish to select |tmp|. Otherwise,
+      // -|divisor| <= |tmp| < 0 and we wish to select |tmp| + |divisor|, which
+      // is |r|. |carry| must then be -1 (all ones). In both cases, |carry| is a
+      // suitable input to |bn_select_words|.
+      //
+      // Although |carry| may be one if |bn_add_words| returns one and
+      // |bn_sub_words| returns zero, this would give |r| > |d|, which violates
+      // the loop invariant.
+      bn_select_words(r->d, carry, r->d /* tmp < 0 */, tmp->d /* tmp >= 0 */,
+                      divisor->width);
+      // The corresponding bit of the quotient is set iff we needed to subtract.
+      q->d[i] |= (~carry & 1) << bit;
+    }
+  }
+
+  if ((quotient != NULL && !BN_copy(quotient, q)) ||
+      (remainder != NULL && !BN_copy(remainder, r))) {
+    goto err;
+  }
+
+  ret = 1;
+
+err:
+  BN_CTX_end(ctx);
+  return ret;
+}
+
 static BIGNUM *bn_scratch_space_from_ctx(size_t width, BN_CTX *ctx) {
   BIGNUM *ret = BN_CTX_get(ctx);
   if (ret == NULL ||
diff --git a/crypto/fipsmodule/bn/gcd.c b/crypto/fipsmodule/bn/gcd.c
index 850d446..bc40ec2 100644
--- a/crypto/fipsmodule/bn/gcd.c
+++ b/crypto/fipsmodule/bn/gcd.c
@@ -114,109 +114,115 @@
 
 #include "internal.h"
 
-static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) {
-  BIGNUM *t;
-  int shifts = 0;
 
-  // 0 <= b <= a
-  while (!BN_is_zero(b)) {
-    // 0 < b <= a
+static BN_ULONG word_is_odd_mask(BN_ULONG a) { return (BN_ULONG)0 - (a & 1); }
 
-    if (BN_is_odd(a)) {
-      if (BN_is_odd(b)) {
-        if (!BN_sub(a, a, b)) {
-          goto err;
-        }
-        if (!BN_rshift1(a, a)) {
-          goto err;
-        }
-        if (BN_cmp(a, b) < 0) {
-          t = a;
-          a = b;
-          b = t;
-        }
-      } else {
-        // a odd - b even
-        if (!BN_rshift1(b, b)) {
-          goto err;
-        }
-        if (BN_cmp(a, b) < 0) {
-          t = a;
-          a = b;
-          b = t;
-        }
-      }
-    } else {
-      // a is even
-      if (BN_is_odd(b)) {
-        if (!BN_rshift1(a, a)) {
-          goto err;
-        }
-        if (BN_cmp(a, b) < 0) {
-          t = a;
-          a = b;
-          b = t;
-        }
-      } else {
-        // a even - b even
-        if (!BN_rshift1(a, a)) {
-          goto err;
-        }
-        if (!BN_rshift1(b, b)) {
-          goto err;
-        }
-        shifts++;
-      }
-    }
-    // 0 <= b <= a
-  }
-
-  if (shifts) {
-    if (!BN_lshift(a, a, shifts)) {
-      goto err;
-    }
-  }
-
-  return a;
-
-err:
-  return NULL;
+static void maybe_rshift1_words(BN_ULONG *a, BN_ULONG mask, BN_ULONG *tmp,
+                                size_t num) {
+  bn_rshift1_words(tmp, a, num);
+  bn_select_words(a, mask, tmp, a, num);
 }
 
-int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) {
-  BIGNUM *a, *b, *t;
+static int bn_gcd_consttime(BIGNUM *r, unsigned *out_shift, const BIGNUM *x,
+                            const BIGNUM *y, BN_CTX *ctx) {
+  size_t width = x->width > y->width ? x->width : y->width;
+  if (width == 0) {
+    *out_shift = 0;
+    BN_zero(r);
+    return 1;
+  }
+
+  // This is a constant-time implementation of Stein's algorithm (binary GCD).
   int ret = 0;
-
   BN_CTX_start(ctx);
-  a = BN_CTX_get(ctx);
-  b = BN_CTX_get(ctx);
-
-  if (a == NULL || b == NULL) {
-    goto err;
-  }
-  if (BN_copy(a, in_a) == NULL) {
-    goto err;
-  }
-  if (BN_copy(b, in_b) == NULL) {
+  BIGNUM *u = BN_CTX_get(ctx);
+  BIGNUM *v = BN_CTX_get(ctx);
+  BIGNUM *tmp = BN_CTX_get(ctx);
+  if (u == NULL || v == NULL || tmp == NULL ||
+      !BN_copy(u, x) ||
+      !BN_copy(v, y) ||
+      !bn_resize_words(u, width) ||
+      !bn_resize_words(v, width) ||
+      !bn_resize_words(tmp, width)) {
     goto err;
   }
 
-  a->neg = 0;
-  b->neg = 0;
-
-  if (BN_cmp(a, b) < 0) {
-    t = a;
-    a = b;
-    b = t;
-  }
-  t = euclid(a, b);
-  if (t == NULL) {
+  // Each loop iteration halves at least one of |u| and |v|. Thus we need at
+  // most the combined bit width of inputs for at least one value to be zero.
+  unsigned x_bits = x->width * BN_BITS2, y_bits = y->width * BN_BITS2;
+  unsigned num_iters = x_bits + y_bits;
+  if (num_iters < x_bits) {
+    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
     goto err;
   }
 
-  if (BN_copy(r, t) == NULL) {
+  unsigned shift = 0;
+  for (unsigned i = 0; i < num_iters; i++) {
+    BN_ULONG both_odd = word_is_odd_mask(u->d[0]) & word_is_odd_mask(v->d[0]);
+
+    // If both |u| and |v| are odd, subtract the smaller from the larger.
+    BN_ULONG u_less_than_v =
+        (BN_ULONG)0 - bn_sub_words(tmp->d, u->d, v->d, width);
+    bn_select_words(u->d, both_odd & ~u_less_than_v, tmp->d, u->d, width);
+    bn_sub_words(tmp->d, v->d, u->d, width);
+    bn_select_words(v->d, both_odd & u_less_than_v, tmp->d, v->d, width);
+
+    // At least one of |u| and |v| is now even.
+    BN_ULONG u_is_odd = word_is_odd_mask(u->d[0]);
+    BN_ULONG v_is_odd = word_is_odd_mask(v->d[0]);
+    assert(!(u_is_odd & v_is_odd));
+
+    // If both are even, the final GCD gains a factor of two.
+    shift += 1 & (~u_is_odd & ~v_is_odd);
+
+    // Halve any which are even.
+    maybe_rshift1_words(u->d, ~u_is_odd, tmp->d, width);
+    maybe_rshift1_words(v->d, ~v_is_odd, tmp->d, width);
+  }
+
+  // One of |u| or |v| is zero at this point. The algorithm usually makes |u|
+  // zero, unless |y| was already zero on input. Fix this by combining the
+  // values.
+  assert(BN_is_zero(u) || BN_is_zero(v));
+  for (size_t i = 0; i < width; i++) {
+    v->d[i] |= u->d[i];
+  }
+
+  *out_shift = shift;
+  ret = bn_set_words(r, v->d, width);
+
+err:
+  BN_CTX_end(ctx);
+  return ret;
+}
+
+int BN_gcd(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) {
+  unsigned shift;
+  return bn_gcd_consttime(r, &shift, x, y, ctx) &&
+         BN_lshift(r, r, shift);
+}
+
+int bn_is_relatively_prime(int *out_relatively_prime, const BIGNUM *x,
+                           const BIGNUM *y, BN_CTX *ctx) {
+  int ret = 0;
+  BN_CTX_start(ctx);
+  unsigned shift;
+  BIGNUM *gcd = BN_CTX_get(ctx);
+  if (gcd == NULL ||
+      !bn_gcd_consttime(gcd, &shift, x, y, ctx)) {
     goto err;
   }
+
+  // Check that 2^|shift| * |gcd| is one.
+  if (gcd->width == 0) {
+    *out_relatively_prime = 0;
+  } else {
+    BN_ULONG mask = shift | (gcd->d[0] ^ 1);
+    for (int i = 1; i < gcd->width; i++) {
+      mask |= gcd->d[i];
+    }
+    *out_relatively_prime = mask == 0;
+  }
   ret = 1;
 
 err:
@@ -224,6 +230,19 @@
   return ret;
 }
 
+int bn_lcm_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) {
+  BN_CTX_start(ctx);
+  unsigned shift;
+  BIGNUM *gcd = BN_CTX_get(ctx);
+  int ret = gcd != NULL &&
+            bn_mul_consttime(r, a, b, ctx) &&
+            bn_gcd_consttime(gcd, &shift, a, b, ctx) &&
+            bn_div_consttime(r, NULL, r, gcd, ctx) &&
+            bn_rshift_secret_shift(r, r, shift, ctx);
+  BN_CTX_end(ctx);
+  return ret;
+}
+
 // solves ax == 1 (mod n)
 static int bn_mod_inverse_general(BIGNUM *out, int *out_no_inverse,
                                   const BIGNUM *a, const BIGNUM *n,
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index 309c0c6..79e5a41 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -379,6 +379,9 @@
 // of the first several odd primes and zero otherwise.
 int bn_odd_number_is_obviously_composite(const BIGNUM *bn);
 
+// bn_rshift1_words sets |r| to |a| >> 1, where both arrays are |num| bits wide.
+void bn_rshift1_words(BN_ULONG *r, const BN_ULONG *a, size_t num);
+
 // bn_rshift_secret_shift behaves like |BN_rshift| but runs in time independent
 // of both |a| and |n|.
 OPENSSL_EXPORT int bn_rshift_secret_shift(BIGNUM *r, const BIGNUM *a,
@@ -416,6 +419,28 @@
 // to 2*|a->width|, to avoid leaking information about |a| and |b|.
 int bn_sqr_consttime(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx);
 
+// bn_div_consttime behaves like |BN_div|, but it rejects negative inputs and
+// treats both inputs, including their magnitudes, as secret. It is, as a
+// result, much slower than |BN_div| and should only be used for rare operations
+// where Montgomery reduction is not available.
+//
+// Note that |quotient->width| will be set pessimally to |numerator->width|.
+OPENSSL_EXPORT int bn_div_consttime(BIGNUM *quotient, BIGNUM *remainder,
+                                    const BIGNUM *numerator,
+                                    const BIGNUM *divisor, BN_CTX *ctx);
+
+// bn_is_relatively_prime checks whether GCD(|x|, |y|) is one. On success, it
+// returns one and sets |*out_relatively_prime| to one if the GCD was one and
+// zero otherwise. On error, it returns zero.
+OPENSSL_EXPORT int bn_is_relatively_prime(int *out_relatively_prime,
+                                          const BIGNUM *x, const BIGNUM *y,
+                                          BN_CTX *ctx);
+
+// bn_lcm_consttime sets |r| to LCM(|a|, |b|). It returns one and success and
+// zero on error. |a| and |b| are both treated as secret.
+OPENSSL_EXPORT int bn_lcm_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
+                                    BN_CTX *ctx);
+
 
 // Constant-time modular arithmetic.
 //
diff --git a/crypto/fipsmodule/bn/shift.c b/crypto/fipsmodule/bn/shift.c
index dae7126..3e71739 100644
--- a/crypto/fipsmodule/bn/shift.c
+++ b/crypto/fipsmodule/bn/shift.c
@@ -197,40 +197,24 @@
   return ret;
 }
 
+void bn_rshift1_words(BN_ULONG *r, const BN_ULONG *a, size_t num) {
+  if (num == 0) {
+    return;
+  }
+  for (size_t i = 0; i < num - 1; i++) {
+    r[i] = (a[i] >> 1) | (a[i + 1] << (BN_BITS2 - 1));
+  }
+  r[num - 1] = a[num - 1] >> 1;
+}
+
 int BN_rshift1(BIGNUM *r, const BIGNUM *a) {
-  BN_ULONG *ap, *rp, t, c;
-  int i, j;
-
-  if (BN_is_zero(a)) {
-    BN_zero(r);
-    return 1;
+  if (!bn_wexpand(r, a->width)) {
+    return 0;
   }
-  i = bn_minimal_width(a);
-  ap = a->d;
-  j = i - (ap[i - 1] == 1);
-  if (a != r) {
-    if (!bn_wexpand(r, j)) {
-      return 0;
-    }
-    r->neg = a->neg;
-  }
-  rp = r->d;
-  t = ap[--i];
-  c = t << (BN_BITS2 - 1);
-  if (t >>= 1) {
-    rp[i] = t;
-  }
-  while (i > 0) {
-    t = ap[--i];
-    rp[i] = (t >> 1) | c;
-    c = t << (BN_BITS2 - 1);
-  }
-  r->width = j;
-
-  if (r->width == 0) {
-    r->neg = 0;
-  }
-
+  bn_rshift1_words(r->d, a->d, a->width);
+  r->width = a->width;
+  r->neg = a->neg;
+  bn_set_minimal_width(r);
   return 1;
 }