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.

---

L'algorithme : https://fr.wikipedia.org/wiki/Baby-st...

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

Moteur de recherche Google (impressionnant !) : https://www.google.fr/

Magma Calculator : http://magma.maths.usyd.edu.au/calc/

10:34 Analyse de la méthode

Code python : https://www.online-python.com/7iP1RVX83C
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).

Site sympa permettant d'utiliser le bon vocabulaire : https://chiffrer.info/
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 !