1. I understand the first two subheadings just fine (The Basic Principle and Fermat's Primality Test). I don't understand the Miller-Rabin Primality Test very well, though. From what I understand, however, it's basically a recurrence algorithm in which you find congruences to some random integer (a) raised to a previously found odd integer. You keep doing this working with the new congruences until you arrive at some number that is in fact congruent to 1 (mod n). Having arrived thus, n can be declared composite. Or you will eventually get to something congruent to -1? My question is, will you always arrive at 1 or -1?
2. On a minor note, what are "pseudoprimes" and "strong pseudoprimes" and the like? Also, these tests always seem to result in vague statements as to the probability that a number is prime. Are there any deterministic tests for large primes?
No comments:
Post a Comment