Legendre Symbol
Pour ce challenge à 35 points, CryptoHack fournit un nombre premier et dix entiers. Un seul de ces entiers possède une racine carrée modulo ce nombre premier. Il faut le retrouver, calculer ses deux racines et envoyer la plus grande.
Préparer les valeurs
Le challenge Legendre Symbol sur CryptoHack donne deux valeurs. p est le nombre premier qui sert de modulo. ints est la liste des dix entiers à tester.
J'ouvre une console avec python3 dans le terminal. Je copie ensuite les deux affectations p = ... et ints = [...] depuis les données du challenge.
Une fois les valeurs chargées je vérifie leur taille et le reste de p modulo 4 :
print("Taille de p :", p.bit_length(), "bits")
print("Nombre de candidats :", len(ints))
print("p modulo 4 :", p % 4)
On retrouve bien un premier de 1024 bits, dix candidats et un reste de 3 modulo 4. Ce dernier résultat va servir pour le calcul de la racine.
Trouver le résidu quadratique
Le critère d'Euler permet de savoir si un entier non nul modulo un premier impair possède une racine carrée : on calcule a^((p - 1) / 2) modulo p.
Si le résultat vaut 1, c'est un résidu quadratique. S'il vaut p - 1, c'est un non-résidu : p - 1 représente ici −1 modulo p. Pour un multiple de p, le résultat vaut 0.
En Python, pow(a, exposant, p) fait directement l'exponentiation modulaire. On évite ainsi de construire toute la puissance avant de prendre son reste.
for i, a in enumerate(ints, start=1):
test = pow(a, (p - 1) // 2, p)
symbole = -1 if test == p - 1 else test
print(f"Candidat {i:2} : Legendre = {symbole:+}")
Le // fait une division entière. La conversion de p - 1 en -1 sert seulement à rendre la sortie plus lisible.
Candidat 1 : Legendre = -1
Candidat 2 : Legendre = -1
Candidat 3 : Legendre = -1
Candidat 4 : Legendre = -1
Candidat 5 : Legendre = -1
Candidat 6 : Legendre = +1
Candidat 7 : Legendre = -1
Candidat 8 : Legendre = -1
Candidat 9 : Legendre = -1
Candidat 10 : Legendre = -1
Seul le sixième candidat donne +1. C'est donc celui dont on doit calculer la racine. Les indices Python commencent à zéro donc il se trouve à ints[5].
Calculer les deux racines
Le symbole de Legendre répond à la question « est-ce qu'une racine existe ? ». Il ne donne pas cette racine.
L'énoncé précise que p ≡ 3 mod 4. Dans ce cas, pour un résidu quadratique a, on peut calculer une racine avec :
a = ints[5]
r = pow(a, (p + 1) // 4, p)
Pourquoi cet exposant ? Comme p donne un reste de 3 modulo 4, (p + 1) / 4 est entier. Si on élève la racine proposée au carré, on obtient :
r² ≡ a^((p + 1) / 2)
≡ a × a^((p - 1) / 2)
≡ a × 1
≡ a (mod p)
Le 1 vient du test précédent : on a justement choisi un entier pour lequel le critère d'Euler donne 1. Le carré de r redonne donc bien a modulo p.
Pour info : cette formule dépend de la condition
p % 4 == 3. Elle ne permet pas de calculer les racines pour tous les nombres premiers impairs.
L'autre racine est p - r, qui représente −r modulo p. Son carré est le même. Cette fois, l'énoncé demande la plus grande :
flag = max(r, p - r)
Vérifier la réponse
Avant de soumettre le nombre je vérifie les deux racines et le choix de la plus grande :
print("Première racine valide :", pow(r, 2, p) == a)
print("Seconde racine valide :", pow(p - r, 2, p) == a)
print("Plus grande racine choisie :", flag > p - flag)
Les deux premiers tests renvoient True. Les carrés de r et de p - r redonnent donc bien a modulo p. Le troisième test renvoie aussi True et confirme que flag contient la plus grande racine.
Il reste à afficher la réponse à soumettre sur CryptoHack :
print(flag)
Conclusion
Le critère d'Euler permet de repérer le seul résidu quadratique de la liste. Comme p % 4 == 3 une puissance suffit ensuite à calculer une racine. Il reste à choisir la plus grande des deux et à vérifier que son carré redonne le nombre de départ modulo p.