Tuesday, July 16, 2013

Decrypting an Encryption?

Today's Puzzler used Number Theory (big surprise, since we learned that yesterday). Imagine that you are in a really long hallway with 20,000 lights. Each is operated by a pull chain. A man walks by and pulls every chain, turning all the lights on. A second person comes by afterwards and pull the chains on light numbers 2, 4, 6, 8, 10, etc. A third person goes after that and pulls 3, 6, 9, 12, 15 etc. A fourth person pulls 4, 8, 12, 16, 20 etc. This continues until the 20,000th person goes by and pulls only the 20,000th chain. After all 20,000 people go by, how many lights will be on? Which ones? As always, STOP reading if you want to solve it yourself. 

In order to solve this problem, you must think about what makes a light turn on, and what makes it turn off. If you pull a string twice, four times, six times etc., it will end up off. If you pull it once, three times, five times etc. it will end up on. Therefore, it a light is pulled an odd number of times, it will be on, and if it is pulled an even number of times, it will be off. Next you must think about what causes an odd number of pulls on the string. Start with 1. 1 is only pulled once, by the first person. 2 is pulled twice (once by the first person, and once by the second person.) 3 is pulled twice (once by the first person, and once by the third person.) 4 is pulled three times (once by the first person, once by the second person, and once by the 4th person.) If you continue with this up to 25, you find that 1, 4, 9, 16, and 25 will be left on. If you have not figured it out already, the number of times any given number is pulled is the number of factors it has. So why do 1, 4, 9, 16, and 25 have an odd number of factors, when factors come it pairs? All these numbers are perfect squares. (If you square a certain integer, you will get each of these numbers. 2 * 2 = 4, and 3 * 3 = 9). Even though a number is used twice, it still counts as only one factor. 9 is only pulled once by the 3rd person, even though 3 *3 = 9. So now we know all square numbers under 20,000 will be left on. But how many square numbers are there? If you take the square root of 20,000, you get 141.42135... This means that there are 141 square numbers under 20,000. So the answer is 141 lights (all square numbers under 20,000) will be left on.

Next, we had independent study for 50 minutes. I made good progress, but am not ready for the quiz yet. After independent study, Dawson gave a lecture on coding using RSA encryption. In fact, this code is used to encrypt credit card numbers. There are 4 steps total, 2 to encode, and 2 to decode. The first step is to convert the letters to numbers. A is 0, B is 1, C is 2, etc. and Z is 25. If you sent a message in this code, anyone could solve it almost instantly, so we have to add a twist. You need to pick a value for m. M must be the product of two primes. You also have to pick a number for e, such that the GCF of e and Phi of m is 1. (We learned about the Euler Phi function yesterday.) You may be wondering how you credit card numbers are safe when the VSA students know how they are encrypted. Don't worry, you credit card numbers are safe. Websites use astronomically large numbers for e and m, so that even super computers cannot hack them. There are an infinite number of possible values for each, and they are changed periodically, so there is virtually no chance of guessing your way through the encryption. Anyway, back to the math.

Now that you have chosen e and m, you need to write an equation for each letter value: the letter value to the power of e is congruent to __ mod m. The blank is the number you would use to represent that letter in the message you send. To decrypt, you need values for d and m. D is the inverse of e. You use the equation ed is congruent to 1 mod Phi of m to solve for d. I really life applications, both sides already know what d, e, and m are so that they don't transmit that in the message. To decrypt, you use a slightly modified encryption equation: the number in the message to the power of d is congruent to __ mod m. __ is the value that represents the letter. (0-25) You then convert that into a letter and get the message. Then Dawson had us try encrypting and decrypting various messages including "Cryptography rules," "Secret Message," and "It's almost lunch time." After we solved the last one, we went to lunch. I also really enjoyed this lecture, as it used Number Theory, but in a practical sense. Proving that an odd + an odd = an even is cool, but has no real-world application, but encryption and decryption do. Dawson even told us that mathematicians used to make jokes about the uselessness of Number Theory. Once the internet came along, Number Theory became widely used, and the jokes stopped. In fact, Number Theory is one of the most used types of math now.

After lunch, Dawson had us write our own message. He gave us an encryption key (e and m), and we coded it. He then gave our message to someone else, along with the corresponding decryption key (d and m). This was quite fun, as we did not know who we were sending a message to, or who sent us a message. After the coding activity, we did more independent study. I made more progress, and will probably take the quiz after one more session of work.

Next up was study hall, which was quite chaotic. Dawson had sent in a request to reserve the computer lab in the Peabody Library all of this week. He never got a response, so he assumed he had it. Yesterday we did not have any problems. Today (and yesterday) when we looked on the door, it just said reserved for VSA, but today there was another class in there. So we waited outside the library computer lab while Dawson ran over to another building to see it that computer lab was available. After about five minutes, he called our TA, and had us come over. Unfortunately, the two computer labs are far apart, so we had to walk for 5 minutes to get there. By the time we got to the second computer lab and sat down, half of our one hour study hall period was over. As you may have guessed, I did not accomplish a whole lot, but I was still productive. I know it's not Dawson's fault but I think it should've been more organized. In all the confusion and wasted time, Dawson was not able to talk to each of us individually about our lesson. He has promised, however, that he will spend more time with each of us tomorrow, especially those presenting on Friday and Saturday.

Next we had Arête. I was so excited about Number Theory yesterday that I forgot to mention Arête at all. This week I have Martial Arts, along with Kimberly and Loan. There are two teachers from a local martial arts club. We have learned some very dangerous and painful stuff. We started with just breaking away from a grab, but are now blocking punches and escaping chokes. We practice in pairs, taking turns being the "attacker" and the "victim." In order for this to be safe, we go slowly, and we tap our hand to our body if our partner's move hurts. All of the moves we have learned put the attacker in a lot of pain. Even without fully executing the move, it can hurt for a little while afterwards. (Most of the moves break bones, so we don't go all the way through with them.) Overall, I think it is a valuable course, but it can be painful to learn. Although I have not broken any bones, I have popped a couple joints that hurt for a little while. Hopefully, I will never have to use the moves I learn in Martial Arts.

After Arête, we had dinner with our proctor at a local restaurant, as tonight was "Proctor Night." The idea is to get closer to you proctor and proctor group, and to get a taste of Nashville's food. Our group ended up going to a restaurant called Cabana, a higher end restaurant, with food ranging from $8-20 per person. Our budget was $12 each, not including tax and tip. (If we went over, we had to pay the difference.) I did not really enjoy it. There were 13 of us in my proctor group, and they crammed us in a booth meant for about eight people. The food was good, but again, there was not space, so it was hard to eat. There was a headphone cord in the booth hooked up to speakers around the booth, so the whole time people were plugging their phone in and playing music. Of course, no one could agree on the songs, and they played it so loud at times that the management had to come by to tell us to turn it down. After dinner we went back to the 3rd floor of Hank Ingram and played cards. I enjoyed this much more, as there was lots of space to spread out.

Tomorrow we are having dinner at the Dean's house. Counselors from undergraduate admissions will also be there. After dinner we will do mock admissions, where they give us a profile, and we accept or reject the "applicant." This will give us an idea what they are looking for in an applicant in a hands on way, instead of them telling us at an info session. I am really looking forward to this, as I really want to go to Vanderbilt. I want to understand exactly what they are looking for, so I can do my best to raise my chances of getting accepted to Vanderbilt when I apply in 2014.

No comments:

Post a Comment