bonjour verdurin , je comprend pas ton idée et juste vous préciser que ce sont des nombre avec plusieurs dizaine de chiffre que je test , je choisi juste de commencer par les plus simples ou du moins les plus petit
verdurin : oui je suis bien d'accord ...
je ne vois pas l'intérêt de mélanger les valeurs lorsqu'on les prend toutes
et on peut les prendre toutes (enfin ce que tu proposes) pour les petites valeurs de et au hasard pour les grandes ...
je proposais une liste pour conserver les valeurs précédentes pour éviter de retomber sur la même lors d'un choix aléatoire ... et qui se construit donc au fur et à mesure ... et non pas à priori !!!
le gain est-il réellement intéressant ... probablement pas comme le laisse penser l'intervention de perroquet
les booléens me viennent à l'esprit mais je sais pas trop comment l'appliquer ici (toujours dans l'optique de refaire le test après un échec
Je ne te demande rien nullptr19.
C'est toi qui demande.
Je vais essayer de résumer.
Tu veux écrire en python un test probabiliste pour savoir si un entier est premier.
Une caractéristique de ce test est que si la réponse est faux l'entier n'est pas premier, mais que si la réponse est vrai on n'est pas certain que l'entier est premier.
Ton premier message donne la méthode du test pour un nombre b et suggère de tester quelques ( là je ne sais pas ce que quelques à comme valeur pour avoir une proba suffisante ).
Ce qui t'es demandé est d'écrire une fonction réalisant ce test.
Elle se décompose de façon évidente en :
une fonction a comme paramètres un nombre b qui vérifie que n et b sont premiers entre eux et que jacobi(b,n)expon(b,(n-1)/2,n) modulo n.
et une répétition de ce test pour un nombre suffisant de valeurs de b prises au hasard entre 2 et n-1.
merci ! Du coup ça marche bien , mais pas pour de très grand nombre malheureusement mais ça marche . et comme le symbole de Jacobi (a/n) ne dépend que de la classe de congruence de a modulo(n) c'est claire que les deux doivent être égaux modulo n , bien vu
verdurin
Pour des très grands nombres je ne sais pas.
Mais j'ai essayé avec n=10007*10009 ( qui sont deux nombres premiers) en testant 10 valeurs aléatoires de b entre 2 et 100160062.
Sur 1000 essais j'ai toujours obtenu que 100160063 n'est pas premier.
def test (n):
liste=[b1 for b1 in range(2,n)]
if (n%2)==0:
return "{} est non premier".format(n)
for b1 in liste:
if pgcd(b1,n)>1:
return "{} est non premier".format(n)
else:
if expon(b1,(n-1)//2,n)!=jacobi(b1,n)%n:
return "{} n'est pas premier".format(n)
else:
return "{} est premier".format(n)
ce pendant j'ai essayé le nombre que tu as proposé et oui j'ai compris pour le nombre d'essais c'est au niveau du range , effectivement au bout de 1000 tests j'obtiens que
100160063 n'est pas premier
Bonjour.
Je propose les modifications de code suivantes:
def test(n):
if (n%2)==0:
return "{} est non premier".format(n)
for i in range(100):
b1 = randint(2,n-1)
if expon(b1,(n-1)//2,n)!=jacobi(b1,n)%n:
return "{} n'est pas premier".format(n)
return "{} est probablement premier".format(n)
perroquet Bonjour ! effectivement tu as raison , en terme de rapidité , pas besoin d'aller jusqu'à (n-1) surtout pour des n très grand , j'ai essayé de faire tourner la boucle , jusqu'à n-1 pour le nombre proposé par verdurin mais ça plante la machine .
mais effectivement b1 in rang(2,5) (3 tours ) suffisent pour conclure , mais bon , merci à vous carpediem merci pour ton temps ,verdurin merci à tous
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :