Inscription / Connexion Nouveau Sujet

1 2 +


Posté par
nullptr19
re : python 18-12-20 à 19:52

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

Posté par
carpediem
re : python 18-12-20 à 20:23

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

Posté par
nullptr19
re : python 18-12-20 à 20:26

par-contre moi je comprend pas ce vous demandez de faire

Posté par
nullptr19
re : python 18-12-20 à 21:40

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

Posté par
nullptr19
re : python 18-12-20 à 22:00

verdurin @ 18-12-2020 à 19:26

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 à 1010 il est certainement beaucoup plus rapide de tester la divisibilité par les valeurs inférieures à  \sqrt{n}.

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



ça marche parfaitement

Posté par
verdurin
re : python 18-12-20 à 22:01

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 n est premier.
Une caractéristique de ce test est que si la réponse est faux l'entier n n'est pas premier, mais que si la réponse est vrai on n'est pas certain que l'entier n 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.

Posté par
nullptr19
re : python 18-12-20 à 22:21

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

Posté par
verdurin
re : python 18-12-20 à 22:45

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.

Posté par
nullptr19
re : python 18-12-20 à 23:11


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)


c'est ce code que j'ai utilisé

Posté par
nullptr19
re : python 18-12-20 à 23:13

comment tu fais pour voir le nombre d'essais ?

Posté par
nullptr19
re : python 18-12-20 à 23:29

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

Posté par
perroquet
re : python 18-12-20 à 23:56

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)


Commentaires:

1) On ne réalise pas n "tests de jacobi", le but est d'obtenir une procédure rapide.
2) De mémoire, lorsque n n'est pas premier, au moins la moitié des entiers b ne passent pas le "test de jacobi" . Si p "tests de jacobi" sont passés avec succès, on a une chance sur 2^p au maximum de déclarer un entier n premier  alors qu'en fait il ne l'est pas. J'ai choisi de prendre p=100, vous pouvez le prendre plus grand si vous voulez mais cela augmentera d'autant le temps de la procédure.
3) Il est inutile de tester si n et p sont premiers entre eux, le "test de jacobi" établira que n n'est pas premier dans ce cas.
3) J'ai testé la procédure pour n=5, puis pour n=2^{607}-1 (premier de Mersenne), puis pour n=2^{601}-1  (il n'est pas premier). Dans les trois cas, le résultat est instantané et juste.
4) Plutôt que de mettre un message convivial, je suggère d'utiliser True et False. Le but de la procédure est de trouver de grands entiers premiers rapidement et il faut tester beaucoup de valeurs de n avant d'en trouver un qui convienne.
5) Je n'ai pas enlevé la vérification du fait que n n'est pas multiple de 2, mais il faudrait l'enlever. On ne teste évidemment pas si un entier pair est premier, on le sait.

Posté par
nullptr19
re : python 19-12-20 à 00:12

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

Posté par
nullptr19
re : python 19-12-20 à 00:36

perroquet  on pouvait du coup prendre deux paramètres pour la fonction

def test (a,k=..) k étant juste le nombre de tours souhaités. et on pouvais prendre un
i in range (2,k-1) .
Mais bon , le plus important est d'avoir compris le sens et je sais comment le réutiliser ailleurs.

1 2 +




Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !