Formule d’inversion d’Arazi

Posted on 21 avril 2011 by Tukikun

Alors que je travaille sur un sujet assez différent, je suis tombé sur une petite formule très amusante que je ne connaissais pas.

Quand $n$ est un nombre premier, l’inverse de $e$ modulo $n$ est donné par le petit théorème de Fermat :

$d=e^{-1}\pmod n = e^{n-2}\pmod n$

Mais quand $n$ n’est pas premier, le « truc » courant est d’appliquer la formule d’Azari qui relie $e^{-1}\pmod n$ et $n^{-1}\pmod e$ .

Soient $e$ et $n$ deux nombres positifs premiers entre eux. Si $e\wedge n=1$ , alors

$d=e^{-1}\pmod n = \dfrac{1+n(-n^{-1}\bmod e)}e$

On démontre cela très simplement en considérant $U=e(e^{-1}\bmod n)+n(n^{-1}\bmod e)$ , congru à $1$ modulo $e$ et modulo $n$ . Le théorème des restes chinois et un encadrement facile donnent alors $U=1+en$ ce qui permet de conclure.

Cette formule est attribuée à Arazi qui était le premier à tirer profit de ce théorème folklorique pour implémenter des inversions modulaires d’exposents RSA rapides sur un processeur cryptographique.

Musique et Pi

Posted on 20 mars 2011 by Tukikun

Le quatorze mars de l’année dernière, je vous parlais de la journée de Pi, qui bien évidemment, revient chaque année. Cette année, on peut trouver un très bel article sur le blog de Eljj sur ce même sujet.

Aujourd’hui je suis tombé sur une petite animation en flash que je souhaitais partager avec vous qui permet de mettre en musique les 10 000 premières décimales de pi… et c’est vous qui choisissez l’air que ça donnera puisque vous choissisez quelle note correspond à chaque chiffre. C’est sans grand intérêt, mais c’est marrant.

Et si vous arrivez à obtenir une jolie mélodie, n’hésitez pas à partager vos notes initiales !

Addendum: ça n’a rien à voir avec ce qui précède, mais j’en profite pour partager cette vidéo de guitare découverte récemment et que je trouve fort sympathique.

Pari/GP

Posted on 4 mars 2011 by Tukikun

Alors que je me promenais sur la page consacrée à sa classe de MPSI, je suis tombé sur un petit document de PB présentant brièvement le langage Python pour faire des calculs sur ordinateur… Ça m’a rappelé (avec émotion je dois avouer) mes débuts en programmation, lorsque je faisais des programmes php pour calculer la suite de Fibonnaci, factoriser un nombre, etc.

Je voulais donc profiter de ce message pour vous présenter un fabuleux système de calcul formel, PARI/GP, qui est principalement utilisé en théorie des nombres mais qui contient beaucoup de fonctions utiles en mathématiques. De plus, il est libre et distribué selon les termes de la licence publique générale GNU. Il est développé par des français de l’université de Bordeaux I.

PARI/GP est avant tout destiné aux théoriciens des nombres, mais peut-être utilisé avec profit dans d’autres cas (algèbre linéaire, arithmétique, etc.). Il est composé de deux parties :

PARI : bibliothèque écrite en C, mais qui peut-être appelée d’un langage haut niveau (Python, C++, Perl, etc.)
gp : interface en ligne de commande permettant l’accès aux fonctions de PARI. Le langage utilisé ressemble à du C.

Les calculs sont effectués en précision arbitraire. Il est également très utilisé en cryptologie (vérification qu’un nombre est premier via l’algorithme AKS, calculs sur les courbes elliptiques, algorithme LLL, etc.). En revanche, ses capacités d’intégration et de dérivation sont moins efficaces que des logiciels de calcul formel comme Xcas, Maple ou Mathematica. Il a également une fonction « graphique » qui me semble limitée (mais j’avoue ne pas avoir regardé si il y avait une possibilité d’interaction avec gnuplot ou autre.).

Mieux que de faire encore de nombreux discours, voici quelques exemples d’utilisation. Dans votre terminal, tapez gp pour accéder à l’interface GP pour PARI.

« Hello World » en PARI/GP

Dans tous les langages de programmation, on commence par une telle application, donc je ne déroge pas à la règle:
print("Hello World")
Aucune difficulté, aucun commentaire.

Une boucle en PARI/GP

