This number (removed, as it seemed to cause problem in some browsers, sorry) fails the Fermat test for base 2 (i.e. 2^(p-1) is not 1 mod p). I can't believe it will pass Miller-Rabin. Edit: fails all bases up to 1000.

Congrats, you broke HN.

What, how?

Stick the number in a code block (4 spaces at the beginning of the line). The CSS here doesn't handle long strings well.

2^-80 is an incomprehensibly tiny number. Malice or incompetence are both FAR more likely.

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

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.

Marilyn Vos Savant got a question on her column I'll never forget. The answer was awesome ..

Q: My friend got a perfect hand in bridge. What are the odds of this happening?

A: Your friend is a liar.

You know, I never know what to make of that logic - what if that tiny probability was exactly this one time? It's not like we saw it happen twice, and it could happen at some point. To my gut it seems you can't really know until you have other positive or negative observations.

I wonder if someone has compiled a list of very improbable events that have been observed.

For many years, in the computer science lab at the college where I sort of work, there was a "serious joke" written on the wall which said, with much better wording and some math to back it up, that the difference between a mathematician and an engineer is that the former was more concerned that a probabilistic primality test could inherently fail while the latter was more concerned that even a guaranteed algorithm was actually more likely to return the wrong answer because the computer was hit by a cosmic ray while it was determining if the number were prime.

Probably a quote from SICP:

https://mitpress.mit.edu/sicp/chapter1/footnode.html#2413

2^-80 (~10^24) is is about as likely as being hit by a meteorite (~10^-16)[1] at exactly the same moment you are learning that you won the Powerball (~10^-8). Alternatively, it is as likely as winning Powerball in three consecutive drawings.

[1] - https://what-if.xkcd.com/19/

A person was hit by a meteorite [1]

[1] http://www.telegraph.co.uk/news/science/space/5511619/14-yea...

We happily incarcerate and (for countries that do so) execute people based on much weaker evidence. 2^-80 is absurdly small, to the point that essentially any other possibility is more likely.

You say you want to see it twice, but one data point with an error rate of 1 in 2^80 is, statistically, about a billion times more convincing than a million observations with an error rate of 1 in a million.

(That being said, there are a lot of of explanations that don't involve malice, including honest error, bugs in any of the software products involved in the process, etc. But no, I don't believe that this was a 1 in 2^80 fluke.)

There are countless other possible causes that are much more probable than M-R returning a false positive. What should we do about all of them? Start ruling them out, one by one, sure, but in which order? Common sense says we should do it in the order of decreasing prior probability. The hypothesis "M-R returned a false positive" is there somewhere, in the space of all possible hypotheses, and we'll surely encounter it after all other more likely alternatives are exhausted. I bet we don't have to go that far.

