Math

Bases

Division euclidienne - division entière avec reste

Cette technique est utilisée dans beaucoup d'autres formules par la suite et doit être vraiment bien acquise. C'est le même concept que les divisions en colonne que l'on a appris à l'école obligatoire, simplement sous une forme plus formelle.

Avec deux entiers a et b, nous faisons à l'origine, a/b qui nous donnait un quotient et un reste. Maintenant, on exprime ça sous forme de , avec égal à multiplié par un certain quotient nommé avec un reste .

Exemples:

Les modulos
Les modulos sont le reste de la division. On exprime le reste d'une division par dans sous la forme . On peut aussi dire que 2 valeurs sont équivalentes avec un modulo défini: , qui se lit "13 est congru à 3 modulo 4".

Propriétés des modulos (liste tirée de slide 14 de M. Duc dans 03_slides_groups.pdf)

Comment faire des modulos sur des nombres négatifs ?

• ? C'est le même concept, juste qu'il faut trouver un multiple de 5 qui est inférieur à , ici . Le reste est à nouveau la distance entre deux, ici donc le reste est
• ? Idem, distance de à est .

Nombres premiers

Un nombre qui a exactement 2 diviseurs distincts: 1 et lui même. 1 n'est donc pas premier. Tout le long de ce cours, les nombres premiers ont des propriétés particulières qui sont mises en avant. Un nombre composé est un nombre qui n'est pas premier.

PGDC - Plus Grand Diviseur Commun

Aussi appelé PGDC, ce diviseur peut être calculé pour et . Si ce PGDC vaut 1, alors et sont premiers entre eux, ce qui signifie qu'il n'ont qu'un seul diviseur commun.

Pour le calculer efficacement, on peut s'aider du fait que si .

PPMC - Plus Petit Multiple Commun

Le est le plus petit multiple commun à a et b. Pour le trouver, il suffit de décomposer et en un produit de facteurs premiers, puis de prendre le produit des puissances maximum de chaque facteur différent.

• , on a et , on va prendre les plus grandes puissances de et :

Propriétés des diviseurs

Si on connait une décomposition en facteurs premiers, comme , comment connaître calculer la liste de tous les diviseurs ou les compter ?

En fait, chaque diviseur est un produit qui est composé d'une partie de ces facteurs premiers. On peut prendre juste le , ou le , mais aussi , prendre ou ne pas prendre le ... Cela revient donc à de l'analyse combinatoire, chaque facteur peut être pris autant de fois que sa puissance + 1 (pour le cas de la puissance 0, où on ne le prend pas). Ainsi, comme les puissances sont 4, 1 et 1, le nombre de diviseurs ici est .

Si on cherche à savoir combien il y a de diviseurs qui respecte une certaine condition: Combien de diviseurs sont aussi multiples de 14 ? Pour qu'un diviseur soit aussi multiples de 14, il doit contenir une fois le 2 et une fois le 7. Nous avons donc 4 possibilités pour le 2 (), puis 1 seul possibilité pour le 7 (qui doit être présent), et 2 possibilités pour le puisque celui-ci n'a pas d'impact. Nous avons donc diviseurs de 62384 aussi multiples de 14.

sage: factor(62384)
2^4 * 7 * 557

Algorithme d'Euclide Etendu (AEE)

Cet algorithme est très utile pour trouver le PGDC, pour calculer un inverse modulo (prochaine section) et permet aussi de trouver et dans . On appelle cette forme le Théorème de Bézout et et sont aussi nommés les "coefficients de Bézout".

Il existe plusieurs techniques, mais celle que je trouve la plus simple est la suivante. Calculer le PDGC, puis reprendre chaque ligne pour construire par mise en évidence et injection, jusqu'à atteindre la forme ax + by égale au PGDC.

Prenons et et faisons d'abord le PGDC.

Le dernier reste non nul étant 1 (avant dernière ligne), notre .

Nous allons réécrire chaque ligne précédente tout en gardant les multiplications avec des nombres, sans les simplifier (garder le au lieu de simplifier en )...

Prenons la première ligne en exemple, et on met le reste en évidence : . Ensuite, on va chercher à réinjecter et . Ici nous donne .

Pour la ligne suivante, notre mise en évidence donne , le est et notre a été défini juste avant par . Ceci nous fait .

On continue comme ça pour toutes les lignes, avec chaque fois la définition de la ligne précédente qui est réutilisée.

On peut s'arrêter et ignorer la dernière ligne comme notre dernier nous donne . Bingo, nous avons atteint la forme . Ainsi et !