Montrons la syntaxe d’une boucle for :
for(i=0, 5, print(i))
Ceci affiche les entiers de 0 à 5 à la ligne.

Pour avoir de l’aide sur une fonction, on peut taper ?for et on obtient :
for(X=a,b,seq): the sequence is evaluated, X going from a up to b.

De même, lorsque l’on cherche une fonction dont on ne connaît pas exactement le nom, on peut chercher avec trois points d’interrogations. Exemple :

???matker

retourne

bnfsignunit idealintersect matinverseimage matker matkerint

Calcul avec des nombres premiers

La fonction isprime est une fonction déterministe (via l’algorithme AKS) qui détermine si un nombre est premier. Jusquà 500 bits de longueur, le calcul est encore rapide pour la primalité :
isprime(2^(501)-1)
retourne 1 en 310 ms environ (pour obtenir le temps de calcul, taper ## après votre dernière opération), alors qu’il met plus de 5 secondes pour un nombre premier de 1024 bits.

D’ailleurs une manière facile d’obtenir un nombre premier aléatoire est d’utiliser la fonction nextprime qui donne le nombre premier qui suit l’argument donné. Par exemple

nextprime(2^(1024)+random(2^(1024)-1))

renvoit le nombre

179769313486231590782518276703737196373630355166285016700028966421710165488969543617 6526889863117584648152455111700332203590123411794386808044158416082415271352025604694004045 5111003982745778025452513076910528815189617790566856810276323839016028883085338806026638240 6524494940761227538110799658431716130780389

qui est un nombre premier de 1024 bits.

Calculs matriciels

On peut faire facilement avec PARI/GP de l’algèbre linéaire. Par exemple :
C=matid(5); C[1,3]=9; C[2,5]=6; b=[1,2,0,1,1];
ne renvoit rien (à cause des ;) mais a bien enregistré la matrice C que l’on peut afficher :
[1 0 5 0 0] [0 1 0 0 6] [0 0 1 0 0] [0 0 0 1 0] [0 0 0 0 1]
et le vecteur b.

On peut alors demander de résoudre l’équation $Cx=b$ d’inconnue $x$ :

a=matsolve(C, b~)

qui renvoit

[1, -4, 0, 1, 1]~

Et on peut vérifier par

C*a-b~

qui renvoit bien le vecteur nul.

Notez que le signe ~ représente la transposition, et que PARI/GP différentie les vecteurs colonnes et lignes. On peut également accéder à la première ligne de la matrice C[1,] ou sa cinquième colonne C[,5].

Procédures en PARI/GP

On peut bien évidemment faire plusieurs opérations en même temps avec des procédures. Par exemple, on peut mettre le code suivant dans un fichier chiffres.gp (dans le dossier où vous êtes avec le terminal, ou on lui donne l’adresse complète)
Chiffres(d,l,n)= { local(i,m,v);


	if(type(d) != "t_INT" || d <= 0, print("d doit être un entier strictement positif"); return([]));

	if(type(l) != "t_INT" || l <= 0, print("l doit être un entier strictement positif"); return([]));

	if(type(n) != "t_INT" || n < 0, print("n doit être un entier positif"); return([]));

m=n; v=vector(l); for(i=0, l-1, v[l-i]=m%d; m=floor(m/d);); return(v) }

et demander à PARI/GP de lire ce fichier :
\r chiffres.gp

Il suffira ensuite d'appeler

Chiffres(3, 4, 28)

pour obtenir dans un vecteur de taille 4, la décomposition de 28 en base 3. Autrement dit,

[1, 0, 0, 1]

Finalement, ces exemples reflètent que peu la puissance de PARI/GP que je vous encourage à découvrir sur le site officiel, et qui est un formidable outil qui peut être très utile. Bien entendu vous pouvez calculer dans des corps finis, sur $\mathbf Z/n\mathbf Z$ , manipuler des polynômes, des fractions rationnelles, les corps de nombres, les fonctions de Bessel, etc.)

Et pour finir, une jolie fonction tracée grâce à plot :

Le théorème de Wilson

Posted on 13 décembre 2010 by Tukikun

Le théorème de Wilson est un résultat très connu d’artihmétique élémentaire, qui donne une caractérisation anecdotique des nombres premiers.

Dans cet article, je rappellerai les démonstrations connues et vous présenterai une démonstration un peu plus étonnante (et très anecdotique) basée sur le théorème de Sylow en théorie des groupes.

Historique

