mat309 2019

Modérateur : xcasadmin

parisse
Messages : 5345
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » mar. déc. 10, 2019 4:05 pm

10/12:
Preuve des 2 propositions.
Def code t-correcteur parfait.
Nombre d'elements dans une boule de rayon t.
2^n=2^k*(1+n+...+comb(n,t))
Cas t=1, codes de Hamming binaires
n=2^m-1, k=n-m
m=1 donne k=0 ne sert a rien
m=2 n=3, k=1 code de repetition
m=3, n=7, k=4 construction d'un code de Hamming systematique de distance 3, la matrice de controle contient l'ecriture en base 2 de tous les entiers de 1 a 7 en colonne. Le syndrome correspond a un entier, dont la colonne correspondante dans la matrice de controle donne le bit a corriger.
Le meme principe fonctionne pour m quelconque, exemple pour m=4, n=15, k=11.

Codes polynomiaux: poly de degre<k -> poly de degre<n, phi(P)=P*g pour g de degre m=n-k. Ce code n'est pas systematique, exemple g=x^3+x+1, k=4, n=7.
Code systematique phi(P)=P*x^m - reste(P*x^m,g), exemple ci-dessus, on retrouve un code de Hamming binaire.

J'ai evoque pour finir 2 prolongements hors programme
* corps fini faciles a manipuler sur ordinateur en base 2: reste de polynomes a coeff dans Z/2Z modulo un polynome irreductible (equivalent des restes d'entiers modulo un nombre premier)
* algorithme de Strassen pour mulitplier 2 matrices viewtopic.php?f=35&t=2432

parisse
Messages : 5345
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » ven. juil. 17, 2020 6:50 am


parisse
Messages : 5345
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » ven. juil. 17, 2020 7:12 am

Sujet juin 2020: https://www-fourier.univ-grenoble-alpes ... juin20.pdf
Elements de correction:
Exercice 1: restes chinois modulo 137 et 2020 (qui sont premiers entre eux)

Exercice 2: 1/ tester la divisibilite par 2 et par les nombres impairs <= racine carree de 2027
2/ Bezout sur E et 2027
3/ le nombre de division s'obtient a partir du nombre de bits et du nombre de 1 de l'ecriture en base 2 de l'exposant 2020=0b11111100100 (7 bits a 1 et 11 bits)
4/ 2027 est premier donc son indicatrice d'Euler vaut 2026, donc E^2026=1 mod 2027 donc E^2020*E^6=1 mod 2027 et E^2020=i^6 mod 2027. Si on connait i, il est donc plus rapide de calculer i^6 mod 2027, mais si on ne le connait pas, il vaut mieux calculer E^2020 directement.

Exercice 3.1:
2/ 10=1 mod 9, donc 10^k mod 9=(1 mod 9)^k=1 mod 9
3/ donc les classes modulo 9 de sum(a_i*10^i) et de sum(a_i) sont identiques. En recommancant autant de fois que necessaire, on en deduit que les classes modulo 9 de a et f(a) sont identiques.
4/ ab mod 9 =(a mod 9)*(b mod 9) donc f(ab)=f(f(a)*f(b)) car ils sont egaux mod 9 et compris entre 1 et 9 qui contient exactement 1 representant par classe modulo 9.
5/ donc si f(c)!=f(f(a)*f(b)) alors c!=a*b. Si f(c)=f(f(a)*f(b)), c n'est pas forcement egal a a*b, par exemple f(3*5)=f(6)
6/ E=q*10^5+r donc E mod 9 =(q+r) mod 9 donc f(E)=f(q+r) mod 9 donc ils sont egaux car compris entre 1 et 9 qui contient exactement 1 representant par classe modulo 9.
7/ En langage naturel, sans utiliser l'analyse mathematique precedente:

Code : Tout sélectionner

fonction f(x)
repeter 
  s := 0 // somme des chiffres de x
  tantque x!=0 faire
    s += reste(x,10) // dernier chiffre de l'ecriture de x en base 10
    x := quotient(x,10)
  fin tantque
  x := s
jusqua x<10
renvoyer x
fin de fonction
En C

Code : Tout sélectionner

int f(int x){
  for (;;){
    int s=0;
    while (x){
      s += x%10;
      x /= 10;
    }
    if (s<10) return s;
    x=s;
  }
}
En Python

Code : Tout sélectionner

def f(x):
  while True:
    s=0
    while x!=0:
      s += x%10
      x = x//10
    if s<10: return s
    x=s
On peut evidemment optimiser en utilisant l'analyse mathematique de f et renvoyer x mod 9 en remplacant 0 par 9, en Python:

Code : Tout sélectionner

def f(x):
  r = x % 9
  if r==0:
    return 9
  return r
en C

Code : Tout sélectionner

int f(int x){
  int r=x%9;
  return r?r:9;
}


Exercice 3.2:
L'analyse mathematique est en tout point similaire puisque 0x10=1 mod 0xF
4/ E=10^5*q+r, donc E=r modulo 16, donc g(E)=g(r) mais on n'a pas en general g(E)=g(q+r) (sauf si q=0 modulo 16).
5 et 6/ dans l'algorithme en langage naturel, remplacer 10 par 16=0x10, en base b remplacer 10 par b. L'analyse mathematique est identique en remplacant 9 ou 0xF par b-1 (puisque b=1 mod b-1)

parisse
Messages : 5345
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » lun. nov. 02, 2020 8:29 pm

Indications CC1 2019:
exercice 1.3/ il doit se terminer par 00, 20, 40 ou 60
exercice 2: Bezout et restes chinois comme en TD

exercice 3: 3n+4=1*(3n+1)+3, donc PGCD(3n+4,3n+1)=PGCD(3n+1,3)=1
L1: 3n+4, 1, 0
L2: 3n+1, 0, 1
L3=L1-L2: 3, 1, -1
L4=L2-n*L3: 1, -n, n+1, donc -n*(3n+4)+(n+1)*(3n+1)=1

exercice 4: 2048=2^11, il faut donc 11 multiplications.
Pour 2051=2^11+2+1, il faut 13 multiplications.

exercice 5:
Bezout sur 13 et 5 donne 2 et -5 donc les solutions de 13x+5y=n sont x=2*n+5*K et y=-5*n-13*K
1/ x=(94+5k) et y=(-235-13k), k entier relatif
2/ On doit avoir x>=0 et y>=0 donc k>=-94/5=-18.8 et k<=-18.08..., pas de solution
3/ meme raisonnement, 1 seule solution x=3, y=2
4/ oui (si x ou y est positif on paie, sinon on rend la monnaie)
5/ calculer le reste de la division par 5 de x pour une solution (x,y) entiers relatifs
6/ Si n est plus grand que 4*13=52 alors l'existence de x et y tels que n=13*x+5*y avec x<=4 entraine que n-13*x>=0 donc y>=0. Il faut encore tester si 48, 49, 50 et 51 conviennent
7/ u, v <- bezout(a,b) avec a*u+b*v=1 donc a*(n*u)+b*(n*v)=n
q,r <- quotient et reste de u par b donc a*(q*b+r)+b*(n*v)=n soit a*r+b*(n*v+q*a)=n
s <- n*v+q*a
si s<0 renvoyer pas de solution sinon renvoyer r,s

exercice 6.1: 1823=23 mod 18 = 5 mod 18 puis puissance rapide
6.2: 18=2*3^2, les inversibles sont les nombres premiers avec 2 et 3: 1, 5, 7, 11, 13, 17
6.3: 5 est inversible donc x=inv(5 mod 18)*3

parisse
Messages : 5345
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » mar. déc. 22, 2020 3:45 pm

Indications ET janvier 2020:
Exercice 1:
1/ il faut trouver n tel que b^n<=10^11-1<b^(n+1), ce qui donne n=2.
2/ en base 16: 0x17*(2^16)^2=0x17*(2^4)^8=0x17*(0x10)^8=0x1700000000
en base 10: 23*65536^2=98784247808
3/ s0 peut prendre toutes les valeurs possibles donc 2^16 (sauf si on depasse 10^11, ce qui peut se produire pour certaines valeurs de s1 et s2).
4/ s2 ne peut pas prendre n'mporte quelle valeur entre 0 et 65535, car s2*(2^16)^2 doit etre plus petit que 10^11.
Donc s2<=23, il y a 24 choix possibles (23 pour certaines valeurs de s0 et s1).
5/ On pourrait choisir d'ecrire en base b=2^13, ainsi s0 et s1 tiendraient sur 13 bits, alors que s2 tiendrait sur 11 bits. Ou partager les 37 bits de 10^11 en 12+12+13.
6/ 2672, 3851, 3052
7/ les nombres sont premiers distincts donc premiers entre eux 2 a 2, par les restes chinois on peut reconstituer de maniere unique tout entier compris entre 0 et le produit des 3 moins 1, soit 100393262856 qui est superieur a 10^11
8/ le partage est bien plus equitable, car les 3 nombres premiers sont tres proches, comme leur produit est tres proche de 10^11, si deux d'entre eux combinent leur part de secret, il restera encore un peu plus de 4600 possibilites.

Exercice 2:
2.1
1/ 10 inversible mod 37 car pgcd(10,37)=1, inverse 26
2/ a*n+b=phi donc n=inv(a)*(phi-b)=26*(phi-3)
3/ irem(10*(asc("janvier") .- 87) .+ 3,37) -> [8,29,11,17,35,32,14]
4/ hiver
5/ attaque frequentielle ou attaque par force brute (37*37 possibilites pour a et b).

2.2
1/ on fait sur A : L2<- L2-7*L1, on obtient [[1,5],[0,10]] avec 10 inversible mod 37 donc A est inversible
Si on ajoute un bloc identite, et qu'on fait L2<- L2-7*L1 puis L2<-L2*26 puis on cree un 0 en ligne 1 colonne 2 (L1<-L1-5*L2), on obtient A^-1=[[23,18],[3,26]]
2/ w=A*v, alors v=A^-1*w
3/ A*[2,0]=[2,14] repete 2 fois.
4/ bonne annee 2020
5/ oui, puisqu'un caractere n'est pas toujours code de la meme maniere, et le nombre de clefs est 37^4 (presque 2 millions de clefs). On pourrait le rendre plus resistant en choisissant un modulo plus grand, mais surtout en prenant une matrice de dimension plus grande.
6/ en langage naturel:

Code : Tout sélectionner

fonction cryptage(A,L) // A matrice, L liste a crypter
si longueur(L) est impaire, rajouter un 0 a la fin de L
initialiser la liste resultat a liste vide ([])
pour k de 0 jusque longueur(L)/2-1 faire
  ajouter à resultat A[0,0]*L[2*k]+A[0,1]*L[2*k+1] mod 37
  ajouter à resultat A[1,0]*L[2*k]+A[1,1]*L[2*k+1] mod 37
fin pour
renvoyer resultat
Pour adapter a une autre valeur de p, et a une dimension de matrice differente

Code : Tout sélectionner

fonction cryptage(A,L,p) // A matrice, L liste a crypter, p nombre premier
d <- dimension de A
tantque longueur(A) mod d est non nul, rajouter un 0 a la fin de L
initialiser la liste resultat a liste vide ([])
pour k de 0 jusque longueur(L)/d-1 faire
  pour j de 0 jusque d-1 faire
    temp <- 0 // produit matrice*vecteur, calcul de la composante j
    pour l de 0 jusque d-1 faire
      temp += A[j,l]*L{d*k+l]
    fin pour
    ajouter à resultat temp mod p
  fin pour
fin pour
renvoyer resultat

Répondre