Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA

On May 30, 9:38 am, Thomas Pornin <por...@xxxxxxxxx> wrote:
Corollarily, a primality test which may get it wrong with probability
2^-100 is not a big concern, because there are other failure reasons
which are million times more probable, and which do not prevent me from
sleeping. In other words, insisting on naming a function
"is_probable_prime()" instead of "is_prime()" due to the slight
probability of mathematical failure just means that you are getting your
priorities wrong: if that worries you, then you should _first_ setup a
redundant architecture to abstract failures, such as what is used in
some critical systems (e.g. planes and rockets).

I disagree with this.

Some people might say that two wrongs do not make a right.

I say it is a matter of principle.

I was reading "Data Structures & Their Alogorithms" by Lewis &
Denenberg, and the only one-line sentence in the entire book is

"Ever."

They wrote that sentence to emphasize that, if an engineer defines a
contract (explicitly) for an algorithm, then it should do that,
without exception. The argument you give above has nothing to do with
the algorithm. It has more to do with philosophy and earthly reality.
Algorithms, those that are deterministic, should not be judged by how
they manifest in reality. And algorithm can be perfect, but the
physical manifestation is never perfect.

Let's say I were building a machine to help eradicate pancreatic
cancer, and I knew in advance that the probability that patient was
going to die so great that a known anomaly in my design would be
essentially ineffectual. Do I deliberately ignore the anomaly if the
costs are equivalent? Do I go to a meeting and say, "Yes, yes, I know
it's wrong, but I did the math, and it is so much likely that the
patient will be dead first that the chance of my flaw having an
adverse effect is less than chance of all of you spontaneously
decomposing."

In the case of this member function, the cost is equivalent. There is
no need to set priorities.

If it is propbabilistic, how hard is it to name it as such.

The user of the function, perhaps myself, can then decide in their own
mind whether probably prime really does mean prime.

Then there is the matter of (momentary) confusion that might arise if
another engineer came across code and assumed that a deterministic
algorithm was being used because of choice of name...

-Le Chaud Lapin-
.

Relevant Pages

  • Re: FYI: RAID5 unusably unstable through 2.6.14
    ... add disks the probability of a single failure is grows linearly, but the probability of double failure grows much more slowly. ... If 1 disk has a 1/1000 chance of failure, ... After the first drive fails you have no redundancy, the chance of an additional failure is linear to the number of remaining drives. ...
    (Linux-Kernel)
  • Re: FYI: RAID5 unusably unstable through 2.6.14
    ... add disks the probability of a single failure is grows linearly, but the probability of double failure grows much more slowly. ... I was speaking in the case of a RAID-5 set, where the minimum is 3 drives, so every additional drive increases the chance of a double fault condition. ...
    (Linux-Kernel)
  • Re: Do not answer Mxsmanic
    ... If the probability of any single engine failing is p, ... Tails = engine failure. ... 50% chance of failure. ...
    (rec.aviation.piloting)
  • Re: PKI: the end
    ... the published deterministic polynomial algorithm ... The usual primality test is Rabin-Miller, with a fixed failure ... number is prime with probability at least 1-2^. ...
    (sci.crypt)
  • Re: FYI: RAID5 unusably unstable through 2.6.14
    ... chance of an additional failure is linear to the number ... of remaining drives. ... F - probability of double failure ...
    (Linux-Kernel)