View
1
Download
0
Category
Preview:
Citation preview
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Racines Carrées dans les Extensions Quadratiques
de Corps Finis
Gora Adj
Mardi 10 Juillet 2012
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Institution
Centre de Recherche et d’Etudes Avançées de l’InstitutPolytechnique National du Mexique
◮ Département d’Informatique, Mexico
◮ Environ 100 publications par an
Maître de Stage : Francisco Rodríguez-Henríquez
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Groupe :
Ensemble non vide G muni d’une loi de composition interne · tels que :
(associativité) ∀ x, y, z ∈ G, (x · y) · z = x · (y · z) (= x · y · z) ;
(élément neutre) ∃ e ∈ G : x ∈ G, x · e = e · x = x ;
(inverse) ∀ x ∈ G, ∃ x′ ∈ G tel que x · x′ = x′ · x = e.
Anneau :
Ensemble A muni de deux lois de composition interne (+, ∗) tels que :
+ définit un groupe abélien sur A, d’élément neutre 0, et l’inversed’un élément x est noté −x ;
∗ est associative, distributive par rapport à + et admet un élémentneutre (noté 1).
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Corps :
Un anneau dans lequel seul l’élément nul est non inversible pour lamultiplication. (F∗
q = Fq\{0})
Corps fini ou groupe de Galois :
Un corps à q éléments noté Fq ou GF (q). Dans ce cas, q est unepuissance d’un nombre premier appelé caractéristique du corps.
Résidu quadratique
Un élément d’un corps admettant une racine carrée dans ce corps.Si le corps est Fq, il existe q−1
2résidus quadratiques dans F
∗
q.
a ∈ Fq est un résidu quadratique ssi aq−12 = 1.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Courbe elliptique sur un corps Fpn (p > 3) :
L’ensemble des points (x, y) ∈ F2pn vérifiant l’équation
E : y2 = x3 + ax+ b,
où a, b ∈ Fpn.
Compression de point
Pour transmettre un point (x, y) ∈ Fpn, on envoie la coordonnée x
et un bit pour le signe de y.Puis retrouver y en calculant y0 =
√x3 + ax+ b selon le bit de
signe reçu.
Hachage vers un point
h ∈ Fpn, le haché d’un message M.Si h est un résidu quadratique dans Fpn ,on calculey =
√x3 + ax+ b pour avoir un point (h, y).
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Contenu
1 Extensions impairesL’algorithme de Shanks pour q ≡ 3 (mod 4)L’algorithme d’Atkin pour q ≡ 5 (mod 8)L’algorithme de Kong pour q ≡ 9 (mod 16)Algorithmes Généraux pour q ≡ 1 (mod 16)
2 Extensions pairesAlgorithme pour q ≡ 3 (mod 4)Algorithme pour q ≡ 1 (mod 4)
3 Comparaisons numériquesComparaisons pour p ≡ 3 (mod 4)Comparaisons pour p ≡ 1 (mod 4)
4 Résumé
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
√· dans Fpm
p premier impair
m impair
pm ≡ 1 mod 4
pm ≡ 1 mod 8
pm ≡ 1 mod 16
Alg. de Müller ou
alg. de Tonelli-Shanks
pm ≡ 9 mod 16
Alg. de Kong
pm ≡ 5 mod 8
Alg. d’Atkin
pm ≡ 3 mod 4
Alg. de Shanks
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
L’algorithme de Shanks pour q ≡ 3 (mod 4)
Si q = pm ≡ 3 (mod 4). En intégrant le test de résidu quadratiqueà l’algorithme de Shanks [5], on obtient l’algorithme 1.
Algorithme 1 Algorithme de Shanks pour q ≡ 3 (mod 4)
Entrée: a ∈ F∗q .
Sortie: x tel que x2 = a, s’il existe etfaux autrement.
1: a1 ← aq−3
4 .2: a0 ← a2
1a.
3: Si a0 = −1 Alors
4: Retourner faux.5: Fin Si
6: x← a1a. {aq+1
4 }7: Retourner x.
Avec la méthode binaire pour l’exponentiation ont obtient unecomplexité de :
1
2
[
⌊log2(q)⌋+ 1]
Mq +[
⌊log2(q)⌋ − 1]
Sq.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
L’algorithme d’Atkin pour q ≡ 5 (mod 8)
Quand q ≡ 5 (mod 8), on peut employer la méthode d’Atkin [1] .
Algorithme 2 Algorithme d’Atkin
Entrée: a ∈ F∗q .
Sortie: x tel que x2 = a, s’il existe etfaux autrement.
PRECALCUL
1: t← 2q−5
8 .
CALCUL
1: a1 ← aq−5
8 .
2: a0 ← (a21a)
2.3: Si a0 = −1 Alors
4: Retourner faux.5: Fin Si
6: b← ta1.7: i← 2(ab)b.8: x← (ab)(i− 1).9: Retourner x.
La complexité de l’algorithme 2 est de :
1
2
[
⌊log2(q)⌋+ 11]
Mq +[
⌊log2(q)⌋ − 1]
Sq.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
L’algorithme de Kong pour q ≡ 9 (mod 16)
L’algorithme de Kong et al. [2] est une généralisation de laméthode d’Atkin pour q ≡ 9 (mod 16), avec une complexitémoyenne egale à :
1
2
[
⌊log2(q)⌋+ 16]
Mq +[
⌊log2(q)⌋+ 1]
Sq.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
L’algorithme de Kong pour q ≡ 9 (mod 16)
Algorithme 3 Algorithme de Kong pour q ≡ 9 (mod 16)
Entrée: a ∈ F∗q .
Sortie: x tel que x2 = a, s’il existe etfaux autrement.
PRECALCUL
1: c0 ← 12: Tant que c0 = 1 Faire
3: Choisir c ∈ F∗q .
4: d← cq−9
8 .5: c0 ← (dc)4.6: Fin Tant que
7: e← c2, t← 2q−9
16 .
CALCUL
1: a1 ← aq−9
16 .2: a0 ← (a2
1a)4.
3: Si a0 = −1 Alors
4: Retourner faux.5: Fin Si
6: b← ta1.7: i← 2(ab)b.8: r ← i2.9: Si r = −1 Alors
10: x← (ab)(i− 1).11: Sinon
12: u← bd.13: i← 2u2ea.14: x← uca(i− 1).15: Fin Si
16: Retourner x.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithmes Généraux pour q ≡ 1 (mod 16)
Algorithme 4 Algorithme de Tonelli-Shanks
Entrée: a ∈ F∗q
Sortie: x tel que x2 = a, s’il existe etfaux autrement.
PRECALCUL
1: Mettre q−1 sous la forme 2st, avect impair.
2: c0 ← 1.3: Tant que c0 = 1 Faire
4: Selectionner aléatoirement c ∈F∗q .
5: z ← ct.6: c0 ← c2
s−1
1 .7: Fin Tant que
COMPUTATION
1: ω ← at−1
2 .2: a0 ← (ω2a)2
s−1
.3: Si a0 = −1 Alors
4: Retourner faux.5: Fin Si
6: v ← s, x← aω, b← xω.7: Tant que b 6= 1 Faire
8: Chercher le plus petit entierr > 0 tel que b2
r
= 1.
9: ω ← z2v−r−1
, z ← ω2, b← bz,x← xω, v ← r.
10: Fin Tant que
11: Retourner x.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithmes Généraux pour q ≡ 1 (mod 16)
L’Algorithme 4 de Tonelli-Shanks [6] a une complexité moyenne de :
1
2
[
⌊log2(q)⌋+ s+3]
Mq+[
⌊log2(q)⌋+1
4
(
s2+3s−12)
+1
2s−1
]
Sq,
où s est défini tel que q − 1 = 2st, avec t impair.
Cette moyenne, comme dans l’analyse de Lindhurst [3], prend encompte toute entrée possible, qu’elle soit résidu quadratique ounon.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithmes Généraux pour q ≡ 1 (mod 16)
Soient α et β ∈ Fq. La suite de Lucas(
Vk(α, β))
k>0
est :
V0 = 2, V1 = α and Vk = αVk−1 − βVk−2, pour k > 1.L’algorithme 5 calcule Vk(α, 1) pour α et k > 1 donnés,
Algorithme 5 Evaluation de terme d’une suite de Lucas
Entrée: α ∈ Fq et k > 2.Sortie: Vk(α, 1).1: Ecrire k sous la forme binaire∑l−1
j=0 bj2j .
2: d0 ← α.3: d1 ← α2 − 2.4: Pour j décroissant de l − 2 vers 1
Faire
5: d1−bj ← d0d1 − α,dbj ← d21−bj
− 2.6: Fin Pour
7: if b0 = 1 then v ← d0d1 − α else
v ← d20 − 2.8: Retourner v.
Sa complexité est :[
⌊log2(q)⌋ − 5
2
]
Mq +[
⌊log2(q)⌋ − 3
2
]
Sq.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithmes Généraux pour q ≡ 1 (mod 16)
Algorithme 6 Algorithme de Müller [4]
Entrée: a ∈ F∗q .
Sortie: x tel que x2 = a, s’il existe etfaux autrement.
1: Si a = 4 Alors
2: Retourner 2.3: Fin Si
4: t← 1.5: a1 ← (at2 − 4)
q−1
2 .6: Tant que a1 = 1 Faire
7: Selectionner aléatoirement u ∈F∗q\{1}.
8: t← u
9: Si at2 − 4 = 0 Alors
10: Retourner 2t−1.11: Fin Si
12: a1 ← (at2 − 4)q−1
2 .13: Fin Tant que
14: α← at2 − 2.15: x← V q−1
4
(α, 1)/t.
16: a0 ← x2 − a.17: Si a0 6= 0 Alors
18: Retourner faux.19: Fin Si
20: Retourner x.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithmes Généraux pour q ≡ 1 (mod 16)
Complexité de l’algorithme 6 :
Si (a− 4)q−12 = −1, en moyenne, on a
[
3
2⌊log2(q)⌋ − 3
]
Mq +[
2⌊log2(q)⌋ − 3
2
]
Sq.
Si (a− 4)q−12 = 1, en moyenne, on a
[
5
2⌊log2(q)⌋ − 3
]
Mq +[
4⌊log2(q)⌋ − 5
2
]
Sq + Iq.
En faisant la moyenne dans ces deux cas, on obtient une complexitémoyenne de :
[
2⌊log2(q)⌋ − 3]
Mq +[
3⌊log2(q)⌋ − 2]
Sq +1
2Iq.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithme pour q ≡ 3 (mod 4)
Remarque
Soit K un corps fini et a ∈ K un résidu quadratique dans K.Soit b ∈ K tel qu’il existe un entier s impair vérifiant b2as = 1,
alors bas+12 est un racine carrée de a .
Supposons q = pn/2 ≡ 3 (mod 4) et a ∈ Fq2 . En posant
b = (1 + aq−12 )
q−12 et i =
√−1,
on a :
x =
{
iaq+14 si a
q−12 = −1;
baq+14 autrement.
(1)
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithme pour q ≡ 3 (mod 4)
L’équation 1 se traduit facilement en l’algorithme 7 avec unecomplexité de :
[
⌊log2(q)⌋+ 2]
Mq2 +[
2⌊log2(q)⌋ − 3]
Sq2 .
Algorithme 7 Racine carrée dans Fq2 , avec q ≡ 3 (mod 4)
Entrée: a ∈ F∗q2 et i ∈ Fq2 tel que
i =√−1.
Sortie: x tel que x2 = a, s’il existe etfaux autrement.
1: a1 ← aq−3
4 .2: α← a1(a1a). {a
q−1
2 }
3: a0 ← αqα. {aq2−1
2 }4: Si a0 = −1 Alors
5: Retourner faux.
6: Fin Si
7: x0 ← a1a. {aq+1
4 }8: Si α = −1 Alors
9: x← ix0.10: Sinon
11: b← (1 + α)q−1
2 .12: x← bx0.13: Fin Si
14: Retourner x.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithme pour q ≡ 1 (mod 4)
Algorithme 8 Racine carrée dans Fq2 , avec q ≡ 1 (mod 4)
Entrée: a ∈ F∗q2 .
Sortie: x tel que x2 = a, s’il existe etfaux autrement.
PRECALCUL
1: c0 ← 1.2: Tant que c0 = 1 Faire
3: Sélectionner aléatoirement cdans F
∗q .
4: d← cq−1
2 .5: c0 ← dqd. {c
q2−1
2 }6: Fin Tant que
7: e← (dc)−1. {(cq+1
2 )−1}8: f ← (dc)2. {cq+1}
CALCUL
1: b← aq−1
4 .2: a0 ← (b2)qb2. {a
q2−1
2 }3: Si a0 = −1 Alors
4: Retourner faux.5: Fin Si
6: Si bqb = 1 Alors
7: x0 ← SQRTq(b2a).
8: x← x0bq .
9: Sinon
10: x0 ← SQRTq(b2af).
11: x← x0bqe.
12: Fin Si
13: Retourner x.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithme pour q ≡ 1 (mod 4)
Dans l’algorithme 8, SQRTq(·) désigne l’opération d’extraire uneracine carrée d’un résidu quadratique dans Fq en utilisant laméthode la plus appropriée.
Si n (Fq2 = Fpn) est divisible par 4,
c.-à-d., Fq est aussi extension de degré paire de Fp,
on peut alors réutiliser l’algorithme 8 ou faire appel à l’algorithme 7pour avoir une racine carrée de b2a ou b2af aux étapes 7 et 10 del’algorithme.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Algorithme pour q ≡ 1 (mod 4)
La complexité moyenne de l’algorithme 8 est de :
[
⌊log2(q)⌋+ 1]
Sq2 +[1
2⌊log2(q)⌋ +
19
6
]
Mq2 +#SQRTq,
où #SQRTq représente la complexité d’une extraction de racinecarrée dans Fq.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Pour illustrer la compétitivité de nos algorithmes nous avons choisi :
pour q = p3 ≡ 3 (mod 4), n = 6 = 2× 3 et l’extension estconstruit selon le schéma
Fp ⊂ Fp3 ⊂ Fp6 ;
pour q = p6 ≡ 1 (mod 4), n = 12 = 22 × 3 et l’extension estconstruit selon le schéma
Fp ⊂ Fp3 ⊂ Fp6 ⊂ Fp12 .
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Comparaisons pour p ≡ 3 (mod 4)
Posons
p1 = 36u4 +36u3 +24u2 +6u+1, avec u = −(262 +255 +1)
et
p2 = 2256 − 2224 + 2192 + 296 − 1.
Tableau 1: Nombre de multiplications dans Fp pour p = 3 (mod 4)
Paramètre Algo 3mod4 Algo Kong Algo T-Shanks Algo Muller
p1[254bits] 11379 46635 46374 71263
p2[256bits] 15751 —– 95162 74225
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Comparaisons pour p ≡ 1 (mod 4)
Posons
p3 = 36u4 + 36u3 + 24u2 + 6u+ 1, avec u = 262 − 254 + 244
et
p4 = 36u4 + 36u3 + 24u2 + 6u+ 1, avec u = 263 − 249
Tableau 2: Nombre de multiplications dans Fp pour p = 1 (mod 4)
Paramètre Algo 1mod4 Algo Kong Algo T-Shanks Algo Muller
p3[254bits] 13751 —– 305616 428628
p4[256bits] 14598 —– 318096 415519
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
√· dans Fpn
p premier impair
n pair
pn/2 ≡ 1 mod 4
Nouv. alg. 1 mod 4
pn/2 ≡ 3 mod 4
Nouv. alg. 3 mod 4
n impair
p ≡ 1 mod 4
p ≡ 1 mod 8
p ≡ 1 mod 16
Alg. de Müller ou
alg. de Tonelli-Shanks
p ≡ 9 mod 16
Alg. de Kong
p ≡ 5 mod 8
Alg. d’Atkin
p ≡ 3 mod 4
Alg. de Shanks
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
Objectif futurs
Aprofondir les techniques utilisées pour application àl’exponentiation
Cryptosystèmes basés sur les code correcteurs d’erreurs et lessystèmes multivariables
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
A.O.L. Atkin.
Probabilistic primality testing, summary by F. Morain.
Research Report 1779, INRIA, pages 159–163, 1992.
F. Kong, Z. Cai, J. Yu, and D. Li.
Improved generalized atkin algorithm for computing square roots in finitefields.
Information Processing Letters, vol. 98, no. 1 :1–5, 2006.
S. Lindhurst.
An analysis of shanks’s algorithm for computing square roots in finitefields.
CRM Proc. and Lecture Notes, Vol. 19 :231–242, 1999.
S. Müller.
On the computation of square roots in finite fields.
J. Design, Codes and Cryptography, vol. 31 :301–312, 2004.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
D. Shanks.
Five number-theoretic algorithms.
Proceedings of the second Manitoba conference on numerical
mathematics, pages 51–70, 1972.
A. Tonelli.
Bemerkung uber die auflosung quadratischer congruenzen.
Götinger Nachrichten, pages 344–346, 1891.
Context Extensions impaires Extensions paires Comparaisons numériques Résumé
MERCI DE VOTRE ATTENTION !
Recommended