nombre premier

dusud · November 2006

Bonjour,
On dit que la programmation d'un algorithme pour savoir si un nombre est premier est complexe.. Pourtant j'ai programmé un algorithme tout simple avec 2 boucles imbriquées qui utilisent seulement des soustractions dont la complexité est de l'ordre il me semble de nlog(n) quand n devient grand.
Je ne comprends donc pas quelle est la difficulté du problème des nombres premiers ?
Merci d'avance

jobherzt · November 2006

Oui, mais le problème c'est que l'unité pour mesurer la complexité d'un algorithme est le nombre de chiffres du nombre que tu testes.
Donc ton algo est en realité en O(k 10^k) avec k le nombre de chiffres..
Ce qui n'est pas terrible :-)

abdoul karim · November 2006

http://www.msn.com/

abdoul karim · November 2006

je trop faible en mathematique et les mathematiques me font peur donc j'ai besoin de beaucoup d'aide.

Chimomo · January 2007

Ce qui compte c'est le nombre de chiffres, mais le nombre de chiffres binaires plutôt (en terme d'opération du processeur).

Il y aurait donc plutôt un 2^k (ce qui ne change pas le caractère inutilisable de l'algorithme pour des grands nombres).

Nico · January 2007

Le problème c'est, en fonction de la taille d'un nombre premier n (ie le nombre de chiffres) et non de sa valeur qui est en e^n, trouver le nombre d'opérations nécessaires pour dire si un nombre est premier ou pas

Lorsque tu fais deux boucles, comme elle sont indexées sur e^n, on fait en gros un nombre d'opérations en O(e^n)

Il existe maintenant un algo polynomial pour trouver si un nombre est premier ou pas, mais il est en O(n^k) avec k pas mal grand (de l'ordre de 80 si je souviens bien) et il utilise pas mal de résultats bourrins de théorie des corps
par contre, on ne sait pas encore si la décomposition en facteurs premiers est NP ou pas

Alain Debreil · January 2007

Bonsoir

Ce dont il faut se rendre compte, c'est l'échelle des valeurs.
Suppose un ordinateur qui fait +1 dans un registre de 64 bits.
Suppose que l'ordinateur a une fréquence de 1GHz ($10^9$ opérations par seconde)
Il faut compter jusqu'à $$2^{64} =2^4.(2^{10})^6 \sim 2^4.(10^3)^6 = 16.10^{18}$$ puisque $2^{10}=1024 \sim 10^3$. On mettra donc
$16.10^9$ secondes
$16.10^4$ jours car $(1j = 24h = 86400 s \sim 10^5 s)$
$160\times 3 = 480$ ans, puisque $3ans = 1095j \sim 10^3j$
Soit pratiquement 500 ans pour le comptage !

Et si on prend 65 bits, il faut 1000 ans.
Que dire alors pour des clefs à 128bits ou plus ... avec un algo en $n\log(n)$.

Alain

SXB · February 2007

SVP sur quels logiciels fait-on la programmation de nombres premiers habituellement.

nombre premier

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 9