Prime numbers

[Bryan_Ekers]

It was in hexadecimal, I just didn’t type any letters. Satisfied?

[Bryan_Ekers]

I decided to just look it up and learned RSA Labs was running contests where they would publish various-sized N values and award prizes for anybody who could find the appropriate p and q. The smallest N not yet factored (admittedly, I expect interest fell off significantly when RSA stopped giving cash prizes) is the 232-digit 1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079.

So… y’know… go nuts.

[pulykamell]

@Bryan_Ekers

It was in hexadecimal, I just didn’t type any letters. Satisfied?

Well, FWIW, the final factorization was: 3343 × 80814 362767 × 49088 464232 315669 000167 × 121139 790939 541766 433273 004057 × 5772 669804 501159 736144 919275 294300 097290 818445 203478 308604 682152 212381 606211 094953 930153

and took 18 minutes. Damn. I’m impressed. (Then again, there was one pretty low prime factor, and another one relatively low). Here’s the site I used for those interested.

[Yask]

@Bryan_Ekers

One of the more common applications (though most people using it don’t understand or need to care about the mechanics) is RSA cryptography, allowing a person to send secret messages. The gist (highly simplified) is that:

Secretly choose a prime number p, which by definition can only be divided by 1 and p itself.
Secretly choose a different prime number q, which by definition can only be divided by 1 and q itself.
Multiply p and q to get N. N, therefore, will only be divisible by 1, p, q and N itself.

What allows RSA cryptography to work is that once you’ve chosen p and q, generating N is easy. If all you have is N, trying to work backward to find p and q is difficult.

Picture 15. Very quickly, anyone can see that its p and q are 5 and 3. But what if N is 927401749817398759182759192911 ? How long would it take even a very fast computer to find p and q? Years? Centuries? The age of the universe?

Anyone can generate their own N and publish it freely. This becomes their “public key”. If I wish to send a secret message to someone, I will use their public key to encrypt it. Then it doesn’t matter who might see the encoded message, because the only way to decrypt it is by using p and q, which the recipient knows and has not published, as they form his “private key”.

I’m sorry to be a bother, but I’m not quite following the end of your explanation. To keep it simple, let’s say that it’s not easy for anyone to see that 5 (p) and 3 (q) are the prime factors of 15 (N). I want to send you a secret message. You give me 15 as your public key. Now what?

[DPRK]

@Yask

I’m sorry to be a bother, but I’m not quite following the end of your explanation. To keep it simple, let’s say that it’s not easy for anyone to see that 5 (p) and 3 (q) are the prime factors of 15 (N). I want to send you a secret message. You give me 15 as your public key. Now what?

N is generated as part of the key, but you also need to pick an exponent for your public key, like 3. Now to encrypt a message like “7”, compute 7^3 modulo 15, which gives “13”. To decrypt you compute 13 to the power of the secret key, also 3 in this example. Needless to say, this is more practical using bigger numbers. See the articles on RSA cryptosystems

[DPRK]

I forgot to explain the most important thing: the reason why you need to factor N is to be able to compute the decryption key given the public, encryption key.

[septimus]

Although it focuses on one specific problem — the most famous of all the Million-Dollar math problems, RH — Derbyshire’s Prime Obsession is an excellent read, accessible to the layman.

In the early 1900s, British mathematician Godfrey Harold Hardy sometimes took out a quirky form of life insurance when embarking on ocean voyages. In particular, he would mail a postcard to a colleague on which he would claim to have found the solution of the Riemann Hypothesis. Hardy was never on good terms with God and felt that God would not let him die in a sinking ship while Hardy was in such a revered state, with the world always wondering if he had really solved the famous problem.

[zimaane]

It’s hard to overstate how important this. Every time you send a credit card number over the internet this procedure (or something similar) is used to encode your message. Modern e-commerce would not be possible without it.

[ftg]

Note that RSA itself is quasi-deprecated by the Crypto community. It’s just not secure enough at the bit sizes needed to do rapid transactions. Look at the table here and note how the latest TSL standard is dropping some forms of it.

AES and SHA-2 are currently the most common system used to encrypt Internet traffic. But like RSA, SHA-2 is being deprecated. SHA-2 reverse hashing is also used as the “work” in Bitcoin mining. So that’s a lot of cycles being used on that right now.

If you search the SHA-2 article for “prime” you will see several places in the code where they are used. But these are small potatoes compared to RSA.

(Note: I am far from an expert on this. But I’m a bit more knowledgeable than the average CS nerd. I was “near” to lot of early public key stuff. E.g., a week after RSA had been developed I was in the back seat of a car with R and A. But compared to Real Experts I’m practically a noob.)

[Chronos]

Quoth septimus:

For a loosely related reason, it is often good practice to arrange that the number of teeth on two interacting gears be relatively prime to each other.

Note that “relatively prime” is not the same thing as “prime”. Two numbers are relatively prime if they have no factors in common (other than 1). For instance, 9 and 10 are relatively prime to each other. But a prime number is relatively prime to everything.

[Dr.Strangelove]

@septimus

Yes. BTW, sometimes “quadratic reprobing” is useful (m, m+1, m+4, m+9, …) although it visits only half the table.

It’s really much easier to use a power-of-2 table size and a probe function of n(n-1)/2. Visits the whole table and no funny business with primes.

[Dr.Strangelove]

@ftg

Note that RSA itself is quasi-deprecated by the Crypto community. It’s just not secure enough at the bit sizes needed to do rapid transactions.

Maybe so, though Diffie–Hellman key exchange is still in widespread use and also depends on the properties of large prime numbers.

[septimus]

@Dr.Strangelove

It’s really much easier to use a power-of-2 table size and a probe function of n(n-1)/2. Visits the whole table and no funny business with primes.

