Vulnese algorithm (2)
The algorithm of the simple number determination is discussed last time, but this algorithm is considerably, it is quite a force for the number of prime numbers (generally less than 108). For example, in the wide range of applications in the public key system, the number of ordinary selection is quite large (usually in 100 or more), if the last test method is used, then it is possible to exhaust your life. Time is not enough. So in the general application field, people use the Rabin-Miller testing. Below is the algorithm of the test method:
First, one measured random number P is selected, and B, B is 2, and the number of times P-1 is used. Then calculate M such that n = 1 (2 ^ b) m.
(1) Select a random number of less than P. (2) Set j = 0 and z = a ^ m mod p (3) If z = 1 or z = p-1, then P By testing, the number of pins (4) can be used if j> 0 and z = 1, then P is not a number (5) set J = J 1. If J P-1, set z = z ^ 2 mod p, then return to (4). If z = p-1, then P is tested, it may be the number of prime. (6) If j = b and z <> p-1, not the number of prime
The probability of digital A was 75%. This means that when the number of iterations is T, it does not exceed 1/4 ^ t. In fact, for most random numbers, almost 99.99% is affirmative A is evidence.
Actual considerations:
In the actual algorithm, the number of generated places is very fast.
(1) Generating a n-bit random number P (2) set high and low position of 1 (set the high position to ensure the number of digits, the low position is to ensure the odd number) (3) Check to ensure that P cannot be by any small pills Except: such as 3, 5, 7, 11, etc. A effective method is to test the number of prime numbers less than 2000. Using a row method faster (4) Running Rabin-miller detection for a random number A, if P is passed, then a random number A is generated at test. Select a small A value to ensure the speed. Do 5 Rabin-Miller test If P fails there, it produces P, and then tested.
After testing, this algorithm implements: 2 .8 seconds to generate a 256-bit prime number 24.0 seconds to generate a 512-bit per 2 minutes to generate a 768-bit number of prime numbers to generate a 1024 bit
