Forum de mathématiques - Bibm@th.net

def t1_t2(a,b):
    try:
        while b!=0:
            a=a%b
            t1.append(a)
            t2.append(b/a)
            b=b%a
            t1.append(b)
            t2.append(a/b)
        return t2
    except:
        return t2
   
print"                                                               *Recherche (a,b) <=> au+bv=gcd(a,b)*"            
a=input('Entrez a:')
b=input('Entrez b:')
t1,t2=[a,b],[a/b]
t2=t1_t2(a,b)
l,xk,yk=1,[1,0,1],[0,1,t2[0]]

while l!=len(t1)-2:
    l=l+1
    xk.append(t2[l-1]*xk[len(xk)-1]+xk[len(xk)-2])
    yk.append(t2[l-1]*yk[len(yk)-1]+yk[len(yk)-2])
   
print"*Solution particuliere:*"
print ""
print a,'*',((-1)**(len(t1)-2))*xk[len(xk)-2],'+',b,'*',((-1)**(len(t1)-1))*yk[len(yk)-2],'=',pgcd(a,b)
print""
print"*Solution generale:*"
print ""
print 'u_k','=',((-1)**(len(t1)-2))*xk[len(xk)-2],'+',xk[len(xk)-1],'k'
print 'v_k','=',((-1)**(len(t1)-1))*yk[len(yk)-2],'-',yk[len(yk)-1],'k'

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)