Sebastiano Vigna : Pseudorandom number generators

- - Anciens Colloques

 Pseudorandom number generators


Sebastiano Vigna

 Dipartimento di Informatica, Università degli Studi di Milano

Jeudi 17 mai 2018, 15:30-16:30, Salle 3195, Pavillon André-Aisenstadt

    Université de Montréal, 2920 Chemin de la Tour

Café avant 15:00-15:30


La conférence sera présentée en anglais


Linear pseudorandom number generators are very popular due to their high speed, to the ease with which generators with a sizable state space can be created, and to their provable theoretical properties. However, they suffer from linear artefactsi, which show as failures in linearity-related statistical tests such as the binary-rank and the linear-complexity test. We describe three new contributions. First, we introduce two new linear transformations that have been handcrafted to have good statistical properties and at the same time to be programmable very efficiently on superscalar processors, or even directly in hardware. Then, we describe a new test for Hamming-weight dependencies that is able to discover subtle, previously unknown biases in existing generators. Finally, we describe a number of scramblers, that is, nonlinear functions applied to the state array that reduce or delete the linear artefacts, and propose combinations of linear transformations and scramblers that give extremely fast pseudorandom generators of high quality. A novelty in our approach is that we use ideas from the theory of filtered linear-feedback shift registers to prove some properties of our scramblers, rather than relying purely on heuristics. In the end, we provide extremely fast generators that use few hundred bits of memory, have provable properties and pass very strong statistical tests.



Détails de l'événement

Date de l'évènement : jeudi 17 mai 2018 15:30
Emplacement : 3195 Pavillon André-Aisenstadt, 2920 chemin de la Tour
Prix : Gratuit

Partager :
  • Envoyer
  • Imprimer