Loading
Notes d'étude
Study Reminders
Support
Text Version

Arithmétique modulaire

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bengaluru Lecture – 55 Number Theory Hello everyone. Bienvenue à cette conférence. Juste un bref résumé, lors de la dernière conférence, nous avons terminé notre discussion sur la cryptographie à clé publique. Ainsi, dans cette conférence, la feuille de route est la suivante. (Référez-vous à l'heure de la diapositive: 00:29) Nous discuterons essentiellement de certains des principaux résultats liés à la théorie des nombres que nous avons utilisés au cours de notre vaste discussion sur la cryptographie à clé publique. J'insiste sur le fait que nous n'aurons pas une discussion à part entière sur la théorie des nombres parce que je pense personnellement que, dans un cours sur les fondements de la cryptographie, nous devrions simplement utiliser les faits importants de la théorie des nombres. Mais j'ai pensé que nous devrions probablement avoir une discussion de très haut niveau sur certains des résultats importants que nous avons largement utilisés lors de notre discussion sur la cryptographie à clé publique. Donc motivé par le fait que nous aurons cette discussion ; aujourd'hui, la conférence de ’ est basée complètement sur la théorie des nombres, nous allons discuter de l'arithmétique modulaire, des nombres premiers et de leurs propriétés et nous allons voir l'algorithme GCD de l'Euclide Euclide. (Voir Heure de la diapositive: 01:28)Commet donc par Arithmétique modulaire. Alors imaginez que vous avez 2 nombres ou 2 entiers a, N appartenant à l'ensemble des entiers Z. Et ici N est le module où N > 1. Ensuite, un mod N est défini comme le reste r, de sorte que le reste r est dans la plage 0 à N-1, de sorte que la relation a = q fois N + r contient pour un entier q. Si c'est le cas, alors on dit qu'un modulo N est r. Donc par exemple, si je veux trouver 5 modulo 4 puis 5 modulo 4 est 1, parce que si je divise 5/4 j'ai le reste 1. De la même façon, si je veux trouver -11 modulo 3 alors -11 modulo 3 est 1 parce que 1 est dans la gamme 0 à 2 et -11 peut être lié à 3 par cette relation, à savoir je peux dire que -11 est 3 fois-4 + 1. Il s'avère que je peux écrire -11 comme une combinaison linéaire de mon module 3 sous une autre forme aussi, c'est-à-dire que je peux dire que – 11 = (3 fois – 3)-2. Et donc on pourrait penser que -11 modulo 3 devrait être-2 mais ce n'est pas le cas car selon notre définition, le reste r doit être compris entre 0 et N-1. C'est pourquoi -11 modulo 3 est 1 et pas -2. Maintenant nous avons la définition d'un modulo N ; si nous avons deux entiers a et b de sorte que tant a que b vous donne le même restant modulo, le module N alors nous disons qu'a est congruent à b et nous sommes la notation que b modulo N. Donc cela signifie que a et b sont équivalents dans le sens qu'ils vous donnent le même rappel quand vous les divisez par le module N. Ainsi, selon la définition d'un modulo N, il s'avère que, si a est congruent à b modulo N, alors ceci est possible si et seulement si la différence de a et b est complètement divisible par N. Parce que si a donne le reste r modulo N et comme a est congruent à b modulo N ce qui signifie B modulo N est aussi le même rappel r et si je soustrais b d'a puis le reste r et r annule et ce que j'ai obtenu, c'est que a-b est complètement un multiple de N et donc il sera complètement divisible par N. (Référez-vous Diapositive: 03:58) Nous avons donc des règles arithmétiques bien connues pour les arithmétiques modulaires. Ainsi, par exemple, nous avons deux nombres a et b et si je sais qu'un modulo N est un’ et que b modulo N est b’ alors je peux dire que le signe + b modulo N sera la même valeur que celle que vous avez obtenue en effectuant l'opération un’ + b’ modulo N. Il en va de même pour la soustraction et la multiplication. Ainsi, la façon dont vous pouvez interpréter ces règles est que vous pouvez imaginer comme si vous pouvez d'abord exécuter les modules ou vous pouvez d'abord faire la réduction modulo, le module N. Et puis vous pouvez effectuer l'addition, la soustraction, l'opération de multiplication au lieu d'ajouter ou de soustraction ou de multiplier puis de faire la réduction modulo N. Pour être plus spécifique, par exemple, imaginez que je veux calculer la valeur de ce nombre, je veux réaliser le produit de 1093028 et 190301 modulo 100. Si je veux calculer cette valeur, il y a deux façons de le faire. La première est que je fais d'abord le produit ici ou que je calcule d'abord le produit ici et ensuite je fais la réduction modulo 100. Mais ce sera une opération compliquée parce que multiplier ces deux grands nombres sera vraiment difficile. Je ne peux pas le faire facilement sur un portable. D'autre part, la même opération que je peux effectuer en réduisant d'abord les valeurs individuelles ici, à savoir 1093028 et 190301 modulo 100. Et la réduction de chacun des modules 100 est très simple. Parce que je dois juste me concentrer sur les deux derniers chiffres ici que j'ai comme 28 et 1 et puis je peux multiplier les 28 et 1 et puis encore la réduire, réduire la réponse modulo 100. Et quel que soit obtenu par l'option 1 et quel que soit le résultat que j'ai obtenu par l'option 2 ils seront les mêmes que pour les règles de calcul arithmétique de l'arithmétique modulaire. C'est donc une astuce très puissante ou un concept puissant applicable dans le contexte de l'arithmétique modulaire où vous devriez ; où ; au lieu d'appliquer l'opération et de faire le module modulaire ou de réduction N et vous pouvez d'abord réduire les opérandes modulo N et ensuite vous pouvez effectuer l'opération et, si nécessaire, vous pouvez à nouveau effectuer une réduction modulo N. (Se reporter à Heure de la diapositive: 06:13) Nous avons donc vu l'addition, la soustraction et la multiplication modulo N et ce que la division modulaire. Donc la question est de savoir ce qui suit, imaginez un modulo N est un’ et b modulo N est b’ alors pouvons-nous dire qu'une division par b modulo N sera la même qu'une’/b’ modulo N. Réponse est non, car en fait il s'avère que l'opération a divisée par b modulo N n'est pas du tout bien défini. Donc pour démontrer mon point d'imaginer mon a et b sont 3 et 5 et mon module est 4 donc je suis donné 3 modulo 4 est 3 et 5 modulo 4 est 1 et je sais que 3 divisé par 1 modulo 4 ce qui m'a donné 3 mais si je veux calculer 3 divisé par 5 modulo 4 Je n'ai pas la réponse, parce que cette opération 3 divisée par 5 modulo 4 n'est pas du tout bien défini. Cela signifie en arithmétique modulaire que je ne peux pas dire cela, si je suis donné que le produit d'ac modulo N et le produit bc modulo N sont identiques. Alors je ne peux pas dire qu'annuler c des deux côtés et il ne peut pas avoir d'implication qu'un modulo N = b modulo N, ce qui aurait été possible si j'avais effectué la même opération en arithmétique et c ne le ferait pas ; et c n'est pas 0. Cela signifie dans l'arithmétique habituelle si je sais que ac = bc et c n'est pas 0 alors je peux dire que si je divise les deux côtés par c, alors j'obtiens a = b. Mais la même chose que je ne peux pas conclure dans l'arithmétique modulaire parce que la division modulaire n'est pas bien définie. (Référez-vous à l'heure de la diapositive: 07:50) Discutons maintenant de certains algorithmes pour l'arithmétique modulaire. Alors imaginez que nous avons deux opérandes a et b chacun de taille n-bit et le modulo N dont la taille est également n-bit, et certaines des opérations courantes que nous avons rencontrées dans la cryptographie à clé publique sont d'effectuer l'addition modulaire, la multiplication, la soustraction et l'exponentiation. Rappelez-vous donc que l'exponentiation modulaire est une opération très importante dans presque toutes les instanciations du cryptosystème à clé publique, où nous avons rencontré une exponentiation modulaire. Donc nous voulons maintenant avoir des algorithmes pour effectuer ces opérations arithmétiques modulaires, de sorte que les algorithmes résultants, leur complexité, leur complexité temporelle devraient être une fonction polynomiale dans le nombre de bits à savoir n. Il s'avère donc que si je veux réaliser des additions modulaires, soustraction et multiplication, je peux les réaliser en poly (n) nombre d'opérations binaires. Mais qu'en est-il de l'exponentiation modulaire, imaginez que je veux calculer ab modulaire N, un algorithme naïf sera que j'exécute a2 modulo N tout ce qui est le résultat que je le multiplie à nouveau avec un et fait un modulo N, et comme que je dois exécuter essentiellement des multiplications modulaires et que chaque multiplication modulaire nécessite un nombre poly (n) d'opérations et que je suis en train de réaliser b de telles opérations, on peut dire que, dans l'ensemble, la complexité du temps de cet algorithme d'exponentiation modulaire naïf sera O (b * poly (n)-bit opérations et donc c'est le polynôme général. Mais ce n'est pas correct parce que c'est exactement la valeur de b ici. Je dois exprimer la valeur de b aussi comme une fonction de n et il s'avère que l'amplitude de b ici est une fonction exponentielle en nombre de bits n. En gros, b peut être aussi large que 2n. Cela signifie, cet algorithme de exponentiation modulaire naïf ; sa complexité temporelle est une fonction exponentielle et le nombre de bits dont vous avez besoin pour représenter votre b et le module N et c'est pourquoi il s'agit de l'algorithme de temps exponentiel. Nous ne pouvons pas utiliser cet algorithme d'exponentiation naïve pour effectuer ; calculer ab modulo N. (Référer le temps de la diapositive: 10:16)Donc maintenant ce que nous allons discuter, c'est que nous allons voir un algorithme de poly time pour calculer des exponentiations modulaires. Cette méthode est appelée la méthode "Square and Multiply". Et pour montrer l'algorithme, je vais prendre un exemple ici. Je veux calculer un à la puissance 53 modulo N. Remember, l'approche naïve sera de multiplier un 52 fois et chacun ; avec chaque multiplication vous faites une opération mod N. En gros, l'approche naïve vous demandera de réaliser 52 multiplications modulaires. Mais ce que nous allons voir ici, c'est que l'utilisation de la méthode carrée et multiple nous permet d'effectuer le même calcul avec seulement 9 multiplications modulaires. L'idée qui sous-tend cette méthode carrée et multiple est la suivante. Donc j'exprime mon exposant 53 dans ce cas en binaire. Et selon la représentation binaire de 53 où que j'ai la valeur de bit 1 je dois prendre cette puissance de 2. Là où la puissance de bit est 0 je dois exclure cette puissance de 2 et donc je peux dire que 53 dépend de sa représentation binaire peut être exprimée comme sommation de ces puissances de 2. Et donc je peux dire que a à la puissance 53 n'est rien d'autre que le produit de certains pouvoirs sélectifs de a à savoir a à la puissance 32, a à la puissance 16, a à la puissance 4 et a à la puissance 1. Donc l'idée derrière cette place et multiplier la méthode comme le nom suggère que dans chaque itération nous accumulerons ou nous calculerons les puissances successives d'a. Et cela signifie que nous allons commencer par une puissance 1 et ensuite nous irons à un carré puis à partir d'un carré nous irons à un à la puissance 4 puis de a à la puissance 4 nous irons à un à la puissance 8 et ainsi de suite et ensuite sélectivement en fonction du bit actuel dans la représentation binaire de l'exposant, à savoir 53 dans ce cas nous déciderions d'accumuler ou non la puissance actuelle de a ou non, et c'est pourquoi le nom carré et multiplier. D'une manière plus détaillée, imaginez que j'écris 53 dans cette représentation binaire de LSB à MSB dans ce formulaire. Et comme je passe de LSB à MSB, les différentes puissances de a que j'obtient comme je passe de 1 bit actuel au bit suivant est juste un carré de la puissance précédente, et il est facile de voir que mon but est de calculer a à la puissance 53 et a à la puissance 53, peut être calculé en multipliant quelques pouvoirs sélectifs d'un à savoir les pouvoirs d'un correspondant aux positions binaires où dans la représentation binaire de 53, où j'ai le bit 1. Donc, sur la base de cette idée, l'algorithme est le suivant. Donc nous avons mis un accumulateur ici qui aura la réponse finale. La réponse finale que je veux calculer est une à la puissance b ou une à la puissance 53 dans ce cas. Alors j'initialise mon accumulateur à 1 et une fois que j'effectue toutes les itérations, mon accumulateur aura la réponse finale. Donc dans chaque itération ce que je vais faire, je vais faire une mise à jour conditionnelle, c'est-à-dire que je ferai l'opération que y = y dans la puissance actuelle de a selon que mon bit actuel dans l'exposant b que j'explore actuellement est 1 ou pas. Ainsi, par exemple, actuellement, je commence par le LSB de 53 ou l'exposant b, maintenant le bit est 1 qui signifie que je dois prendre accumuler ce pouvoir et c'est pourquoi je vais mettre à jour mon accumulateur par y existant et la puissance actuelle de a et ensuite je vais à la puissance suivante de a. Et je vérifie la position de bit, la position de bit est 0 ; bit est 0 donc je n'ai pas besoin d'accumuler ce pouvoir. Puis je vais à la puissance suivante d'un qui sera un à la puissance 4 et je vérifie le bit actuel, c'est un. Cela signifie que je dois accumuler ce pouvoir, c'est pourquoi je vais mettre à jour mon accumulation en multipliant le contenu actuel de l'accumulation avec la puissance actuelle d'un. Puis je vais à la puissance suivante d'un que je n'ai pas besoin d'inclure ou d'accumuler parce que la position de bit dans l'exposant est 0 alors je vais à la puissance suivante d'a et je vérifie la position de bit de l'exposant dans sa représentation binaire il est 1, donc je dois accumuler. Et donc je mise à jour mon accumulateur, et ensuite je vais au MSB de la représentation binaire de mon exposant, c'est 1, ça veut dire que je dois accumuler le pouvoir actuel de a et donc c'est ma réponse finale. Je ne suis donc pas en train d'écrire le pseudo code ici. Vous pouvez comprendre ; j'espère que vous pourrez écrire le pseudo code ici. Mais l'idée ici est que j'ai besoin d'effectuer une séquence d'itération, le nombre d'itérations n'est rien d'autre que le nombre de bits dont vous avez besoin pour représenter votre exposant b. Et dans chaque itération nous devons faire une quadrature obligatoire de l'ordinateur la puissance suivante d'un. Et une accumulation facultative selon que le bit actuel dans la représentation binaire de l'exposant b est 0 ou 1 et il s'avère que dans le pire des cas mon exposant b pourrait être tel que tous les bits de sa représentation binaire est 1, ce qui signifie dans le pire des cas à chaque itération cette accumulation facultative doit être exécutée obligatoire. Mais même dans ce cas le nombre total de multiplication modulaire que nous finissons par réaliser est deux fois n qui est une fonction polynomiale dans le nombre de bits dont vous avez besoin pour représenter votre n, votre module et vos nombres a et b et donc il s'agit d'un algorithme de poly time et c'est l'algorithme que nous utilisons pour effectuer une exponentiation modulaire dans tous nos cryptosystèmes à clé publique. (Référez-vous à l'heure de la diapositive: 15:33)Discutons maintenant des nombres premiers. Par conséquent, la définition des nombres premiers est qu'un nombre entier p > 1 est appelé un nombre premier si ses seuls facteurs positifs sont le nombre lui-même et 1. Et un nombre entier positif supérieur à 1 qui n'est pas premier est appelé le nombre composite. Et un théorème bien connu de l'arithmétique qui est aussi souvent appelé comme le théorème fondamental de l'arithmétique est que tout nombre n > = 1 peut toujours être exprimé en tant que produit de différents pouvoirs de premier et c'est vrai pour chaque n > = 1. C'est un fait bien connu que nous pouvons prouver par induction et ne pas entrer dans la preuve exacte. Et il y a un autre fait bien connu de la théorie des nombres qui dit que, il y a infiniment beaucoup de nombres premiers. Il n'est pas vrai que vous n'avez qu'un nombre fini de nombres premiers. Et encore ce théorème nous permet de prouver l'utilisation de la contradiction ou de toute méthode de preuve. Il y a donc plusieurs preuves bien connues pour prouver qu'il y a infiniment beaucoup de nombres premiers. Je ne vais pas entrer dans les détails de la preuve ici. (Voir Heure de la diapositive: 16:39)Si vous vous souvenez que dans notre cryptosystème RSA et aussi dans le contexte du schéma de chiffrement Elgamal, nous avons essentiellement besoin de faire partie de la description de la configuration d'un nombre premier pour être disponible pour toutes les parties et le nombre premier doit être suffisamment grand. La question est donc de savoir comment nous choisissons exactement les nombres premiers. Cela signifie que nous avons besoin d'un algorithme pour vérifier si un numéro de n-bit choisi au hasard est un nombre premier ou pas. Et il y a un algorithme naïf pour faire ça. Et l'algorithme naïf est basé sur le fait que si un nombre p est composite, alors il a au moins un des diviseurs qui est inférieur ou égal à   et la preuve de ce théorème est très simple car si vous avez tous les diviseurs d'un nombre composite p supérieur à  . Supposons que vous avez deux de ces facteurs a et b et que ni a ni b n'est inférieur ou égal à et que b et b sont les facteurs de p et p est composite puis il s'avère que le produit ab sera plus grand que p ce qui est une contradiction. Donc, cela signifie que si vous avez un nombre composé p, il est tenu d'avoir au moins un des facteurs de l'intervalle 1 à. Et sur la base de cette observation, nous pouvons avoir cet algorithme de Primality Testing. Alors imaginez que vous avez un numéro p et vous voulez vérifier si le nombre p est premier ou pas et dire que le nombre p est un nombre n-bit. Donc, l'algorithme naïf est essentiellement vous vérifiez s'il existe un diviseur i dans la plage 2 à   pour le nombre p. Parce que si effectivement p aurait été composite sa borne à avoir au moins un des diviseurs de l'intervalle 2 à cela signifie qu'il aura au moins un diviseur i dans l'intervalle 2 à et c'est ce que vous recherchez dans cet algorithme naïf. Il s'avère que l'heure d'exécution de cet algorithme est O ( ) Des divisions car vous exécutez le nombre de divisions dans cet algorithme. Et puisque p est le nombre n-bit de l'amplitude de p est 2n, donc vous effectuez essentiellement 2 des divisions de puissance n / 2 dans cet algorithme naïf. Il s'agit donc d'un algorithme de temps exponentiel que nous ne pouvons utiliser dans la pratique pour vérifier si un nombre donné est premier ou non, si mon n est suffisamment grand. Donc c'était vraiment un problème très difficile de vérifier si un nombre donné de p est premier ou pas en quantité polynomiale de temps. En fait, les gens croient qu'il n'est pas possible de trouver l'algorithme de poly time pour vérifier si un nombre donné est premier ou non. Mais l'histoire a été faite en 2002 où un groupe d'informaticiens de IIT-Kanpur, à savoir Manindra Agrawal, Neeraj Kayal et Nitin Saxena. Ils sont arrivés avec un algorithme de poly time, polynomial en nombre de bits que vous devez représenter avec votre premier p, ou numéro p. Et ils ont mis en place cet algorithme de poly time qui vous dit si un nombre donné p est premier ou pas et que l'algorithme est maintenant bien connu comme algorithme AKS. Vous pouvez donc utiliser cet algorithme pour vérifier si un nombre donné est premier ou non. Mais il s'avère que nous n'utilisons pas l'algorithme AKS car même s'il s'agit d'un algorithme de polytime, les polynômes sous-jacents sont suffisamment grands et cela nous empêche de déployer cet algorithme tel qu'il est en pratique. Au contraire, ce que nous faisons en réalité pour vérifier si un nombre donné est premier ou non, c'est utiliser un algorithme qui est appelé algorithme de test de primalité Miller-Rabin. Et c'est un algorithme aléatoire en ce sens que vous ne pouvez pas toujours faire confiance à la sortie de cet algorithme. Dans le sens où, pour 99,99% des cas, il vous donnera la bonne réponse alors qu'il y a une petite probabilité d'erreur dans la sortie de cet algorithme. Cela signifie que même si votre entrée peut ne pas être un nombre premier, elle peut finir par étiqueter le nombre comme un nombre premier. Donc, en ce sens, il s'agit d'un algorithme à risque d'erreur. Et la raison pour laquelle nous avons utilisé le test de Miller-Rabin pour vérifier si un nombre donné est premier ou pas est que son temps de fonctionnement est super, super rapide comparé à votre algorithme AKS. Je souligne que l'algorithme AKS est complètement exempt d'erreurs. Vous pouvez entièrement faire confiance au résultat qui est donné par l'algorithme AKS parce qu'il s'agit d'un algorithme déterministe. Il n'y a pas de randomisation dans le cadre de l'algorithme. (Référez-vous à la diapositive: 21:08) Maintenant, parlons de Greatest Common Divisor ou GCD. Donc si a et b sont deux entiers non nulles, alors la GCD de a et b est le plus grand entier qui est un facteur commun aussi bien pour a que b. Et si nous avons 2 nombres ou 2 entiers a et b dont la GCD est 1, nous disons que les entiers a et b sont co-premiers. Et si nous avons plusieurs paires de ces nombres ou de plusieurs entiers dire a1 à un nous disons qu'ils sont co-premiers ou relativement prime si les paires de GCD sont de 1 pour chaque paire d'entiers ai, aj dans la liste. Donc si on veut sortir de la GCD de 2 nombres a et b alors l'algorithme naïf sera que je trouve d'abord la factorisation principale d'a parce que, selon le théorème fondamental de l'arithmétique, je peux exprimer comme le produit des pouvoirs de premier choix. Et de la même façon, je peux exprimer mon numéro b comme un produit de pouvoirs de premier choix. Et puis je peux dire que GCD d'a et b n'est rien, mais je prends les exposants minimum de la factorisation individuelle de a et b et les arrange et cela me donnera la GCD de a et b. Mais le problème avec cet algorithme est que, en premier lieu, je trouve la factorisation principale de a et b. (Voir Heure de la diapositive: 22:31) Il s'avère donc que nous pouvons faire quelque chose de très intéressant ici. Nous pouvons utiliser un algorithme efficace pour calculer l'algorithme GCD et cet algorithme est appelé algorithme GCD Euclid ’. Et l'algorithme de base pour Euclid ’ est le fait suivant. Donc si on vous donne des entiers a et b de telle sorte a est (b fois q) + r. Et si votre but est de trouver GCD d'a et b puis de GCD d'a et b n'est rien d'autre que la GCD de b et r, si a = (b fois q) + r. Encore une fois, je ne donne pas la preuve de ce fait. Tu dois me croire. Mais sur la base de cela, nous pouvons trouver un algorithme pour calculer la GCD d'a et b. Et en gros, ce que nous faisons dans cet algorithme est que nous fixons ma valeur x à a et y valeur à b et itérativement je trouve la valeur de x modulo y, j'ai mis mon courant y à être le prochain x et je prends le reste de mon actuel x modulo y pour être à côté y. Et j'effectue cette opération jusqu'à ce que ma y soit 0. Dès que mon y devient 0 qui finira par arriver, j'obtiens le x à ce point pour être la GCD de a et b. Et l'exactitude de cet algorithme découle du fait que GCD d'a et b sera identique à la GCD de b et r et GCD de b et r sera identique à la GCD de r et b modulo r et ainsi de suite. Cela signifie à chaque étape que je réduis fondamentalement la valeur de ce qu'on appelle b et finira par devenir 0,Donc si vous vous demandez ce qui est la complexité du temps ou le nombre de divisions modulaires que je fais ici ; le nombre d'opérations de mod que je fais à l'intérieur de cet algorithme Euclid ’. I can come up with an exact bound using well-connais Lame ’ s théorm which says that if the GCD of a, b is calculé using Euclid ’ s algorithme and it needs n number of divisions then your b should be at least n + 1th Fibonacci numbers savoir b should be supérieur than or equal to f (n + 1), so here f (n + 1) symbolise a Fibonacci n + 1 Fibonacci number. Si vous vous demandez quel est le numéro de Fibonacci, il s'agit d'une séquence commençant par 0 le chiffre suivant. Ce sont les deux premiers nombres de Fibonacci. Et si je veux calculer la valeur de la jème Fibonacci, le nombre de Fibonacci est essentiellement la somme du numéro de Fibonacci précédent, puis précédent du numéro de Fibonacci précédent. C'est donc ma séquence de Fibonacci ici. Donc ce que dit fondamentalement le théorème de Lame ’ c'est que si l'algorithme GCD de l'Euclide ’ aurait joué n nombre de divisions, alors l'amplitude de b sera au moins aussi grande que le n + 1 Fibonacci. Et il existe aussi des limites bien connues sur la valeur du nth Fibonacci. Il est dit que la borne inférieure dit que pour chaque extrémité de la valeur du nième nombre de Fibonacci est au moins α fois n-2 où α est également appelé le rapport d'or à savoir 1 + 5. 2 Donc, sur la base de ces deux faits, je peux dire que si ma GCD d'a, b a besoin de n nombre de divisions, alors il est de la plus grande importance que la n sera la plus grande 5 fois 10 (b). Ainsi, asymptotiquement le nombre de divisions que nous avons besoin de réaliser dans cet algorithme est proportionnel au nombre de bits dont nous avons besoin pour représenter la valeur b et donc l'algorithme global est un algorithme efficace. (Référez-vous à l'heure de la diapositive: 25:57)Il s'avère que nous pouvons utiliser l'algorithme GCD Euclid ’ pour faire quelque chose de plus. Donc pour comprendre que je vais d'abord aller ici Bezout ’ s théorème ici. Ce que dit le théorème de Bezout, c'est que vous pouvez toujours exprimer la GCD de deux nombres a et b comme la combinaison linéaire des nombres a et b. Cela signifie que vous pouvez toujours trouver, vous pouvez toujours trouver des combinaisons linéaires s et t, de sorte que vous pouvez exprimer les entrées a et b comme une combinaison linéaire qui vous donnera la GCD de a et b. Cela signifie que la GCD d'a et b peut être toujours exprimée comme une combinaison linéaire des entrées a et b où les combinateurs s et t existent toujours. Et si vous vous demandez comment exactement vous pouvez trouver ces coefficients de Bezout, les coefficients s et t ou les combinateurs s et t où vous pouvez faire cela en effectuant des bookkeeping supplémentaires ou en conservant quelques variables supplémentaires dans l'algorithme Euclid ’. Et cet algorithme étendu où vous réalisez l'activité supplémentaire de tenue de livres pour découvrir les combinateurs linéaires s et t est également connu comme l'algorithme de l'Euclide de Extended Euclide. Je ne vais donc pas entrer dans les détails complets de l'utilisation de cette comptabilité supplémentaire dans l'algorithme Euclid ’. Laisse-moi la montrer. Supposons que vous voudrez trouver les coefficients des combinateurs linéaires ou les coefficients de Bezout pour les nombres a à être 252 et b à 198. Ainsi, si vous voyez la façon dont l'algorithme GCD fonctionnera, l'algorithme GCD d'Euclid fonctionne pour l'entrée a pour être 252 et b à 198 est comme suit. Dans la première itération, votre a sera 252, b sera 198 et vous obtiendrez la valeur de 252 modulo 198. Dans la prochaine itération, votre a deviendra 198 et votre b deviendra le reste 54 et ainsi de suite. Et vous faites cette opération jusqu'à ce que votre reste devienne 0. Et quand votre reste devient 0, vous savez que 18 est votre GCD. Donc maintenant votre but est de trouver les combinateurs linéaires pour que vous puissiez représenter le GCD 18 comme la combinaison linéaire de 252 et 198. Et pour cela, ce que nous pouvons faire, c'est que nous pouvons reculer ici et nous pouvons voir que je peux réécrire 18 pour être ; sur la base de cette équation, je peux réécrire 18 pour être 54 fois 1-36. Et si je retourne une fois de plus, je sais que mon 36 n'est rien d'autre que 198-3 fois 54. Donc si je reviais ici et que je substituais la valeur de 36 ici, alors j'obviens que 18 peuvent être réécrits comme une combinaison linéaire de 54 et 198, mais ce n'est pas mon but. Ce que je peux faire c'est de revenir en arrière et je peux réécrire mon 54 comme une combinaison linéaire de 252 et 198. Et si je remplace cette combinaison linéaire dans cette dernière équation, j'ai fini par obtenir que 18 est représenté comme une combinaison linéaire de 252 et 198, c'est-à-dire que mes coefficients de Bezout sont 4 et-5. Donc dans cette démonstration en fait pour découvrir les coefficients de Bezout, j'ai fait un suivi de retour, mais dans l'algorithme d'Euclid ’ dont vous avez besoin uniquement pour le passage à terme, vous n'avez pas besoin de faire une bonne marche arrière, de faire la comptabilité et de trouver les coefficients de Bezout ’ s. (Reportez-vous à la section Heure de la diapositive: 29:21)Ainsi, l'algorithme GCD d'Euclid Extended Euclid est très utile. Il sera donc utile de calculer le modulo inverse modulo N. So recall how did ; the way we define multiplicative modulo N operation. Donc a * b modulo N est défini pour le rappel d'a en b modulo N et rappelons que nous définissons un entier b pour être l'inverse multiplicatif d'un modulo N si le produit de a et b modulo N vous donne 1. Et nous utilisons la notation b = a-1 pour désigner l'inverse multiplicatif d'un modulo N et le fait de base ici est que si b est l'inverse multiplicatif d'un modulo N, alors a est aussi l'inverse multiplicatif de b modulo N et il s'avère que si nous avons en effet un inverse multiplicatif d'un modulo N, à savoir si vous avez b tel que b modulo N est 1, alors est b + tout multiple du module N. Cela signifie qu'il n'a pas d'importance que vous ajoutez des multiples de module N à b ou que vous soustrayez des multiples de module N de b tous aussi sera l'inverse multiplicatif d'un modulo N et ceci est dû au fait qu'une fois b +-k fois N se termine à la combinaison linéaire d'un et de N à l'aide des combinateurs s et t. Et maintenant si je prends le mod N sur les deux côtés de cette équation, alors sur le côté droit, j'obtiens un modulo N et 1 modulo N me donnera 1. Mais mon côté gauche, à savoir une fois s + N fois t modulo N me donnera un temps s modulo N parce que N fois t modulo N me donnera 0 parce que c'est le multiple de N. Donc ce que j'obtient en prenant mod N sur les deux côtés est que j'ai obtenu la relation qui a fois modulo N = 1 qui montre que s est en fait l'inverse multiplicatif d'un modulo N. Et c'est ainsi que nous pouvons obtenir le ; ou vous pouvez calculer l'inverse multiplicatif d'un nombre a si c'est co-prime à N. Donc cela m'amène à la fin de cette conférence. Juste pour résumer et cette conférence, nous venons de discuter d'un très haut niveau de la base ; certains des faits importants de la théorie des nombres que nous avons largement utilisés lors de notre discussion sur la cryptographie à clé publique. Plus précisément, nous avons vu ; discuté de l'arithmétique modulaire. Nous avons vu un algorithme de poly time pour calculer l'exponentiation modulaire qui est une opération clé que nous exécutons dans n'importe quel cryptosystème de clé publique ou tout algorithme de chiffrement dans le cryptosystème de la clé publique. Nous avons également discuté d'un test de Primauté, les propriétés du nombre premier. Nous avons également discuté de l'algorithme de l'algorithme Euclide étendu pour calculer le GCD de deux nombres et pour calculer les coefficients de Bezout ’ il sera utile de calculer l'inverse multiplicatif des nombres.