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
13 October 2016
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!
Journal 4 to be submitted by 5:30 PM today
This post is to clarify what goes into this journal submission and what its number is.
This is journal 4, so when you name your file that is the journal number you should use.
(If you have already submitted it, please make sure that you used the number 4, and if you did not, please go back and change the filename. You do not need to make a new post: you can just edit the post you already made, remove the uploaded file link, rename the file, and edit the post again to put in the file with the correct name. PLEASE DO NOT LEAVE THE FILE WITH THE WRONG NAME POSTED!)
Journal 4 submission should contain everything in your journal since Test 1: in other words, starting with Tuesday the 19th, up until what you have as of the start of class today (not including today's class, obviously!)
Please make sure that you follow the instructions in this post (as always) for naming your file and for posting it to Piazza, and what your summary line of your Piazza post should be.
This is journal 4, so when you name your file that is the journal number you should use.
(If you have already submitted it, please make sure that you used the number 4, and if you did not, please go back and change the filename. You do not need to make a new post: you can just edit the post you already made, remove the uploaded file link, rename the file, and edit the post again to put in the file with the correct name. PLEASE DO NOT LEAVE THE FILE WITH THE WRONG NAME POSTED!)
Journal 4 submission should contain everything in your journal since Test 1: in other words, starting with Tuesday the 19th, up until what you have as of the start of class today (not including today's class, obviously!)
Please make sure that you follow the instructions in this post (as always) for naming your file and for posting it to Piazza, and what your summary line of your Piazza post should be.
If you fail to follow the instructions I will simply respond to your post telling you that you did not follow instructions, and I will not evaluate your journal until you've corrected the situation.
27 September 2016
National Voter Registration Day - register to vote
Today is National Voter Registration Day.
If you are eligible to vote and have not already done so, please register and vote in the upcoming November elections. (There are many positions on the ballot, not just the Presidential election!)
In New York state, the deadline to register for this election is the 14th of October. You can find information for NY State about how to check eligibility and how to register either online, by mail, or in person, at this link. (Thanks, Google!) You can also check the status of your registration if you previously registered to vote, to make sure everything is OK.
If you are eligible to vote and have not already done so, please register and vote in the upcoming November elections. (There are many positions on the ballot, not just the Presidential election!)
In New York state, the deadline to register for this election is the 14th of October. You can find information for NY State about how to check eligibility and how to register either online, by mail, or in person, at this link. (Thanks, Google!) You can also check the status of your registration if you previously registered to vote, to make sure everything is OK.
Here is the link with information for registering in New Jersey. NJ does not have online registration: you must register by mail or in person. The deadline for NJ is the 18th of October.
Note: in NY State, Students may establish voting residency in the place they consider their principal home, whether that be their current school address or at another address (such as a parent’s address) they still consider to be “home.”
So if you are an out-of-state student living in a Brooklyn College dorm you may register to vote in NY State or in your home state, it is up to you. Source: the Brennan Center.
Tuesday 27 September class
Topics:
• Warmup for RSA (although the connection will not be made until next time):
Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value) is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)
• We discussed some of the homework problems, specifically, what in the multiplication table mod 4 is problematic.
The problem with using a modulus that is not prime is that there will be products which are 0 but where the factors are both non-zero. (These are called zero divisors.) In mod 4, we have 2•2 ≡ 0. This means that there is no "zero product principle" in that number system: if a•b = 0, it is not necessarily true that a=0 or b=0.
• Warmup for RSA (although the connection will not be made until next time):
Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value) is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)
Note: In general, an equation which is to be solved for solutions in the integers is called a Diophantine equation. We will see another example (coming from the Pythagorean Theorem) later in the course.
• Note that when we use the word "code" or "coding" in what follows, it does not always mean that we are trying to keep something a secret! See these Wikipedia articles about code and coding theory.
• UPCs (Universal Product Codes) as an application of modular arithmetic: modular arithmetic is employed to check that the code has been entered correctly. In a 12-digit UPC, the first 6 digits represent the company that makes the product, and the next 5 digits represent the product itself. The last digit is a check digit, chosen so that a certain sum will be congruent to 0 mod 10.
If we call the digits d1, d2,d3,..., d12, then the checksum is
3d1 + d2 + 3d3 + d4 + 3d5 + d6 + ... + 3d11 + d12
and we require that this checksum be ≡ 0 (mod 10)
We checked some examples in class and also checked to see what happened when we reversed two of the digits in a UPC (an easy mistake to make). When two adjacent nonzero digits were reversed, the checksum was no longer ≡ 0 (mod 10).
This sort of checksum catches many (most?) errors but there are some errors that it will not catch. This is a tradeoff: we want the checking process to be simple and quick (not to waste time) but we also want to catch as many errors as possible. A more elaborate checking process might catch more errors but also would take more time to carry out. In each case of a coding like this (ISBNs, credit card numbers, account numbers, etc.) a decision has to be made how to balance out these two concerns.
Homework:
• Journal assignment: Write up what you learned about the purpose of the checksum for a UPC. How does it check for errors? Why is it important to check for errors? You may want to see if you can find out what kind of checksums are used for other important numbers, such as ISBNs.
Also use your journal (as always) to work out concepts in the lesson that may not be clear to you.
• Problems on UPCs: these are all based on real UPCs, and all the real UPCs I have found so far begin with 0. I don't know why that is.
1) Is each of the following a valid UPC or not? (I've put spaces in them to represent how they are usually shown on the products these days.)
a) 0 28367 82855 9
b) 0 75063 01114 0
2) Find the check digit for the UPC: (if you have any doubt about how to do this, consult the Wikipedia article - remember that you want the checksum to be congruent to 0 mod 10)
a) 0 28367 82903 _
b) 0 50428 10148 _
3) The UPC for a product is 0 50428 32193 5
Explain why the checksum will not catch the following errors:
a) 0 50428 39123 5
b) 0 50428 19323 5
4)(Based on a problem from The Heart of Mathematics)
A friend with bad handwriting writes down a UPC. Unfortunately, you can't tell his 4's from his 9's (they look alike), or his 1's from his 7's (they also look alike). If the code looks like 903068823517, is there any way you can figure out what the real UPC is? If so, what do you do and what is the real UPC? If it is not possible to determine the correct UPC, explain why.
• Next topic is the RSA algorithm for encoding a message to be sent, for security purposes. Make sure that you read this RSA algorithm background article (from Slate).
There will be three phases of discussion of the RSA algorithm:
First, how it is carried out. We will do this next time with two examples.
Second, how we find the two public keys and the private key. That's coming up later. And then finally:
Third, how to prove that the algorithm works.
My notes were handed out in class and are also available here. You could take look through the first page, after reading the background article linked above. We will also use this reading from Serge Matovic's homepage. (Section 2 and Section 3 where he encodes and decodes the message. He shows how to use a calculator and some tricks to find the remainder we need.)
• Warmup for RSA (although the connection will not be made until next time):
Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value) is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)
• We discussed some of the homework problems, specifically, what in the multiplication table mod 4 is problematic.
The problem with using a modulus that is not prime is that there will be products which are 0 but where the factors are both non-zero. (These are called zero divisors.) In mod 4, we have 2•2 ≡ 0. This means that there is no "zero product principle" in that number system: if a•b = 0, it is not necessarily true that a=0 or b=0.
• Warmup for RSA (although the connection will not be made until next time):
Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value) is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)
Note: In general, an equation which is to be solved for solutions in the integers is called a Diophantine equation. We will see another example (coming from the Pythagorean Theorem) later in the course.
• Note that when we use the word "code" or "coding" in what follows, it does not always mean that we are trying to keep something a secret! See these Wikipedia articles about code and coding theory.
• UPCs (Universal Product Codes) as an application of modular arithmetic: modular arithmetic is employed to check that the code has been entered correctly. In a 12-digit UPC, the first 6 digits represent the company that makes the product, and the next 5 digits represent the product itself. The last digit is a check digit, chosen so that a certain sum will be congruent to 0 mod 10.
If we call the digits d1, d2,d3,..., d12, then the checksum is
3d1 + d2 + 3d3 + d4 + 3d5 + d6 + ... + 3d11 + d12
and we require that this checksum be ≡ 0 (mod 10)
We checked some examples in class and also checked to see what happened when we reversed two of the digits in a UPC (an easy mistake to make). When two adjacent nonzero digits were reversed, the checksum was no longer ≡ 0 (mod 10).
This sort of checksum catches many (most?) errors but there are some errors that it will not catch. This is a tradeoff: we want the checking process to be simple and quick (not to waste time) but we also want to catch as many errors as possible. A more elaborate checking process might catch more errors but also would take more time to carry out. In each case of a coding like this (ISBNs, credit card numbers, account numbers, etc.) a decision has to be made how to balance out these two concerns.
Homework:
• Journal assignment: Write up what you learned about the purpose of the checksum for a UPC. How does it check for errors? Why is it important to check for errors? You may want to see if you can find out what kind of checksums are used for other important numbers, such as ISBNs.
Also use your journal (as always) to work out concepts in the lesson that may not be clear to you.
• Problems on UPCs: these are all based on real UPCs, and all the real UPCs I have found so far begin with 0. I don't know why that is.
1) Is each of the following a valid UPC or not? (I've put spaces in them to represent how they are usually shown on the products these days.)
a) 0 28367 82855 9
b) 0 75063 01114 0
2) Find the check digit for the UPC: (if you have any doubt about how to do this, consult the Wikipedia article - remember that you want the checksum to be congruent to 0 mod 10)
a) 0 28367 82903 _
b) 0 50428 10148 _
3) The UPC for a product is 0 50428 32193 5
Explain why the checksum will not catch the following errors:
a) 0 50428 39123 5
b) 0 50428 19323 5
4)(Based on a problem from The Heart of Mathematics)
A friend with bad handwriting writes down a UPC. Unfortunately, you can't tell his 4's from his 9's (they look alike), or his 1's from his 7's (they also look alike). If the code looks like 903068823517, is there any way you can figure out what the real UPC is? If so, what do you do and what is the real UPC? If it is not possible to determine the correct UPC, explain why.
• Next topic is the RSA algorithm for encoding a message to be sent, for security purposes. Make sure that you read this RSA algorithm background article (from Slate).
There will be three phases of discussion of the RSA algorithm:
First, how it is carried out. We will do this next time with two examples.
Second, how we find the two public keys and the private key. That's coming up later. And then finally:
Third, how to prove that the algorithm works.
My notes were handed out in class and are also available here. You could take look through the first page, after reading the background article linked above. We will also use this reading from Serge Matovic's homepage. (Section 2 and Section 3 where he encodes and decodes the message. He shows how to use a calculator and some tricks to find the remainder we need.)
23 September 2016
Math Club talk about proving the infinitude of primes
This may be of interest since we have already discussed one of the proofs. And there's pizza!
----------------------------------------
Title: Four Proofs of the Infinitude of Primes
Abstract: We will discuss one of the most beautiful theorems in all of mathematics – the infinitude of primes. We will give four proofs with variations: Euclid's indirect proof, Euler's analytic proof, Furstenberg's topological proof, and Chaitin's complexity proof. These proofs reflect the evolution of techniques in number theory and in mathematical proofs in general.
Date: Tuesday September 27, 2016
Time: 12:30 pm - 1:30 pm
Location: 1146 Ingersoll Hall
Pizza will be served.
This colloquium is sponsored by the Math Club www.facebook.com/bcmathclub
----------------------------------------
Mathematical Sciences Colloquium
Alexander Gindes
Brooklyn College
Mathematics
Title: Four Proofs of the Infinitude of Primes
Abstract: We will discuss one of the most beautiful theorems in all of mathematics – the infinitude of primes. We will give four proofs with variations: Euclid's indirect proof, Euler's analytic proof, Furstenberg's topological proof, and Chaitin's complexity proof. These proofs reflect the evolution of techniques in number theory and in mathematical proofs in general.
Date: Tuesday September 27, 2016
Time: 12:30 pm - 1:30 pm
Location: 1146 Ingersoll Hall
Pizza will be served.
This colloquium is sponsored by the Math Club www.facebook.com/bcmathclub