Groupes cycliques | Introduction | Alison
Loading
Notes d'étude
Study Reminders
Support
Text Version

Introduction aux groupes cycliques

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 Prof. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture-38 Cyclic Groups Hello everyone. Bienvenue à cette conférence. (Reportez-vous à la diapositive Heure: 00:30) Le plan de cette conférence est le suivant. Dans cette conférence, nous présenterons le concept de groupes cycliques. Vous verrez différentes définitions et propriétés et la raison pour laquelle nous nous intéressons aux groupes cycliques est que plus tard, nous introduisons des hypothèses de dureté cryptographique dans le contexte de groupes cycliques qui nous aideront à concevoir ou à développer les idées de base qui sont utilisées pour concevoir le protocole d'échange de clés de Diffie – Hellman. (Voir Diapositive Heure: 01 :00) So remember the abstract Diffie – Hellman key Exchange Protocol which we have expliqués présumons that we have some special functions E and F. Just to recall what exactly the exigence from the function E and F étaient, well we need the following properties: we need that function E should be easy to calculer for any input. Nous avons également besoin que si vous êtes donné un α du domaine E et une sortie de fonction E (β), sans connaître la valeur β, il doit être facile de calculer la valeur de la fonction F sur la paire d'entrée (α, β) Et cela doit être le cas échéant (α, β). Si vous voulez obtenir une confidentialité faible, alors la propriété dont nous avons besoin ici de la fonction E et F est que pour chaque aléatoire (α, β) Il doit être difficile de calculer la valeur de F (α, β) Si vous avez juste la valeur E (α) Et E (β). Alors que pour une vie privée forte, nous avons besoin que la valeur de F (α, β) Doivent être impossibles à distinguer de toute valeur aléatoire du codomaine même si vous connaissez la valeur E (α) Et vous connaissez la valeur E (β). Maintenant, la question est que comment pouvons-nous instancier cette fonction E et F? Cela pourrait être le suivant: imaginez que nous prenons une exponentiation à la base publique g. Vous supposez donc que g est une base fixe connue du public et que nous pouvons prendre la fonction candidate E comme suit: E (α) Est définie comme étant cette base g α et cette fonction F (α, β) Peut être défini comme étant l'exponentiation de ceci par rapport à cette base g et une puissance d'exponentiation de puissance est α fois β. Donc c'est mon candidat F (α, β). Il est maintenant facile de voir que si je définis ma fonction E et la fonction F comme ça. Ensuite, je suis en mesure de satisfaire une des exigences de la fonction E et F qui m'intéresse. A savoir si je suis donné E (α) Et si je souhaite calculer F (α, β) Alors ce que je dois faire, c'est que je dois juste relever que E (α) β qui me donnera la valeur de F (α, β). De la même façon si je possède E (β) Et je ne sais pas β, alors que vous connaissez α et E (β) Je peux calculer F (α, β) En augmentant la valeur E (β) α. Donc cela satisfait une des exigences clés que j'ai besoin de ma fonction E et de la fonction F, mais il s'avère que prendre cet entier exponentiation n'est pas suffisant pour instancier ce résumé Diffie – Hellman Key Exchange Protocol car il y a plusieurs autres problèmes de sécurité avec cette fonction E et F. Le premier problème majeur est que la fonction E n'est pas une fonction unidirectionnelle candidate et que vous pouvez imaginer que vous connaissez la description de la base g et que vous connaissez la valeur E (α) à savoir g α et votre but est de trouver l'α puis il est très facile de calculer l'α inconnu en prenant simplement le logarithme naturel. Et le calcul du logarithme naturel est une tâche facile à calculer. Donc, la fonction E en premier lieu n'est pas une fonction unidirectionnelle et cela signifie que je ne peux pas atteindre ces notions de faible protection de la vie privée et de respect de la vie privée. Non seulement la fonction E est une fonction unidirectionnelle, mais le problème est que je ne peux pas l'utiliser à des fins pratiques. Je ne peux pas utiliser la fonction candidate E et la fonction candidate F à des fins pratiques car ici mon α et β peuvent être des entiers arbitraires. Alors que si je veux instancier et implémenter cette fonction E et F, je ne peux pas travailler sur une fonction ou un domaine à l'intervalle qui est constitué d'entiers arbitraires et qui peut être de taille infinie. Nous serons plutôt intéressés à travailler sur des domaines qui sont de nature finie, et c'est pourquoi nous allons maintenant essayer de rechercher les fonctions des candidats E et F qui ne sont pas seulement des fonctions unidirectionnelles et non seulement satisfaire les exigences des fonctions E et F que nous avons besoin pour ce résumé Diffie – Hellman Key Exchange Protocol, mais nous sommes également intéressés que ces fonctions soient du domaine algébrique fini approprié. (Référez-vous à la diapositive: 05 :25) Pour cela, nous devons maintenant rappeler la théorie des groupes que nous avions vue lorsque nous avons construit nos MACs théoriques de l'information, c'est-à-dire lorsque nous avons construit une fonction universelle. Permettez-moi donc de passer rapidement à la définition de groupes. Donc un groupe que je dénote par ce symbole est un ensemble avec une opération appropriée sur les éléments de l'ensemble et nous disons que cet ensemble (est un groupe s'il satisfait aux axiomes suivants, à savoir qu'il devrait satisfaire la propriété de fermeture qui stipule que pour chaque, l'élément. La seconde propriété est que l'opération doit satisfaire la propriété d'associativité, c'est-à-dire pour chaque,, () = (). Nous avons besoin de l'existence d'un élément d'identité, c'est-à-dire qu'il devrait exister un élément unique que je dénote comme dans l'ensemble de ce genre, c'est-à-dire pour tous. Vous devriez avoir un élément inverse pour chaque élément de l'ensemble, à savoir pour chaque élément a à partir de l'ensemble il devrait exister un élément unique que je dénote par un -1 de tel que 1 = a -1 = contient. Je souligne que cet élément a -1 ne signifie pas le 1/a numérique. C'est juste une interprétation ou juste une notation pour l'élément inverse spécial correspondant à l'élément a que j'ai besoin de mon ensemble. Donc, encore une fois, juste pour rappeler que nous avions également vu quelques exemples de groupes. L'ensemble des entiers (Z, +) constitue un groupe abélien. Qu'est-ce qu'un groupe abélien? Un groupe abélien est un groupe spécial qui satisfait tous les axiomes du groupe et, en plus, il doit satisfaire la propriété commutative. A savoir que votre opération doit satisfaire la propriété commutative et il est facile de voir que l'ensemble des entiers avec cette opération + qui satisfait les axiomes du groupe. Si vous prenez 2 entiers, vous obtenez un entier, l'addition est associative, 0 est l'élément d'identité, car si vous ajoutez 0 à un entier, vous obtenez cet entier. Si vous prenez un entier a, l'inverse correspondant est – a. Alors qu'il s'avère que l'ensemble des nombres naturels ne forme pas de groupe par rapport à l'opération + parce que nous n'avons pas l'inverse de l'additif. Parce que l'inverse additif de l'élément, par exemple 2 est – 2, mais -2 n'appartient pas à l'ensemble des nombres naturels. De la même façon l'ensemble des nombres réels non nuls R − { 0 } forment un groupe par rapport à l'opération de multiplication car la multiplication des 2 nombres réels vous donne un nombre réel, donc la fermeture est satisfaite, la multiplication est associative, l'élément 1 est l'élément d'identité. Pour chaque élément non nul a, l'inverse correspondant est le chiffre 1/a parce que le nombre réel a multiplié par 1/a inverse vous donne l'élément d'identité 1 et c'est pourquoi l'ensemble des nombres réels non nulles forme un groupe. (Référez-vous à la diapositive: 08:59) Nous nous intéressons maintenant à des types particuliers de groupes que nous appelons des groupes cycliques. Alors, voyons ce qu'est exactement un groupe cyclique? Un groupe à l'égard d'une opération o est appelé un groupe cyclique d'ordre q si les conditions suivantes sont réunies: tout d'abord, (, o) doit satisfaire les axiomes de groupe, à savoir la fermeture, la propriété associative, l'existence de l'identification, l'existence de l'inverse pour chaque élément de groupe. S'il s'agit d'un groupe abélien, c'est bien, mais nous n'avons pas besoin qu'il s'agit d'un groupe abélien. Alors imaginez picturalement que nous avons certains éléments de cet ensemble et cette opération o satisfait tous les axiomes de ce groupe. La deuxième condition nécessaire est que, puisque je dis que le groupe est un groupe cyclique d'ordre q. Par ordre q, je veux dire qu'il y a un certain nombre d'éléments dans mon ensemble. Donc, c'est ce que je veux dire par l'ordre du groupe à être q. Et pourquoi on l'appelle le groupe cyclique? Il est appelé un groupe cyclique parce que j'ai besoin d'un élément spécial que j'appelle un générateur que je dénote par exemple g. Ce g doit être l'un des éléments de cet ensemble de telle sorte que tous les éléments de l'ensemble puissent être générés par cet élément spécial par des puissances différentes. Ici “ pouvoirs ”, il vous sera très bientôt clair ce que je veux dire par les pouvoirs ici. Fondamentalement, l'idée ici est que cet élément spécial g que j'appelle le générateur il a la capacité, il a la capacité de générer tous les éléments de votre ensemble. Si j'ai au moins un de ces éléments de générateur spécial que j'appelle générateur, alors mon groupe est appelé comme un cyclique, mais je n'ai pas un tel élément spécial g alors mon groupe n'est pas appelé un groupe cyclique. Alors, laissez-moi vous expliquer ce que je veux dire par la génération d'éléments différents selon les différentes puissances du générateur d'éléments. Alors laissez p être un premier et j'ai défini un ensemble Zp * qui se compose de l'élément 1 à p – 1 et maintenant laissez-moi définir une opération de multiplication qui est différente de la multiplication arithmétique normale de sorte que l'opération que je vais définir est qu'elle est notée par .p et qui est aussi appelée comme modulo de multiplication p. La façon dont cette multiplication va être effectuée est la suivante: Si je prends les 2 éléments a, b de l'ensemble Zp * puis la multiplication modulo p de a et b est la même que vous multipliez a et b numériquement et prenez le rappel par rapport au modulo p. Quel que soit le rappel que vous obtenez, ce sera un nombre compris entre 0 et p-1 et c'est ainsi que nous définissons cette opération de multiplication modulo p. Maintenant, je vais dire un résultat qui est un résultat standard qui découle de la théorie des nombres. Je ne vais pas le prouver, mais si vous êtes intéressé par la preuve de ce théorème, alors vous pouvez vous référer à n'importe quelle référence standard de la théorie des nombres. Donc le théorème indique essentiellement que pour chaque nombre premier p le set Zp * avec l'opération modulo p est un groupe ou qu'il constitue un groupe composé de p – 1 éléments. Cela signifie que l'ordre du groupe est p – 1. Nous n'allons donc pas le prouver, mais je vais démontrer que c'est vrai si p est votre choix. Donc je prends p = 5 ici et Z5 * est essentiellement composé d'éléments { 1, 2, 3, 4 }. Donc ce que j'ai fait c'est le long des lignes que j'ai écrites dans les éléments 1, 2, 3, 4 et le long des colonnes que j'ai dénoté les éléments 1,2, 3, 4 et c'est comme une matrice ici. Et ce que j'ai fait ici est l'entrée (i, j) correspond aux résultats de (i. J) modulo 5 ici. Si je considère cette entrée, c'est le résultat de (2. 2) modulo 5. De la même façon (4. 3) modulo 5 va vous donner 2, etc. Vous pouvez donc voir à partir de cette matrice que votre propriété de fermeture est satisfaite. Vous prenez tout i et tout j dans la plage qui appartient à Z5 * et effectuez l'opération (i. J) modulo 5, vous allez obtenir le nombre entre 1 et 4. L'opération de multiplication que nous avons définie ici il satisfait la propriété de l'associativité qui signifie que si je prends (i, j) ème entrée, alors elle n'a pas d'importance dans quel ordre je multiplie (i, j) ème entrée et prendre modulo 5, je vais obtenir le même rappel. L'élément identité est l'élément 1 ici car si vous voyez cette matrice ici et si vous vous concentrez sur la colonne de 1 ici, alors sous ce 1, 1 point 1 modulo 5 vous donne 1, 2 dot 1 modulo 5 vous donne 2, 3 point 1 modulo 5 vous donne 3 et 4 point 1 modulo 5 vous donne 4. L'élément 1 sert donc d'élément d'identité ici. Maintenant, sous chaque élément, vous aurez l'élément inverse correspondant. Donc l'inverse de 1 est 1 ici parce que 1 point 1 vous donne 1. L'inverse de 2 est 3 car 2 point 3 modulo 5 vous donne l'élément d'identité 1, l'inverse de 3 est 2 car 3 point 2 modulo 5 vous donne l'élément d'identité 1 et l'inverse de 4 est 4 car 4 point 4 modulo 5 vous donne l'élément d'identité 1. Donc vous avez tous les axiomes satisfaits et maintenant vous pouvez voir, vous avez des éléments de générateur spéciaux présents ici aussi. Je vais le démontrer également. Avant d'aller voir si l'élément générateur existe ou non, permettez-moi d'abord de définir ce que nous entendons par exponentiation de groupe dans cet ensemble Zp *. Pour tout élément g appartenant à l'ensemble Zp *, je définit g0 comme étant 1. Et je définit g 1 pour être g car en effet g0 modulo p vous allez obtenir 1 modulo p qui est identique à 1 et g 1 si g est un élément de Zp *. Bien sûr, il est inférieur à p et si vous faites g1 et ensuite prenez mod p alors l'effet du mod p n'a pas d'effet. Vous n'obtiendrez que g. Alors que je définit g i comme étant la multiplication modulo p opération appliquée i – 1 fois, il s'avère que peu importe si je prends le rappel à la fin ou si je prends un rappel après avoir effectué chaque individu. P opération i – 1 fois, les résultats seront identiques car ils proviennent de la propriété d'associativité de mon groupe Zp *. Donc je peux définir les gi pour être les mêmes que pour les gi numériques et ensuite vous prenez un dernier mod p pour ramener le résultat dans la gamme 0 à p – 1. Donc, en raison de la façon dont le gi est défini pour le cas i à être 0, i à être 1 et i à être générique i, je peux dire que je peux définir mon gi. I can use the notation gi in the set Zp * to denote the value numeric gi modulo p so that is a notation I am going to use here and that is what I mean by power of an element g in the set Zp * here. Encore une fois, je vais dire un autre résultat bien connu de la théorie des nombres qui dit que pour chaque nombre premier p, il existe au moins un élément g dans le set Zp * tel que lorsque vous calculez quand vous levez des pouvoirs différents et que vous effectuez une opération modulo p, c'est-à-dire que vous faites g0 mod p, g1 mod p up to gp – 2 mod p, alors vous allez obtenir tous les éléments de l'ensemble Zp * dans un ordre arbitraire. Cela signifie p – 1 pouvoirs distincts de cet élément spécial g va vous donner tous les éléments dans Zp * et cela signifie que vous avez au moins un générateur présent dans cet ensemble Zp *. C'est ce que je veux dire en générant tous les éléments de l'ensemble par des puissances différentes. Ton ici dans cet exemple particulier est Zp * et la revendication de la théorie des nombres est qu'il existe au moins un élément dans cette Zp * de telle sorte que si vous levez g aux différentes puissances ici et effectuez l'opération de groupe, à savoir la multiplication modulo p opération vous allez obtenir tous les éléments de Zp *. Encore une fois, je n'en ai pas la preuve, mais si vous êtes intéressé par la preuve, vous pouvez voir n'importe quelle référence standard. Voyons si ce théorème tient pour l'exemple actuel que nous examinons ici. Donc si je prends l'élément 2 qui est un élément de Z5 * et exécute 20 modulo 5, 21 modulo 5, 22 modulo 5 et 23 modulo 5, je vais obtenir les éléments 1, 2, 4, 3 respectivement. Alors remarquant que je n'ai pas obtenu tous les éléments de Z5 * dans l'ordre exact. Mais j'obtiens tous les éléments dans un ordre arbitraire. Donc, pour la définition de groupe cyclique, l'exigence est que les différents pouvoirs de g doivent vous donner tous les éléments de cet ensemble dans n'importe quel ordre arbitraire. L'ordre n'a pas d'importance ici. De la même façon que l'élément 3 est aussi un élément spécial ici parce que 30 modulo 5, 31 modulo 5, 32 modulo 5 et 33 modulo 5 va vous donner l'élément 1,3, 4, 2 à savoir la totalité de Z5 *. Mais si je prends l'élément 4 et essaie d'augmenter ou de calculer des puissances différentes de 4, je ne suis pas en mesure de générer tous les éléments de Z5 *. Je ne pourrais générer que les éléments 1 et 4. Donc, depuis le résultat de la théorie des nombres que je déclare ici les états que j'ai un élément spécial g qui a la capacité de générer l'ensemble du set Zp *. Cela signifie que l'ensemble Zp * avec cette opération de multiplication modulo p est un groupe cyclique d'ordre p – 1. Parce qu'il a p – 1 éléments et en effet dans cet exemple 2 est l'un des générateurs de Z5 *, 3 est aussi l'un des générateurs de Z5 *, mais 4 n'est pas un générateur de Z5 *. Vous vous demandez peut-être pourquoi le nom cyclique ici. La raison pour laquelle je l'appelle cyclique car dès que vous avez un générateur g say par exemple pour le groupe Zp*et ensuite si vous calculez la puissance suivante de g à savoir g p – 1 vous allez obtenir l'un des éléments qui est déjà là dans Zp *. Pour l'essentiel, vous n'obtiendrez que l'élément g0. Encore une fois la preuve de ce qui suit de la théorie des nombres, mais je ne vais pas prouver que si vous calculez g p – 1 vous obtiendrez la même valeur que g 0. La puissance suivante de g vous donnera g1 et ainsi de suite. En ce sens, c'est cyclique, c'est-à-dire dès que vous allez jusqu'à la limite gp – 2, et si vous allez commencer à prendre la prochaine séquence de puissances de g, vous commencerez à reprendre le même cycle. Vous obtiendrez les mêmes éléments de Zp * et cela continuera à se produire et c'est pourquoi le nom du groupe cyclique. Donc les groupes cycliques, juste pour résumer les groupes cycliques sont des types spéciaux de groupe qui a au moins un générateur. (Voir Diapositive Heure: 20 :59) Le groupe Zp * par rapport à l'opération multimodulo p constitue le groupe cyclique multiplicatif parce qu'il y a eu multiplication. Ce n'était pas la multiplication naturelle. Ce n'était pas la multiplication des entiers, mais elle pouvait être interprétée comme une opération multiplicative. Il s'avère que nous pouvons également définir des groupes cycliques basés sur la notion d'opération d'addition et faisons cela. Donc, laissez p être un choix et je définit un ensemble Zp comme étant l'ensemble des entiers 0 à p – 1. Ainsi, la différence entre Zp * et Zp est que l'élément 0 n'est pas là dans Zp *, mais l'élément 0 est maintenant autorisé dans Zp. Maintenant laissez-moi définir une opération d'addition dans cet ensemble Zp que j'appelle comme ajout modulo p désigné par ce symbole + p et l'addition modulo p de certaines paires de nombres a, b de l'ensemble Zp n'est rien d'autre que de réaliser l'addition numérique ou entière a et b et de prendre le modulo p. Donc, pour que le résultat soit un élément de l'ensemble 0 à p – 1. Encore une fois, prenons un exemple ici le jeu Z5 est constitué de l'entier { 0, 1, 2, 3, 4 } et ce que j'ai fait ici est que j'ai fait la matrice qui indique le résultat de l'exécution de l'opération + modulo 5 sur n'importe quelle paire d'éléments de l'ensemble Z5. Encore une fois, il y a un fait bien connu de la théorie des nombres qui stipule que si vous prenez n'importe quel premier p alors l'ensemble Zp avec l'addition modulo p constitue un groupe. Mais maintenant, l'ordre du groupe est premier, c'est-à-dire qu'il a le nombre d'éléments parce que vous avez maintenant l'élément 0 à p – 1 alors que l'ensemble Zp * était un groupe multiplicatif de commande p – 1. Donc maintenant, voyons comment on peut interpréter l'exponentiation du groupe dans ce groupe d'additifs. Donc nous avons défini 0 fois g à être 0 et nous avons défini une fois g à être g où g est tout élément dans le jeu Zp. Alors que i fois g est défini comme étant le résultat de cette opération modulo p appliquée sur l'élément g, i – 1 fois. Il s'avère que peu importe si je prends le mod au dernier ou si je prends le mod après chaque opération + le résultat va être le même car cela découle de la propriété de l'associativité de l'opération + et donc je peux dire que i fois g est le même que la multiplication entière de i et g modulo p. Donc quand je dis i fois g qui ne voulait pas dire que je me multiplie i et g, i fois g est la notation que j'ai suivie par g et i suivie par g est la même que la multiplication entière de i et g modulo p. Donc, sur la base de ces 3 voies ou de la façon dont ce groupe exponentiation est défini par rapport à cette opération + je peux utiliser la notation que i. G est identique à la multiplication des entiers de i et g modulo p. Et là encore, il y a un résultat bien connu de la théorie des nombres qui affirme que pour chaque prime p il existe au moins un élément spécial g dans le set Zp tel que 0 fois g, 1 fois g jusqu'à p – 1 fois g à savoir le p – 1 pouvoirs distincts de g va rendre tous les éléments de l'ensemble Zp dans un ordre arbitraire. Donc ici, l'exponentiation est essentiellement traitée comme si vous voulez calculer g x. En gros, g x ici est interprété comme si vous effectuez l'opération + modulo p x – 1 nombre de fois. C'est donc l'interprétation de la puissance de g lorsque je considère l'opération de groupe sous-jacente dans les ensembles d'additifs. Encore une fois, dans le contexte de Z5, l'élément 1 s'avère être un de ces éléments spéciaux où toutes les puissances différentes de 1 vont vous donner tous les éléments de Z5. La même attente pour 2 aussi bien des puissances différentes de 2 va vous redonner tous les éléments de Z5. Cela signifie que l'ensemble Zp avec l'opération + modulo p est un groupe cyclique d'ordre p. Nous avons donc vu des exemples de groupes cycliques basés sur l'opération de multiplication. (Référez-vous à la diapositive: 25 :26) Nous avons donc vu des exemples de groupes cycliques basés sur des opérations d'addition. Maintenant, définissons ce que nous entendons par exponentiation de groupe dans des groupes cycliques abstra­les. Donc, pour une explication, je suppose que mon est un groupe abstrait où l'opération sous-jacente est une opération multiplicative. Il n'a pas besoin d'être une multiplication entière, mais elle peut être interprétée dans le sens multiplicatif et elle a une commande q à savoir qu'elle contient q nombres d'éléments. Étant donné qu'il s'agit d'un groupe abstrait, je dénote l'élément d'identité à e et laissez g être un élément de ce groupe. Ensuite, nous utilisons la notation suivante. Donc, puisque nous utilisons la notation multiplicative ici pour ce groupe abstrait, je vais utiliser la notation g0 pour indiquer l'élément identité et g1 pour indiquer l'élément identité. Et la notation gi pour indiquer l'élément que j'obtient en composant ou en exécutant l'opération de groupe sur l'élément g, i – 1 nombre de fois. Je souligne que cette notation est complètement différente de l'exponentiation entière. C'est juste une notation, gi ne signifie pas que je me multiplie g, i – 1 fois. Il s'agit essentiellement d'une notation que j'ai utilisée pour représenter l'opération de groupe sur l'élément g, i – 1 nombre de fois. Cependant, il s'avère que les règles de l'exponentiation entière sont toujours applicables dans ce groupe multiplicatif abstrait. A savoir si je prends l'élément de groupe gm qui est essentiellement l'élément g composé à lui-même m – 1 nombres de fois selon l'opération de groupe et je prends l'autre élément de groupe dire g n qui est l'élément de groupe g composé à lui-même n – 1 nombre de fois. Ensuite, si j'effectue l'opération de groupe sur ces 2 éléments, le résultat sera le même que l'élément g étant composé m + n – 1 nombre de fois. De la même manière, si je prends l'élément gm et exécute l'opération de groupe sur cet élément n – 1 nombre de fois, je vais obtenir le même résultat que celui que j'ai obtenu en effectuant l'opération de groupe sur l'élément g, m + n – 1 nombre de fois et ainsi de suite. De plus, si cet élément g est un groupe cyclique, il s'avère que des puissances différentes de g et de nouveau par des puissances différentes de g I ne signifient pas l'exponentiation entière. Le pouvoir par différents pouvoirs de g signifie la définition de l'exponentiation de groupe dans ce sens abstrait. Donc si ce g est un générateur puis des puissances différentes de g allant de la puissance de la 0e au q – 1 th power va me donner tout l'élément de jeu dans un ordre arbitraire. Et enfin un fait intéressant que nous allons rencontrer plus tard ou utiliser plus tard est le suivant: si vous avez un élément g qui est un générateur du groupe, alors l'élément gi est le même que l'élément gi modulo q, cela signifie que vous pouvez effectuer une opération mod q dans l'exposant aussi. Donc pour n'importe quel i qui est < q ce fait est trivialement vrai parce que gi et gi mod q sont identiques si i < q. Mais ce que ce fait dit que si i est plus grand que q, alors g à la puissance que la puissance plus grande i va vous donner la même réponse que le résultat que vous obtiendrez en augmentant g à l'index i modulo q. Encore une fois, je ne vous donne pas la preuve que vous pouvez vous référer à n'importe quel texte standard sur la théorie des nombres pour la preuve de cela. Maintenant, cette discussion que nous avons jusqu'ici est à l'égard d'un groupe cyclique multiplicatif. Nous pouvons étendre notre définition pour tout groupe cyclique abstrait où l'opération sous-jacente est additive. Donc on peut définir g à g fois par g à être e ou l'élément d'identité, à savoir la 0e puissance de g ici est l'élément d'identité et g1 dans le groupe cyclique additif sera interprété comme une fois g et la définition dit que 1 fois g va vous donner l'élément g. Et gi dans ce groupe cyclique additif sera interprété comme i fois g qui est défini comme étant l'opération de groupe, ou l'opération de groupe additive effectuée sur l'élément g, i – 1 fois. Et il s'avère que les règles de l'exponentiation tiennent aussi dans le groupe cyclique additif. À savoir si je prends l'élément m fois g qui est identique à la gm dans le groupe cyclique additif et un autre élément n fois g qui est l'équivalent de gn dans le groupe cyclique additif. Si j'effectue l'opération de groupe, le résultat sera le même que m + n fois l'élément g, c'est-à-dire l'équivalent de l'élément g (m + n).Et la même tient comme ça. Si je prends l'élément m time g et si je exécute n fois cet élément, alors le résultat sera le même que nm fois l'élément g et ainsi de suite. De plus, si l'élément g est un générateur, alors les différents pouvoirs de g vont me donner l'ensemble dans un ordre arbitraire et les différentes puissances de g sont écrites comme 0 fois g, 1 fois g et q- 1 fois g. Et comme c'était le cas pour le groupe cyclique multiplicatif, j'ai un fait correspondant ici aussi que si g est un générateur, alors toute i fois g qui est l'équivalent correspondant de gi est la même que i modulo q fois g. Cela signifie que si i > q et si vous voulez calculer que i fois g, vous pouvez d'abord réduire cet index i modulo q puis augmenter cet index à l'élément g pour obtenir la réponse résultante. (Voir la diaporama: 31:55) Nous avons maintenant défini une notion de groupes cycliques et maintenant nous voyons ce que nous entendons par logarithme discret dans les groupes cycliques. Alors imaginez que vous êtes donné un groupe cyclique arbitraire d'ordre q et sans perte de généralité suppose que l'opération de groupe sous-jacent est une opération multiplicative. Il ne doit pas être une multiplication entière, mais à des fins de notation nous allons utiliser la notation multiplicative ici. Puisque la commande est q, cela signifie qu'elle a un nombre fini d'éléments. Ce point de couleur indique donc les différents éléments de votre ensemble. Comme il s'agit d'un groupe cyclique, il a un générateur au moins un générateur que je dénote par g. J'ai donc mis en évidence cet élément g ici et selon la définition de groupe cyclique différents pouvoirs de cet élément g va vous donner l'ensemble dans un ordre arbitraire. Ce que cela signifie, c'est que si vous prenez un élément y de cet ensemble, alors il existe un index unique x dans la plage 0 à q – 1 tel que gx vous a donné l'élément y et souvenez-vous que gx effectue l'opération de groupe sur l'élément g, x – 1 nombre de fois. Cela ne signifie pas nécessairement que je multiplie g, x nombre de fois. J'effectue l'opération de groupe multiplicative sous-jacente sur l'élément g, x – 1 nombre de fois. Donc la raison pour laquelle il existe un x unique dans cette plage 0 à q – 1 tel que gx vous aurait donné y. Il vient du fait que l'élément g est un générateur. Maintenant, ce x unique dans la plage 0 à q – 1 il est appelé le logarithme discret de votre élément y à la base g que nous désigons par cette notation DLog yg = x. Et vous pouvez considérer ce journal discret comme un équivalent du log naturel. Dans le monde réel si vous avez un nombre réel g à la puissance qui vous donne y alors nous disons que nous définissons ce log yg = x. Ce que nous essayons de faire ici, c'est que nous essayons de donner une définition équivalente dans le monde discret, c'est-à-dire dans le contexte d'un groupe où nous avons un nombre fini d'éléments qui disent q nombre d'éléments et puisque nous envisageons un groupe. Les éléments ici sont discrees. Entre deux éléments de groupe ne sera pas un élément de groupe arbitraire. C'est pourquoi ce logarithme que nous définissons la notion de logarithme que nous définissons dans ce groupe cyclique est appelé le logarithme discret. Fait intéressant, il s'avère que le logarithme discret obéit aux règles du logarithme naturel i.e Dlogge = 0, Dlogghr = r (Dloggh) mod q. Pourquoi nous prenons modulo q est que c'est la chose que nous avons le crochet qui peut sortir de q, qui peut traverser la plage 0 à q – 1, mais selon la définition de log discret l'indice le logarithme discret doit être dans la plage 0 à q – 1 et c'est pourquoi nous prenons modulo q ici et de la même façon Dloggh1 h2 = (Dloggh1 + Dloggh2) mod q. Vous allez vérifier ces faits. Ce sont des exercices simples pour vous et le fait final que nous allons utiliser dans le contexte du logarithme discret est que si vous avez un gx donné pour être y où x n'a pas besoin d'être dans la plage 0 à q – 1. Puis le DLogyg est le même que x modulo q. Eh bien si votre x que vous êtes donné est en effet dans la gamme 0 à q – 1 alors x module q est identique à x. Mais le fait intéressant ici est que si vous avez si vous avez un x qui est en dehors de la plage 0 à q – 1 tel que gx est donné y et si vous êtes intéressant de calculer le DLogyg est le même que celui de l'opération x module q. Encore une fois, c'est un fait bien connu de la théorie des nombres que je ne vais pas prouver ici vous pouvez voir n'importe quel texte standard pour la preuve de ce théorème. Cela m'amène à la fin de cette conférence. En résumé dans cette conférence, nous avons introduit la notion de groupes cycliques et nous avons vu la définition du logarithme discret. Au cours de la prochaine conférence, nous verrons des hypothèses de dureté de la cryptographie candidate basées sur un cycle cyclique.

Notification
You have received a new notification
Click here to view them all