- On 04/21/2010 09:01 PM, Ali Adams wrote:
> Greetings all,

(in another posting, asked)

>

> Can someone please help with validating if the following 62-digit

> number is a prime or not:

>

> 11108195956680805165653650502135350605769090617575464617311659

>

> I am aware of IsProbablePrime but need a definite primality test.

> What about this 309-digit number?

(Which is not even probable-prime, as one single strong pseudoprime

>259336006801222696014182798990654577020329185417451253947966996203374778056958592994128470622708352120230964321433370545343196089458222530238878359827583627468563462233210398589090852507947007265127498998595582306765369537411175275870858814651979141558307396316154291312142703185675301452916463755740936626397

test shows.)

I'm about to sermonize, so be prepared, my brothers and sisters.

Whenever someone says they "need" a definite primality test, they, by

their actions, usually prove that they don't understand that a

primality-proving test, by itself, is not an infallible proof of

primality (in the real world) and they rarely if ever do the correct

thing to decrease the probability of error, giving them a result that's

effectively no more certain than a working pseudoprime test (and, by

probabilities and failure modes that I'll cite here, probably quite a

bit weaker. And by "quite a bit" I mean 20 orders of magnitude, easy.)

Note: Keep in mind that all of this analysis applies in the *real

world*, not to some perfect, fictitious mathematical abstraction where

programmers don't make errors and hardware never fails and you can

ignore most algorithms and divide out big pesky constants because the

ideal theoretical asymptotic performance is always what you get when you

run programs.

It is simple to implement and perform a strong pseudoprime test in

which the probability that a randomly-chosen composite number is

mistakenly stated to be prime is so low that it would never happen in

your lifetime.[1] Not only that, you can trivially make the probability

of this mistake so low that you could test trillions of numbers every

second for the lifetime of the universe, and the probability of *any* of

those tests failing are still astronomically low, and that's even taking

the old ultra-conservative bound that as many as 1/4 of strong

pseudoprime tests can fail. See citations in the link below for numbers

about how conservative that estimate really is.

Many people have pointed out over the years that the probability that

your *hardware* or *software* fails (say, due to a high-energy particle

passing through your processor, or random thermal drift of electrons[2],

or a bad transistor) during your primality test or primality "proof"

becomes rapidly much, much higher than the probability that, say, a

Rabin-Miller test incorrectly declares a composite to be prime.

Depending on the size of the number, this is true *even if you only do

one pass of a Rabin-Miller test*, and the probability of error in the

algorithm is far less than the probability of hardware failure, possibly

by hundreds or thousands of tens of thousands of *orders of magnitude*!

It may also be far, far more probable that the number you meant to

test or the reply (with certificate) was corrupted during communication

with someone else. For example, TCP only has a 16-bit checksum, and can

miss, say, two single-bit errors separated by 16 bits, for a possible

undetected error rate of 2^-16, or 1/65536 in a noisy channel. (Other

error-correcting algorithms apply to communication across the internet,

and most channels have fairly good s/n ratios so the end-to-end

probability of error is luckily usually lower than this.)

There's also the probability that Yahoo does something stupid with

the long line and cuts off a digit or something. (Some would say the

probability of Yahoo's software doing something stupid when adding their

cruft to a posting is 1, but that's being mean. Their software isn't

really that bad. The probability is actually 1-epsilon.)

To see approximate probabilities of the Rabin-Miller test failing

for certain number sizes, even with a *single* round of tests, see:

http://primes.utm.edu/notes/prp_prob.html

Those probabilities of failure, especially for large numbers, are

mind-bogglingly small! Far smaller than the probability of some other

source of error.

Note that for the 309-digit number posted above, the probability of a

strong pseudoprime test mistakenly returning "prime" for a composite

number is less than 5.8*10^-29. Is that probability higher than other

probabilities we've already listed? (And note that since a strong

pseudoprime test easily catches that the number is actually composite.

No matter what base you choose. I'm sure that many here wouldn't

hesistate to give a cash reward for anyone who can find *any* prime base

smaller than the number for which a strong pseudoprime test fails. I

will initially offer all the money in my wallet. And I haven't even

tried to look for one. I'm that confident in the probabilities, or my

wallet is at its usual sad level.)

