Hacker News Reader

Comment by mehwoot | Hacker News Reader

Assuming you are given a single number and you test it and is_prime says it is prime.

If on the other hand you are looking for a number that is_prime says is prime, and you are iterating through candidates, you need to know how likely it is to find a prime number in the first place to tell you how unlikely this is. In most cases the chance of a false positive will be much, much higher than 2^-80.

If for example, you only expected to find a true prime in 1 every 2^80 numbers anyway, there would be a 50% chance that a number you found is prime and a 50% chance it would not actually be.

https://en.wikipedia.org/wiki/Bayes%27_theorem

View on HN

There are approximately x / ln (x) primes below x. That means that there are 2^1024 / (1024 ln 2) - 2^1023 / (1023 ln 2) = 1.3e305 1024-bit primes. There are 2^1024 - 2^1023 = 9.0e307 1024-bit numbers. So, the chance that a randomly-selected 1024-bit number is prime is a little higher one in a thousand, that is, a little higher than 2^-10.

So Bayes' theorem doesn't save you here: it is still statistically unlikely that you will stumble upon a 1024-bit pseudoprime by mistake.

"There are 2^1024 - 2^1023 = 9.0e307 1024-bit numbers"

This is the count of 1023 bits numbers [(x - x/2) = x/2]. 0 is a valid leftmost digit.

The standard usage in the field of crypto is that a phrase like "1024-bit prime" means a number between 2^1023 and 2^1024. For symmetric keys, yes, a "128-bit key" can start with a 0 and can even be all zeros. But for integers with mathematical properties like prime numbers, there's a big difference in the ability to e.g. factor the product of two "1024-bit primes" randomly chosen from [2^1023, 2^1024) and the product of two "1024-bit primes" randomly chosen from [0, 2^1024).

It matches the common-English usage of a phrase like "a six-figure salary." A salary of $020,000 isn't what's meant by the phrase.

You can verify this by, say, running `openssl genrsa 1024 | openssl rsa -noout -text` a few times and looking at the generated prime1 and prime2. They each have the 512th bit set. (They seem to be printed with a leading hex "00:", but there are 512/8 = 64 bytes afterwards, and the first byte always has the high bit set.)

I don't think Bayes' theorem applies very well here, because there's no practical way to check enough numbers such that the effect you're describing comes into play. 2^80 is approximately a million billion billion (10^24), so if you had a million CPUs each checking a billion numbers every second, it would still take a billion seconds (over 30 years) to check that many numbers. I suspect that's why such a small level of uncertainty was chosen in the first place.

Why would 10^24 be a million billion billion? It's 4 blocks of 6 zeros each, so that I'd expect you to call it a billion billion billion billion, if anything.

1 million = 10^6. 1 billion = 10^9. 6+9+9 = 24.

This isn't rocket science.

Reply on news.ycombinator.com