Number Theory and Cryptography

share ›
‹ links

Below are the top discussions from Reddit that mention this online Coursera course from University of California San Diego.

Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an ... Enroll for free.

Reddsera may receive an affiliate commission if you enroll in a paid course after using these buttons to visit Coursera. Thank you for using these buttons to support Reddsera.

Taught by
Alexander S. Kulikov
Professor
and 2 more instructors

Offered by
University of California San Diego

Reddit Posts and Comments

0 posts • 1 mentions • top 1 shown below

r/codes • comment
1 points • Appropriate-Tadpole4

First of all, I'm no expert. But here was my process. I started by writing the initial list of numbers into a Python script, and then proceeded to do the following:

  1. I measured the frequency with which each number appeared. This was almost uniform. They all appear once or twice, with the exception of 57 which appears 3 times. I did this because a good first step is to look for numbers which appear more often than other numbers. Had this worked I'd have assumed that it was English, and that the common ones were either vowels or spaces or something. I recently took a class that covered some of this, which helped a lot in giving me some context. Unfortunately, the numbers were fairly uniformly distributed. I didn't think to try the Caesar Cipher at first, because the largest number in that list is 157 and that's way higher than 26... and the smallest number is 3! So the range is way too big. There's a question mark and a dash in there that I simply threw out and didn't use. You can always take a series of seemingly-uniform numbers and "squish" them by taking the whole thing modulo something (which may expose new patterns), but I had no reason to think that would work at this point. I threw out the idea that it was a Caesar cipher, initially.

  2. Since that didn't work, I measured the increments and decrements between each number. They follow a pattern: They rise and fall. I've seen this pattern before when dealing with modular arithmetic. The instances where the numbers decrease several times in a row are not decreases, but increases! This was my thought process. I figured: "I wonder if I can find the modulus?" I tried assuming it was 158 and working from there. I thought maybe I could figure something out by guessing a modulus and measuring the increment distance between each pair as if that modulus were the constraint. I was assuming modular addition within mod 158 at this point. If you try doing this mod 158 you'll see that the distribution of the increments is also pretty uniform (it increments by a few numbers repeatedly, but it's mostly one-offs). At this point I figured I was out of my depth or something. I do a lot of coding and think ciphers and stuff are fun, but I don't have much experience trying to crack them.

  3. As a last ditch attempt, I thought "What if it's ASCII?" I make a lot of little games and stuff in my terminal using ASCII, and I just completed a class where I was dealing with ASCII on every assignment, so I have a little experience with that. At first I tried: ((num % 26) + 65) + caesar_shift but that didn't work and I ran into the obvious problem of the number going out of range and showing non-letters. I needed a clever way to get it to wrap. To see the entire alphabet (assuming it's an alphabetic simple Caesar cipher) you should only need to try caesar_shift values of up to +26 and I was checking all values up to that for the caesar_shift variable with the script I wrote. So I added an extra ...) % 26) + 65 just to see what would happen, and proceeded to check all values from +0 thru +26 for caesar_shift. I did not expect that to work and was surprised when it did. The reason I chose those numbers is that there are 26 letters in the alphabet. If you are doing a Caesar shift and you need to apply the shift in such a way that it will "roll over" the end of the alphabet, then it's modulo 26. In the normal alphabet, 'A' is at the 0th index, and 'Z' is the 25th. In the ASCII alphabet, 'A' is 65 and 'Z' is 90. Lowercase occupy 97-122. 32 is space. Before 65 and after 90 are non-letters, until you get to 97. I made a guess that I was dealing with capital letters between 'A-Z', but as it turns out if you use +97 instead of +65 you'll get the answer on the 6th iteration instead of the 12th. I suspect this is because there's a better way to solve it than the one I stumbled upon.

For the last hour or so I've been trying to simplify my solution to see if there was a better way. The reason I solved this problem is because I chipped away at it slowly, looked for patterns, and systematically tried different things until something worked. It was a lot of fun and I think I'm going to try some more of these. I'd like to take a more targeted approach the next time I try to solve one of these.