Commit a2e15e2d10edf389094c77624f33164f00c93b1c
2018-05-05T03:20:39
Added tests to demo.c, switched off Lucas-Selfridge because it failed a test, and changed MP_8BIT handling in mp_prime_is_prime
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
diff --git a/bn_mp_prime_is_prime.c b/bn_mp_prime_is_prime.c
index e9cadc2..1cae3e6 100644
--- a/bn_mp_prime_is_prime.c
+++ b/bn_mp_prime_is_prime.c
@@ -109,18 +109,21 @@ int mp_prime_is_prime(const mp_int *a, int t, int *result)
if (res == MP_NO) {
goto LBL_B;
}
-// strong Lucas Selfridge test needs some changes to be usable with 8-bit
-#ifndef MP_8BIT
-// commented out for testing purposes
-//#ifdef LTM_USE_STRONG_LUCAS_SELFRIDGE_TEST
+
+
+#ifdef MP_8BIT
+ t = 8;
+#else
+// switched off, failed a test, said 2^1119 + 53 (a cert. prime) is not prime
+#ifdef LTM_USE_STRONG_LUCAS_SELFRIDGE_TEST
if ((err = mp_prime_strong_lucas_selfridge(a, &res)) != MP_OKAY) {
goto LBL_B;
}
if (res == MP_NO) {
goto LBL_B;
}
-//#endif
#endif
+// commented out for testing purposes
//#ifdef LTM_USE_FROBENIUS_UNDERWOOD_TEST
if ((err = mp_prime_frobenius_underwood(a, &res)) != MP_OKAY) {
goto LBL_B;
@@ -129,6 +132,7 @@ int mp_prime_is_prime(const mp_int *a, int t, int *result)
goto LBL_B;
}
//#endif
+#endif
/*
abs(t) extra rounds of M-R to extend the range of primes it can find if t < 0.
diff --git a/demo/demo.c b/demo/demo.c
index 368f062..8bc7eb6 100644
--- a/demo/demo.c
+++ b/demo/demo.c
@@ -118,6 +118,35 @@ static struct mp_jacobi_st jacobi[] = {
{ 7, { 1, -1, 1, -1, -1, 0, 1, 1, -1, 1, -1, -1, 0, 1, 1, -1 } },
{ 9, { -1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 } },
};
+
+struct mp_kronecker_st {
+ long n;
+ int c[21];
+};
+static struct mp_kronecker_st kronecker[] = {
+ //-10, -9, -8, -7,-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
+ { -10, { 0, -1, 0, -1, 0, 0, 0, 1, 0, -1, 0, 1, 0, -1, 0, 0, 0, 1, 0, 1, 0 } },
+ { -9, { -1, 0, -1, 1, 0, -1, -1, 0, -1, -1, 0, 1, 1, 0, 1, 1, 0, -1, 1, 0, 1 } },
+ { -8, { 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0 } },
+ { -7, { 1, -1, -1, 0, 1, 1, -1, 1, -1, -1, 0, 1, 1, -1, 1, -1, -1, 0, 1, 1, -1 } },
+ { -6, { 0, 0, 0, -1, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0 } },
+ { -5, { 0, -1, 1, -1, 1, 0, -1, -1, 1, -1, 0, 1, -1, 1, 1, 0, -1, 1, -1, 1, 0 } },
+ { -4, { 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0 } },
+ { -3, { -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1 } },
+ { -2, { 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0 } },
+ { -1, { -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1 } },
+ { 0, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
+ { 1, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } },
+ { 2, { 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0 } },
+ { 3, { 1, 0, -1, -1, 0, -1, 1, 0, -1, 1, 0, 1, -1, 0, 1, -1, 0, -1, -1, 0, 1 } },
+ { 4, { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 } },
+ { 5, { 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0 } },
+ { 6, { 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, 0 } },
+ { 7, { -1, 1, 1, 0, 1, -1, 1, 1, 1, 1, 0, 1, 1, 1, 1, -1, 1, 0, 1, 1, -1 } },
+ { 8, { 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0 } },
+ { 9, { 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 } },
+ { 10, { 0, 1, 0, -1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, -1, 0, 1, 0 } }
+};
#endif
#if LTM_DEMO_TEST_VS_MTEST != 0
@@ -133,6 +162,7 @@ int main(void)
gcd_n, lcm_n, inv_n, div2_n, mul2_n, add_d_n, sub_d_n;
#else
unsigned long s, t;
+ long k, m;
unsigned long long q, r;
mp_digit mp;
int i, n, err, should;
@@ -261,6 +291,45 @@ int main(void)
}
}
+
+ mp_set_int(&a, 0);
+ mp_set_int(&b, 1u);
+ if ((err = mp_kronecker(&a, &b, &i)) != MP_OKAY) {
+ printf("Failed executing mp_kronecker(0 | 1) %s.\n", mp_error_to_string(err));
+ return EXIT_FAILURE;
+ }
+ if (i != 1) {
+ printf("Failed trivial mp_kronecker(0 | 1) %d != 1\n", i);
+ return EXIT_FAILURE;
+ }
+ for (cnt = 0; cnt < (int)(sizeof(kronecker)/sizeof(kronecker[0])); ++cnt) {
+ k = kronecker[cnt].n;
+ if (k < 0) {
+ mp_set_int(&a, (unsigned long) (-k));
+ mp_neg(&a, &a);
+ }
+ else {
+ mp_set_int(&a, (unsigned long) k);
+ }
+ /* only test positive values of a */
+ for (m = -10; m <= 10; m++) {
+ if (m < 0) {
+ mp_set_int(&b,(unsigned long) (-m));
+ mp_neg(&b, &b);
+ }
+ else {
+ mp_set_int(&b, (unsigned long) m);
+ }
+ if ((err = mp_kronecker(&a, &b, &i)) != MP_OKAY) {
+ printf("Failed executing mp_kronecker(%ld | %ld) %s.\n", kronecker[cnt].n, m, mp_error_to_string(err));
+ return EXIT_FAILURE;
+ }
+ if (err == MP_OKAY && i != kronecker[cnt].c[m + 10]) {
+ printf("Failed trivial mp_kronecker(%ld | %ld) %d != %d\n", kronecker[cnt].n, m, i, kronecker[cnt].c[m + 10]);
+ return EXIT_FAILURE;
+ }
+ }
+ }
/* test mp_complement */
printf("\n\nTesting: mp_complement");
for (i = 0; i < 1000; ++i) {
@@ -604,6 +673,25 @@ int main(void)
}
printf("\n");
+
+ // strong Miller-Rabin pseudoprime to the first 200 primes (F. Arnault)
+ puts("Testing mp_prime_is_prime() with Arnault's pseudoprime 803...901 \n");
+ mp_read_radix(&a,"91xLNF3roobhzgTzoFIG6P13ZqhOVYSN60Fa7Cj2jVR1g0k89zdahO9/kAiRprpfO1VAp1aBHucLFV/qLKLFb+zonV7R2Vxp1K13ClwUXStpV0oxTNQVjwybmFb5NBEHImZ6V7P6+udRJuH8VbMEnS0H8/pSqQrg82OoQQ2fPpAk6G1hkjqoCv5s/Yr",64);
+ mp_prime_is_prime(&a, 8, &cnt);
+ if (cnt == MP_YES) {
+ printf("Arnault's pseudoprime is not prime but mp_prime_is_prime says it is.\n");
+ return EXIT_FAILURE;
+ }
+ // About the same size as Arnault's pseudoprime
+ puts("Testing mp_prime_is_prime() with certified prime 2^1119 + 53\n");
+ mp_set(&a,1u);
+ mp_mul_2d(&a,1119,&a);
+ mp_add_d(&a,53,&a);
+ mp_prime_is_prime(&a, 8, &cnt);
+ if (cnt == MP_NO) {
+ printf("A certified prime is a prime but mp_prime_is_prime says it not.\n");
+ return EXIT_FAILURE;
+ }
for (ix = 16; ix < 128; ix++) {
printf("Testing ( safe-prime): %9d bits \r", ix);
fflush(stdout);