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>
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));
