Racines Carr s dans les Extensions Quadratiques de Corps Finisdelta.cs.cinvestav.mx/~francisco/goraM.pdf · 2016-08-10 · L’Algorithme 4 de Tonelli-Shanks [6] a une complexité

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


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


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).


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.


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).


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é


√· 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


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.


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



PRECALCUL

1: t← 2q−5

8 .

CALCUL

1: a1 ← aq−5

8 .

2: a0 ← (a21a)

2.3: Si a0 = −1 Alors


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.


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.


L’algorithme de Kong pour q ≡ 9 (mod 16)

Algorithme 3 Algorithme de Kong pour q ≡ 9 (mod 16)



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


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.


Algorithmes Généraux pour q ≡ 1 (mod 16)

Algorithme 4 Algorithme de Tonelli-Shanks

Entrée: a ∈ F∗q


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


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.



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.



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.



Algorithme 6 Algorithme de Müller [4]



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


20: Retourner x.



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.


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)



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.


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.



Algorithme 8 Racine carrée dans Fq2 , avec q ≡ 1 (mod 4)

Entrée: a ∈ F∗q2 .


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


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.



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.



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.


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 .


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


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


√· 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


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


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.


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.


MERCI DE VOTRE ATTENTION !

Documents

Racines Carr s dans les Extensions Quadratiques de Corps Finisdelta.cs.cinvestav.mx/~francisco/goraM.pdf · 2016-08-10 · L’Algorithme 4 de Tonelli-Shanks [6] a une complexité