Le théorème de Wilson a été découvert par Ibn al-Haytham (aussi connu comme Alhazen) vers les années 1000, mais est attribué à John Wilson (un étudiant de Edward Waring) qui l’a conjecturé au dix-huitième sicècle. C’est Waring qui publia la conjecture 1770, mais sans démonstration. La première preuve est dûe à Lagrange, et a été publiée en 1773. Il semblerait que Leibniz connaissait le résultat un siècle plus tôt, mais ne l’a jamais publié.

Théorème de Wilson

Un entier naturel $p>1$ est premier si et seulement si

$(p-1)!+1 \equiv 0 \pmod p$

Cette caractérisation des nombres premiers est un peu anecdotique et ne constitue pas un test de primalité utile (calculer la factorielle de $p-1$ n’est pas envisageable). Son principal intérêt réside dans son histoire et la simplicité de son énoncé et de ses preuves (exceptée bien entendu celle dont je vais parler en dernier et qui justifie l’existence de cet article).

Démonstration du sens réciproque

Commençons par démontrer que si $(p-1)!+1\equiv 0\pmod p$ , alors $p$ est premier. Supposons que cette équation est vraie, cela signifie qu’il existe $k\in\mathbf Z$ tel que

$kp-(p-1)!=1$

Ainsi, on a une relation de Bezout entre $p$ et $1<\ell <p$ , donc $p$ est premier.

Démonstration du sens direct

par Lagrange

Notons $\mathbf F_p=\mathbf Z/p\mathbf Z$ . C’est un corps et le groupe $\mathbf F_p^\times$ de ses inversibles est d’ordre $p-1$ . Ainsi, le petit théorème de Fermat implique que ses $p-1$ éléments sont racines du polynôme $X^{p-1}-1\in\mathbf F_p[X]$ de degré $p-1$ . Comme $\mathbf F_p$ est un corps, et que les éléments $1\leq \ell < p$ sont racines de ce polynôme, on a

$X^{p-1}-1=(X-1)(X-2)\cdots(X-(p-1))$ .

En évaluant cette expression en $p$ , on trouve le résultat voulu.

par Gauss

Si $p=2$ , le résultat est clair. On suppose donc $p$ impair.

Le principe de cette jolie démonstration est de grouper deux par deux les éléments de $\mathbf F_p^\times$ . Pour tout $k\in\mathbf F_p^\times$ , $k\neq 1, -1$ , il existe $\ell\in \mathbf F_p^\times$ , $\ell\neq k$ (sinon $k^2=1$ , i.e., $k\in\left\{-1,1\right\}$ ce qu’on a justement exclu) tel que $k\ell =1$ . Ainsi, lorsqu’on élimine, dans le produit $\prod_{1\leq k\leq p-1}k\in\mathbf F_p$ , les paires d’inverses mutuels dont le produit vaut $1$ , il ne reste que

$\prod_{1\leq k\leq p-1}k = 1\times (p-1) = -1 \in \mathbf F_p$ ,

ce qui prouve le résultat.

… par le théorème de Sylow

Commençons par dénombrer le nombre de $p$ -Sylow du groupe symétrique $\mathfrak S_p$

Dans $\mathfrak S_p$ , il y a $(p-1)!$ éléments d’ordre $p$ . En effet, un élément d’ordre $p$ est un $p$ -cycle car $p$ est premier, et un $p$ -cycle peut s’écrire avec n’importe quel élément en premier, et c’est l’ordre des $p-1$ éléments restants qui importe.

Maintenant, un $p$ -Sylow est de cardinal $p^\alpha$ maximal avec $p^\alpha$ qui divise le cardinal de $\mathfrak S_p$ . Ainsi, $\alpha=1$ et les $p$ -Sylow sont d’ordre $p$ , et contiennent l’identité et $p-1$ $p$ -cycles. Réciproquement, chaque $p$ -cycle est contenu dans un $p$ -Sylow. Il y a donc

$\frac{(p-1)!}{p-1}=(p-2)!$ $p$ -Sylow.

Avec le théorème de Sylow…

on sait que le nombre de $p$ -Sylow est congru à $1$ modulo $p$ . Ainsi

$(p-2)!\equiv 1\pmod p$ ,

et en multipliant par $p-1$ , on a

$(p-1)!\equiv p-1\equiv -1\pmod p$ .

Petit mot de la fin

