ajout -a

diff --git a/mathematiquesettechnologie.pdf b/mathematiquesettechnologie.pdf
new file mode 100644 (file)
index 0000000..58c10cf
Binary files /dev/null and b/mathematiquesettechnologie.pdf differ

diff --git a/partiels/contrôle1.odt b/partiels/contrôle1.odt
new file mode 100644 (file)
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 (file)
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 (file)
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 (file)
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 (file)
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 (file)
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 (file)
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 (file)
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!