(Difficult) The most difficult part to understand in this section was the Miller-Rabin Primality Test: The process itself seemed straightforward, except for how we get the value m for n -1 = 2^k (m). It seems as though we take n - 1, then divide it by 2 until the quotient is an odd number, then we use that odd number as m? Once we have m, the test is fairly straight forward: square 2^m (mod n) until we get a result that is +/- 1.The other question I had was if we are guaranteed to get a -1 or +1 for every test. Is it possible that any (mod n) group would not have a square congruent to 1 or -1? This would imply that no element of the group was its own inverse, right?
(Reflective) I was thinking about why a definitive primalty test was more difficult than proving a number is composite, and in reading pg. 181 I realized it goes back to the Jacobi Symbol, where we had 'a' over 'n' = 1. Since this 'a' over 'n' was equal to 1, if n was composite, then a/p and a/q would be equal, and could either be +/- 1. Thus, without factoring n into p and q, we could not say whether 'a' was a square or not. Likewise with primality testing, it leaves us with a "probable answer" but doesn't guarantee a prime without further work. Given the similarities in testing for square roots mod n, and testing primality, it would seem the only "simple" way to prove primality would be to factor the number. My question now is how does the AKS algorithm prove primality without factoring?
No comments:
Post a Comment