Primalité d'un grand nombre

[Anonyme]

Pour vérifier qu'un grand nombre est premier j'utilise l'algorithme de
Solovey Strassen
Y a t'il un moyen plus rapide?

Merci

--
Ceci est une signature automatique de MesNews.
Site : http://www.mesnews.net

[Anonyme]

Jean-Laurent wrote:

> Pour vérifier qu'un grand nombre est premier j'utilise l'algorithme de
> Solovey Strassen
> Y a t'il un moyen plus rapide?
>
> Merci
>

Bonsoir,

Attention, le test de Solovay-Strassen est un test probabiliste. Il ne
permet pas d'affirmer avec certitude qu'un nombre est premier.
Quant à l'efficacité des algorithmes, tout dépend du nombre que vous voulez
tester. S'agit-il d'un nombre quelconque d'une centaine de chiffres, d'un
nombre de Mersenne de plusieurs millions de chiffres, ...? Par exemple,
pour ces derniers, le GIMPS (http://www.mersenne.org) utilise le
test de Lucas-Lehmer avec lequel ils viennent de déterminer la primalité
d'un nombre de près de 8 millions de chiffres.
Pour plus d'informations, demandez à google d'effectuer une recherche sur
"primality test".

-- Eric Guirbal