PRIMALITÉ TESTS DE

Articles

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD et Philippe FLAJOLET
  • 6 654 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...

• INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

  • Écrit par Jean-Paul DELAHAYE
  • 1 990 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 a^n—1...

• MERSENNE NOMBRES DE

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

  Un nombre de Mersenne est un nombre entier naturel de la forme 2ⁿ – 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...