|
Size: 1675
Comment:
|
← Revision 18 as of 2020-01-26 17:11:14 ⇥
Size: 1540
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 28: | Line 28: |
| 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 <<latex($\phi(n)$)>>. If a number is of this order, it is referred to as a primative root. | 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. |
| Line 32: | Line 32: |
| Given a primary root a, the index i of a number n is the power of a such that <<latex($n=a^i$)>>. The index thought of as a function behaves like a 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. |
| Line 34: | Line 34: |
| {{{#!latex \usepackage{geometry} \geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in} %%end-prologue%% 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} }}} |
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}$$$ |
Fermat's Little Theorem
See
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
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
The equation below gives the exponential form and then the logarithmic form where