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!

[blaidddrwg]

Si, si le nombre est premier!

Quel test as-tu fait ?
Car testé à part, miller-rabin dit que non, et en testant avec ntheory de sympy, la réponse est la même.
J'ai tenté aks (avec les factorielles), mais overflow :p

[tyrtamos]

Quel test as-tu fait ?
Car testé à part, miller-rabin dit que non, et en testant avec ntheory de sympy, la réponse est la même.
J'ai tenté aks (avec les factorielles), mais overflow :p

Voilà un petit test.

Je fabrique un nombre premier de 5.000 chiffres, et un nombre non premier de même taille.

C'est facile à faire (nbc = nombre de chiffres du nombre cherché):

Code :

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

1
2
3
4
5
6
7
8
import gmpy2
import random
 
def genpremier(nbc):
    while True:
        x = random.randint(10**(nbc-1), 10**nbc-1)
        if gmpy2.is_prime(gmpy2.mpz(x)):
            return x

Par exemple:

Code :

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

1
2
prem = 15143558183462527818336663761683957016514454401747860063118643597799286193110153123715803117293240930500078733760495625257567705671485867093535468914544049141322278298196978830084968863043188566875713725811381458746941340140857102858815919292272363314713549086157811257378794736586347442316514173490808508233982844644662109119444377085052511905963232324763352582091214733371496982647622999810603785856885678317029403715197578884930886822854738417790987177117658803059173565047725741411373661051960859260947626968843795729014087307772144240938049733393511370084403505931579044424748656137333449885690531670660091919738224498623410943936288283544859634539308766615541474453413778102562461716036924126615641539185332114859260305044399473873426007847526752580026564042507908254607088398076597955605944410231731090204703934790122389152543168368544196501392050540917565970011062032199627963653307918386613434203180119555516345983603222629872037098027227665212374837381269071824311938383812609281275851874252206640167881293814596949023248532930543533038771065242474266724394013928805461474550921062565985453112789024702399254040695634678082070161933735103411805922492425764322289182964432022616866578091446262555421898389561412299478966537754891993245598071629963005319780433864422641621505589923113762491500502556752419123394490723761157359195333555283351282470388796366109312613041603798906842712156402261823362301468087681577443303615822480841153649952301591483814268695606498770172291477353001257140921286042923095225177834366756286752932371872368169676002274999981151929399658411128494437977357533798677901866632745076660712027111405398738980877065999420729625356553297252971481806328020734768279065824203646459368025939695617777923376139617438814471466229259126369161319841529832686685170668667347784815955421849108600104430485843934446668353727860913561445379669954070624306131321814851280011766327470364888290964059220019330029545682632425559495792326477649482109414567120963265549165561460639067669261358878350239212864439247970728967951897076633710873823592352803088794256595390202651487628724252969310027044613101397114488085281638756750367490601788100902532347022595520188918894945745627895427762136898985999212367722035461916877651135117551824616574826360471393057781260747618186643379465143111352558466769062866380124649226243004233262120948479436765769427121311474162190838019753013312568575674515174555102834635755653615310669851759266614061597522696603840940919418666142178124805963576067982565518255205362112589542823923786215821956561807529042172608607153494251141814434795689387276808638073760983282248529375630219020599658416777699568651586128542242201727193088145290965096035265875178427599294159190126260738656264630309178014907855798736314773733397599049022698109493189378313293677811659958187432799574362269268061505132241802332091549178631750860231022343254173494875706601951067961785188940859467389169098712288264799838423421992533493989155629396709647916061343274690184494785261262682675162218566717918557847751324174998492194754745047160210531171547752536144719193300203171737470846520412866807370755206729987976261574440498390814082995507273981615514253354213943834919905870806737032662864245081233456940154577653140805058800547821403674579568154539593915522085655756769828099166287693368703847928947299640464469938631809772917933680618716337650058165384375459663099930503131241091503378548366671223527413834445189336773568280960370103531007836869311658317619115618799000991455112691677528807799174156816627023970480099281315442886261764940413972773607607400845225132599133184578336846714021705403662493059130874387917703862842490183374531577843590931472292481095331251112083720604317477591098309171733073600498227148958517230788269786915517125449844535438802683411396335935696668698499613251502220526381515517935421033600710666671965949287438617126110771608731131602963447278559857391878419634498082318258637213914960974061632392070510604622215262877162198863134501591709909698251245047591734256638526883158010005486616992352741096803291857976604961016812267839297335275891803545473052675886179827232973770078703920673157508858064047479259338887125065111122752610228087512455765823754941845281830560972594614099444432219062513001382968961252414778765838011872604293759970171799543580512835581791304667935362953131079223395661281775516066893367259865519410113680359661691920817164122055991009634015303303230236894396339152897200808892498601611646916077037679661744070976589746831484107448969625577535219536949115375430261610890656495513181474853145352512872975614728172845865440766536211941882276352259140911025579837888042147541474401891596669792067027060277469186648959690031541773287793937172794347922118058635528208936727945371608239128960832022664281593018070996763879934947962456871609699726211528781501460107562138449746117771839074133663460837186352685474116820939726521349821351441480344219133803780003653854215308050442989569154744348676613674917789202445511803702409
nonprem = 12620331215339541328201049932288339296047451289881669701311924098624555040468025447915462481831262648630724086246465509562710164324758929293356714604145183041895915479102964741257371163518058035023121820373181499330964463228934493318530338283612572261378355428820424448619444766708274205817259543863104926673216080043322060990545683122860640918471307904566574874241853569712995081552967099196965440078381525673414791036699302902616172286371614429673484685216537168753307697148210022026303865496346172609621152548061530121386017303074801172573159732744444931743927429710477027094967784351247517723562443886616077467112064997197898592715876345207360528330443057331135587176117601773624296310721055036647852550168689907321586431797489714450759388907215611469894336463616917443890579935757579522141786443489277370261106571993191662422596905766726183759037101688003340680278112936965233288224059043422522262641111275771709503776898550466412759533505278396410758678296428295164843950733954936563799855239728564158981156510873310362687978255729213439954958857007057236822025510942723885484364815907392599064093266585607357648040176460384957172175824246583057913500832060232275675555811614949547283939505964685929918184502978446482541791710919939550783578973689274890940588252368750245501378928361284418389575973005526595622468662535198278833641786044992178406267196846646290048542249931881356126073846572103106738725441001647782443551598692252665401787049092884857794526642722604568142618917978195187728672099575313489944183233625584649140601546474314423615542109305108170773484450029859976498642151706010489692991295689144948747360464002293325563238197856254685749714714607521950930267276331720156172960628479006561979176920809611782477091775892469211882255733443980650402838786882447022779994024193666364112193101162411542621824688802787718439457637407819442297990163293274433137651915950638873052395405142253616711350722609673668941858760329749224912675580434029701598026215883607479272252457707734939667317114260075114617602698094793347146728142830349512821481790811142536238380439833771085625002784270713969079791883497195306744048864852590109146903011880764979462303997522310015301193634977393590282692129654360892122270818243689301671267723076763159444209501474784964182105932005025136444267610378101855804362392978283543651446140328384747719475253789266476955461434720624496439380704177138942870585220942922529466835018069439581566301055941148008676769398243054077435657800296591896511526511087049824652552578611861876153509215158059860718644975132377086440433595492591165741884687746275465924344533682878051610774597366388751313554860541157479064438469856098945279747853700366300116109615899322193414334146936713965458105444628478247424856196352793946947487801360711536870544295078398242526139341600284245259589791566626609237597635247448271818166015706788501220502205002947117848155407965918486617611260080235905375929709862462315332882231906958358283650687843160682705174791730449347949233735417699311178615719950473593905938578260883961848645893810843949198342258805267431886451208051811772415637850131768134827184031975390115583846439421032206731092976322678794743810954271164837091149314022758135522811758070222242871115699071012575707484794744330065013161484964669313516484260837261719174900386929384943103018249851074941761320564660863321015966063409855581124740358754769965536541276223089711648969389421392516214218060254357421519701072021875250666008756967131394219537909383223576888241026665440622179770785109383846809704929822724409719105155104676040088625619979029487593720636905804961400507530957340473729867866724824560215626356753974749836959789892041030533066111410773724379738084744733315419024638534766156530868509890769691194041716736231011213402438127867636246774421084991108869712471369659847537264657519670571433478305661162171577843441329106720914388799967651087481867527713756302840831616062546885842624351043087672428737844194336946704441644863640783084452321899496533140506783177651667817974543793941753240680016408477248563303939226610949458475983989064126424975386694061338069445948917003227958677123992502759023430021593235856364390583440104084459575584793829390500526935453595375727906290209348358301531768677325199656843595722489219776245593701858521399502874278268050188268163011896932763376374921544575002507242227001170492592118232486827694324695012652506987382952250042198905302591558474227810574911525866062676575962943805568607479122540065477772208823739908709294082857235418831322242295624827038594725610448712548884550473072913442244131585708493412149783638324014613051265739010640617608173037539013679155327539860993716400512023356078292420062732453378191523150305540038680406275694487176041052532972692516372082925953553920356005073291745682722151598762505772191495884802863082565662953700201341144717920738598210020174370207321083997711984749879296417181296999116497992628944645608838763181592518577046768910646140610578022156963414527526868908235096324544

Je teste ensuite le temps passé pour chacun de ces nombres avec miller-rabin:

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
import gmpy2
import time
 
t1 = time.perf_counter()
okprem = gmpy2.is_prime(nonprem) 
t1 = time.perf_counter() - t1  
print(okprem)
print(t1)
print()
 
t2 = time.perf_counter()
okprem = gmpy2.is_prime(prem) 
t2 = time.perf_counter() - t2  
print(okprem)
print(t2)
print()
print(t2/t1)

Résultat:

Code :

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

1
2
3
4
5
6
7
False
9.599999999998499e-06
 
True
2.0741283
 
216055.0312500338

On voit que sur un nombre déjà grand (5.000 chiffres), le test de Miller-rabin met 216.055 fois plus longtemps pour le nombre premier que pour le nombre qui ne l'est pas.

Comme je le disais, les tests de primalité sont en général plus longs pour les nb premiers.

Imagine un peu sur des nombres de plusieurs millions de chiffres!

[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.