P4
A DESCRIPTION OF THE PROBLEM :
The enhancement request concerns the function "passesMillerRabin" from the class BigInteger.
When performing the probabilistic Miller-Rabin primality test on a prime candidate n, some base b from interval [1, n-1] must be chosen. The Miller-Rabin test will then output "composite" or "probable prime" for prime candidate n. For at most 1/4 of the possible bases b, the test will output "probable prime" although n is composite. When this happens, the chosen base b is called a strong liar (to primality) for n.
The bases b=1 and b=n-1= -1(mod n) are strong liars for all candidates n.
These bad choices can be avoided by choosing the base b from interval [2, n-2].
In the implementation "passesMillerRabin" from the class BigInteger, the base b is chosen from interval [2, n-1].
In order to improve the implemetation by choosing bases b from interval [2, n-2], the code line
} while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);
could be replaced with
} while (b.compareTo(ONE) <= 0 || b.compareTo(thisMinusOne) >= 0);
The comment above the algorithm indicates that the test is taken from the DSA spec (NIST FIPS 186-2).
In fact, this specification suggests choosing base b in range [2, n-1]. Thus, the algorithm does align to this specification.
However, 186-2 was superseded in 2001. The most current revision of this publication is 186-5. Here, the base b is chosen in range [2, n-2]. This has been the case since version 186-3.
References:
FIPS 186-5, chapter B.3.1, Process step 4.2, https://csrc.nist.gov/publications/fips#fips186-5
FIPS 186-3, chapter C.3.1, Process step 4.2, https://csrc.nist.gov/csrc/media/publications/fips/186/3/archive/2009-06-25/documents/fips_186-3.pdf
FIPS 186-2, chapter 2.1, process step 3, https://csrc.nist.gov/csrc/media/publications/fips/186/2/archive/2000-01-27/documents/fips186-2.pdf
Further Reference:
The Handbook of Applied Cryptography, Chapter 4.2.3 (5th printing, 2001)
The enhancement request concerns the function "passesMillerRabin" from the class BigInteger.
When performing the probabilistic Miller-Rabin primality test on a prime candidate n, some base b from interval [1, n-1] must be chosen. The Miller-Rabin test will then output "composite" or "probable prime" for prime candidate n. For at most 1/4 of the possible bases b, the test will output "probable prime" although n is composite. When this happens, the chosen base b is called a strong liar (to primality) for n.
The bases b=1 and b=n-1= -1(mod n) are strong liars for all candidates n.
These bad choices can be avoided by choosing the base b from interval [2, n-2].
In the implementation "passesMillerRabin" from the class BigInteger, the base b is chosen from interval [2, n-1].
In order to improve the implemetation by choosing bases b from interval [2, n-2], the code line
} while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);
could be replaced with
} while (b.compareTo(ONE) <= 0 || b.compareTo(thisMinusOne) >= 0);
The comment above the algorithm indicates that the test is taken from the DSA spec (NIST FIPS 186-2).
In fact, this specification suggests choosing base b in range [2, n-1]. Thus, the algorithm does align to this specification.
However, 186-2 was superseded in 2001. The most current revision of this publication is 186-5. Here, the base b is chosen in range [2, n-2]. This has been the case since version 186-3.
References:
FIPS 186-5, chapter B.3.1, Process step 4.2, https://csrc.nist.gov/publications/fips#fips186-5
FIPS 186-3, chapter C.3.1, Process step 4.2, https://csrc.nist.gov/csrc/media/publications/fips/186/3/archive/2009-06-25/documents/fips_186-3.pdf
FIPS 186-2, chapter 2.1, process step 3, https://csrc.nist.gov/csrc/media/publications/fips/186/2/archive/2000-01-27/documents/fips186-2.pdf
Further Reference:
The Handbook of Applied Cryptography, Chapter 4.2.3 (5th printing, 2001)