Discussion :

[blaidddrwg]

Salut tout le monde,

J'ai fait un petit programme en python, qui utilise gmpy2 (donc derrière, ce sont des bibliothèques en c++).
Je ne comprend pas, les 7 premiers tests de primalités (miller-rabin) sont faits en un claquement de doigts et au 8ème, on dirait qu'il tourne dans le vide !
Est-ce que cela le fait aussi chez vous ? Un problème dans mon code ?

Si une âme charitable pouvait m'aiguiller

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
from gmpy2 import mpz
import time
import gmpy2
 
 
mersenne=51
start=time.time()
for i in range(mpz(82589934),mpz(10000000000)):
    print(i)     
    if i % 2 == 0 :
 
        a=gmpy2.sub(pow(pow(mpz(2),mpz(i)//2),2),1)        
 
    else:
 
        a=gmpy2.sub(pow(pow(mpz(2),mpz(i)//2),1)*2,1)
 
    if gmpy2.is_prime(a) :
       mersenne +=1
       with open("{}.txt".format(mersenne),"w") as fichier:
           convertednumber="{}".format(a)
           fichier.write(convertednumber)
           fichier.close
 
end=time.time()
print(end-start)

[tyrtamos]

Bonjour

Pour savoir où ça coince, il suffit de rajouter quelques "print" aux bons endroits.

Ça coince à la ligne "if gmpy2.is_prime(a):" pour le nombre i = 82589941

Pourquoi ça coince? Le nombre "a" calculé à partir de "i" est ENORME: 12.431.025 chiffres. Et manifestement, même s'il est très efficace, le test miller-rabin est dépassé. S'il n'est pas planté, il cherche, et il risque de chercher longtemps...

Les tests de primalité ont des temps de réponse qui dépendent souvent du nombre testé, et en général, le temps le plus long correspond aux nombres premiers. Avec miller-rabin, on peut tester des nombres de plusieurs centaines de chiffres, mais pas un nombre premier de plus de 12 millions de chiffres...

[blaidddrwg]

Bonjour,

Merci pour votre réponse.
En effet, j'ai fini par y penser à ce que vous me dites supra. Cela coince au niveau du test de primalité.
En faisant l'opération manuellement, qui a généré un nombre de 25 millions de chiffre et en testant sa primalité avec la même fonction, la réponse est sortie en un claquement de doigt !!

J'ai pensé que comme était mon code, cela faisait comme un appel impropre, j'ai donc défini une fonction (def test_prtimalite) qui va tester la primalité, même résultat.
Ensuite, je me suis dit que j'allais lui faire recharger la bibliothèque, mais toujours le même constat, il patauge...
J'ai refait un test séparé, avec 37 millions de chiffres, pas de soucis....

Là, je suis perdu

[tyrtamos]

Mais comme j'ai dit, le temps de réponse des tests de primalité augmente quand le nombre est premier. Ce n'est donc pas le seul nombre de chiffres qui compte. D'ailleurs, dans le code, les 7 premiers nombres "i" donnent des "a" qui ne coincent pas le test Miller-rabin, alors qu'ils ont le même nombre de chiffres. Le 8ème nombre "a" doit être premier, mais je ne vois pas comment le prouver...

[blaidddrwg]

En utilisant aks ou lacas lehmer, qui sont des tests déterministes.
Comme j'ai dit, j'ai fait le calcul séparement (dans une autre session python, je suis sur linux), le résultat tombe immédiatement !
J'ai même fait le test sur un nombre dépassant les 370 millions de chiffres sans soucis...

La grandeur des nombres ne serait pas en cause à priori...

[tyrtamos]

La grandeur des nombres ne serait pas en cause à priori...

Si, si le nombre est premier!

[Sve@r]

Bonjour

Code python :

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

1
2
3
4
5
6
if gmpy2.is_prime(a) :
	mersenne +=1
	with open("{}.txt".format(mersenne),"w") as fichier:
		convertednumber="{}".format(a)
		fichier.write(convertednumber)
		fichier.close

Pas besoin de fermer un fichier ouvert avec with, le but de mettre en place un gestionnaire de contexte étant de ne plus avoir à se préoccuper de libérer les ressources puisque c'est le gestionnaire qui s'en charge.
Mais si on y tient quand-même, alors la fermeture s'effectue via l'action de la fonction close ; et demander l'action d'une fonction se fait en lui mettant des parenthèses indiquant qu'on veut qu'elle s'exécute. Parce que là, ça n'a pas plus d'effet que si tu avais écrit...

Code python :

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

1
2
3
4
5
6
if gmpy2.is_prime(a) :
	mersenne +=1
	with open("{}.txt".format(mersenne),"w") as fichier:
		convertednumber="{}".format(a)
		fichier.write(convertednumber)
		"toto"

... c'est à dire placé dans ton code une expression sans ni la récupérer, ni l'utiliser de quelque manière que ce soit.

Ensuite bon si tu écris un nombre dans ton fichier, ou plus généralement quoi que tu écrives, si c'est un fichier destiné à un humain (fichier texte), alors on termine proprement la ligne en lui mettant un '\n' final. Et avec Python3 ce n'est même plus une difficulté car print() le fait automatiquement et peut aussi écrire dans un fichier.

Code python :

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

1
2
3
4
if gmpy2.is_prime(a) :
	mersenne+=1
	with open("{}.txt".format(mersenne), "w") as fp:
		print(a, file=fp)

[Beruco]

Il existe plusieurs algorithmes de test de primalité qui sont plus rapides que le test de Miller-Rabin, bien que leur fiabilité puisse varier en fonction de la taille et de la forme des nombres à tester. Voici quelques exemples d'algorithmes de test de primalité rapides que vous pouvez utiliser :

L'algorithme de Baillie-PSW : cet algorithme utilise une combinaison de tests de Fermat et de Lucas pour vérifier la primalité d'un nombre. Il est généralement considéré comme l'un des algorithmes de test de primalité les plus fiables et les plus rapides pour les nombres de grande taille.

L'algorithme de Miller : cet algorithme utilise une variante du test de Fermat pour vérifier la primalité d'un nombre. Il est généralement plus rapide que le test de Miller-Rabin, mais moins fiable pour les nombres de grande taille.

L'algorithme de Frobenius : cet algorithme utilise une technique de factorisation pour tester la primalité d'un nombre. Il est généralement plus rapide que le test de Miller-Rabin, mais moins fiable pour les nombres de grande taille.

Il est important de noter que tous ces algorithmes de test de primalité sont probabilistiques, c'est-à-dire qu'ils ne garantissent pas la primalité d'un nombre avec une certitude absolue. Toutefois, ils sont souvent utilisés dans la pratique car ils offrent un bon compromis entre vitesse et fiabilité pour de nombreux cas d'utilisation. Si vous avez besoin d'une garantie absolue de primalité pour vos nombres, vous pouvez utiliser des algorithmes de démonstration de primalité qui, bien que plus lents, permettent de démontrer la primalité d'un nombre avec une certitude absolue.