So the idea that companies use very large primes for security got me thinking about what they do. First of all, how do they get a list of very large primes in the first place? Couldn't "hackers" use this same method? Second, how do the prime numbers correspond to the 16 digit number on the front, and the three digit number on the back? Are they both prime?

To be completely honest, I do not know about credit card numbers but to be somewhat on topic, I learned about an RSA Encryption System in an algebra class. It involves choosing two different primes, say $p$ and $q$, and then multiplying them to receive a modulus $m = pq$. A number called the *totient* $t = lcm(p - 1 , q - 1)$ is computed in order to choose an integer $1 < x < t$ used as a *public key*. But there is a *private key* $r$, taken from the computation $rx \equiv 1 (m)$.

The process was a few pages long in my notes so here's a link to a Wikipedia article that I used to clarify my notes (which includes how this system is used). I guess I should have looked at the book in the first place…chapter 8.2, page 233 is where the RSA stuff begins.

Well, even though it didn't really contribute to your questions specifically, this is a way prime number computation can be used in systems security. At the very least, it's an example that encompasses a lot of the things we've been learning so far!

There are some good questions here, many of which I hope to be able to talk about by the end of the term. Your first point (how are large primes found?) is a great question; in fact, there are methods in place for finding so-called "industrial strength" primes. These methods give you ways for finding a handful of such primes, but they aren't good at generating complete lists of primes. The way encryption methods work, the fact that "hackers" can also generate primes won't help them break the codes unless they have a **complete** list of primes. This is why companies have a current leg-up on hackers.

As for credit card numbers: the security measures taken to protect credit card numbers comes not in the way that numbers are issued on cards, but rather how those numbers are transmitted from your computer to your vendor. This transmission involves an "encryption" phase where your credit card number is scrambled into unreadable gobblity-gook and a "decryption" phase where the transmitted gobbilty-gook is turned back into your credit card number. The security of the encryption, then, is in its ability to keep people who intercept the gobbilty-gook from being able to decrypt it back into your credit card number. Its in this encryption/decryption that number theory creeps in. Dan's got the right idea about how this stuff works, but we'll talk about it at length closer to the end of the term.

I should also say: there is typically some number theory involved in credit card numbers. Someone should look up "check digits" or "luhn algorithm" and post what they find.

here's an informal explanation of the luhn algorithm by wikipedia: http://en.wikipedia.org/wiki/Luhn_algorithm

After doing a little more research, another reason (which I think is similar to what Andy was saying) is that, even though it's not terrible difficult to generate large prime numbers, it is extremely difficult to find 2 products of a number that have large prime numbers as factors. For example, the number 51920810450204744019132202403246112884629925425640897326550851544998255968235697331455544257

(as given from an example here) has 2 products (other than 1 and itself), both of which are extremely large prime number. Clearly, this wouldn't be very easy number to factor quickly, even if you do have an entire list of prime numbers, and I'm guessing it isn't nearly as difficult as numbers that websites use for encryption.

Also, if you're interested, the website I linked to earlier has a challenge problem so you can try hacking a large prime number like the one above.