My own list is of length 1 as a category of events. Back in July (it's a bit harder now), the odds that someone's calculated sha256 sum solved a new bitcoin block were around 2^-68. This very tiny probability event was observed on average once every 10 minutes.

2^-80 is absurdly small. But that only means something useful if the number of attempts isn't absurdly large.

I get what you're saying, but 2^-80 is very VERY improbable. Hitting it once is equivalent to a merely "very unlikely" event like winning powerball happening multiple times in a row.

Wow - this has got to be my most downvoted comment. I can't edit the original anymore, so here's my update:

I guess the harsh reaction came from the fact that I didn't define the scope very well: My question wasn't in reference to M-R specifically, just in general. I understand that in this case it makes sense to look at likelier causes (see Sharlin's response).

My point was that it's interesting to look at what happens (or what our reaction is) when very very very improbable events do happen. It seems weird to go with the assumption that because something is extremely unlikely that it won't happen.

When I roll a dice 20 times, I get a particular arrangement of numbers. Given the total number of arrangements possible, that particular arrangement is extremely unlikely, yet I just got it.

A guy got struck by lightning 7 times (https://en.wikipedia.org/wiki/Roy_Sullivan). The odds of any person getting struck by lightning is 1 in 10000. Seven times in a row is 1 in 2^93. But then when you start drilling down, you see that he's a park ranger, and that he's out while lightning happens, which makes the probability that he'll get struck much higher.

If I had phrased the question to you asking what the likelihood of any given person in the world being struck seven times was, you could have calculated the former and said 2^-93 is such a small probability that it's not worth thinking about - and yet here is Roy Sullivan, so there's some sort of conflict in my logic. What's wrong with the former calculation?

Why is it that for any given person the probability is 2^-93 but for Roy it's somehow different, even though he is a "given person"? Is it that the 1 in 10000 number was wrong? But then if we look at all the people who never once got struck, it seems about right. If we inflate that number to 1 in 100 to make Roy likelier to get 7 in a row, then it seems everyone also should be getting shocked more often at least once or twice.

Or maybe it's that somehow the probability changes when we have more information and those two numbers and situations are not comparable on an absolute scale. Maybe if you get hit twice then you're much likelier to get hit again because you're probably in some dangerous location - but how was I to know to factor this in? It seems that it's very much about how you calculate the probability. Who knows what other hidden factors could be wildly affecting the true value of the probability?

That also makes me think - is there even such a thing as the "true" or inherent probability of an event happening?

edit: Or maybe it's the law of large numbers - given enough "trials" or in this case lightning events with people around, even something with an absurdly small probability is bound to happen eventually. But then why do we never factor that in and always just call it a day with 10000^7?

The catch with your logic is that "The odds of any person getting struck by lightning is 1 in 10000" is sloppy phrasing. Of the number of people studied, one ten-thousandth of them got struck by lightning, but lightning does not, as you have observed, choose people at random among those 10,000. Some people are constantly indoors; some are constantly outdoors. Some live in places with frequent thunderstorms; some don't. The only way to get that 1/10000 probability is to pick a person randomly. Picking Roy Sullivan isn't random; neither is picking me.

"The probability of a randomly-selected 1024-bit number passing this primarily test without being prime is 2^-80" is a much more precise statement, because you have selected that number randomly. Obviously, if you have a specific number in mind, the probability of that number being a false positive is either 0 or 1. It either is prime, or it isn't.

Remember that there is no such thing as a random number; there is only a randomized process for selecting numbers.

You've touched upon an old conflict. http://lesswrong.com/lw/oj/probability_is_in_the_mind/

There's no need to refer people to lesswrong for this. The interpretation of probability as a subjective degree of knowledge/evidence is well-known. For example: http://plato.stanford.edu/entries/probability-interpret/ or http://plato.stanford.edu/entries/epistemology-bayesian/

No need to spam links to that cult site.

"It seems weird to go with the assumption that because something is extremely unlikely that it won't happen."

No, it's rational.

As for the rest of your post, you are confused between a priori and a posteriori probability.

"Or maybe it's that somehow the probability changes when we have more information"

Um, yes, that's all that probability is. See Bayes Theorem.

> Why is it that for any given person the probability is 2^-93 but for Roy it's somehow different, even though he is a "given person"?

Because it isn't true that the probability of any given person being struck by lightning is 1/10000. For instance, the internet says that men are around 4 times as likely to be struck by lightning as women. Rather, what's true is that the likelihood of a randomly selected person being struck by lightning is 1/10000. Each individual person has a different likelihood to be struck. I don't know how to calculate it for Roy, but given that he's been struck 7 times I'm sure it's way higher than 1/10000.

> That also makes me think - is there even such a thing as the "true" or inherent probability of an event happening?

I love when people email me after reaching an enlightenment.

There was a probability question that drove me nuts until I figured out what was going on. The question is "A woman has two children. One of her children is a boy. What is the probability that she has two boys?".

The question isn't well defined, because it matters how you learned that one of her children is a boy.

If you asked her "what is the gender of your oldest child?", and she says it's a boy, then the probability that she has two boys is 1/2.

But if you asked her "do you have at least one boy?", and she says yes, then the probability that she has two boys is 1/3.

I don't know what the lesson here is. Probability is hard? Always ask about the experiment?

> is there even such a thing as the "true" or inherent probability of an event happening?

The probability of something depends on what you know. What's the chance that Roy will be struck by lightning tomorrow? If you don't know who Roy is, you might say 1/(10000 * 28000) (where 28000 days is the average human lifespan.). If you do know Roy's history, you'll probably bump that estimate up quite a bit. But if you look up the weather in his park tomorrow and see that it will be sunny all day, the probability will go back down close to zero.

Some things are so hard to know they might as well have an inherent probability, though. If you roll a die, no one's going to predict the outcome of the roll, so we might as well say it's inherently got a 1/6 chance of rolling a 5. And if you shine a photon at a half-silvered mirror, it's actually impossible to predict which way it will go, so I guess that really does have in inherent probability.

You've got to watch out for your probability estimates being wrong, though. I thought the probability of my friend flipping a coin and getting heads was 1/2, until he demonstrated that he could flip heads 10 times in a row.

> edit: Or maybe it's the law of large numbers - given enough "trials" or in this case lightning events with people around, even something with an absurdly small probability is bound to happen eventually. But then why do we never factor that in and always just call it a day with 10000^7?

Because even with 10 billion people, each living a billion days, and having a billion things happen to them in a day... well coincidentally that's exactly 10^28=10000^7, so never mind.

Your gut is bad at statistics.

The likelihood of 1/2^80 is on the same order as me picking out a thousand grains of sand from the Sahara desert, spreading them randomly out through the desert and having you pick out those exact thousand grains of sand.

It's a practical impossibility, a philosophical exercise.

No, it's not the same order. 1/2^80 is the same order as the likelihood of as picking 1000 grains out of 1010, and I'm sure you'll agree that Sahara has more grains that 1010.

However, if you picked a single grain from Sahara desert, you'll be only 2 or 3 orders of magnitude off, so one could say that 2^-80 is only slightly easier than finding a particular grain in a Sahara desert.

Yes, but 1/2^80 is ridiculously large compared to 1/2^1024.

Given that there is so much probability in the world, you would think you would want to be certain about things you can be objectively 100% certain about, especially for one off long term choices that have big implications.

2^-80 is orders and orders of magnitude less likely than the chance of a bit error in RAM when performing the calculation. Or of fucking up the implementation of such a check. Or of a CPU error.

https://blogs.msdn.microsoft.com/oldnewthing/20160114-00/?p=...

So how did it happen in this case?

> 2^-80 is an incomprehensibly tiny number.

When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.

This is not a valid comparison.

An attacker who can bruteforce, say, 2^80 128-bit keys (approximate limit of the computational power of the largest adversaries) has 1 chance out of 2^48 to break the security.

But an attacker has only 1 chance out of 2^80 that this parameter is a non-prime.

2^80 is much larger than 2^48, therefore it is not a problem.

It's not about bruteforcing.

If I want a 128-bit security level, I'm willing for a random guess of my key to have a 2^-128 chance of being correct. I'm likewise willing for a prime I generate to have a 2^-128/uses chance of not being prime (where uses is equal to the number of times I'll actually be using it).

I can't be 100% certain that a large number is actually prime. But I can be certain enough. Having a 2^-80 chance of being wrong isn't good enough when I want a 2^-128 security level.

Yes, security margins are all about what can and cannot be brute forced!

You can't compare these 2 scenarios directly, because in practice:

- attackers can take as many guesses as they want against a piece of data protected by a 128-bit key, but

- attackers get only 1 chance that a particular piece of data protected by a supposed prime is not a prime.

Apples and oranges. When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken.

Most protocols do allow the attacker to choose how many times the defender must win at some game of probability.

If the defender is somehow put in a situation to generate 2^80 primes, then he's in trouble.

Sure, I'd aim for a higher security level in a "attacker can keep asking for new primes until we screw up" scenario.

> When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken.

But it also implies that e.g. the attacker has a 2^-128 chance of randomly guessing a key.

Except for a possible bug, 2^-80 is effectively zero, and getting a non-prime from this routine is effectively impossible.

Would it be reasonable to say that the following scenarios are more probable?

* The specific version of the software that was used to generate the non-prime contained a bug in its implementation of the algorithm

* The specific hardware upon which the software was run was flawed in a way that generated an incorrect output number from the program (i.e. on-disk corruption, RAM corruption, etc., undetected by the checksums in the hardware)

Both of those scenarios are more probable. But neither is anywhere nearly as probable as human error or human malice.

In the case of human error, it could be as simple as a bad cut-and-paste. In that case the number likely has a half-dozen or so factors, some of which should be found relatively easily.

Malice is, of course, impossible to verify.

It would be fantastic to see this fix accompanied by a patch that adds a test that runs that primality check again.

It's a check that probably doesn't need to run in CI over and over again, but boy would it be nice to have it codified so everyone reading now could reproducibly run the check if we felt the desire.

There's one in a thousand chances and there's 1-2^-80 chances. Wouldn't that be some "electrons in the universe" level coincidence? Believing in that borders on religion.

That would be 10^80 which is much, much larger than 2^80.

Unrelated, but 2^80 isn't that astronomic when it comes to computers, considering that the entire Bitcoin network has performed 2^84 hashes.

> I'm pretty sure that when you generate a prime you're using the Miller–Rabin primality test in which case you only probabilistically choose a prime.

Why would somebody use MR when there are faster sieves already running, as well as additional public lists of known large primes?

Maybe they shouldn't be near primes, let alone picking them.

2^1024 is a lot larger than 2^80. The implication is clear.