J’aime bien cette dernière démonstration pour deux raisons. La première, c’est qu’elle relie les sous-groupes de Sylow avec un théorème d’arithmétique élémentaire, ce qui prouve (si besoin est encore) qu’en mathématiques il n’y a jamais qu’un seul moyen de prouver les choses. La seconde est que les étudiants, face au dénombrement des $p$ -Sylow de $\mathfrak S_p$ , utilisent immédiatement le théorème de Sylow et restent bloqué avec

$n_p\equiv 1\pmod p$ ,

où $n_p$ est le nombre de $p$ -Sylow. Là, il faut remettre les mains dans le cambouis pour s’en sortir. De plus, ce n’est pas un exercice difficile.

L’historique et les premières démonstrations sont tirées de la page sur le théorème de Wilson de la wikipédia.

Un petit séjour à Singapour

Posted on 15 septembre 2010 by Tukikun

Dans le cadre de mes études, j’ai effectué un stage à la Nanyang Technological University de Singapour en juin et juillet dernier, dans la School of Physical and Mathematical Science, c’est-à-dire le bâtiment réservé aux mathématiques, à la physique, à la chimie et à la chimie biologique. Cette université est très récente, et le bâtiment dans lequel je me trouvais était neuf (construit en 2007, 38000 m², ouvert officiellement en juin 2009), très moderne, très grand, très beau : des conditions optimales pour travailler. Je n’étonnerai personne lorsque je révélerai que je n’ai rencontré qu’un seul Singapourien à l’université parmi les post-doc, professeurs, chercheurs et thésards. Cette université se sert du fait que Singapour est une pierre angulaire du commerce mondial pour en faire un rayonnement culturel international au niveau des sciences. Il est connu que les universités singapouriennes viennent aux congrès de mathématiciens (par exemple) avec des liste de 40 postes à pourvoir (ce qui est du jamais vu !).

SPMS, Singapore

J’ai rencontré de nombreuses personnes : des allemands, chinois, malais, indiens, turques, israéliens, suisses, américains, etc. C’est une expérience extraordinaire d’être en contact avec des gens de toute la terre, de discuter avec eux, de découvrir d’autres cultures, et de travailler ensemble. Des millions de dollars sont investis dans les universités à Singapour pour en faire des pôles d’excellence : la ville-État mise énormément sur la recherche et l’enseignement pour garder son avance sur les autres pays asiatiques, et s’immiscer au même niveau que l’Occident. Occident, qui soit-dit en passant, est très présent là bas dans la vie de tous les jours. Singapour est un étonnant mélange entre l’extrêmement moderne (Ion Orchard, Marina Bay Sands : le dernier hôtel casino, lubie du multi-milliardaire juif Sheldon Adelson) et le plus traditionnel, voire ressemblant aux pays en voie de développement (temples indiens, quartiers de petites maisons, superstition chinoise, etc.)… Mais le gouvernement lutte actuellement pour que les jeunes ne s’occidentalisent pas trop.

J’étais à l’université pendant les vacances scolaires de là bas, donc je n’ai pas vu l’effervescence des étudiants (excepté les remises de diplômes — correspondant à nos licences européennes — qui se déroulaient comme l’on voit dans les films américains), mais il y avait quand même beaucoup de personne dans l’immense campus, qui travaillent dans les différentes universités.

Au niveau des mathématiques, là-bas on travaille les mathématiques technologiques, pratiques. Dans l’autre université (très connue) de Singapour, la NUS, il y a plus de mathématiques « pures ». Le département de cryptologie est très développé et on trouve de nombreuses personnes qui travaillent dessus : mathématiciens, informaticiens, ingénieurs, etc. Cependant malgré cette effervescence, d’un point de vue extérieur, le cadre ne semblait pas du tout stressant : les conditions de travail sont très bonnes — bureaux clairs, environnement vert, climatisation (ô combien nécessaire), une grande bibliothèque, proximité des laboratoires de recherche avec les bureaux personnels des professeurs, salles de discussions, nombreux séminaires, et un calme qui vous transperce complètement et propice au travail…

Là-bas j’ai travaillé sur le partage de secret en cryptologie, qui a fait l’objet d’un article précédent sur ce blog.

Un séjour très instructif et agréable (excepté le climat pas très accueillant : chaud et humide, très humide, trop humide… équatorial !).

Kilomaths.com

Un autre blog de maths…

Author Archives: Tukikun

Formule d’inversion d’Arazi

Musique et Pi