Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Prepa (autre)
test probabiliste python
Posté par nullptr19
Bonsoir à toutes et à tous .
voici un test de primalité que j'aimerai rentrer en machine , c'est celui de Miller-Rabin plus précisément .
soit n un entier impair.
on definit r et s teles que n=2^r.s+1 avec s impair et r
1.
Choisir un nombre avec 1<
<n et calcluler (
,n)
. Si (c1,n)>1 alors n n'est pas premier et le test est terminé .
. sinon , calculer (mod n)
- si alors soit n est premier soit n est pseudo premier-fort de base c1 .
- sinon , calculer
- si , alors soit n est premier soit n est pseudo-premier fort de base c1
-sinon calculer , tant que
- si pour 1
i r-1 alors n n'est pas premier et le test est terminé .
Si le test n'a pas été interompu , recommencer le test pour un autre entier que c1 , puis un autre entier que c1 et c2 ...
voici ce que je propose mais ca me ca marche pas j'ai essayé de respecter le l'algorithme mais je sais pas ,
def TestMiller(n):
s = n-1
r = 0
while (s%2)==0:
s//=2
r+=1
for c1 in range(2,100):
if pgcd(c1,n)>1:
return " {} n'est pas premier".format(n)
else :
if expon(c1,s,n) == 1 :
return "{} pseudo premier de base {}".format(n,c1)
else :
if expon(c1,2*s,n)==-1:
return "{} pseudo premier de base {}".format(n,c1)
else:
i=2
while expon(c1,2**i*s,n)!=-1:
i=+1
for i in range (2,r):
while expon(c1,2**i*s,n)!=-1:
return "{} n'est pas premier".format(n)notez par ailleurs que les fonction pgcd et expon sont respectivement les fonction me return le pgcd et l'exponentiation rapide .
Merci!
Bonjour,
je me demande pourquoi ça marcherait.
La question est : l'entier n est-il premier ?
la réponse est oui ou non.
Ici on va regarder si l'entier n est fortement pseudo-premier en base c pour un certain nombre de valeurs de c.
Le schéma de la fonction est donc :
répéter k fois :
choisir un entier c
si n n'est pas pseudo-premier en base c : # utilisation du test de Miller-Rabin
on arrête tout et on répond non # n n'est pas premier
fin de la boucle
on répond oui # n est vraisemblablement premierQuelques remarques.
On peut renvoyer la valeur de c qui prouve que n n'est pas premier.
On trouve un pseudo-code dans Wikipédia
Bonjour verdulin , non , d'après l'énoncé , n n'est pas premier , je m'y met du coup merci pour votre réponse j'essaie de le rentrer en machine et je reviens vers vous
verdurin Bonjour , je reviens un peu tardivement sur le programme , car en travaillant sur sur certains code , j'ai remarqué que mon test probabiliste me renvoyait un peu n'importe quoi , voici à nouveau ce que je propose :
from random import *
def testMiller(n,k):
r=0
s=n-1
while (s%2)==0:
s//=2
r+=1
for i in range (2,n):
c1=randint(2,n)
if pgcd(c1,n)>1:
return"{} n'est pas premier".format(n)
break
x=expon(c1,s,n)
if x==-1 or x==1 :
return"{} est pseudo premier fort de base {}".format(n,c1)
x=expon(c1,2*s,n)
i=2
if x==-1:
return "{} pseudo premier de base {}".format(n,c1)
while expon(c1,2**i*s,n)!=-1 and 1<i<r:
x=expon(c1,2**i*s,n)
i=+1
if x!=-1:
return "{} n'est pas premier".format(n)
breakPs: expon et pgcd sont des fonctions déjà programmées et elle compile très bien et les résultats renvoyés sont juste :
aussi j'ai simplifié les phrases au niveau des return car je ceux juste voir si mes résultats sont bon dans un premier temps
sauf que avec ce programme j'ai apparemment ça parcours le programme en prenant en compte juste la dernière condition (le dernier if ) du coup je sais plus quoi faire , comme tu peux le constater je me suis un peu passé des else , après tout en mettant les else ça me renvoie les même résultats , c'est un peu bizarre en vrai je comprend pas ...
carpediem oui si tu regardes dans l'algorithme proposé , on a 1<c1<n , du coup je dois commencer à 2 et m'arrêter à n-1 , non ?
Bonjour, nullptr.
Ce deuxième programme est vraiment catastrophique:
- l'objection de carpediem, qui a raison
- def testMiller(n,k) ... k n'apparait jamais dans la suite
- for i in range(2,n): ... évidemment, c'est for j in range(k):
Et beaucoup de défauts du premier programme n'ont pas été corrigés:
- chaque fois que "-1" apparaît, il faut le remplacer par "n-1" (problème qui avait déjà été constaté dans un programme précédent)
- les "return" sont très mal conçus: relis la fonction pgcd, les return ne s'écrivent pas avec des "le plus grand diviseur de a et b est égal à ....". Même chose pour la fonction expon . Si tu tiens absolument à mettre des messages, il faut utiliser la fonction "print".
- ce n'est pas parce que expon(c1,s,n) est égal à 1 que la procédure doit s'arrêter, il faut tester tous les c1
- i =+ 1 !!!! c'est pourtant facile à corriger !!!
- toute cette partie autour des est à réécrire complètement
Un seul point positif:
la détermination de r et s est correcte
Un conseil, que verdurin t'avait déjà donné (ou du moins fortement suggéré):
écrire une fonction testMiller(n,c1,r,s) qui détermine si n est pseudopremier de base c1 (avec un "return False" ou "return True" et pas de return "phrase en français").
mais return la phrase en français c'est ce qui nous a été demandé en TP , j'avoue que écrire avec des booléens simplifie les choses , mais en TP il est demandé de renvoyer ces phrases ....
je prend en compte vos remarques et je vais essayer d'améliorer le programme.
Bonsoir nullptr19,
si on te demande de retourner des phrases tu peux écrire une fonction qui retourne True ou False suivant que n est composé ou que n est pseudo-premier pour toutes les valeurs essayées.
Ensuite tu utilises cette fonction pour retourner les phrases voulues
Je n'avais pas lu ta seconde proposition. 
Elle est pire qu'absurde : tu fais n-1 tests pour savoir si n est premier !
L'algorithme trivial : essayer tous les entiers inférieurs à et regarder si l'un d'eux divise n est plus efficace !
Une autre remarque :
utiliser
x=expon(c1,2**i*s,n) Il suffit de calculer le carré de la précédente valeur de x modulo n.
Du genre
x=(x*x)%nBonjour je viens de voir vos remarque , tout en m'excusant du retard je bosse un peu de tout actuellement , ce pendant je m'y met actuellement et je reviens vers vous dans la journée , merci bien car ce programme est vraiment la base pour la continuité du cours du second semestre .
j'ai en effet fait un peu n'importe quoi ..
je reviens .
Bonjour à tous , j'ai consacré presque une nuit entière pour essayer d'adapter vos remarques à mon mon programme et j'ai testé , ça marche très bien , j'ai mis quelques commentaire , si vous avez besoin que je clarifie un passage , je le ferai , j'ai juste pas mis l'intégralité de mes commentaire pour plus de lisibilité ,
voici ce que je propose :
from random import *
def testMiller(n,k):
if n == 2 or n ==3 :
return True
if n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for j in range(k): # ici il sera question de définir un compteur , c'est à dire le nombre de fois que mon test sera effectué
# cette boucle va contenir l'essentiel de mon programme
c1 = randrange(2, n - 1) # on choisi de manière aléatoire un nombre 1<c1<n
a = expon(c1, s, n) # on calcul par l'exponentiation rapide le reste modulo n de c^s_1
if pgcd(c1,n)>1:
return True
if a == 1 or a == n - 1: # le n-1 c'est suite à la remarque de perroquet , je comprend bien que a=-1 mod n peut
continue # également s'écrire a=kn-1 , en particulier pour k=1
for i in range(r - 1):
a = expon(a, 2, n) # verdurin j'ai pris en compte ta remarque du coup
if a == n - 1:
break
else:
return False
return True verdurin comment puis je trouver dans ce cas la base dans le cas ou n est pseudo premier fort ? j'ai travaillé avec les booléens comme vous m'avez proposez
Bonsoir,
as tu vraiment besoin de trouver les valeurs de c1 pour les quelles n est pseudo-premier fort ?
Si oui je ne sais pas comment faire pour les trouver toutes de façon efficace et le test de Miller-Rabin n'est pas vraiment fait pour ça.
Sinon, à propos de ta fonction, le test
if pgcd(c1,n)>1: Comme on te demande de faire une fonction qui retourne des phrases, je déplacerais le début de ce que tu as écris dans cette fonction qui peut être quelque chose comme
def utiliseMiller(n,k) :
""" explications """
#on peut rajouter des contrôles sur les valeurs de n et k
if n == 2 or n ==3 :
return "{} est premier".format(n)
if n % 2 == 0:
return "{} n'est pas premier".format(n)
#fin des contrôles
if testMiller(n,k):
return "{} est peut-être premier".format(n)
else :
return "{} n'est pas premier".format(n)
verdurin oui en fait en TP , le prof nous a donné certain exemple de nombres pseudo premier fort , exemple :
L'entier 4147168775 est pseudo-premier fort de base 7