To Know: I’ve put another chapter on canvas — the one with elliptic curves (and removed chapter 2)
To Know: Module 3 is due Monday.
To Know: Module make-up is due Friday the 30th. Please see the replacement problems on canvas.
To Do: Determine P^1(F_5). That is, just like the example from class today where I did P^1(F_3). List out all the elements, as I did in that example. Please give all the equivalent ways to write each element (just as I did in class). Class notes are available under “History” and the video is on canvas. Hand it in on canvas.
To Know: I’ve put up re-do problems. I’ve added a few new ones. You can do 2 from Module 1 and 2 from Module 2. You choose. If you want one that’s not there, let me know. It’s due the Friday after Module 3.
Use EC Factoring Tools to factor n = 290265623. You might want to increase the size of the loop! You’ll notice I modified the code so that it will catch and report on the errors it encounters. Use the result to factor n (that is, take the gcd of the non-invertible residue with n to get a non-trivial factor).
Now do it again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs). Factor n.
Now try modifying one of the middle digits of n, and see how long it takes. Factor n.
Try modifying one of the digits a couple more times and see how long it takes. Factor n.
Report to canvas on how long it took (what multiple of P) on different curves and points, and different n. Explain why you think it was fast sometimes and slow other times.
That’s it for now. I’ve decided to talk about projective geometry in class, since students seem curious about it and it’s a very good topic. You can devote whatever other time you have to working on the module and re-do problems.
To Know: I will post the next assessment either late tonight or early on the weekend. I will make it due Monday the 26th. I hope to have the 2nd assessment back to you this weekend.
To Do: Practice with finite fields!
Please create a finite field of size 9. To do this, you will need to find an irreducible polynomial of degree 2 in F3[X]. To do this, just try some polynomials. One way to check if something that has degree 2 is irreducible is to check if it has any roots (since if it factors, it will have to have a linear root, i.e. factor). There are only 3 possible roots (namely 0,1,2) because we are working in F3. Hint: choosing a polynomial without a linear coefficient will simplify your computations later on.
Next, make a complete multiplication table for your finite field of 9 elements. Take advantage of symmetry to speed this up. Practice makes perfect!
Use the Finite Field Tools to check your work (figure out what the tools do, then check your polynomial is irreducible and at least spot check some items on your multiplication table).
Today, we’re going to try a little Quadratic Sieve factoring. Let n = 539873. Use the Quadratic Sieve Tools to show how the Quadratic Sieve would factor this. That is, write up a description of your factor base, what numbers you will B-factor and where they come from, what results (“facts”) you get, and how you use that to factor. Hand this in on the dropbox. Note: it’s up to you how many primes to keep in the factor base, and how big a list of numbers to B-factor. Just try to guess how much you’ll need to get facts, and expand your net if you need to. Comment: I say “would factor this” because I’m going to allow you a little shortcut. I’ve built in a “B-factor” function that will factor out small divisors of a number. You set the factor base and then it will factor powers of those numbers out. In the real quadratic sieve, you would use “sieving” to find the B-factorizations, not do them one-by-one (for runtime reasons). Instead, here, the tools will simply print out the B-factorizations and you can proceed from there.
Also To Do: Please finish the RSA ciphertext chain (including decrypting the message sent to you) because it’s important practice.
Module “corrections” (repeating because it’s important). I’d like to allow you to do corrections for the module assessments. For Module 1, I’d like you to email me / direct message me a maximum of two problems (individual problems/parts, not problems with multiple parts, e.g. 4d) from the assessment that you would like to re-do, to replace your current grade on those problems, up to a maximum of 80% credit. I will then look at the problems people are asking for and make “replacement” problems for you to attempt. This cannot lower your grade, it can only improve it. It is optional.
To Know: I’ve updated/combined the modules on the website under “Goals” because I got confused and combined the second and third into one thing anyway. You can check that out if you’d like — we’ll have just 6 assessments overall, not 9.
Module “corrections”. I’d like to allow you to do corrections for the module assessments. For Module 1, I’d like you to email me / direct message me a maximum of two problems (individual problems/parts, not problems with multiple parts, e.g. 4d) from the assessment that you would like to re-do, to replace your current grade on those problems, up to a maximum of 80% credit. I will then look at the problems people are asking for and make “replacement” problems for you to attempt. This cannot lower your grade, it can only improve it. It is optional.
To Do: Factor the number 184507 using the p-1 factoring method from today’s class. Tell me what you choose for a, and tell me what powers of a you compute, and tell me what gcd you tried, and what factor you found (you may need to keep lengthening the chain and trying again). You can use the Sage command “factorial(n)” if you want to save time. You can use the command “is_prime(n)” to check that you’ve factored it all the way. Do not ever use the command “factor(n)” since that’s cheating (except to check your answer after you’re done). Note: It’s in Section 6.4 of 2nd edition of text.
To Do: Hallowe’en RSA Ciphertext Chain!
Review the way the RSA cryptosystem works.
For this activity, you can use the helpful Sage tools on the RSA Tools page.
Create your own Public Key:
Choose two primes p and q of 10 digits each. Compute n, e, d according to the RSA system. Write down d so you don’t forget.
Publish (n,e) as your public key on the #ciphertexts channel on discord.
Encrypt a message to the last person in the chain:
Obtain their public key (n,e).
Make a message in ASCII (just like in the El Gamal ciphertext chain), which is a number < n. It should be an answer to a question “What would be fun to be for Halloween?” You probably have room for about 6 letters.
Encrypt your message to the person’s public key according to RSA, and post the ciphertext with a @whoever on the ciphertext channel.
Decrypt the message you receive:
Use the RSA decryption method with your own private key to read the message and post it on the ciphertext channel with @whoever for confirmation.
For the following problems, you can use a calculator and/or Sage for basic computations (reducing mod n, modular exponentiation, multiplication etc.). But otherwise work by hand showing your work.
Solve the linear congruence 50x = 10 mod 75.
Solve the linear congruence 13x = 14 mod 15.
Solve the linear congruence 7x = 13 mod 14.
The euler-phi function gives: phi(21733) = 21420. Use this fact to factor 21733. (Hint: revisit notes in class, I explained how to use a quadratic formula to do this).
Suppose Eve has an RSA modulus n = 47053, and also knows the encryption and decryption exponents e = 3497 and d=2333. Use the method shown in class (adapated Miller-Rabin algorithm, also explained on page 168 of 2nd edition of text (in Section 6.1)), to factor n.
In the problems above, show all the steps by hand and hand in on canvas. Useful functionality in Sage is basically just modular arithmetic functionality, but you might find the Miller-Rabin tool for determining how many powers of 2 are in something helpful.
Try out this Chinese Remainder Theorem problem, by hand: x = 3 mod 244 and x = 17 mod 495. Show all the steps of the process, including the extended euclidean algorithm. You can use the computer to do modular arithmetic for you (e.g. multiplying things if needed), but show the steps as if doing it by hand. Hand this in on the dropbox.
In preparation for class, try to solve 2x = 4 (mod 6). How many solutions are there? Can you give a generalizable theoretical proof your solution method is correct (not just an exhaustive check)?
To Know: Assessment for Module 2 is open and due on Wednesday.
Next up is to learn the Extended Euclidean Algorithm: video (10:58). Use it to solve the following linear Diophantine equation, to find one solution in integers x and y: 440x + 377y = 1. Write it up neatly.
Using Sage to do a single modular exponentiation, use the Fermat Primality Test to test if n = 3057601 is composite or probably prime, using the base 99908. Write down what you computed and what you conclude.
Next, using the Miller-Rabin Tools, implement the Miller-Rabin primality test to test if n = 3057601 is composite or probably prime, using the base 99908. (These are the same numbers as above.) Write out the steps (the b_i’s and how you calculate them and what you observe and conclude).