Cs425
Stallings Cryptography and NetWork Security
Chapter 8 (Introduction to Number Theory)
Spring 2003

8.1 Prime Numbers

Definition

A positive integer $p>1$ is prime if its only divisors are $\pm 1$ and $\pm p.$

Theorem

(Fundamental Theorem of Arithmatic) Every positive integer $n$ can be written uniquely as
MATH
where MATH and $n_{t}>0$

8.2 Fermat's and Euler's Theorem

Theorem

If $G$ is a finite group of order $n,$ then $g^{n}=1$ for every element $g$ of $G$

Proof: The theorem is true for any finite group, but we will prove it only for the abelian case. Write out the elements of $G$ as MATH If we multiply each element by $g,$ then we have the set MATH Because we can cancel in $G,$ these two sets must be equal. Multiplyting them together we get MATH Cancelling leaves MATH

Theorem

(Fermat's Little Theorem) If $p$ is a prime number and $a$ is any integer not divisible by $p,$ then
MATH

Proof: If $p$ is prime, the non-zero elements of $Z_{p}$ from a group of order $p-1$ under multiplication$\blacksquare $

Note that MATH does not imply $n$ is prime.

Definition

A Fermat pseudoprime base b is a composite number $n$ which satisfies the Fermat condition MATH. For example MATH but MATH

Definition

A Carmichael number is a pseudoprime for every possible base $b$: that is, for every $b$ coprime to $n$. It was recently shown that there infinitely many of these numbers. The carmichael numbers less than 10,000 are
MATH
For example MATH MATH MATH etc.

Definition

Euler's Totient function, MATH is the number of positive integers less than $n$ and relatively prime to $n.$

Lemma

MATH for a prime and MATH if $p$ and $q$ are primes

Theorem

(Euler's Totient Theorem) If MATH then MATH

Proof: The integers relatively prime to $n,$ form a group under multiplication modulo $n$ of order MATH

8.3 Testing for Primality

Testing $n$ for primality. We may assume $n$ is odd. Write
MATH

Choose an integer $a,1<a<n-1$ and compute the sequence
MATH
If $n$ is prime, then we know that MATH. However, there may be an earlier element in the list with residue $1.$ Let $j,0\leq j\leq k$ be the smallest value such that MATH Two cases:

Case 1 MATH In this case MATH

Case 2 MATH Then MATH Therefore $n$ divides one of these products. By choice of $j,$ $n$ does not divide MATH Therefore $n$ divides MATH implies MATH If $n$ is prime, then either MATH or MATH for some $j.$ If $n$ does not pass this test it is composite. If the number does pass the test, it might be composite.

final int COMPOSITE = 1;

final int INCONCLUSIVE = 2;

int Test(int n){

Find $k$ such that $n-1=2^{k}q$

$a=$ random(2,n-2);

if MATH

return INCONCLUSIVE;

for (int j = 0; j < k; j++)

if (MATH

return INCONCLUSIVE

return COMPOSITE;

}

If the function returns COMPOSITE then the number is composite. If it returns INCONCLUSIVE then the number may be prime or composite. However, we can actually compute the probability the number is composite.

Note. Could also think of INCONCLUSIVE as Probably Prime.

Theorem

(Miller-Rabin) If Test(n) returns INCONCLUSIVE the number $n$ is composite with probability <$\frac{1}{4}.$

If you repeat Test(n) $k$ times with $k$ independent choices of $a,$ then $n$ is prime with probability $1-\frac{1}{4^{k}}.$

Example 1 $977$

MATH

MATH

MATH

Example 2 $221$

MATH

MATH

MATH

MATH

Example 3 $100\,697$

MATH

MATH

MATH

MATH

MATH

Agrawal, Kayal and Saxena published a paper on 6 August 2002 entitled PRIMES is in P. They found a deterministic algorithm which always prime or not prime and does it in polynomial time. It is, however, still relatively slow.

8.4 The Chinese Remainder Theorem

Modern formulation
Definition

If $R_{1},\cdots R_{k}$ are rings, then the Cartesian product of the rings MATH is a ring under componetwise addition and multiplication

Let MATH be pairwise relatively prime integers, that is, MATH Then MATH There is a $1-1$ correspondence given by MATH

Example $n=10$

MATH

Classical Formulation

Let MATH be pairwise relatively prime integers, that is, MATH Then the system of congruences
MATH
has a unique solution modulo $m.$

Example

MATH

MATH implies that $x=12+101k.$ Substitute this into the second equation to get MATH Since $73$ and $101 $ are relatively prime, $101$ has an inverse mod $73$ so we can solve for $k$ to get MATH Use this to find MATH

Check.

MATH

MATH

8.5 Discrete Logarithms

By our previous theorem, we know that if MATH then MATH

Definition

The smallest integer $k$ such that MATH is called the order of $a$ mod $n.$ If the order $a$ is MATH then we say that $a$ is a primitive root of n.

Lemma

If $a$ is a primitive root of $n$ then every number $x$ such that MATH is of the form $x=a^{s}$ for some MATH

Proof The powers MATH are unique and there are MATH of them.$\blacksquare $

Corollary

For any prime number $p,$ integer $n>0,$ primitive root $a$ of $p,$ there is an a unique integer $s,0\leq s\leq p-1$ such that MATH

Example $p=11$

The powers of $2\func{mod}11$ are MATH so $2$ is a primitive root of $11.$ However, the powers of $9\func{mod}11$ are $9,4,3,5,1$ so $9$ is not a primitive root of $11.$

n index
$1$ $0$
$2$ $1$
$3$ $8$
$4$ $2$
$5$ $4$
$6$ $9$
$7$ $7$
$8$ $3$
$9$ $6$
$10$ $5$

Definition

In analogy with traditional logarithms, we define the discrete logarithm of $x\func{mod}p$ base $a$ to be the unique integer $s,0\leq s\leq p-1$ such that MATH

Given $x,a,$ and $p,$ it is trivial to write an algorithm to find MATH simply by computing powers of $a$ up to $p-1 $ and finding the index $s$ such that MATH If $p $ is large, this is not feasible. Apparently, computing a discrete logarithm is as difficult as factoring a number.

This document created by Scientific Notebook 4.1.