Computations of combinatoric and statistics functions and inverses which deliver good accuracy over a wide range of values. Accuracy tests allow the functions to be checked in any computing environment.
Please send comments and suggestions for improvement to: firstname.lastname@example.org. You may wish to help support this work by patronizing Ritter's Crypto Bookshop.
The binomial distribution represents the probability that a particular type of event will occur a given number of times. When each "success" has probability p, and there are n trials, we can compute the probability of getting exactly k successes. We can also compute the cumulative probability of getting k or fewer successes; this is the cumulative distribution function or c.d.f.
For the binomial to be an appropriate model, it must describe Bernoulli trials. This is sampling with replacement in which:
Since it is common in cryptography to create random-like events, these conditions are often met, although the values involved may be far larger than could be easily handled with a normal calculator.
The binomial distribution gives the probability of finding exactly k successes (or at least k successes in the c.d.f.) over n trials given probability p of success on each trial:
n k n-k B(k,n,p) = ( ) p (1-p) k
The binomial is the appropriate distribution for bit-changes from an invertible substitution table or cipher. This is the source of bit diffusion within a substitution table, and is related to avalanche.
Suppose we have some input value to a substitution table or cipher. Now suppose we change that input value. This will select a different value from the table. We can expect about half of the output bits to change on average, but we could get as few as one, or as many as all of them. The distribution is binomial.
The Poisson distribution is a simplified model for the binomial distribution under certain conditions:
The Poisson distribution gives the probability of finding exactly k successes (or at least k successes in the c.d.f.) given success expectation u:
k -u P(k,u) = u e / k!where e is the base of natural logarithms:
e = 2.71828...and u is:
u = n p