Nitpicks:

• If 134 million entries isn’t quite enough, you’ll need 268 million with that scheme. This is too profligate if memory is scarce.
• Taking residue with a prime divisor provides a “hashing” (randomization) utility that power-of-two divisors lack.
• When quadratic reprobing is used, a tiny number of additional lines of code suffice to probe the other half of the table if necessary.
• Anyway, reprobing is altogether unnecessary with some of the best hash table schemes.

[Dr.Strangelove]

@septimus

Nitpicks:

Depends on the application, sure. Though I’d be curious if you know anything about the typical distribution of probes between the two cases. I’m not super convinced that the mod p effect is really any more effective at spreading out the probes.

I sorta reminded myself that I’d always been curious about a proof that triangular number probing (still quadratic, of course) hits every element in a 2^b size table. I found one, but didn’t read it. Nothing has come to mind yet aside from the obvious fact that on the Nth probe, the next index will repeat and thus collide (since n(n-1)/2 + n = (n+1)n/2).

[Hari_Seldon]

@ftg

Note that RSA itself is quasi-deprecated by the Crypto community. It’s just not secure enough at the bit sizes needed to do rapid transactions. Look at the table here and note how the latest TSL standard is dropping some forms of it.

AES and SHA-2 are currently the most common system used to encrypt Internet traffic. But like RSA, SHA-2 is being deprecated. SHA-2 reverse hashing is also used as the “work” in Bitcoin mining. So that’s a lot of cycles being used on that right now.

If you search the SHA-2 article for “prime” you will see several places in the code where they are used. But these are small potatoes compared to RSA.

(Note: I am far from an expert on this. But I’m a bit more knowledgeable than the average CS nerd. I was “near” to lot of early public key stuff. E.g., a week after RSA had been developed I was in the back seat of a car with R and A. But compared to Real Experts I’m practically a noob.)

I’m even less than an expert, but I know that AES is a symmetric key encryption which obviates having a public key. I couldn’t quite figure out whether SHA is. But my impression is that RSA, though rather slow, is still used in conjunction with AES to send out the required key for a symmetric system. So if you use a product of two 500 digit primes (or even pseudoprimes) it will be very slow to encrypt and decrypt the needed key, but it need be done only once for each message.

Aren’t there public key methods based on discrete logarithms or on the arithmetic of elliptic curves? Will they succumb to quantum computers?

[septimus]

@Dr.Strangelove

I sorta reminded myself that I’d always been curious about a proof that triangular number probing (still quadratic, of course) hits every element in a 2^b size table. I found one, but didn’t read it. Nothing has come to mind yet aside from the obvious fact that on the Nth probe, the next index will repeat and thus collide (since n(n-1)/2 + n = (n+1)n/2).

I’d never heard of this nifty fact! A little Googling suggests that Donald Knuth might be the discoverer, but I stopped Googling when I also decided to add “Try to find a proof” to my To-Do list.

But I still like prime-sized tables. And when feasible, Cuckoo Hash Tables seem like a good way to go: trivial “reprobing,” efficient in space and time, quite flexible and very elegant!

[Buck_Godot]

@Hari_Seldon

That’s only 154 digits. I think such numbers can now be factored, although not easily. But the product of two 500 digit primes will be essentially unfactorable, at least without a quantum computer.

One interesting fact is that there are algorithms that can quickly test to see if a 500 digit prime with 99.9999999…% probability. There are also much slower ones that give 100% but I doubt they are worth the effort. This is what makes RSA encryption so successful.

In order to avoid a severe hijack, please find a different notation to indicate a 99.99 with an arbitrarily large but finite number of 9’s if you want to distinguish it from 100%.

@am77494

With the cryptography applications mentioned, it is also to be said that math guys love prime numbers for the same reason climbers like mountains. They are challenging to get to.

Not me. I’m a math guy and I can’t stand prime numbers because they are such a pain to work with. On the other hand I also think that people who climb mount Everest are crazy.

[Pleonast]

@Chronos

Note that “relatively prime” is not the same thing as “prime”. Two numbers are relatively prime if they have no factors in common (other than 1). For instance, 9 and 10 are relatively prime to each other. But a prime number is relatively prime to everything.

A prime number is not relatively prime to itself. And that actually matters in gearing.

[iamthewalrus_3]

@TriPolar

Really? You think that was needed to determine whether a set of 19 or less objects could be evenly divided?

No, the bone wasn’t required to know that. The bone was an artifact that noted the thing they had figured out.

Like, you don’t need a multiplication table to know how to multiply, but a multiplication table is an artifact of having figured out some useful amount of math and written it down.

I can easily believe that numbers that won’t evenly divide would be useful to know in early human society, given how greedy and attuned to inequality we are.

[DPRK]

@Hari_Seldon

I’m even less than an expert, but I know that AES is a symmetric key encryption which obviates having a public key. I couldn’t quite figure out whether SHA is. But my impression is that RSA, though rather slow, is still used in conjunction with AES to send out the required key for a symmetric system. So if you use a product of two 500 digit primes (or even pseudoprimes) it will be very slow to encrypt and decrypt the needed key, but it need be done only once for each message.

That is indeed how it is used in practice. There was some vulnerability involving the specific TLS_RSA implementation, but like you I am not an expert on TLS and don’t know how widely applicable it is. It definitely serves to illustrate that badly-implemented RSA is vulnerable to side-channel attacks as well as direct cryptographic attacks.

SHA is a (family of) cryptographic hashing algorithms.

Aren’t there public key methods based on discrete logarithms or on the arithmetic of elliptic curves? Will they succumb to quantum computers?

I’m not an expert on this field either, but certainly there are quantum algorithms and this (old!) paper suggests that elliptic-curve arithmetic is more vulnerable than straight RSA.