It's hard to approximate the probability that a particular piece of

software or hardware or communication will fail, but you can never

expect your primality "proof" to be any stronger than the most likely

error in the chain.

If you really *need* a prime number, you *must* then be sure to take

the certificate produced by one program's prime number proof *and verify

this certificate*, presumably with different software on a different

machine and hardware architecture! (I feel I should repeat this

sentence many times!) And then verify it again with another piece of

software! If you *don't* do this, the probability that the primality

"proof" is in error is approximately the probability of the thing most

likely to go wrong in the entire chain. (Again, maybe cosmic rays,

software bugs, Pentiums, race conditions in software, power glitches,

probability of human error, etc.) The primality certificate gives you a

way of verifying (without performing the whole proof again) that the

proof is indeed valid for that number.

However, there's nothing that prevents even the *verification* of the

certificate from having a similar unlikely failure! (Or similar

implementation bugs.)[3] Assuming the implementations and hardware are

completely independent, the best you can do is to multiply the

probability of failure in both systems. Thus, if the probability of

failure in each system independently is 10^-32, then the probability

that *both* fail completely independently but in a way that gives the

same flawed result is at best 10^-64. Look at the URL cited above and

compare that to the probability of a probable-prime test failing. Is it

larger or smaller? If the probability is larger, the likelihood of your

"proof" being better than a pseudoprime test is purely illusory.

I'm not sure what the exact failure probability for a single

instruction is in modern hardware, but it's almost certainly *not*

better than 10^-32. (Multiply this by the number of instructions

required to perform the calculation.)

One of the best sources of information I've seen about actual failure

rates in installed hardware was done by the SETI@Home team, (which had

the world's largest distributed supercomputer at some points) which

cited detected error rates in returned work units (each work unit was

given to at least two people for validation, so errors could be

detected.) I don't remember the exact numbers, but the actual failure

rate appeared to be many, many orders of magnitude lower than 10^-32. I

don't seem to be able to find these stats at the moment. Does anyone

have the link?[4]

If you haven't verified a primality certificate independently to

decrease your probability of hardware or software error, (and there is

*always* a non-zero probability of error on real physical hardware and

where humans are involved, even in a primality "proof") you're likely

not doing any better than a probabilistic prime test, in which the

unreliability of hardware, software, communications, and humans, rapidly

become the limiting factors.

You're also much more likely that some random mischiefmaker will say,

"sure it's prime" when it's not because they're annoyed with you for not

doing these simple tests yourself, and for refusing to take advice on

tools that will do the work for you. But if people didn't refuse to

listen, I wouldn't get a chance to gratuitously sermonize.

If you didn't verify the primality certificate as many ways as

possible, you clearly can't claim you understand that you "need" a prime

number, and don't really understand the probability of all the different

ways that failure could have occurred. Do you even know that the

primality certificate that was posted here was valid for the number you

gave, or did someone maybe miss the last digit digit during

cut-and-paste? Do you even know that the certificate was anything but a

cat walking across a keyboard? The probability that *you*

cut-and-pasted the number incorrectly is orders of magnitude higher than

probability of failure of a pseudoprime algorithm.[5]

Homework: 1.) Can anyone else estimate probabilities of certain

types of errors? What do you think are the probabilities of various

failure modes in posting "prove this number prime for me" to a public

group? Do any of those probabilities exceed that of failure of a

probabilistic test? (Hint: The answer is yes.)

2.) Even if you get a provable prime number handed down impeachably

from the ghost of Fermat, what's the probability that when you're

*using* this prime number that something goes wrong in those

calculations? (Hint: Weakest link in the chain.)

================

Footnotes:

[1] I intentionally state "randomly-chosen" because there are ways

to generate a very sparse set of numbers that can fool one of these

tests if you know in advance the bases it's going to test, which is why

most Rabin-Miller tests choose some bases randomly if there is the

potential for adversarial assault. See, for example:

François Arnault, Constructing Carmichael numbers which are strong

pseudoprimes to several bases, Journal of Symbolic Computation, v.20

n.2, p.151-161, Aug. 1995

[2] There's a certain nonzero probability that an electron will go

"the wrong way" and potentially tunnel "backwards" through a potential

barrier. As voltages used in processors get lower, and as gates get

