Voici un Algo par divisions successives pour une décomposition d’un nombre en produit de facteurs premiers.
Le nombre 1 n'est pas par convention un nombre premier. Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer.
Par ailleurs pour accélérer le processus à partir du diviseur 3 j’ai placé un pas de 2. Ainsi les diviseurs ne seront plus que des nombre impairs 3 5 7 9 11 13 15 etc..Ceci permet de diviser le temps par plus de 2
Attention?
Vous pouvez tester avec ce nombre 9223372036854675807
9223372036854675807=3*4324027*711017148047 avec un temps sur ma machine de 106,687 secondes
Alors que
9223372036854775807=7*7*73*127*337*92737*649657 avec un temps sur ma machine de 0,154 seconde
On peut en déduire qu’on ne sait ni le nombre de facteurs ni le temps que le processus va mettre.
Cet algo peut prendre un temps extrêmement important sur les nombres très grands de Mersen Mn=2^n-1 ou mieux sur les nombres très grands de Fermat Fn= 2^(2^n)+1 ou sur les très grands nombres premiers
Les nombres de Mersenne sont de la forme Mn=2^n-1
M1=2^1-1=1
M2=2^2-1=3
M3=2^3-1=7
M4=2^4-1=15
M5=2^5-1=31
M7=2^7-1=127
Propriétés des nombres de Mersenne
Si n n'est pas premier alors 2^n – 1 n'est pas premier.
Mais M11=2^11-1=2047=23*89 n’est pas premier
Seules les 5 premiers nombres de Fermat sont premiers Il est difficile de contrôler les autres nombre car ils augmentent très rapidement
Voici le 6 premiers nombres de Fermat Fn= 2^(2^n)+1
F0=2^(2^0)+1=3
F1=2^(2^1)+1=5
F2=2^(2^2)+1=17
F3=2^(2^3)+1=257
F4=2^(2^4)+1=65537
F5=2^(2^5)+1= 4294967297 celui-ci n’est pas premier = 641*6700417
Avant le 3 février 2010, le plus petit nombre de Fermat composé dont on ne connaissait aucun diviseur premier était F14. Le 3 février 2010, un facteur premier de F14 a été découvert par Tapio Rajala, Département de Mathématiques et Statistiques, Université de Jyväskylä, Finlande. Voir le site prothsearch . Tapio Rajala a annoncé sur le mersenneforum que F14 est divisible par 116928085873074369829035993834596371340386703423373313.
Comme ces nombres très grands n'ont pas beaucoup de facteurs premiers, ils prennent beaucoup de temps machine c’est pourquoi d’autres algo ont été trouvés.
S’il est facile d' obtenir le produit de deux grands nombres premiers donnés. Par contre, il est beaucoup plus difficile de trouver les facteurs premiers de celui-ci. C'est ce que l'on appelle une fonction trappe. Ceci s'applique pour les systèmes modernes en cryptologie (l'algorithme à clé publique RSA)
Voici à titre de document les différents algo de décomposition (je ne les connais pas tous).
Le temps d'exécution des algorithmes de factorisation à but général dépend de la taille de l'entier à factoriser et des facteurs qui le composent. Ceci est le type d'algorithme utilisé pour factoriser les nombres RSA. La plupart des algorithmes de factorisation à but général sont basés sur la méthode des congruence de carrés.
- Divisions successives
- Algorithme rho de Pollard
- Algorithme p-1 de Pollard
- Factorisation en courbe elliptique de Lenstra
- Congruence de carrés (Méthode de factorisation de Fermat)
- Crible spécial de corps de nombres (SNFS)
- Crible quadratique
- Crible général de corps de nombres (GNFS)
Code : Tout sélectionner
; algorithme de DECOMPOSITION EN FACTEURS_PREMIERS
; Le nombre 1 n'est pas par convention un nombre premier.
; Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer
EnableExplicit
Define nb$,nb.q,l2nb.d,nbl2.q,nbMAX.q,NBREC.q,P.q,i,pas,fact_prem$,j,deb.q,mess$
saisie:
mess$+"Décomposition en facteur premier"
If Len(mess$)>99
MessageRequester("Erreur","Donnez un entier positif < ou 9223372036854775807"+#CR$+"Relancez le prg")
End
EndIf
nb$=InputRequester(mess$,"Donnez un entier positif < ou = 9223372036854775807","9223372036854775807") ; c'est la limite d'un type q
If Len(nb$)>Len("9223372036854775807")
Goto saisie
EndIf
nb.q=Val(nb$)
If nb<1
Goto saisie
EndIf
; si le nombre nb est pair il peut être une puissance de 2 nb=2^n avec n positions max dans la table donc n=log2(nb)
; si le nombre nb est impair il peut être une puissance de 3 nb=3^n avec n positions max dans la table donc n=log3(nb)
If nb%2=0
l2nb.d=Log(nb)/Log(2)
Else
l2nb.d=Log(nb)/Log(3)
EndIf
nbl2.q=l2nb ; conversion en nb entier
NBMAX.Q=Sqr(NB) ;limite de recherche des facteurs premiers
NBREC.Q=1
Dim Tab.q(NBl2)
p=2
i=0
pas=1
fact_prem$=nb$+"="
deb.q=ElapsedMilliseconds()
While (p<=NBMAX) And (nb>1)
If nb%p=0
tab(i)=p
nb=nb/p
i+1
Else
p+pas
EndIf
; ********** les 3 instructions suivantes accélèrent le processus sur les grands nombres (pas de 2 à partir du diviseur 3 on ne garde que les diviseurs impairs )
If p=3
pas=2
EndIf
Wend
tab(i)=nb
If tab(i)<>1
I+1
tab(i)=1
EndIf
For j=0 To i
fact_prem$+tab(j)
NBREC*tab(j) ; Vérification de la décomposition
If j<i
fact_prem$+"*"
EndIf
Next
MessageRequester("Résultat",fact_prem$+#CR$+Str(NBREC)+": contrôle"+#CR$+"temps="+Str(ElapsedMilliseconds()-deb)+"ms"+#CR$+"Nb postions de la table :"+Str(nbl2))