Transcript Primes, Factorization, and the Euclidean Algorithm

Primes, Factorization, and the
Euclidean Algorithm
• The purpose of sections 4.1 and 4.2 is to
provide the mathematics background
necessary to understand the RSA
Cryptosystem. The RSA cryptosystem is widely
used today…
Prime Numbers
• A positive number p > 1 is prime if its only positive
integer divisors are 1 and itself.
• A number that is not prime is said to be composite.
• A list of the primes less than 100 are: {2, 3, 5, 7, 11, 13,
17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 91, 97}
• Facts about primes:
– There are an infinite number of primes. (proof)
– Every natural number can be factored into a product of
primes (Fundamental Theorem of Arithmetic). (proof: Use
induction.)…
Determining the Primality of Larger
Positive Integers
• Determining whether a large number is prime is important today in
cryptology.
• Fact: 2 is the only even prime. Any even number larger than 2 is
not prime since 2 is a divisor.
• Example 1: Is 10000024 prime?.
– Answer: No, since 10000024 is even, and hence divisible by 2.
• How can we determine if a number N is prime?
– The fundamental theorem of arithmetic says that all numbers can be
factored into a product of primes.
– Note: The largest number p that can divide into N satisfies: p ≤ N^(1/2)
(the square root of N).
– By dividing all the primes that satisfy the second observation into N,
we can determine if N is prime.
– Note: With a computer program, it is much easier to test all numbers n
≤ N, then to first determine if the number is prime.
Determining the Primality of Larger
Positive Integers
•
•
•
•
•
•
Example 2: Is 127 prime?
Example 3: Determine if 839 is prime?
Example 4: Is 1073 prime?
Example 5: Is 1709 prime?
Example 6: Determine if 958090550047 is Prime?
Being able to determine whether large numbers are
prime will be important later on when we study the
RSA cryptosystem. To deal with larger numbers, much
more sophisticated tests for primality testing have
been developed and are an ongoing topic of research.
• Largest Prime Number…
Factorization of Composite
Numbers
• If a number is composite, then it can be
factored into primes.
• Example 7: Factor 3267 into a product of
prime factors.
• Example 8: Factor 429229 into a product of
prime factors.
• Example 9: Factor 1511 into a product of
prime factors…
The Greatest Common Divisor Of
Two Numbers
• Given two numbers a, and b the greatest common divisor:
– Is denoted gcd(a, b).
– Is the largest integer that will divide evenly into both a and b.
• One way to find the gcd is to list all the primes of the two
numbers and then find all those in common.
– Example: Find gcd(50, 70).
– Example: Find gcd(24, 36).
– This method is not practical when the numbers get large.
• A second way is using the Euclidean Algorithm.
– The Euclidean Algorithm
• Example 10: Find gcd(2299, 627).
• Example 11: Find the gcd(54321, 9875)…
The Greatest Common Divisor of
Two Numbers
• Theorem: For any two positive integers a and b,
there are integers s and t where:
– as + bt = gcd(a, b)
– Note: To finds and t, we solve for the remainders
starting with the first step in the Euclidean algorithm,
substituting each remainder we obtain into the
remainders we obtain in successive steps until the gcd
of a and b is reached.
– Example 12: Find s and t where as + bt = gcd(2299,
627).
– Example 13: Find s and t where as + bt = gcd(54321,
9875)…
The Greatest Common Divisor of
Two Numbers
• Now we want to consider the problem of solving the
modular equation bt = 1 MOD a for t.
– Here t is the multiplicative inverse of b MOD a.
• Notation
–
–
–
–
–
–
–
Example 14: Find Multiplicative Inverse
Corollary: Relatively Prime
Example 15: Compute Inverse
Example 16: Compute Inverse
Example 17: Solve Equation
Note if gcd(a, b)≠ 1 then the inverse of b does not exist.
Example 18: Compute Inverse…!