from random import *



testes = []

def testPrimaliteFermat(n,t):
    global testes
    j = 0 
    ret = True
    while j < t and ret :
        print j
        # choix de a 
        a = randint(1,n-1)
        while a in testes:
            a = randint(1,n-1)
        #calcul de a^(n-1) [n]
        #if a**(n-1) % n != 1 :
        if pow(a,n-1,n) != 1 :
            ret = False
        else : 
            j+= 1
            testes +=[a]
    return ret







def testPrimaliteMillerRabin(n,t):
    global testes 
    if n % 2 == 0:
        return False
    
    # ecrire  n-1 comme 2**s * d
    s,d = 0, n-1
    while d % 2 == 0 :
        s +=1
        d /= 2 
    #testes = []
    j = 0 
    ret = True
    while j < t and ret :
        # choix de a 
        a = randint(1,n-1)
        while a in testes:
            a = randint(1,n-1)
        # calcul de a^(d) [n]
        if pow(a, d, n) != 1:
            ret = False
            r=0
            while r < s and not ret:
                if pow(a, 2**r * d, n) ==  n-1:
                    ret= True
                else :
                    r+=1
        j+=1
        #print j
        testes +=[a]

    return ret


n=651693055693681
#n= 39341 
#n=561

#print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500)
#print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30)


def genereUnNombrePremier(nbChiffre):
    estPremier=False
    compteur, r = 0, 0 
    mini = 10**(nbChiffre-2)
    maxi = 10**(nbChiffre-1)-1
    chiffreFinal=[1,3,7,9]
    while (not estPremier):
        r = randint(mini,maxi)*10
        r += chiffreFinal[randint(0,3)]
        #print r
        compteur += 1
        if testPrimaliteMillerRabin(r,50):
            estPremier = True
    return (r,compteur)

nbit,l=0,100
for k in range(l):
    (r,n)= genereUnNombrePremier(100)
    nbit += n
    print r
print float(nbit)/l

"""












    



t = 50
n = 393413 #premier
n=651693055693681
#n = 393417 #premier
n=9623827 #et  343570291. % res=2953*3259     res = 17729*19379
print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,t)
print "probabilite d'etre premier (MILLER-RABIN)", testPrimaliteMillerRabin(n,t)

    
    

"""