摘要 |
PURPOSE:To decrease a calculation processing and to shorten the prime number deciding time by deciding successively a composite number, or a non-composite number, or a prime number by the first - the third deciding means and a random number generating means. CONSTITUTION:A given positive integer N is inputted to the first deciding means 8, and unless N is a prime to each other to a positive integer M determined in advance, it is decided that N is not a prime number. When the first deciding means 8 has not decided that N is not a prime number, the second deciding means 10 decides that N is not a prime number if A<(>N<-1)/2>(mod N) is not '1' nor N-1, with respect to an integer generated by a random number generating means 9. Also, when the second deciding means 10 decides that N is not a prime number with respect to the optional number of random numbers generated by the random number generating means 9, the third deciding means 11 decides that N is a prime number.
|