Mathematical studies of arithmetical pseudo-random numbers generators

Les générateurs de nombres pseudo-aléatoires linéaires sont faciles à comprendre et à mettre en œuvre. Le plus célèbre d’entre eux est le générateur congruentiel linéaire . Dans la première partie de cette thèse, nous présentons ce générateur et les différents algorithmes de récupération de clés qui ont été conçus contre lui depuis les années soixante-dix. Parce que ce générateur est simple, il a été utilisé pour concevoir des générateurs plus complexes, que nous avons attaqué.

D’autres générateurs de nombres pseudo-aléatoires sont basés sur des problèmes difficiles, tels que le Knapsack generator et ses variantes. Hélas ils ne sont pas prouvé, même sous l’hypothèse que le problème sous-jacent, le Subset Sum problem, est dur. Nous les avons également attaqués avec succès.