smaller and the number of electrons required to switch a gate get fewer,

this becomes increasingly more probable. (I don't have my "Feynman

Lectures on Computation" at hand or I'd post some equations for this

probability. Very highly recommended!

http://tinyurl.com/9q4p8o )

[3] Multiple programmers creating similar software bugs is more

common than you might think. Sun's Java implementation had a famous bug

in their calculation of the Jacobi symbol, which caused

primality-testing routines to fail:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4624738

When I implemented a function to calculate the Jacobi symbol in my

Frink programming language ( http://futureboy.us/frinkdocs/ ) I

initially created a similar bug, because my algorithm didn't work for

some negative numbers either. I didn't use Sun's algorithm, but I can

see how they went wrong. The algorithm often cited on the web, in

several number theory books, etc. needs preconditioning to handle

negative numbers correctly. Even more insanely, when evaluating

negative numbers, Java uses different sign conventions for the %

(modulus) operator (used for "int" values) and the BigInteger.mod(n)

function! It's easy to see how Sun even confuses their own programmers.

This bug in Sun's implementation caused some significant pain. Their

primality testing was originally a probabilistic Rabin-Miller test (with

probabilities that can easily be set that it won't return a wrong result

during the lifetime of the universe, and many users set them *way*

higher than that to be very safe) yet that bug caused failures much more

often, and introduced a method of failure that Rabin-Miller *can't*

produce, (Rabin-Miller can't ever declare a prime to be composite, but

it can, very rarely, declare a composite to be probably prime,) which is

why this failure mode was particularly unexpected to a lot of people,

and caused numbers above a certain size to fail mysteriously and

sporadically.

Note: When I was informed of this bug in my implementation of my

JacobiSymbol[x] function, (it didn't affect my primality testing, which

has always worked properly,) I was ashamed that I wasn't able to release

a fix until I got home from work later that day. Sun, on the other

hand, took *3 years* to release a fix. (This bug was present in Java

versions 1.3 through 1.4.2.)

[4] Of course, some of their "failures" were due to intentional

attempts of people to corrupt their results, so exact probabilities of

failure are impossible to come by. There were interesting stories,

though, of *all* or *almost all* of the work units returned by several

well-meaning participants returning incorrect results. The SETI team

contacted these people and were able to verify that their computers'

floating-point units were indeed failing. (Sometimes subtly enough to

not make everything crash, but enough to make all extended calculations

wrong.) This is interesting and probably indicates that the frequency

of subtly or explicitly broken processors in the world is far less than

10^-9, setting a bound for what reliability we might expect for

primality testing.

[5] Don't laugh. This happened on this very list. A few years ago,

an intrepid researcher stated that they had been running a computer for

3+ years to find the factors of one of the RSA factoring challenge

numbers. Awesome persistence! And then one day it beeped! (I can't

imagine the excitement!) He announced to this list that he had

submitted his solution to RSA and was awaiting confirmation of the

factors, and he wasn't sure if the numbers were factors. I asked him

the obvious question, "did you multiply the two factors together and did

they come up with the original number?" The next day, with a leaden

heart, he responded to me and indicated that he had accidentally cut off

a digit when pasting in the original RSA number to his factoring

program. It still hurts me to think about it.

--

Alan Eliasen

eliasen@...

http://futureboy.us/ - --- In primenumbers@yahoogroups.com,

"Jens Kruse Andersen" <jens.k.a@...> wrote:

> It will often be more important to an audience of an announced prime

Jens, as per usual, put his finger on the core of this debate.

> that you say "Trusted program X proved primality" than you argue

> about the microscopic risk that something went wrong in all the

> pseudoprime tests.

In primality proving, we subject ourselves to two disciplines:

1) do not proclaim a proof if you cannot understand the proof method

2) take reasonable precautions that your claim has not been

vitiated by egregious soft/hard-ware errors.

Alan's points are well put. Yet he has missed the essential

gravamen of Jens' dictum

> in practice the negative consequences of an alleged prime

No-one suffers if a cosmic ray hits your computer during a test.

> being composite are usually so small

No-one suffers if George's FFT's screw up during that test.

We are trying to be as careful and honest as humanly possible.

The pursuit of excellence is a greater cause than its achievement.

David