Test some Euler pseudoprimes.

The Miller-Rabin test is an extension of the Fermat test (in addition to
looking for a^(n-1) != 1, it also looks for a non-trivial square root of
unity). It thus seems prudent to sanity-check we indeed reject Fermat
pseudoprimes. Euler pseudoprimes are a stronger constraint, so test
those.

Change-Id: I959769de2da3f8579403621bcf893e7c9247ca33
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/37785
Reviewed-by: Adam Langley <agl@google.com>

crypto/fipsmodule/bn/bn_test.cc

diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index b7427d5..23c7574 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -2012,10 +2012,10 @@
                                 nullptr /* callback */));
   EXPECT_EQ(0, is_probably_prime_2);
 
-  // The following composite numbers come from http://oeis.org/A014233 and are
-  // such that the first several primes are not a Miller-Rabin composite
-  // witness.
-  static const char *kA014233[] = {
+  static const char *kComposites[] = {
+      // The following composite numbers come from http://oeis.org/A014233 and
+      // are such that the first several primes are not a Miller-Rabin composite
+      // witness.
       "2047",
       "1373653",
       "25326001",
@@ -2026,8 +2026,44 @@
       "3825123056546413051",
       "318665857834031151167461",
       "3317044064679887385961981",
+
+      // The following composite numbers come from https://oeis.org/A033181
+      // which lists Euler pseudoprimes. These are false positives for the
+      // Fermat primality
+      // test.
+      "1729",
+      "2465",
+      "15841",
+      "41041",
+      "46657",
+      "75361",
+      "162401",
+      "172081",
+      "399001",
+      "449065",
+      "488881",
+      "530881",
+      "656601",
+      "670033",
+      "838201",
+      "997633",
+      "1050985",
+      "1615681",
+      "1773289",
+      "1857241",
+      "2113921",
+      "2433601",
+      "2455921",
+      "2704801",
+      "3057601",
+      "3224065",
+      "3581761",
+      "3664585",
+      "3828001",
+      "4463641",
+      "4903921",
   };
-  for (const char *str : kA014233) {
+  for (const char *str : kComposites) {
     SCOPED_TRACE(str);
     EXPECT_NE(0, DecimalToBIGNUM(&p, str));