Comment exécuter le test de Fermat pour la primalité en moins de 3 minutes

Le test de Fermat est basé sur un résultat de la théorie des nombres connu sous le nom de petit théorème de Fermat.

D'après le petit théorème de Fermat, si n est un nombre premier et d est un entier positif inférieur à n , alors d élevé à la nième puissance est congru à d modulo n .

Si deux nombres ont le même reste lorsqu'ils sont divisés par n, ils sont dits modulo n congruents . d modulo n est simplement le reste d'un nombre d lorsqu'il est divisé par n .

Par exemple, 34 est congru à 16 (modulo 3) comme

34 modulo 3 = 1 et 16 modulo 3 = 1.

Test de Fermat pour la primalité

  1. Pour un nombre n donné , choisissez un nombre aléatoire positif d tel que d < ; n.
  2. Calculer (d ^ n) modulo n .
  3. d modulo n va toujours être d car nous choisissons toujours d qui satisfait la condition d < ; n.
  4. Si le résultat de (d ^ n) modulo n n'est pas égal à d , alors d n'est certainement pas premier.
  5. Si le résultat de (d ^ n) modulo n est égal à d , alors les chances sont bonnes que n soit premier.
  6. Choisissez un autre d aléatoire qui satisfait la condition d < n et répétez les étapes ci-dessus.

Remarque : les exemples de cet article utilisent Swift 4.1

Nous avons besoin d'une fonction pour calculer l'exponentielle d'un nombre modulo un autre nombre.

Nous utilisons l'exponentiation modulaire pour calculer des valeurs lorsque l'exposant est supérieur à 1 car cela nous permet d'effectuer des calculs tout en ne traitant que des nombres inférieurs à n ( modulo dans la fonction ci-dessus).

Le test de Fermat choisit au hasard un nombre d entre 1 et n-1 ( nombre - 1 dans la fonction ci-dessus) inclus. Le but est de vérifier si le reste modulo n de la nième puissance de d est égal à d.

Le test de Fermat est exécuté pour le nombre spécifié. Si un nombre échoue au test de Fermat, nous sommes assurés qu'il n'est pas premier. Si un nombre passe le test de Fermat, il n'est pas garanti qu'il soit premier. Nous essayons de réduire la probabilité d'erreur dans notre test de primalité en exécutant le test suffisamment de fois.

En essayant de plus en plus de valeurs de d (un nombre positif aléatoire entre 1 et n-1), nous pouvons augmenter notre confiance dans le résultat.