Forum de mathématiques - Bibm@th.net

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

[Python] test de primarité probabiliste

Rebonjour,

Le prog de mon post d'avant comprenait une erreur ; celui-ci marche maintenant très bien. C'est le test de Miller Rabin où k est le nombre de fois où l'on veut répéter l'algorithme pour une probabilité d'erreur < (1/4)^k (voir tableau).
A titre indicatif, il met 2 minutes pour un nombre de 2048 bits et pour k=6 (c'est la borne fréquemment utilisée en cryptographie) puis 1 minute pour k=3..etc

from math import log  

def DivPuiss(n,v,t1=[]):
    while v%2==0:
        v=v/2
        t1.append(v)
    return len(t1)

def pgcd(a,n):
    try:
        while n!=0:
            a=a%n
            n=n%a
        return a
    except:
        return n
a=1

def tdeux(d,f=0,t2=[]):
    while d!=f:
        d=d-f
        c=int(log(d)/log(2))
        f=2**c
        t2.append(c)
    return t2

def fabrkttroiquatr(a,t3=[a],t4=[],p=-1,u=0,j=a,z=a):
    while u!=t2[0]:
        z=j**2%n
        j=z
        u+=1
        t3.append(z)
    while p<len(t2)-1:
        p+=1
        t4.append(t3[t2[p]])
    return reduce(lambda x, y: x *y,t4)%n

t5=[]
n=input('Entrez un nombre>3 impair:')

print '                                       ************************'
print '                                       *|  k  |  Probabilité |*'
print '                                       *|--------------------|*'                            
print '                                       *|  1  |     4^-1     |*'                                
print '                                       *|--------------------|*'                                        
print '                                       *|  2  |     4^-2     |*'                                  
print '                                       *|--------------------|*'
print '                                       *|  3  |     4^-3     |*'
print '                                       *|--------------------|*'
print '                                       *|  4  |     4^-4     |*'
print '                                       *|--------------------|*'
print '                                       *|  5  |     4^-5     |*'
print '                                       *|--------------------|*'
print '                                       *|  6  |     4^-6     |*'
print '                                       ************************'

k=input('Entrez la borne k<n:')
v=n-1
s=DivPuiss(n,v,t1=[])
d=(n-1)/(2**s)
t2=tdeux(d,f=0,t2=[])
for i in range(1,k):
    a=a+1
    if pgcd(a,n)!=1:
        t5.append(0)
        break
    elif pgcd(a,n)==1:
        e,l=fabrkttroiquatr(a,t3=[a],t4=[],p=-1,u=0,j=a,z=a),0
        if s==1 and e==n-1:
            t5.append(1)
        elif e==1:
            t5.append(1)
        else:
            while e!=n-1:
                f=e
                e=f**2%n
                l=l+1
                if e==n-1:
                    t5.append(1)
                    break
                if l==s:
                    t5.append(0)
                    break

def verif(t5,w=-1):
    while w!=len(t5)-1:
        w=w+1
        if t5[w]==0:
            return 'Ce nombre est composé !'
            break
        elif w==len(t5)-1:
            return 'Ce nombre est premier !'

print verif(t5,w=-1)

Dernière modification par Golgup (13-07-2009 13:39:51)

---

« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »