Elle utilise p-e l'algo de Fermat (qui s'applique aux nombres impairs) :
SI N est pair --> on divise par 2 et on recommence jusqu'à obtenir un nombre impair.
SI N est impair et qu'il peut s'écrire sous la forme u*v avec u<=v
Posons : x=(u+v)/2 et y=(v-u)/2
On a alors :
N=u*v=x²-y² avec 0<=y<=x<=N.
Il faut chercher x et y afin de satisfaire le relation ci-dessus en commencant par rechercher le plus gd diviseur de N (qui est <= sqrt(N) (cf cours de spe maths Ts
)
( E[a]=partie entiere de a ).
On commence avec x=1+2*E[sqrt(N)] et y=1
Soit r=E[srt(N)]²-N , on distingue 3 cas :
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 alors le plus grand diviseur <= sqrt(N)
si r<0 : r=r+x et x=x+2
Et on reteste la valeur de r.
Qd r=0 (x-y)/2 et (x+y-2)/2 sont ls facteurs de N cherchés.
Il suffit d'appliquer l'algo à chaque facteur pour trouver la décomp en nombres premiers.
[edit]Edité par TachMan le 25-02-2002 à 21:08:25[/edit]
)
