j'avais oublié un détail voici l'énoncé légèrement modifié.


Soit n un entier impaire
.choisir un nombre b avec 1<b<n
. calculer (b,n)
       .si (b,n)>1 , alors n n'est pas premier et le test est terminé
        .sinon , calculer
( (b/n) : symbole de Jacobi)
                 * si ces deux élément ne sont pas égaux alors n n'est pas premier et le test s'arrête.
                   * sinon recommencer le test pour un autre b ,puis un autre entier b1...

voici ce que je propose mais j'ai pas fat la dernière question qui consiste à vérifier pour un autre b

salut

le pb avec l'instruction b = randint (2, n - 1) c'est que tu eux retomber sur le "même  b" que précédemment ...

je travaillerai plutôt avec la structure set (ensemble) ou liste dans laquelle je mettrai les entiers de 2 à n - 1 puis à chaque fois que j'en choisis un je l'enlève ... pour ne plus le choisir ...

ensuite je ne comprends pas ton script ....

def test(n):
     b=randint(2,n-1)
     pgcd(b,n)                 à quoi sert cette instruction : tu fais appel à une fonction ... pour rien en faire !!!
     i=0
     while (n%2)==0:     ici aussi je ne comprends rien de ce que tu fais : pourquoi diviser n par 2
         n//=2
         i+=1                  que fais-tu avec ce i ensuite ?
     if pgcd(b,n)>1 :                                ces deux lignes devraient
         return "{} n'est pas premier ".format(n)    être au tout début

     else :
         a=expon(b,(n-1)/2,n)
         b=jacobi(b,n)
         
         if a!=b:

             return "{} n'est pas premier".format(n)

en fait je traiterai simplement tous les entiers de 2 à n - 1 dans une boucle ...

while (n%2)==0:
         n//=2
         i+=1

ok j'essaie de ton idée

je ne comprends pas !!!

tu veux tester si un entier impair est premier

donc tu rentre un entier n et il suffit de tester au si cet entier est pair ou impair tout simplement

j'écrirai simplement :

n = 0
while n%2 == 0 :
    n = int(input( "entrer un entier impair"))
...

et la structure set peut être effectivement intéressante pour choisir au hasard ...

ah oui , ok je reviens vers toi

Bonjour à tous les deux.

@carpediem:
Je pense que l'algorithme qui est demandé à nullptr est un algorithme probabiliste de détection d'un nombre premier.

Lorsqu'il répond que le nombre n n'est pas premier, alors, n n'est pas premier, c'est certain. Par contre, lorsqu'il répond que n est premier, alors, il y a une probabilité non nulle que ce nombre ne soit pas premier (cette probabilité pouvant être très faible).

