Algorithme de Fermat.

L'algorithme de Fermat (1643) permet de factoriser un nombre entier N et donc de vérifier si un nombre est premier.

Voici l'algorithme:
Imaginons que N est impair et puisse s'écrire sous la forme u*v avec u£v.
Si on pose : x=(u+v)/2 y=(v-u)/2 on a : N=u*v=x²-y² avec 0£y<x£N
L'algorithme de Fermat consiste en la recherche de x et y satisfaisant la relation précédente et fournissant le plus grand facteur de N qui est £ÖN.
On commence avec xß1+2*[ÖN] , yß1 et rß[ÖN]²-N
Si r>0:rßr-y et yßy+2
si r=0:N=(x-y)/2 * (x+y-2)/2 où (x-y)/2 est le plus grand facteur £ÖN
si r<0:rßr+x et xßx+2
Et on reteste la valeur de r.

 Voici l'algorithme écrit sous forme de fonction et appliqué à la recherche des 1000 premiers nombres premiers qui sont stockés dans un tableau: 
fonction Premier(N)
  paramètre N: entier
  à valeur: booléen
entier x, y, r
booléen OK
si N mod 2=0 alors OK ß FALSE
sinon x ß 1+2*[ÖN]
      y ß1
      rß[ÖN]²-N
      tant que NOT (r=0) faire
         si r>0 alors rßr-y
                      yßy+2
         sinon rßr+x
               xßx+2
         fsi
      ftant
      OK ß x-y=2
fsi
résultat((N=2) ou OK)

tableau Tabi i=1,..,1000 de entier
entier i, j, NMAx
Nmax ß 1000
j ß 1
Tab1 ß 2
i ß 1
tant que NOT (j=NMax) faire
  i ß i+2
  si Premier(i) alors j ß j+1
                      Tabj ß i
  fsi
ftant
pour i de 1 à NMax faire
  écrire Tabi
fpour

Voici la traduction en Pascal de la fonction décrite ci-dessus: 

FUNCTION Premier(N:WORD):BOOLEAN;
VAR x,y,r,N2: WORD;
    OK:BOOLEAN;
BEGIN
IF N mod 2=0 THEN OK <-- FALSE
ELSE BEGIN
     N2:=N;
     N2:=SQRT(N2);
     x:=1+2*TRUNC(N2);
     y:=1;
     r:=TRUNC(N2)*TRUNC(N2)-N;
     WHILE NOT (r=0) DO
       IF r<0 THEN BEGIN
                   r:=r+x;
                   x:=x+2
                   END
       ELSE BEGIN
            r:=r-y;
            y:=y+2
            END
     OK <-- x-y=2
     END;
Premier:= (N=2) ou OK 
END;
Cliquez ici pour récupérer une archive contenant une implémentation en Delphi de la décomposition d'un nombre entier par l'amgorithme de Fermat.
Page précédente.
Page d'accueil.