Confused on Miller-Rabin

Question

As an exercise for myself, I'm implementing the Miller-Rabin test. (Working through SICP). I understand Fermat's little theorem and was able to successfully implement that. The part that I'm getting tripped up on in the Miller-Rabin test is this "1 mod n" business. Isn't 1 mod n (n being some random integer) always 1? So I'm confused at what a "nontrivial square root of 1 modulo n" could be since in my mind "1 mod n" is always 1 when dealing with integer values. What am I missing?

Answer 1

1 is congruent to 9 mod 8 so 3 is a non trivial square root of 1 mod 8.

what you are working with is not individual numbers, but equivalence sets. [m]n is the set of all numbers x such that x is congruent to m mod n. Any thing that sqaures to any element of this set is a square root of m modulo n.

given any n, we have the set of integers modulo n which we can write as Zn. this is the set (of sets) [1]n, [2]n, ... ,[n]n. Every integer lies in one and only one of those sets. we can define addition and multiplication on this set by [a]n + [b]n = [a + b]n and likewise for multiplication. So a square root of [1]n is a(n element of) [b]n such that [b*b]n = [1]n.

In practice though, we can conflate m with [m]n and normally choose the unique element, m' of [m]n such that 0 <= m' < n as our 'representative' element: this is what we usually think of as the m mod n. but it's important to keep in mind that we are 'abusing notation' as the mathematicians say.

here's some (non-idiomatic) python code as I don't have a scheme interpreter ATM:

>>> def roots_of_unity(n):
...      roots = []
...      for i in range(n):
...          if i**2 % n == 1:
...               roots.append(i)
...      return roots
... 
>>> roots_of_unity(4)
[1, 3]
>>> roots_of_unity(8)
[1, 3, 5, 7]
>>> roots_of_unity(9)
[1, 8]

So, in particular (looking at the last example), 17 is a root of unity modulo 9. indeed, 17^2 = 289 and 289 % 9 = 1. returning to our previous notation [8]9 = [17]9 and ([17]9)^2 = [1]9

Answer 2

I believe that the misunderstanding comes from the definition the book gives about the nontrivial root:

a “nontrivial square root of 1 modulo n” , that is, a number not equal to 1 or n - 1 whose square is equal to 1 modulo n

Where I believe it should say:

whose square is congruent to 1 modulo n

Answer 3

That is why the wording was for a NONTRIVIAL square root of 1. 1 is a trivial square root of 1, for any modulus n.

17 is a non-trivial square root of 1, mod 144. Thus 17^2 = 289, which is congruent to 1 mod 144. If n is prime, then 1 and n-1 are the two square roots of 1, and they are the only two such roots. However, for composite n there are generally multiple square roots. With n = 144, the square roots are {1,17,55,71,73,89,127,143}.