Cet algorithme est habituellement employé pour de très grands nombres (au moins plusieurs dizaines de chiffres dans l'écriture décimale). Il est donc impossible en python  de créer des ensembles dont le cardinal soit égal à n-2. Donc, l'instruction randint doit faire l'affaire . Il peut arriver que l'entier ait déjà été testé mais cela n'arrivera que rarement.

merci perroquet , je m'en doutais en cours le prof m'avait dit que randint fait l'affaire ce pendant , le programme que j'ai proposé , qu'est ce que j'ai mal fait du coup histoire de rectifier et ranger un peu tout ça

perroquet : ha d'accord ...et merci

effectivement j'avais compris qu'on était certain d'une affirmation mais pas certain de sa négation

alors peut-être pour éviter la répétition du même choix de b ajouter les valeurs choisies dans une liste et comparer le "nouveau b" avec ceux de la liste ...

mais effectivement la probabilité de retomber sur le même b ... est de l'ordre de 1/n donc très faible pour de "très grand" nombre !!

carpediem pour à chaque fois renvoyer sous forme de liste le résultat issue de randint , comment devrais je m'y prendre ? j'ai essaye avec une boucle for et effectuer des petit calcul à l'intérieur mais ça me renvoi que le premier nombre choisi c'est assez ennuyeux

random.random()  fait l'affaire je crois

L = []
b = randint (2, n - 1)
while b in L :
   b = randint (2, n - 1)
L.append (b)
... suite du traitement

def ref (n):
    L = []
    b = randint (2, n - 1)
    while b  in  L :
        b=randint (2, n - 1)
        L.append (b)
    return L
print (ref(20))

oupss c'est bon j'ai pu trouver une autre solution , je la met en pratique et je reviens vers vous

voici ce que je propose , mais le seul probleme est que ca ne me renvoit rien j'ai l'impression que la boucle tourne infiniment sans pour autant trouver un candisat

import random
def test(n):
    i=0
    liste=[]
    while (n%2)==0:
        n//=2
        i+=1
    for a in range (n):
            x=random.randint(2,n)
            liste.append(x)
    for b1 in liste:
        pgcd(b1,n)
        if pgcd(b1,n)>1 :
            return "{} n'est pas premier ".format(n)

        else :
         expon(b1,(n-1)//2,n)
         jacobi(b1,n)
         
         a=expon(b1,(n-1)//2,n)
         b=jacobi(b1,n)
         if a!=b:
             return "{} n'est pas premier".format(n)

        return "premier"

à quoi sert le test : while n%2 == 0 ?

si n est pair on est certain que n n'est pas premier et on s'arrête immédiatement ...

et je ne comprends pas non plus à quoi sert la variable i ...

import random
def test(n):
    i=0
    liste=[]
    while (n%2)==0:
        n//=2
        i+=1
    for a in range (n):
            x=random.randint(2,n)
            liste.append(x)
    for b1 in liste:
        pgcd(b1,n)
        if pgcd(b1,n)>1 :
            return "{} n'est pas premier ".format(n)

        else :
         expon(b1,(n-1)//2,n)
         jacobi(b1,n)
         
         a=expon(b1,(n-1)//2,n)
         b=jacobi(b1,n)
         if a!=b:
             return "{} n'est pas premier".format(n)

        return "premier"

OK mais en procédant au modification je ne trouve pas des résultats vrais

import random
def test(n):
    liste=[]
    for a in range (n):
        x=random.randint(2,n)
        liste.append(x)
    
    for b1 in liste:
        if pgcd(b1,n)>1 :
            return "{} n'est pas premier ".format(n)

        else :
         a=expon(b1,(n-1)//2,n)
         b=jacobi(b1,n)
         if a!=b:
             return "{} n'est pas premier".format(n)

    return "premier"

j'éliminerai dès le début le cas n pair et j'écrirai simplement :

import random
def test(n) :
  if n%2 == 0 :
     return "{} n'est pas premier ".format(n)
  liste = []
  for k in range (2, n - 1)
    b = random.randint (2, n - 1)
    while b in liste :
       b = random.randint (2, n - 1)
    liste.append(b)
    if pgcd(b1, n) > 1 :
      return "{} n'est pas premier ".format(n)
    else :
       if expon(b,(n - 1)//2, n) != jacobi(b1, n) :
           return "{} n'est pas premier".format(n)

  return "premier"

Je comprend ce vous me proposez et je suis d'accord du moins de ne relevé aucune ambiguïté , sauf que ça compile pas toujours correctement

J'ai du faire quelque rajustement : et avec ceci ça marche bien :

import random
def test(n) :
  if n%2 == 0 :
     return "{} n'est pas premier ".format(n)
  liste = []
  for k in range (2, n - 1):
    b = random.randint (2, n - 1)
    while b in liste :
       b = random.randint (2, n - 1)
       liste.append(b)
  for b1 in liste :
    if pgcd(b1, n) > 1 :
      return "{} n'est pas premier ".format(n)
    else :
       a=expon(b1,(n - 1)//2, n) 
       c=jacobi(b1, n)
       if a!= c :
           return "{} n'est pas premier".format(n)
  return "premier"

il ne vérifie pas pour tout le monde

oui il y avait une erreur d'indentation ...

en fait il y a encore une "erreur" : ce devrait être : for k in range (2, n)

puisque n n'est pas pris en compte ... enfin à voir ...

je ne comprends pas ton dernier msg ni la boucle avec b1

ton nouveau b tu l'as !!! tu choisis b au hasard tant qu'il n'est pas déjà dans la liste (pour éviter une répétition inutile) et tu fais ton traitement avec ce nouveau b ...

mais en même temps tu fais éventuellement des tours et des tours dans cette boucle pour avoir un b que tu n'as pas déjà

on peut donc faire mieux et plus efficace si tu veux une liste complète dès le départ il y a beaucoup plus simple : il y a une fonction python qui mélange aléatoirement une liste

import random
def test(n) :
  if n%2 == 0 :
     return "{} n'est pas premier ".format(n)
  liste = [i for i in range (2, n)]
  random.schuffle(liste)
  for b in liste :
    if pgcd(b1, n) > 1 :
      return "{} n'est pas premier ".format(n)
    else :
       if expon(b,(n - 1)//2, n) != jacobi(b1, n) :
           return "{} n'est pas premier".format(n)

  return "premier"

on peut même encore simplifier :

import random
def test(n) :
  if n%2 == 0 :
     return "{} n'est pas premier ".format(n)
  liste = [i for i in range (2, n)]
  random.schuffle(liste)
  for b in liste :
    if pgcd(b, n) > 1 or  expon(b,(n - 1)//2, n) != jacobi(b1, n) :
           return "{} n'est pas premier".format(n)

  return "premier"

même ceci j'essaie mais ça renvois des erreurs

quand j'essaie avec 5 , tanto ça me renvois premier tanto pas premier

dans jacobi j'ai oublié de remplacé b1 par b :

import random
def test(n) :
  if n%2 == 0 :
     return "{} n'est pas premier ".format(n)
  liste = [i for i in range (2, n)]
  random.schuffle(liste)
*
  for b in liste :
    if pgcd(b, n) > 1 or  expon(b,(n - 1)//2, n) != jacobi(b, n) :
           return "{} n'est pas premier".format(n)

  return "premier"

excuser moi je vous embête un peu trop mais étant donné que dans mes différents test il peut arriver par exemple que quand je test 5 ça m'affiche non premier et au bout de quelques tour j'obtiens le résultat , n'est ce pas même ça le sens de test de primalité  probabiliste ? et que des que j'ai un résultat vrai "premier" je conclut que le nombre est premier ?

ça n'est pas normal puisqu'on test tous les entiers entre 2 et n - 1

et le test pgcd(b, 5) > 1 est toujours faux  ... reste à voir ce que donne jacobi en théorie ...

Moi non plus je ne comprend pas , j'ai l'impression que le test se fait à chaque fois que je compile

et cela varie y'a certains b qui vérifie , d'autre pas du coup un temps pour 5 ça affiche premier et  quand je compile à nouveau le résultat change .

il serait bien d'avoir tes fonctions jacobi et expon ...

sûrement du à la présence des faux témoins d'Euler ? J e sais pas mais les résultats me semble logiques à cause du mot probabiliste , pour un nombre premier il ya une certaine probabilité que à un certain tour  il soit premier , vous me direz si je raconte un peu n'importe quoi , mais j'essaie juste de traduire la manière selon laquelle mon cerveau traduit tout ça

def jacobi(a, n):
    if n <= 0:   
        return False
    if n % 2 == 0:
        return False  
    a %= n  
    ValeurJacobi = 1
     
    
    while a != 0 and pgcd(a,n)!=0:  
        while a % 2 == 0:     
                             
            a //= 2        
            r= n % 8 
            if r in (3,5):  
                ValeurJacobi = -ValeurJacobi
            if r in (1,7):          
                ValeurJacobi        
        a, n = n, a  
        if (a % 4) == 3 and (n % 4) == 3:   
                                        
            ValeurJacobi = -ValeurJacobi
        a %= n
    if n == 1:                       
        return ValeurJacobi
    else:
        return 0     

def expon (a,k,n): 
    compteur=1
    while(k>0):                     
        if k%2!=0:           
            compteur=(compteur*a)%n 
        a=(a*a)%n
        k=k//2                          
    return compteur 

rien à dire sur la fonction expon qui traduit l'exponentiation "rapide" : on élève au carré tant qu'on peut

j'utiliserai plutôt la notation p (pour puissance) que compteur qui n'en est pas un ...

pour la fonction jacobi la première partie se résume simplement en

def jacobi(a, n):
    if n <= 0 or n%2 == 0 :   
        return False
    a %= n  
    ValeurJacobi = 1

En ce qui est de Jacobi , je n'ai fait qu'utiliser les propriétés :

pour a un nombre entier et  n entier  naturel positif impaire ,
(a/n)= 1 si n ≡ 1 ou 7 (mod 8), et -1 si n ≡ 3 ou 5 (mod 8)

Du coup je comprend pas trop bien ce que vous me suggérez de faire :

voici du coup quelques modifs  apportées mais toujours rien de bien concret

from random import shuffle 
import random
def test(n) :
  if n%2 == 0 : 
      return "{} nest pas premier le test est inutil d'etre refait".format(n)
  liste = [i for i in range (2, n)] 
  random.shuffle(liste) 
  for b1 in liste : 
      if pgcd(b1, n) > 1:
          return "{} n'est pas premier , le test est terminé".format(n)
      else :
          expon(b1,(n-1)/2,n)
          jacobi(b1,n)
          if expon(b1,(n-1)/2,n)!=jacobi(b1,n):
              return "{} nest pas premier , le test est terminé".format(n)
      
      return "premier " 

En cherchant un peu, on trouve un algorithme de calcul du symbole de Jacobi sur le net.
Par exemple ici

merci verdulin , en gros c'était mon programme sur Jacobi qui causait soucis dans le test primalité probabiliste ?

Je ne sais pas si c'était le seul soucis, mais il est certain que s'en était un.

verdurin ,carpediem Bonjour à vous .

voici pour le symbole de Jacobi

def jacobi(a,n):
    ValeurJacobi=1
    while a!=0:
        while (a%2)==0:
            a//=2
            if (n%8==3 or n%8==5):
                ValeurJacobi=-ValeurJacobi
        a,n=n,a  
        if (a%4==3 and n%4==3):
            ValeurJacobi=-ValeurJacobi
        a=a%n
    if n==1:
        return ValeurJacobi
    else:
        return 0

Bonsoir,
je crois voir où est le problème :
jacobi(2,5) retourne -1 et expon(2,(5-1)/2,5) retourne 4.
Ces deux valeurs sont évidement égales modulo 5 mais ne sont pas égales pour le programme.

Pour donner un avis plus général l'usage de random.shuffle me semble complètement inutile.
Un test aléatoire n'a d'intérêt que pour les grandes valeurs de n.
Si n est « petit » disons inférieur à 10¹⁰ il est certainement beaucoup plus rapide de tester la divisibilité par les valeurs inférieures à .

Et faire le test jacobi(b,n)%n==expon(b,(n-1)//2,n) est beaucoup trop long.