Discussion :

[azman0101]

pourriez vous m'aidez svp! je dois gerer les trés grand nombr dans un prog C: premier nombre premier superieur à m=10^100+1
comment puis-je faire?

[Chupakabra]

test par division successives des nombres premiers jusqu'a sa racine carré (+1) good luck

méthode communément appelée "bourrinos faritas"

[delphi-fan]

Difficile à dire : il faudrait que tu encadres (limites) ta recherche par la connaissance de certaines formes de nombres premiers, comme 2^p -1 avec p impair par exemple. Il existe par ailleurs des tests de primalité qui pourraient peut être servir ?

A+

[Tellmarch]

Ton pb c'est de gérer les très grands nb ou de trouver les nb premiers?

[Invité]

En ce qui concerne la primalité:

test par division successives des nombres premiers jusqu'a sa racine carré (+1)

Cette réponse est si souvent donné que je me dois d'intervenir.
Pour un nombre d'environ 100 chiffres, cela fait environ 10^50 divisions. Avec 10^9 ordinateurs calculant une division en 1ns, cela prendrait environ 10^32 s = 3.16 * 10^24 années >> âge de l'univers (qui vaut environ 15.10^9 années, donc environ 2 million de milliard de fois l'âge de l'univers) !!!!
Cette méthode est donc à proscrire pour les grands nombres.

Pour trouver le premier premier > m (m impair) la méthode est de tester la primalité de m, m+2, m+4, ... jusqu'a ce que l'on tombe sur un premier. La théorie des nombres nous dit que cela arrive rapidement (en fait environ O(ln(n)) tests).

Pour savoir si un nombre est premier, il y a 2 types de méthodes
1- Les méthodes probabilistes:
Ces méthodes répondent à la question
"le nombre P est'il premier"
par
"il est composé" ou "il est premier avec une probabilité d'erreur (ie il est en fait composé) < eps".
On peut prendre eps aussi petit que l'on veut (jusqu'à une proba inférieur à celle d'un dysfonctionnement du processeur dû à un rayon cosmique par exemple).
Ces méthodes sont rapides (polynomiales) et trés utilisé (par exemple dans la génération des clés RSA ou l'on a juste besoin de nombre SPRP cf le lien ci-dessous).

2- Les méthodes déterministes: test p-1, p+1, ECPP (Elliptic Curve Primality Proving), ATK: cf lien ci-dessous.
Méthodes assez compliquée et bcp plus lentes que les tests probabilistes (et pas toujours appliquables comme les méthodes p-1,p+1).

Dans la pratique, on fait un (ou des) tests probabilistes jusqu'a une proba suffisament petite. Si on est parano, on lance alors un test déterministe.
Pour une brève description des méthodes:
http://www.utm.edu/research/primes/prove/

A+

PS: Le premier premier > 10^100 + 1 est 10^100 + 267 avec une proba d'erreur < (1/4)^100=6.2.10^(-59) (100 tests de Miller-Rabbin indépendants).