Merge pull request #273 from czurnieden/cleanup_prime_is_prime prime_is_prime: remove obsolete restriction on PRIME_SIZE
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
diff --git a/bn_mp_prime_is_prime.c b/bn_mp_prime_is_prime.c
index 6f91e18..c020e62 100644
--- a/bn_mp_prime_is_prime.c
+++ b/bn_mp_prime_is_prime.c
@@ -137,41 +137,12 @@ mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
}
/*
- abs(t) extra rounds of M-R to extend the range of primes it can find if t < 0.
Only recommended if the input range is known to be < 3317044064679887385961981
- It uses the bases for a deterministic M-R test if input < 3317044064679887385961981
+ It uses the bases necessary for a deterministic M-R test if the input is
+ smaller than 3317044064679887385961981
The caller has to check the size.
-
- Not for cryptographic use because with known bases strong M-R pseudoprimes can
- be constructed. Use at least one M-R test with a random base (t >= 1).
-
- The 1119 bit large number
-
- 80383745745363949125707961434194210813883768828755814583748891752229742737653\
- 33652186502336163960045457915042023603208766569966760987284043965408232928738\
- 79185086916685732826776177102938969773947016708230428687109997439976544144845\
- 34115587245063340927902227529622941498423068816854043264575340183297861112989\
- 60644845216191652872597534901
-
- has been constructed by F. Arnault (F. Arnault, "Rabin-Miller primality test:
- composite numbers which pass it.", Mathematics of Computation, 1995, 64. Jg.,
- Nr. 209, S. 355-361), is a semiprime with the two factors
-
- 40095821663949960541830645208454685300518816604113250877450620473800321707011\
- 96242716223191597219733582163165085358166969145233813917169287527980445796800\
- 452592031836601
-
- 20047910831974980270915322604227342650259408302056625438725310236900160853505\
- 98121358111595798609866791081582542679083484572616906958584643763990222898400\
- 226296015918301
-
- and it is a strong pseudoprime to all forty-six prime M-R bases up to 200
-
- It does not fail the strong Bailley-PSP test as implemented here, it is just
- given as an example, if not the reason to use the BPSW-test instead of M-R-tests
- with a sequence of primes 2...n.
-
+ TODO: can be made a bit finer grained but comparing is not free.
*/
if (t < 0) {
t = -t;
@@ -200,15 +171,6 @@ mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
}
}
- /* for compatibility with the current API (well, compatible within a sign's width) */
- if (p_max < t) {
- p_max = t;
- }
-
- if (p_max > MP_PRIME_SIZE) {
- err = MP_VAL;
- goto LBL_B;
- }
/* we did bases 2 and 3 already, skip them */
for (ix = 2; ix < p_max; ix++) {
mp_set(&b, ltm_prime_tab[ix]);
diff --git a/doc/bn.tex b/doc/bn.tex
index 906e58e..a183729 100644
--- a/doc/bn.tex
+++ b/doc/bn.tex
@@ -2018,11 +2018,7 @@ If $t$ is set to a positive value $t$ additional rounds of the Miller-Rabin test
One Miller-Rabin tests with a random base will be run automatically, so by setting $t$ to a positive value this function will run $t + 1$ Miller-Rabin tests with random bases.
-If $t$ is set to a negative value the test will run the deterministic Miller-Rabin test for the primes up to
-$3317044064679887385961981$. That limit has to be checked by the caller. If $-t > 13$ than $-t - 13$ additional rounds of the
-Miller-Rabin test will be performed but note that $-t$ is bounded by $1 \le -t < PRIME\_SIZE$ where $PRIME\_SIZE$ is the number
-of primes in the prime number table (by default this is $256$) and the first 13 primes have already been used. It will return
-\texttt{MP\_VAL} in case of$-t > PRIME\_SIZE$.
+If $t$ is set to a negative value the test will run the deterministic Miller-Rabin test for the primes up to $3317044064679887385961981$. That limit has to be checked by the caller.
If $a$ passes all of the tests $result$ is set to one, otherwise it is set to zero.