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 $ϕ (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{array}{r} x = a^{i n d_{a, p} (x)} mod p \\ i n d_{a, p} (x) = c mod p \end{array}$

-  ⇤ ← Revision 9 as of 2005-10-18 15:01:47 → 
  Size: 8757
  Editor: yakko
  Comment:
+   ← Revision 18 as of 2020-01-26 17:11:14 → ⇥
  Size: 1540
  Editor: 68
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 3:
-{{{#!latex2
\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
\usepackage{geometry}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in}
+See  $L A T E X$  document:
-Line 34:
+Line 5:
-%%end-prologue%%

 $Unknown environment 'theorem'$ 

 $Unknown environment 'proof'$ 

 $Unknown environment 'theorem'$ 

 $Unknown environment 'definition'$ 

 $Unknown environment 'lemma'$ 

 $Unknown environment 'theorem'$ 

 $Unknown environment 'proof'$ 

 $Unknown environment 'theorem'$ 

 $Unknown environment 'proof'$ 

 $Unknown environment 'theorem'$ 

 $Unknown environment 'corollary'$ 

 $Unknown environment 'theorem'$ 

 $Unknown environment 'proof'$ 
}}}
+ * [[attachment:fermatlittle.pdf]]
 * [[attachment:fermatlittle.tex]]
-Line 276:
+Line 12:
+A prime number is a number that is divisable only by 1 and itself.
-Line 277:
+Line 14:
-'''What is the meaning of the xpresion a divides b?'''
+'''What is the meaning of the expression a divides b?'''
-Line 279:
+Line 16:
+a divides b if a is a factor of b.
-Line 282:
+Line 20:
+Given a number n the totient of n is the number of integers less than n that are relatively prime to n.
-Line 285:
+Line 24:
+By repeatedly running the test with different random numbers we and getting indeterminite answers we increase the probability that a number is prime.
-Line 287:
+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  $ϕ (n)$ . If a number is of this order, it is referred to as a primative root.
-Line 288:
+Line 31:
+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{array}{r} x = a^{i n d_{a, p} (x)} mod p \\ i n d_{a, p} (x) = c mod p \end{array}$

Diff for "Csce877Ch8Notes"

Review Questions