Merge pull request #349 from czurnieden/sans_eight Remove support for 8-bit (MP_8BIT)
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 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
diff --git a/bn_mp_from_ubin.c b/bn_mp_from_ubin.c
index 7f73cbc..f6d6e2a 100644
--- a/bn_mp_from_ubin.c
+++ b/bn_mp_from_ubin.c
@@ -23,15 +23,8 @@ mp_err mp_from_ubin(mp_int *a, const unsigned char *buf, size_t size)
if ((err = mp_mul_2d(a, 8, a)) != MP_OKAY) {
return err;
}
-
-#ifndef MP_8BIT
a->dp[0] |= *buf++;
a->used += 1;
-#else
- a->dp[0] = (*buf & MP_MASK);
- a->dp[1] |= ((*buf++ >> 7) & 1u);
- a->used += 2;
-#endif
}
mp_clamp(a);
return MP_OKAY;
diff --git a/bn_mp_montgomery_setup.c b/bn_mp_montgomery_setup.c
index 39f6e9d..ad245eb 100644
--- a/bn_mp_montgomery_setup.c
+++ b/bn_mp_montgomery_setup.c
@@ -24,10 +24,8 @@ mp_err mp_montgomery_setup(const mp_int *n, mp_digit *rho)
x = (((b + 2u) & 4u) << 1) + b; /* here x*a==1 mod 2**4 */
x *= 2u - (b * x); /* here x*a==1 mod 2**8 */
-#if !defined(MP_8BIT)
x *= 2u - (b * x); /* here x*a==1 mod 2**16 */
-#endif
-#if defined(MP_64BIT) || !(defined(MP_8BIT) || defined(MP_16BIT))
+#if defined(MP_64BIT) || !(defined(MP_16BIT))
x *= 2u - (b * x); /* here x*a==1 mod 2**32 */
#endif
#ifdef MP_64BIT
diff --git a/bn_mp_prime_frobenius_underwood.c b/bn_mp_prime_frobenius_underwood.c
index 253e8d5..618aa7c 100644
--- a/bn_mp_prime_frobenius_underwood.c
+++ b/bn_mp_prime_frobenius_underwood.c
@@ -9,7 +9,6 @@
*/
#ifndef LTM_USE_ONLY_MR
-#ifdef MP_8BIT
/*
* floor of positive solution of
* (2^16)-1 = (a+4)*(2*a+5)
@@ -19,10 +18,8 @@
* But it is still a restriction of the set of available pseudoprimes
* which makes this implementation less secure if used stand-alone.
*/
-#define LTM_FROBENIUS_UNDERWOOD_A 177
-#else
#define LTM_FROBENIUS_UNDERWOOD_A 32764
-#endif
+
mp_err mp_prime_frobenius_underwood(const mp_int *N, mp_bool *result)
{
mp_int T1z, T2z, Np1z, sz, tz;
diff --git a/bn_mp_prime_is_prime.c b/bn_mp_prime_is_prime.c
index 49fde93..86edcb6 100644
--- a/bn_mp_prime_is_prime.c
+++ b/bn_mp_prime_is_prime.c
@@ -57,13 +57,6 @@ mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
return MP_OKAY;
}
}
-#ifdef MP_8BIT
- /* The search in the loop above was exhaustive in this case */
- if ((a->used == 1) && (MP_PRIME_TAB_SIZE >= 31)) {
- return MP_OKAY;
- }
-#endif
-
/* first perform trial division */
if ((err = s_mp_prime_is_divisible(a, &res)) != MP_OKAY) {
return err;
@@ -112,7 +105,7 @@ mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
* MP_8BIT (It is unknown if the Lucas-Selfridge test works with 16-bit
* integers but the necesssary analysis is on the todo-list).
*/
-#if defined (MP_8BIT) || defined (LTM_USE_FROBENIUS_TEST)
+#ifdef LTM_USE_FROBENIUS_TEST
err = mp_prime_frobenius_underwood(a, &res);
if ((err != MP_OKAY) && (err != MP_ITER)) {
goto LBL_B;
@@ -240,20 +233,6 @@ mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
* an unsigned int and "mask" on the other side is most probably not.
*/
fips_rand = (unsigned int)(b.dp[0] & (mp_digit) mask);
-#ifdef MP_8BIT
- /*
- * One 8-bit digit is too small, so concatenate two if the size of
- * unsigned int allows for it.
- */
- if ((MP_SIZEOF_BITS(unsigned int)/2) >= MP_SIZEOF_BITS(mp_digit)) {
- if ((err = mp_rand(&b, 1)) != MP_OKAY) {
- goto LBL_B;
- }
- fips_rand <<= MP_SIZEOF_BITS(mp_digit);
- fips_rand |= (unsigned int) b.dp[0];
- fips_rand &= mask;
- }
-#endif
if (fips_rand > (unsigned int)(INT_MAX - MP_DIGIT_BIT)) {
len = INT_MAX / MP_DIGIT_BIT;
} else {
@@ -264,18 +243,6 @@ mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
ix--;
continue;
}
- /*
- * As mentioned above, one 8-bit digit is too small and
- * although it can only happen in the unlikely case that
- * an "unsigned int" is smaller than 16 bit a simple test
- * is cheap and the correction even cheaper.
- */
-#ifdef MP_8BIT
- /* All "a" < 2^8 have been caught before */
- if (len == 1) {
- len++;
- }
-#endif
if ((err = mp_rand(&b, len)) != MP_OKAY) {
goto LBL_B;
}
diff --git a/bn_mp_prime_strong_lucas_selfridge.c b/bn_mp_prime_strong_lucas_selfridge.c
index b50bbcd..a5ea16d 100644
--- a/bn_mp_prime_strong_lucas_selfridge.c
+++ b/bn_mp_prime_strong_lucas_selfridge.c
@@ -10,12 +10,6 @@
#ifndef LTM_USE_ONLY_MR
/*
- * 8-bit is just too small. You can try the Frobenius test
- * but that frobenius test can fail, too, for the same reason.
- */
-#ifndef MP_8BIT
-
-/*
* multiply bigint a with int d and put the result in c
* Like mp_mul_d() but with a signed long as the small input
*/
@@ -286,4 +280,3 @@ LBL_LS_ERR:
}
#endif
#endif
-#endif
diff --git a/bn_mp_to_ubin.c b/bn_mp_to_ubin.c
index 1681ca7..a2c6e28 100644
--- a/bn_mp_to_ubin.c
+++ b/bn_mp_to_ubin.c
@@ -20,11 +20,7 @@ mp_err mp_to_ubin(const mp_int *a, unsigned char *buf, size_t maxlen, size_t *wr
}
for (x = count; x --> 0u;) {
-#ifndef MP_8BIT
buf[x] = (unsigned char)(t.dp[0] & 255u);
-#else
- buf[x] = (unsigned char)(t.dp[0] | ((t.dp[1] & 1u) << 7));
-#endif
if ((err = mp_div_2d(&t, 8, &t, NULL)) != MP_OKAY) {
goto LBL_ERR;
}
diff --git a/bn_prime_tab.c b/bn_prime_tab.c
index 6bd53fe..92a5159 100644
--- a/bn_prime_tab.c
+++ b/bn_prime_tab.c
@@ -7,9 +7,7 @@ const mp_digit s_mp_prime_tab[] = {
0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
- 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F,
-#ifndef MP_8BIT
- 0x0083,
+ 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
@@ -41,7 +39,6 @@ const mp_digit s_mp_prime_tab[] = {
0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
-#endif
};
#endif
diff --git a/demo/shared.c b/demo/shared.c
index dc8e05a..e47e481 100644
--- a/demo/shared.c
+++ b/demo/shared.c
@@ -23,9 +23,6 @@ void ndraw(mp_int *a, const char *name)
void print_header(void)
{
-#ifdef MP_8BIT
- printf("Digit size 8 Bit \n");
-#endif
#ifdef MP_16BIT
printf("Digit size 16 Bit \n");
#endif
diff --git a/demo/test.c b/demo/test.c
index 4c3f1cc..9002e96 100644
--- a/demo/test.c
+++ b/demo/test.c
@@ -1022,7 +1022,6 @@ static int test_mp_prime_is_prime(void)
}
/* Check regarding problem #143 */
-#ifndef MP_8BIT
mp_read_radix(&a,
"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
16);
@@ -1041,8 +1040,6 @@ static int test_mp_prime_is_prime(void)
putchar('\n');
goto LBL_ERR;
}
-#endif
-
printf("\n\n");
mp_clear_multi(&a, &b, NULL);
@@ -2040,17 +2037,9 @@ static int test_mp_root_u32(void)
if ((e = mp_init_multi(&a, &c, &r, NULL)) != MP_OKAY) {
return EXIT_FAILURE;
}
-#ifdef MP_8BIT
- for (i = 0; i < 1; i++) {
-#else
for (i = 0; i < 10; i++) {
-#endif
mp_read_radix(&a, input[i], 64);
-#ifdef MP_8BIT
- for (j = 3; j < 10; j++) {
-#else
for (j = 3; j < 100; j++) {
-#endif
mp_root_u32(&a, (uint32_t)j, &c);
mp_read_radix(&r, root[i][j-3], 10);
if (mp_cmp(&r, &c) != MP_EQ) {
diff --git a/doc/bn.tex b/doc/bn.tex
index 5512bcd..27f27e7 100644
--- a/doc/bn.tex
+++ b/doc/bn.tex
@@ -2035,9 +2035,7 @@ from the Libtommath build if not needed.
\begin{alltt}
int mp_prime_frobenius_underwood(const mp_int *N, int *result)
\end{alltt}
-Performs the variant of the Frobenius test as described by Paul Underwood. The single internal use is in
-\texttt{mp\_prime\_is\_prime} for \texttt{MP\_8BIT} only but can be included at build-time for all other sizes
-if the preprocessor macro \texttt{LTM\_USE\_FROBENIUS\_TEST} is defined.
+Performs the variant of the Frobenius test as described by Paul Underwood. It can be included at build-time if the preprocessor macro \texttt{LTM\_USE\_FROBENIUS\_TEST} is defined and will be used instead of the Lucas-Selfridge test.
It returns \texttt{MP\_ITER} if the number of iterations is exhausted, assumes a composite as the input and sets \texttt{result} accordingly. This will reduce the set of available pseudoprimes by a very small amount: test with large datasets (more than $10^{10}$ numbers, both randomly chosen and sequences of odd numbers with a random start point) found only 31 (thirty-one) numbers with $a > 120$ and none at all with just an additional simple check for divisors $d < 2^8$.
@@ -2053,7 +2051,7 @@ int mp_is_square(const mp_int *arg, int *ret);
\begin{alltt}
int mp_prime_is_prime (mp_int * a, int t, int *result)
\end{alltt}
-This will perform a trial division followed by two rounds of Miller-Rabin with bases 2 and 3 and a Lucas-Selfridge test. The Lucas-Selfridge test is replaced with a Frobenius-Underwood for \texttt{MP\_8BIT}. The Frobenius-Underwood test for all other sizes is available as a compile-time option with the preprocessor macro \texttt{LTM\_USE\_FROBENIUS\_TEST}. See file
+This will perform a trial division followed by two rounds of Miller-Rabin with bases 2 and 3 and a Lucas-Selfridge test. The Frobenius-Underwood is available as a compile-time option with the preprocessor macro \texttt{LTM\_USE\_FROBENIUS\_TEST}. See file
\texttt{bn\_mp\_prime\_is\_prime.c} for the necessary details. It shall be noted that both functions are much slower than
the Miller-Rabin test and if speed is an essential issue, the macro \texttt{LTM\_USE\_ONLY\_MR} switches both functions, the Frobenius-Underwood test and the Lucas-Selfridge test off and their code will not even be compiled into the library.
diff --git a/mtest/mtest.c b/mtest/mtest.c
index 06c9afb..c8d9e95 100644
--- a/mtest/mtest.c
+++ b/mtest/mtest.c
@@ -28,11 +28,7 @@ mulmod
*/
-#ifdef MP_8BIT
-#define THE_MASK 127
-#else
#define THE_MASK 32767
-#endif
#include <stdio.h>
#include <stdlib.h>
diff --git a/testme.sh b/testme.sh
index 40fa32d..2f7235f 100755
--- a/testme.sh
+++ b/testme.sh
@@ -378,13 +378,11 @@ do
then
_runvalgrind "$i $a" "$CFLAGS"
[ "$WITH_LOW_MP" != "1" ] && continue
- _runvalgrind "$i $a" "-DMP_8BIT $CFLAGS"
_runvalgrind "$i $a" "-DMP_16BIT $CFLAGS"
_runvalgrind "$i $a" "-DMP_32BIT $CFLAGS"
else
_runtest "$i $a" "$CFLAGS"
[ "$WITH_LOW_MP" != "1" ] && continue
- _runtest "$i $a" "-DMP_8BIT $CFLAGS"
_runtest "$i $a" "-DMP_16BIT $CFLAGS"
_runtest "$i $a" "-DMP_32BIT $CFLAGS"
fi
diff --git a/tommath.h b/tommath.h
index 6c4e957..cca5411 100644
--- a/tommath.h
+++ b/tommath.h
@@ -6,6 +6,10 @@
#include <stdint.h>
#include <stddef.h>
+#ifdef MP_8BIT
+# error "Support of 8-bit architectures has been dropped in this version of LTM."
+#endif
+
#ifndef MP_NO_FILE
# include <stdio.h>
@@ -35,7 +39,7 @@ extern "C" {
defined(__sparcv9) || defined(__sparc_v9__) || defined(__sparc64__) || \
defined(__ia64) || defined(__ia64__) || defined(__itanium__) || defined(_M_IA64) || \
defined(__LP64__) || defined(_LP64) || defined(__64BIT__)
-# if !(defined(MP_64BIT) || defined(MP_32BIT) || defined(MP_16BIT) || defined(MP_8BIT))
+# if !(defined(MP_64BIT) || defined(MP_32BIT) || defined(MP_16BIT))
# if defined(__GNUC__) && !defined(__hppa)
/* we support 128bit integers only via: __attribute__((mode(TI))) */
# define MP_64BIT
@@ -47,7 +51,7 @@ extern "C" {
#endif
#ifdef MP_DIGIT_BIT
-# error Defining MP_DIGIT_BIT is disallowed, use MP_8/16/31/32/64BIT
+# error Defining MP_DIGIT_BIT is disallowed, use MP_16/31/32/64BIT
#endif
/* some default configurations.
@@ -59,11 +63,8 @@ extern "C" {
* [any size beyond that is ok provided it doesn't overflow the data type]
*/
-#ifdef MP_8BIT
-typedef uint8_t mp_digit;
-typedef uint16_t private_mp_word;
-# define MP_DIGIT_BIT 7
-#elif defined(MP_16BIT)
+
+#if defined(MP_16BIT)
typedef uint16_t mp_digit;
typedef uint32_t private_mp_word;
# define MP_DIGIT_BIT 15