PRIMALITÉ TESTS DE

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 831 mots
  •  • 3 médias

Dans le chapitre « Tests de primalité et de factorisation »  : […] 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 m si m est composite – et un test de primalité – si aucun diviseur n'a été obtenu. Contrairement aux algorithmes précédemment […] Lire la suite

INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 990 mots
  •  • 1 média

Dans le chapitre « Preuves probabilistes de primalité »  : […] La cryptographie a fréquemment besoin de grands nombres premiers (de cent chiffres décimaux et plus) 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 a n —1 e […] Lire la suite

MERSENNE NOMBRES DE

  • Écrit par 
  • Jean-Marie PRUVOST-BEAURAIN
  •  • 537 mots

Un nombre de Mersenne est un nombre entier naturel de la forme 2 n – 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é M n , soit premier (c'est-à-dire n'ait pas d'autre diviseur que 1 et lui-même), il faut que n (appelé l' indice de M n ) soit un […] Lire la suite