Inversibles modulo

Un nombre est inversible modulo si et seulement si . La définition de l'inverse de , notée est: .

Par exemple l'inverse de c'est car .

Cela correspond à la définition sur : l'inverse de est car .

Une fois qu'on sait que c'est inversible, il y a deux approches possibles pour trouver l'inverse:

1. Par tatonnements: Pour les petites valeurs, il est possible de calculer de tête en parcourant des multiples. Pour l'inverse de , on cherche des multiples de qui donne un de plus qu'un multiple de .
   • L'inverse de , on prend , ce n'est pas égale à ou ... Le multiple suivant c'est pareil. Puis , c'est aussi ! Comme , l'inverse de est et on peut le noter .
   • , on teste les multiples de 3: , , , , , ... jusqu'à trouver un de plus qu'un multiple de 10: , , ... On a donc trouvé le multiple 21, qui vient de donc ,
   • en fait en positif c'est . Pour chercher l'inverse, toujours la même technique: , , , et comme et que est un multiple de alors l'inverse est .
2. Par calculs: Dès que les valeurs sont trop grandes, il est plus long mais facile de sortir l'inverse grâce à l'AEE présenté au dessus.
   • Pour calculer l'inverse de , il faut faire l'AEE avec ces deux valeurs
   • En reprenant le résultat de la section précédente: , et , ce qui nous donne et
   • Ainsi il est possible de simplifier par étapes, en appliquant le modulo à gauche et à droite, ce qui retire le . Comme on cherchait l'inverse de , on voit directement son inverse qu'il suffit de remettre en positif.

   • Pour le vérifier on peut taper à la calculette: . Comme est bien une valeur entière donne bien 1 de plus qu'un multiple de )

Groupes, anneaux et corps

Classes de congruence: .
L'ensemble de tous les nombres dont le reste de la division entière par 5 est égal à 3. Le est le représentant de cette ensemble.

• = l'ensemble des restes modulo . En plus formel: l'ensemble des classes de congruence modulo n.
• l'ensemble ds restes modulo qui sont premiers avec . En plus formel: l'ensemble des classes de congruence modulo n qui sont inversibles.

En partant de , on va retirer tous les éléments qui ne sont pas inversibles.

Comment savoir si un élément est inversible ? Si .

• 0 pas possible comme c'est nul ( est impossible)
• 1: toujours inversible comme
• 2: donc pas inversible
• 3: donc pas inversible
• 4: donc pas inversible
• 5: donc inversible !

Au final nous avons un ensemble à un seul élément:

Pour inverser un nombre il faut faire le AEE de x et n.

Pour si premier.

Suite

La fonction indicatrice d'Euler

La fonction donne le nombre de valeurs inversibles modulo ou dit autrement le nombre d'éléments qui sont premiers avec . Valeurs utiles tirées du support de cours de M. Gafaiti page 14.

2. si p est premier
3. si p et q premiers et distincts
4. si p est premier, et k un entier naturel non nul
5. si le
6. De manière générale: la décomposition en facteur premier peut-être transformée avec chaque facteur par . Exemple:

Le théorème de Fermat-Euler

Source: Tiré de la slide 31-33 de M. Duc sur 03_slides_groups.pdf

• Fermat: avec premier et non divisible par
• Euler:
• Conséquence: si

Exponentiation rapide

Si le théorème de Fermat-Euler au-dessus ne peut pas être utilisé, pour résoudre rapidement avec un grand , on peut le simplifier par si est pair, et sinon par .

Equations premier degré à résoudre en modulo

Source: Tirées en partie de la page 13 du support de cours. 2 patterns d'exercices ressortent avec une stratégie similaire pour permettre de isoler . Voici les 2 cas avec la constante connue .

1. • Si , alors est inversible. Il nous multiplier par l'inverse (AEE): pour et que le disparaisse. En multipliant des 2 côtés par , on obtient qu'il est facile de développer avec une calculatrice.
   • Sinon, si est un diviseur de 3, on peut diviser toute l'équation par
   • Sinon pas de solution
2. , par exemple -> à condition que mais c'est le cas si et ici , on peut l'appliquer:
   • On cherche l'inverse de ,
   • Ainsi nous avons

Ensemble d'équations modulo de premier degré - Théorème des restes chinois - CRT

Source: inspiré des slides 12 et 13 des slides de M. Duc.

