PRIMALITÉ TESTS DE
Articles
-
ALGORITHMIQUE
- Écrit par Philippe COLLARD, Philippe FLAJOLET
- 6 652 mots
- 3 médias
Un entier m composite (non premier) possède nécessairement un facteur plus petit que √ m. Il en résulte que l'essai successif des divisions exactes de m par les nombres 2, 3, 4...,[√ m]constitue à la fois un algorithme de factorisation – qui détermine les diviseurs de... -
INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE
- Écrit par Jean-Paul DELAHAYE
- 1 988 mots
...et aucune méthode sûre ne permet aujourd'hui d'en produire dans un délai raisonnable. On utilise donc ce qu'on appelle des algorithmes probabilistes. Le test probabiliste de primalité de Fermat en fournit un exemple élémentaire : choisir un nombre entier a au hasard entre 2 et n–1 ; si an—1... -
MERSENNE NOMBRES DE
- Écrit par Jean-Marie PRUVOST-BEAURAIN
- 516 mots
Un nombre de Mersenne est un nombre entier naturel de la forme 2n – 1, où n est un nombre entier naturel. Ces nombres ont été nommés ainsi en l'honneur du Français Marin Mersenne (1588-1648), qui en avait entrepris l'étude.
Pour qu'un tel nombre, généralement noté Mn, soit...
