Logarithme discret : méthode pas de bébé - pas de géant (BSGS : baby-step giant-step)

⚠ Erratum (merci à @jean-michelmasereel8867 pour les précisions) :

Pour le choix du N, cela dépend d'une condition : si le modulo est un nombre premier ou non. On nomme ce modulo m.

Si m est premier (comme dans la vidéo, où l'on a m = 43) :
On pose phi(n) = m - 1. Ensuite, on choisit N, l'une des racines les plus proches de phi(n) (comme dans la vidéo, avec l'expression des racines). De plus, à 08:01, il faudra compter modulo phi(n), donc modulo 42 dans l'exemple (et non pas modulo 43).

Si le m n'est pas premier :
On pose phi(n) = (p-1)(q-1), avec p et q facteurs de m. Par exemple, si l'on a choisi le nombre 39, il est divisible par p=3 et q=13, donc phi(n) = (3-1)(13-1) = 24. La suite de la méthode reprend celle du cas où m est premier.

---

00:00 Introduction

00:23 Énoncé type

01:19 Méthode pas de bébé - pas de géant

09:06 Outils d’aide à la résolution

10:34 Analyse de la méthode

Si le site est HS, voici le code (attention à l'indentation sur la dernière ligne !) :
############################################
modulo = 43
base = 3
for index in range(1, modulo):
print(str(base) + "^" + str(index) + " mod " + str(modulo) + " = " + str(base ** index % modulo))
############################################
Vous pourrez remplacer les valeurs de modulo et base comme bon vous semble afin de résoudre en bruteforce tout problème de logarithme discret (avec des petits nombres).

13:47 Calcul de la complexité

15:36 Application en cryptanalyse

Actuellement, en cryptographie, pour garantir une sécurité humainement incassable, on utilise un modulo de taille 3072 bits (environ 926 chiffres décimaux).

Dans le cas de la vidéo on utilise décrypter (d'où cryptanalyse) car on cherche à trouver la clé, en n'y étant pas autorisé.

16:46 Outro

Bientôt 100 abonnés :) Merci pour le soutien !

[gatius]

Merci pour la vidéo, elle fut très claire !

[etiennelemonnier]

Erratum (merci à @jean-michelmasereel8867 pour les précisions) :

Pour le choix du N, cela dépend d'une condition : si le modulo est un nombre premier ou non. On nomme ce modulo m.

Si m est premier (comme dans la vidéo, où l'on a m = 43) :
On pose phi(n) = m - 1. Ensuite, on prend l'une des racines les plus proches de phi(n) (comme dans la vidéo, avec l'expression srqt(r-1) < sqrt(phi(n)) < sqrt(r)). De plus, à 08:01, il faudra compter modulo phi(n), donc modulo 42 dans l'exemple (et non pas modulo 43).

Si le m n'est pas premier :
On pose phi(n) = (p-1)(q-1), avec p et q facteurs de m. Par exemple, si l'on a choisi le nombre 39, il est divisible par p=3 et q=13, donc phi(n) = (3-1)(13-1) = 24. La suite de la méthode reprend celle du cas où m est premier.

Complément : Vers la fin de la vidéo, j’oublie de préciser que lorsque l’on avance d’une case dans le sens horaire de la roue, cela revient à multiplier par 3 (modulo 43), d’où le fait de multiplier par 3^6 lors d’un pas de géant (= avancer de 6 cases dans le sens horaire). Avec la même logique, tourner dans le sens trigonométrique (antihoraire), revient à diviser par 3 (modulo 43) pour chaque case.

[fenitraramiaramanana]

Facile à comprendre et très intéressant, encore merci pour l'explication
Bonne continuation pour la suite

[etiennelemonnier]

Bonnes révisions aux étudiants de l’UQAC ! :)

[amine]

Pendant le calcul de pas géant, on fait le modulo sur (P-1). C a d (mod 42) dans ton cas.

[lucasjouvet]

Salut, ta vidéo est super, je ne suis pas très doué en math et j’ai réussi à suivre :D.

Je me demande juste pourquoi la remonter dans la partie « pas de géant » se faisait en modulo 42 (si je m’appuie sur l’erratum)? Est-ce que nous sommes dans N*, qui nous prive de 0 et donc donne l’apparence d’un modulo 42 alors qu’on est toujours sur un modulo 43, mais dans N* ? (je dois sûrement me tromper.)

Sinon, quand tu dis qu’il est mathématiquement faut de dire que -6 = 42, je crois que c’est mathématiquement vrai (mais intuitivement faut), cela dépend de ton environnement (je m'appuie sur "Pensée" de Pascal, qui lui est un peu hardcore à ce niveau ^^).

Une réflexion que j’ai, et en partant du postulat que plus on va dans les grands nombres et moins il y a de chance d’avoir un carré parfait (J’espère ne pas me tromper ah ah!). Je me demande si le choix de la racine (dans ton exemple 6 ou 7) n’a pas une importance. Choisir 7 permettrait d’avoir une palette de « pas de bébé » plus large et donc de probablement tomber plus rapidement sur un résultat durant nos « pas de géant »
Alors évidemment, la complexité ne changera pas, c’est un peu comme quand on divise par 2 l’infini (N*/2) pour trouver des nombres premiers, ça reste l’infini ah ah

[tristanclerc]

L'algo BSGS est plus performant que l'algo Pohlig-Hellman ?