Pour résoudre un système d'équations à une inconnue avec des modulo, il faut s'assurer que les modulos soient tous premiers entre eux. Avec , la formule pour isoler est la suivante.

Voici un exemple pour illustrer cette formule peu lisible.

• 3 équations de départ

• Calcul du modulo final

• Calculs des inverses (parenthèse large) par tatonnements
  Note: résultats du tatonnements: , ,
• Conclusion: solution simple

• Conclusion: solution générale

Dans le cas d'un système d'équations avec facteurs devant , il faut d'abord s'en débarrasser, simplement en trouvant leur inverse pour isoler , ensuite le CRT fonctionne.

Ordres et générateurs

L'ordre d'un groupe est son nombre d'éléments.

• -> 5 éléments (0,1,2,3,4)
• -> éléments
• un corps de taille , donc éléments dans le corps.
• Et est la taille du groupe multiplicatif, qui inclue des éléments tous inversibles sauf le polynome qui est zéro.

L'ordre d'un élément est la plus petite puissance de qui équivant à 1: . Lagrange nous dit que l'ordre d'un élément divise toujours l'ordre de son groupe.

• L'ordre de -> attention ! pas inversible modulo 80!
• L'ordre de -> .
  • L'ordre du groupe est ordre de 77 -> .
  • Les diviseurs de l'ordre du groupe, ici sont , on teste par tatonnement de les utiliser en puissance de .
  • ...
  • Nous avons donc trouvé la plus petite puissance qui donne 1.
  • L'ordre est donc .

Si l'ordre de l'élément est égale à l'ordre du groupe, il est générateur du groupe.

Polynomes et corps de Galois

c'est l'ensemble des polynomes dont les coefficients sont dans .

• Un exemple de contenu infini de
• Le degré d'un polynome est vaut la puissance maximum sur x, dont le coefficient n'est pas .

: un ensemble de polynomes qui sont des restes modulo avec coefficients dans . Ces restes viennent de la division de chaque polynôme de par .

• On nomme cette construction un Corps de Galois, nommé GF (Galois Field en anglais). Dans le cas de degré 8 et , il se note .
• Pour , l'ensemble contient éléments comme il ne peut y avoir au maximum monomes (chaque monome peut avoir comme les coefficients donc valeurs possibles). Petit raisonnement de combinatoire: possibilités pour monomes, donne . Ainsi contient éléments.

Inspiré de slides de M. Duc (voir slide 16 de 04_slides_field.pdf).

Pour tester à la main si un polynôme est irréductible (il ne peut pas factorisé en 2 sous polynômes), il y a plusieurs possibilités

• Si degré du polynôme est 2 ou 3, tester dans toutes les valeurs de 0 à (le vient de ) sans qu'il ne donne zéro. S'il donne zéro c'est qu'on a trouvé une racine. Cela a revient à tester si des polynômes du degré 1 pourrait être extrait.
• Pour des degrés > 3, il faut tester les racines (pour trouver des polynômes du degré 1) mais aussi si les polynômes irréductible de degrés divisent notre polynôme.

Exemple dans pour chercher les polynômes irréductibles de degré 2, on va tester pour les racines avec

• , tests de et donc pas irréductible. La racine nous permettrait de factoriser encore
• , tests de et et -> irréductible !
• , tests de et et -> irréductible !
• , tests de pas irréductible
• , tests de pas irréductible
• ... il en reste encore pas mal à tester pour les coefficients 2 devant et devant .

Exemple dans pour savoir si un polynôme de degré 6 est irréductible:

• Tester pour les racines avec
• Tester si les polynômes irréductibles de degrés donc divisent le polynome donné
• Pas besoin de tester pour degré 4 et 5 car s'ils existent, ils y a un polynôme de degré 2 ou 1 respectivement, qui serait détecté par le check précédent.

Liste de polynomes irréductibles utiles

2. Sur

• Degré 2

• Degré 3

2. Sur

• Degré 2

• Degré 3

Créer des tableaux de puissance sur un générateur

Etant donné

Etapes de construction

1. On commence par poser en se basant sur .

1. On complète les puissances inférieures à par l'égalité
2. On complète les lignes suivantes (seulement celles utiles), en se basant sur les lignes existantes. Ainsi , il nous faut chaque fois simplifier pour atteindre un résultat en degré 3.

Note: dans les équations du dessus: parce qu'on est dans donc que les coefficients sont modulo 2.

TODO: finir de compléter et checker que =1 !! et que bien générateur.

Ceci est notamment utile dans les codes BCH.