Discussion :

[kaari kosaku]

Salut,

Je cherche à créer un programme pour calculatrice qui teste la primalité d'un nombre n.

Pour l'instant mon programme consiste à se servir d'une liste L de nombre premier.

ensuite j'effectue une boucle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
x=0
Jusqu'à ce que ((n/L(x) est entier) OU (L(x)>racine(n))
<div style="margin-left:40px">x=x+1</div>Fin
 
Si (n/L(x) entier)
<div style="margin-left:40px">alors n est entier</div>Fin

Le programme marche à merveille le problème c'est que lorsque l'on a un n au dessus de 10^10, l'exécution du programme est assez longue, et surtout, la taille de la liste de nombre premier commence à saturer la mémoire de la calculatrice.

Je cherche donc une autre méthode pour tester la primalité.
J'ai vu comment fonctionnait le logiciel de chiffrement PGP grâce au petit théorème de Fermat, seulement selon ce test n est "probablement premier", alors je voudrais savoir à partir de quel n les nombres ne sont plus "sûr" d'être premier (étant donné que le calculateur va pas au dessus de 10^500, si tous les premiers inférieurs à 10^500 respectent tous la méthode PGP, alors je peux l'utiliser)

J'espère que vous avez compris mon problème et j'espère que vous m'aiderez à trouver une solution.
Merci d'avance

[ToTo13]

Bonjour,

il faut regarder du coté de la cryptographie où ces algorithmes sont largement utilisé.
En gros le principe est de faire N fois "quelques tests" et tu obtiens alors une probabilité inférieure à 1/2^N que le nombre soit premier. Certains algorithmes donnent des probabilités plus faibles.