Fermat's Little Theorem
See $$\LaTeX$$ document:
Review Questions
What is a prime number?
A prime number is a number that is divisable only by 1 and itself.
What is the meaning of the expression a divides b?
a divides b if a is a factor of b.
What is Euler's totient?
Given a number n the totient of n is the number of integers less than n that are relatively prime to n.
The Miller-Rabin test can determine if a number is not prime but can't determine if a number is prime. How can such an algorithm be used to test for primality?
By repeatedly running the test with different random numbers we and getting indeterminite answers we increase the probability that a number is prime.
What is a primative root of a number?
A primitive root is a number a that generates (via powers) a set (like Zn). We can also say that the highest possible exponent to which a number can belong (mod n) is $$\phi(n)$$. If a number is of this order, it is referred to as a primative root.
What is the difference between an index and a discrete logarithm?
Given a primary root a, the index i of a number n is the power of a such that $$n=a^i$$. The index thought of as a function behaves like a logarithm.
The equation below gives the exponential form and then the logarithmic form where $$x=a^c$$: $$$\begin{eqnarray} x = a^{ind_{a,p}(x)} \bmod p \\ ind_{a,p}(x)= c \bmod p \end{eqnarray}$$$