From: couchot Date: Thu, 13 Nov 2014 08:12:26 +0000 (+0100) Subject: ajout -a X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/modelisationMathS3.git/commitdiff_plain/f14f155ac3fd4de01b79c669af7f037baba449e3?ds=sidebyside;hp=f182c99c4479f3f0875b1d7b162248b7a00fc7b5 ajout -a --- diff --git a/mathematiquesettechnologie.pdf b/mathematiquesettechnologie.pdf new file mode 100644 index 0000000..58c10cf Binary files /dev/null and b/mathematiquesettechnologie.pdf differ diff --git "a/partiels/contr\303\264le1.odt" "b/partiels/contr\303\264le1.odt" new file mode 100644 index 0000000..300137c Binary files /dev/null and "b/partiels/contr\303\264le1.odt" differ diff --git a/tps/AlgoFermatFacto.py b/tps/AlgoFermatFacto.py new file mode 100644 index 0000000..1bce276 --- /dev/null +++ b/tps/AlgoFermatFacto.py @@ -0,0 +1,26 @@ +import math as m + +def estUnCarre(k): + return (int(m.sqrt(k)))**2 == k + +def facto(n): + t= int(m.sqrt(n))+1 + sp = t**2 - n + while not estUnCarre(sp): + t += 1 + sp = t**2 -n + print "+", + return(int(t+m.sqrt(sp)),int(t-m.sqrt(sp))) + + + + + +print facto(5959) +print facto(2953*3037) +print facto(6197*6299) +print facto(2953*3037) +print facto(17729*17939) +print facto(9623827) +print facto(343570291) + diff --git a/tps/AlgoFermatFacto.py~ b/tps/AlgoFermatFacto.py~ new file mode 100644 index 0000000..685f2a7 --- /dev/null +++ b/tps/AlgoFermatFacto.py~ @@ -0,0 +1,28 @@ +import math as m + +def estUnCarre(k): + return (int(m.sqrt(k)))**2 == k + +def facto(n): + t= int(m.sqrt(n))+1 + sp = t**2 - n + while not estUnCarre(sp): + t += 1 + sp = t**2 -n + print "+", + return(int(t+m.sqrt(sp)),int(t-m.sqrt(sp))) + + + + + +print facto(5959) +print facto(2953*3037) +print facto(6197*6299) +print facto(2953*3037) +print facto(17729*17939) + + +print facto(9623827) +print facto(343570291) + diff --git a/tps/testProbabilite.py b/tps/testProbabilite.py new file mode 100644 index 0000000..1f2fd5d --- /dev/null +++ b/tps/testProbabilite.py @@ -0,0 +1,74 @@ +from random import * + + + + + +def testPrimaliteFermat(n,t): + 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^(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): + 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 + 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=561 +print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500) +print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,3) + +n= 39341 +print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500) +print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30) + +n=651693055693681 +print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500) +print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30) + diff --git a/tps/testProbabilite.py~ b/tps/testProbabilite.py~ new file mode 100644 index 0000000..66edb82 --- /dev/null +++ b/tps/testProbabilite.py~ @@ -0,0 +1,125 @@ +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) + + + + +""" + diff --git a/tps/testProbabiliteAvecGeneration.py b/tps/testProbabiliteAvecGeneration.py new file mode 100644 index 0000000..bba8111 --- /dev/null +++ b/tps/testProbabiliteAvecGeneration.py @@ -0,0 +1,154 @@ +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 + +""" + +def bezout(a,b): + if b==0: return [1,0] + else: + uv= bezout(b,a%b) + return [uv[1],uv[0]-uv[1]*(a/b)] + + + +(p,_)= genereUnNombrePremier(100) +(q,_)= genereUnNombrePremier(100) + +n=p*q +phi=(p-1)*(q-1) + +(e,_)= genereUnNombrePremier(30) +print "cle publique",e + +(d,_)=bezout(e,phi) +d = d%phi +print "cle privee",d + + +m=3402752281514000316845 + +a = pow(m,e,n) +print "message encodee ",a + +mp = pow(a,d,n) +print "message decodee ",mp + + + + + + + + + + + +""" + + +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) + + + + +""" + diff --git a/tps/testProbabiliteAvecGeneration.py~ b/tps/testProbabiliteAvecGeneration.py~ new file mode 100644 index 0000000..66edb82 --- /dev/null +++ b/tps/testProbabiliteAvecGeneration.py~ @@ -0,0 +1,125 @@ +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) + + + + +""" + diff --git a/tps/texput.log b/tps/texput.log new file mode 100644 index 0000000..1c89d9b --- /dev/null +++ b/tps/texput.log @@ -0,0 +1,21 @@ +This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2014.4.22) 13 OCT 2014 21:22 +entering extended mode + restricted \write18 enabled. + %&-line parsing enabled. +**"Cours de ski.tex" + +! Emergency stop. +<*> "Cours de ski.tex" + +End of file on the terminal! + + +Here is how much of TeX's memory you used: + 4 strings out of 494999 + 116 string characters out of 6180228 + 46040 words of memory out of 5000000 + 3324 multiletter control sequences out of 15000+600000 + 3640 words of font info for 14 fonts, out of 8000000 for 9000 + 14 hyphenation exceptions out of 8191 + 0i,0n,0p,22b,6s stack positions out of 5000i,500n,10000p,200000b,80000s +! ==> Fatal error occurred, no output PDF file produced!