La relation (a) montre que l'on peut savoir si Q = [1/2]P ou Q = [1/2]P + T2 en regardant si les coordonnées de QI, appartiennent à F2" ou à un sur-corps de FZ" . Comme QI est déterminé par les équations (i), (ii) et (iii), nous avons à étudier les opérations utilisées dans la résolution de ces équations qui ne sont pas internes au corps, mais ont leur résultat dans un sur-corps de FZ" . Le seul cas possible est celui de la résolution de l'équation du 2"d. degré (i) : on doit aussi calculer une racine carrée pour calculer la 1e'e coordonnée de QI, mais en caractéristique 2 la racine carrée est une opération interne au corps. On a donc Q=(u,v) =[1/2]P 3Â E F2" :Â2+A=a+u Cette condition nécessaire et suffisante s'écrit aussi, puisque la racine carrée est interne au corps Q = (u, v) = [1/2] P 3Â E F2" : #Z 2 + /. = a2 + u2 La relation précédente permet d'optimiser l'algorithme énoncé ci-dessous dans les cas où le temps de calcul de la racine carrée n'est pas négligeable. Pour P E G, les 2 solutions de (i) sont Â [1,2]p et Â, [1/21p + 1, et on déduit de (ii) que les 1ères coordonnées des points associés sont u et (u + #x_). On peut donc en déduire un algorithme permettant de calculer [112]P de la façon suivante Si F2" est un corps fini de 2n éléments, E (F " ) est le sous-groupe d'une courbe elliptique E, défini par E(F2., ) = @(x,y) E F2" X F2" 1y2 + xy = x3 + axe + @} U {O} aI@ E F2" O et E[21] est l'ensemble des points P de ladite courbe elliptique tels que P, additionné 2 1 fois à lui même donne l'élément neutre O avec k entier supérieur ou égal à 1, alors, un point P = (x,y) de ladite courbe elliptique donne par ladite division par deux le point P= (uo, vo) de ladite courbe elliptique, obtenu en effectuant les opérations suivantes # on cherche une première valeur Â,, telle que X^2 +#=#+X # on calcule une seconde valeur uô telle que uô = x (X^ + 1) + y # si k vaut 1, on cherche si l'équation : Â. 2+Â =a2 + Uô a des solutions dans F Z" # dans l'affirmative on calcule ladite division par deux par vo = Uo (U0 + Io) et # dans la négative, on ajoute x à ladite deuxième valeur uo2 et on ajoute 1 à ladite première valeur Xo pour calculer ladite division par deux comme dans l'opération précédente; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur. i, telle queÂ i 2 + @,i = a + ui-J puis calculer la valeur u2; telle que U2i = u;_, (@,i + + ui-1 +1) en incrémentant i à partir de i=1 jusqu'à obtenir la valeur u k_ 1 2 # on cherche si l'équation @,2 + X = a2 + u2 k-, a des solutions dans FZ# dans l'affirmative on calcule ladite division par deux par vo =Uo(Uo+@o) et # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur a., pour calculer ladite division par deux comme dans l'opération précédente. Si on choisit de représenter le point = (u., vo) de la courbe elliptique par (uo,,Io) avec @,o = uo + vo lu, alors l'algorithme devient # on cherche une première valeur X,, telle que 2 + #,o = a + x # on calcule une seconde valeur uô telle que : uô = x (%,o+ 1)+ y, # si k vaut 1, on cherche si l'équation : 2,2o +X, =a' +u'o a des solutions dans F Z" , # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uo2 et on ajoute 1 à ladite première valeur a,, pour calculer ladite division par deux comme dans l'opération précédente, # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur,; , telle que Â.; 2 + 1; = a + u;_1 puis calculer la valeur u;2 telle que u? = u;_1 (a,; + 1;_1 + u;-1 +1) en incrémentant i à partir de i = 1 jusqu'à obtenir la valeur u2 k_1 # on cherche si l'équation ;,2 + 1. = a2 + U2 k-, a des solutions dans F Z" # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur @,o pour calculer ladite division par deux comme dans l'opération précédente.