In several branches of mathematics, we use random sequences. The problem is that it is difficult to manufacture them automatically. We then use sequences built from a deterministic algorithm which seems to have all the properties of random sequences. We speak of pseudo-random sequences.
To randomly choose a number between 0 and 1.024, one idea is to flip a coin ten times. By noting 0 the stacks and 1 the faces, we obtain a number with ten digits binaries, like for example 1001011111 (which we actually found as well). In decimal, this gives 1 + 2 + 4 + 8 + 16 + 64 + 512, or 607. Of course, if you flip a coin eleven times, you get a number between 0 and 2,048, and so on.
In several areas of mathematics (simulation, scientific computing, cryptography), we need a large amount of random numbers therefore immediately such numbers. The method we have just proposed quickly becomes impractical.
The creation of pseudo-random
It is more economical to use a deterministic sequence having the appearances of a random sequence. Here is a recipe for making one, with numbers between 0 and 2147483646. We take a first term really at random, for example the hour in nanoseconds, which we call the germ, say 3248455607. We multiply this number by 16807 and we keep the remainder of the result in the division by 2147483647. We obtain 1316629168. We repeat the same operation with this new number and so on: 914927888, 1210101096, 1498983382, 1283038317, etc. . This sequence looks like a random sequence, it passes all the usual tests for the distribution of random sequences, but it is nevertheless deterministic.
Use
When the important thing is to use a sequence of numbers evenly distributed over a given interval, pseudo-randomness can replace randomness without any problem. When the important thing is that the terms of the sequence are unpredictable, this is not the case. In the first category, we find the uses in simulation and calculation digital, in the second, the uses in cryptography.
Learn more about Hervé Lehning
Normalian and agrégé in mathematics, Hervé Lehning taught his discipline for more than forty years. Crazy about cryptography, member of the Association of Reservists of Cipher and Information Security, he in particular unraveled the secrets of Henry II’s cipher box.
- His blog MATH’MONDE on Futura
- the last book by Hervé Lehning :
Also to discover: The universe of secret codes from Antiquity to the Internet published in 2012 by Ixelles.
Interested in what you just read?
Subscribe to the newsletter Fun math : every week, Futura deals with a mathematical question for the pleasure of 7 to 77 year olds. All our newsletters
.
fs4