p: and q: implement Miller-Rabin as modelled by Cliff Reiter. You can see the model by following the link in the "q: improved" item in the J5.04 release notes. http://www.jsoftware.com/books/help/release/qco.htm
If the test says a number is composite then it is composite; if it says a number is prime then the probability of an error is 0.25^100. Calling 1&p: or q: more than once on the same argument does not buy you anything. ----- Original Message ----- From: Andrew Nikitin <[EMAIL PROTECTED]> Date: Saturday, June 17, 2006 6:33 pm Subject: [Jprogramming] details on 1&p: > Dictionary says about 1&p: > "Currently, arguments larger than 2^31 are tested to be prime > according to a > probabilistic algorithm (Miller-Rabin)." > > Miller Rabin (as described in a book) is supposed to choose a at > random, > raise it to some power (modulo n) and test the result for certain > property. > This test process is repeated until desired probability is reached. > Few questions: > How J chooses a? > How many times it performs the test? > Does it choose different a if 1&p: called on same number again? > > The point of my questions is, if I want to test that number is > prime with > probability of mistake less then, say 2^-200, does it make sense > to call > 1&p: more than once, and if yes, how many times (assuming 1/4 per > random a). ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
