Topics:
• Outlining the proof that there is no largest prime number
For this purpose the best source to use is Delphi For Fun on Proof by Contradiction, which explains a bit of the logic behind proofs by contradiction. You may then also want to look at these sources:
Why are there infinitely many prime numbers? (from Peter Alfeld, University of Utah)
Euclid's proof that there are an infinite number of primes (from Susan Stepney, University of York, UK) - this one, beware: the part below the line, where it says "for example", is not part of the proof!
And also the sources linked below...
• How Euclid (and those of his time and place) conceived of the proof and their concept of "number":
See Cut-The-Knot, which gives alternate versions of the proof as well,but is rather technical: and also the proof as described in the Prime Number Pages, which describes how Euclid would have thought of numbers.
Here is the outline of the proof we developed in class. I've put an asterisk * next to parts that need proving but are not proved in any of the sources linked above, for some reason. We did the proofs of those parts in previous classes.
To prove: there is no largest prime number
Proving by contradiction (reductio ad absurdum): we will assume the opposite, and show that assumption leads to a contradiction.
Outline of Proof:
• Assume that there is a largest prime number. Call it p.
[Note: either there is a largest prime number, or there is not a largest prime number. There is no other possibility. This is important for the logic of the proof.]
Commentary: This assumption puts us into an alternate universe, not the one we actually live in. The rest of this proof will be showing that that alternate universe cannot exist. In that alternate universe, we know everything else we know about prime numbers from our universe, including the Fundamental Theorem of Arithmetic (Unique Prime Factorization), but we are assuming that in that universe there is a largest prime number.
OK, now in the alternate universe:
• Construct the number N = (the product of all the prime numbers 2 through p) +1.
Then N has these properties:
* • N > p
[so N cannot be prime, as p is the largest prime number in the alternate universe]
* • N is not divisible by any of the prime numbers 2 through p
[so N must be prime, as these are all the possible prime factors of N in the alternate universe]
• But N cannot be both non-prime and prime at the same time:
CONTRADICTION!
A final note about this proof: where do we use the Fundamental Theorem of Arithmetic? It is in the step where we prove that N is not divisible by any of the prime numbers 2 through p, and conclude from this that N must be prime. (Some people say that we conclude that either N is prime or N has a prime factor greater than p. The second part is not necessary, but if it makes you feel better, go ahead and put it in. You'll have to patch up the contradiction in the last line of the proof, in that case.)
27 October 2016
20 October 2016
Thursday 20 October class
Topic:
Outlining the "proof" that the RSA works, for the example given in my notes.
This is not a real proof (hence the scare quotes above), because it only proves that RSA works for this particular example. However, if you read carefully, you can see that nothing in the proof depends on the specific numbers we use, but only on their relationship to each other. (UPDATE: here are the revised notes. I hope they are a bit clearer: certainly they are longer!)
The essential thing we are trying to prove is this:
If we encode a message, and then decode it, we come back to the original message.
In the example, the message was the number 71.
The public keys were the numbers 143 = 11*13 (the modulus) and 7 (the exponent).
To find 143, we chose two prime numbers and multiplied them together.
Then we had to compute the number (11-1)*(13-1) = 120 and choose the exponent so that it had no factors in common with that number 120.
The private key was the number 103. This number came from solving the Diophantine equation ed-my=1, or equivalently, from solving the modular congruence ed ≡ 1 (mod m), where e=7 (our public key exponent) and m = 120 (the number that e was chosen to have no factors in common with).
What we want to prove in the example is that if we encode the message 71 by taking 717 (mod 143), and then decode that encoded message by taking it to the 103rd power (mod 143), we get back the original message 71.
In other words, we want to prove (without actually computing it) that
(717)103 ≡ 71 (mod 143)
Here are the essential steps of the proof:
• Prove that 717 ≡ 124 (mod 143) means that 717 ≡ 124 (mod 11) and 717 ≡ 124 (mod 13)
[This is a special case of a general theorem: if two numbers are equivalent mod n, then they are also equivalent modulo any prime factor of n.]
• Prove that (717)103 ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 11 (division algorithm)
• Prove that (717)103 ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 13 (division algorithm0
• Since (717)103 - 71 is divisible by both 11 and 13, it must be divisible by their product 143 (Here we use Unique Prime Factorization, a/k/a the Fundamental Theorem of Arithmetic.)
• So (717)103 ≡ 71 (mod 143)
Outlining the "proof" that the RSA works, for the example given in my notes.
This is not a real proof (hence the scare quotes above), because it only proves that RSA works for this particular example. However, if you read carefully, you can see that nothing in the proof depends on the specific numbers we use, but only on their relationship to each other. (UPDATE: here are the revised notes. I hope they are a bit clearer: certainly they are longer!)
The essential thing we are trying to prove is this:
If we encode a message, and then decode it, we come back to the original message.
In the example, the message was the number 71.
The public keys were the numbers 143 = 11*13 (the modulus) and 7 (the exponent).
To find 143, we chose two prime numbers and multiplied them together.
Then we had to compute the number (11-1)*(13-1) = 120 and choose the exponent so that it had no factors in common with that number 120.
The private key was the number 103. This number came from solving the Diophantine equation ed-my=1, or equivalently, from solving the modular congruence ed ≡ 1 (mod m), where e=7 (our public key exponent) and m = 120 (the number that e was chosen to have no factors in common with).
What we want to prove in the example is that if we encode the message 71 by taking 717 (mod 143), and then decode that encoded message by taking it to the 103rd power (mod 143), we get back the original message 71.
In other words, we want to prove (without actually computing it) that
(717)103 ≡ 71 (mod 143)
Here are the essential steps of the proof:
• Prove that 717 ≡ 124 (mod 143) means that 717 ≡ 124 (mod 11) and 717 ≡ 124 (mod 13)
[This is a special case of a general theorem: if two numbers are equivalent mod n, then they are also equivalent modulo any prime factor of n.]
• Prove that (717)103 ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 11 (division algorithm)
• Prove that (717)103 ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 13 (division algorithm0
• Since (717)103 - 71 is divisible by both 11 and 13, it must be divisible by their product 143 (Here we use Unique Prime Factorization, a/k/a the Fundamental Theorem of Arithmetic.)
• So (717)103 ≡ 71 (mod 143)
13 October 2016
Thursday 13 October class
Note: No journals are due this week. Hold on till next week.
Also don't forget that this class will not meet on Tuesday the 18th of October!
After Test 2 our next meeting will be Thursday the 20th.
Topics:
• Activity related to the video on Fermat's Little Theorem linked in last time's post.
• Review of reasoning I used in computing 71492 (mod 100) (to remind that we could not just reduce the exponent mod 100) - see more on this below
• Showing why the RSA algorithm works (from my notes) - we only got through the first part of the proof on p. 3 of these notes, so it will continue next time.
More comments on the problem of computing exponential expressions in modular arithmetic:
I asserted and also gave an example in class to show that you cannot reduce the exponent (at least, not to the modulus you are starting with). I do not know if I wrote up my example in the blog, so here is an example (which may or may not be the one I did in class):
Suppose we want to compute 318 (mod 5).
This can be found with a calculator by computing 318 = 387420489, and then reducing mod 5, so we get 318 ≡ 4 (mod 5).
But if we try to shortcut by reducing the exponent mod 5, we get 18 ≡ 3 (mod 5), so we would think that our answer could be computed by taking 33 = 27 ≡ 2 (mod 5), which is not the correct answer.
Referring back to this post (or to the reading from Art of Problem Solving), the cases where we can reduce before performing the computations (and then reduce again, if necessary) are these:
• In addition or subtraction, we can reduce the numbers before adding or subtracting
• In multiplication, we can reduce the numbers before multiplying - (please note that there is no division in modular arithmetic)
• Because we can reduce factors before we multiply them together, we can reduce the base of a natural number exponent (since the base represents the factor which is being repeatedly multiplied together) before taking the power.
When it is the exponent which is "too big", other tricks must be used, such as looking for patterns in the powers of the base (as in the example of 71492) or using Fermat's Little Theorem (which is a special case of looking for patterns in the powers.)
Homework:
• Journal assignment: watch the video on Fermat's Little Theorem (which was assigned previously!), write on what you learn from it, and then use that to try the Activity again.
• Problems related to Fermat's Little Theorem:
1) Compute each of the following:
a) 14 (mod 5), 24 (mod 5), 34 (mod 5), 44 (mod 5)
b) 16 (mod 7), 26 (mod 7), 36 (mod 7), 46 (mod 7), 56 (mod 7), 66 (mod 7)
c) How does Fermat's Little Theorem relate to the answers in (a) and (b)?
2a) Using Fermat's Little Theorem (not by direct computation), find 800030 (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
b) Compute 80004 (mod 5). The answer is not 1. Why doesn't this contradict Fermat's LittleTheorem?
Up next: Completing the verification of the RSA algorithm (showing why it works). Reread the part of the proof on p. 3 of the notes and make sure that you are following the reasoning being used at each step (even if you don't see where it is going yet). Next time we will outline or "flowchart" the proof to get a better idea of how it fits together.
Also don't forget that this class will not meet on Tuesday the 18th of October!
After Test 2 our next meeting will be Thursday the 20th.
Topics:
• Activity related to the video on Fermat's Little Theorem linked in last time's post.
• Review of reasoning I used in computing 71492 (mod 100) (to remind that we could not just reduce the exponent mod 100) - see more on this below
• Showing why the RSA algorithm works (from my notes) - we only got through the first part of the proof on p. 3 of these notes, so it will continue next time.
More comments on the problem of computing exponential expressions in modular arithmetic:
I asserted and also gave an example in class to show that you cannot reduce the exponent (at least, not to the modulus you are starting with). I do not know if I wrote up my example in the blog, so here is an example (which may or may not be the one I did in class):
Suppose we want to compute 318 (mod 5).
This can be found with a calculator by computing 318 = 387420489, and then reducing mod 5, so we get 318 ≡ 4 (mod 5).
But if we try to shortcut by reducing the exponent mod 5, we get 18 ≡ 3 (mod 5), so we would think that our answer could be computed by taking 33 = 27 ≡ 2 (mod 5), which is not the correct answer.
Referring back to this post (or to the reading from Art of Problem Solving), the cases where we can reduce before performing the computations (and then reduce again, if necessary) are these:
• In addition or subtraction, we can reduce the numbers before adding or subtracting
• In multiplication, we can reduce the numbers before multiplying - (please note that there is no division in modular arithmetic)
• Because we can reduce factors before we multiply them together, we can reduce the base of a natural number exponent (since the base represents the factor which is being repeatedly multiplied together) before taking the power.
When it is the exponent which is "too big", other tricks must be used, such as looking for patterns in the powers of the base (as in the example of 71492) or using Fermat's Little Theorem (which is a special case of looking for patterns in the powers.)
Homework:
• Journal assignment: watch the video on Fermat's Little Theorem (which was assigned previously!), write on what you learn from it, and then use that to try the Activity again.
• Problems related to Fermat's Little Theorem:
1) Compute each of the following:
a) 14 (mod 5), 24 (mod 5), 34 (mod 5), 44 (mod 5)
b) 16 (mod 7), 26 (mod 7), 36 (mod 7), 46 (mod 7), 56 (mod 7), 66 (mod 7)
c) How does Fermat's Little Theorem relate to the answers in (a) and (b)?
2a) Using Fermat's Little Theorem (not by direct computation), find 800030 (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
b) Compute 80004 (mod 5). The answer is not 1. Why doesn't this contradict Fermat's LittleTheorem?
Up next: Completing the verification of the RSA algorithm (showing why it works). Reread the part of the proof on p. 3 of the notes and make sure that you are following the reasoning being used at each step (even if you don't see where it is going yet). Next time we will outline or "flowchart" the proof to get a better idea of how it fits together.
Activity for Thursday 13 October
Fermat's Little Theorem: for any prime number p, and any natural number a which is not divisible by p,
$a^{p-1} \equiv 1$ (mod p)
For example, $4^{10} \equiv 1$ (mod 11)
because 11 is a prime number and 4 is not divisible by 11.
Based on your viewing of the video, assigned last time, from Maths by Jay, which discussed Fermat's Little Theorem and how it can be used to simplify some calculations:
Use the above-mentioned fact to find the value of
$4^{1357}$ (mod 11)
Hint: You'll use the division algorithm on the exponent 1357
You want to rewrite $4^{1357}$ as a power of $4^{10}$, times another power of 4
$a^{p-1} \equiv 1$ (mod p)
For example, $4^{10} \equiv 1$ (mod 11)
because 11 is a prime number and 4 is not divisible by 11.
Based on your viewing of the video, assigned last time, from Maths by Jay, which discussed Fermat's Little Theorem and how it can be used to simplify some calculations:
Use the above-mentioned fact to find the value of
$4^{1357}$ (mod 11)
Hint: You'll use the division algorithm on the exponent 1357
You want to rewrite $4^{1357}$ as a power of $4^{10}$, times another power of 4
30 September 2016
Test 2 review problems
Test 2 is scheduled for Friday 14 October. The review problems are here. Answers and/or links will be posted soon, but I strongly encourage everyone to go back and review the proof that there is no largest prime number and make sure that you understand the reasoning that is being used in the proof. In particular, make sure that you understand how proof by contradiction works! The relevant links describing the proof are in this post (the readings at the end of the post), and a description of how the division algorithm fits in is in this post.
29 September 2016
Thursday 29 September class
• Warmup activity: finding a pattern in the powers of 8 mod 5, and in the powers of 5 mod 3
We observed that in each case the powers cycled through all the possible nonzero residues, ending with 1:
Next time I will show you how you can exploit modular arithmetic to keep the numbers small when doing this type of computation - which will partially answer the question of what happens in RSA when the numbers get too big for even a computer to handle.
These are examples of Fermat's Little Theorem:
If p is a prime number, and a is any integer which does not have p as a factor, then
ap-1 ≡ 1 (mod p)
In the two examples we had
a=8, p=5: 85-1 = 84 ≡ 1 (mod 5)
a=5, p=3: 53-1 = 52 ≡ 1 (mod 3)
This Theorem plays a role in proving that the RSA algorithm works. (see the notes)
• We showed how the two public keys and the private key are found, first by the example in my notes, and then by the example in this reading (Serge Matovic's homepage: see Section 1). We showed how his method for finding the private key is really the same as the method in my notes.:
In a sense the RSA algorithm is a generalization of the Little Fermat Theorem, as discussed in the background article.
Homework:
• Journal assignment:
• Problems related to the RSA algorithm: (corrected problem number references)
1) Choosing the prime numbers p=3 and q=5, compute m [as in my notes on RSA] and then find possible values for e and d, using trial and error. Record your trial and error or other reasoning to explain how you got them! And try to keep them small.
2) Using the public and private keys you found in problem (1), encode the message 809.
3) Using the private key you found in problem (1), decode the encoded message from problem (4) and show that the decoded message is the original message 809.
• For future use: you will be asked to write a short essay on some aspect of the RSA algorithm. Start thinking about this and doing research on the area you would like to write about. Here are some suggestions (pick ONE, or make up one of your own):
• The history of the RSA algorithm: how and why it came to be developed by Rivest, Shamir, and Adleman
• How RSA is used today
• How long would it take the fastest computer to factor large numbers? What progress has been made on this problem in recent years?
Next up: Explaining why the RSA algorithm works, and how to exploit modular arithmetic to keep the numbers for getting too large when we take those powers. This will involve using Fermat's Little Theorem: please view this video which gives an example and then shows you how it can be used!
We observed that in each case the powers cycled through all the possible nonzero residues, ending with 1:
| 81 ≡ 3 (mod 5) | 51 ≡ 2 (mod 3) |
| 82 ≡ 4 (mod 5) | 52 ≡ 1 (mod 3) |
| 83 ≡ 2 (mod 5) | 53 ≡ 2 (mod 3) |
| 84 ≡ 1 (mod 5) | 54 ≡ 1 (mod 3) |
| 85 ≡ 3 (mod 5) | 55 ≡ 2 (mod 3) |
| ... etc. ... | ... etc. ... |
Next time I will show you how you can exploit modular arithmetic to keep the numbers small when doing this type of computation - which will partially answer the question of what happens in RSA when the numbers get too big for even a computer to handle.
These are examples of Fermat's Little Theorem:
If p is a prime number, and a is any integer which does not have p as a factor, then
ap-1 ≡ 1 (mod p)
In the two examples we had
a=8, p=5: 85-1 = 84 ≡ 1 (mod 5)
a=5, p=3: 53-1 = 52 ≡ 1 (mod 3)
This Theorem plays a role in proving that the RSA algorithm works. (see the notes)
• We showed how the two public keys and the private key are found, first by the example in my notes, and then by the example in this reading (Serge Matovic's homepage: see Section 1). We showed how his method for finding the private key is really the same as the method in my notes.:
In my notes, to find the private key d, we solve the Diophantine equation ed - my = 1 for integers d and y (actually, we want them to be natural numbers in fact)
So in Serge's example, we would be solving 7d - 20y =1 for natural numbers d and y
In Serge's webpage, he does this by solving the modular equation 7d ≡ 1 (mod 20)
By the division algorithm, this is the same as saying that 7d = 20q + 1 for some whole number q.
If you take our Diophantine equation and add 20y to both sides, you get exactly this - it doesn't matter whether you call the quotient q or y.
So these are actually the same procedure written in different ways. It's an equally difficult or easy problem either way. It is just a matter of taste which way to go.
In a sense the RSA algorithm is a generalization of the Little Fermat Theorem, as discussed in the background article.
Homework:
• Journal assignment:
• Problems related to the RSA algorithm: (corrected problem number references)
1) Choosing the prime numbers p=3 and q=5, compute m [as in my notes on RSA] and then find possible values for e and d, using trial and error. Record your trial and error or other reasoning to explain how you got them! And try to keep them small.
2) Using the public and private keys you found in problem (1), encode the message 809.
3) Using the private key you found in problem (1), decode the encoded message from problem (4) and show that the decoded message is the original message 809.
• For future use: you will be asked to write a short essay on some aspect of the RSA algorithm. Start thinking about this and doing research on the area you would like to write about. Here are some suggestions (pick ONE, or make up one of your own):
• The history of the RSA algorithm: how and why it came to be developed by Rivest, Shamir, and Adleman
• How RSA is used today
• How long would it take the fastest computer to factor large numbers? What progress has been made on this problem in recent years?
Next up: Explaining why the RSA algorithm works, and how to exploit modular arithmetic to keep the numbers for getting too large when we take those powers. This will involve using Fermat's Little Theorem: please view this video which gives an example and then shows you how it can be used!