Point aléatoire dans l'algorithme d'appariement de Weil de Miller

J'essaie d'implémenter l'algorithme Miller's Weil Pairing mais j'ai un problème.
J'ai utilisé le livre "Une introduction à la cryptographie mathématique" de Hoffstein, Pipher et Silverman et j'ai essayé mon implémentation avec l'exemple donné dans le livre:

J'obtiens la même réponse donc les calculs devraient être bons mais j'ai un problème pour choisir un point aléatoire S. Dans le livre, il est indiqué qu'il faut choisir un point S non dans {O,P,-Q,PQ}.
Mais avec cette équation:
j'essaie de calculer e(P,Q) avec P = (1,5) et Q = (12,2) d'ordre 9 mais il y a toujours une erreur à un instant car le résultat de la fonction de Miller est 0/0. -Q = (12,11) et PQ = (9,6) donc j'ai essayé avec tous les autres points et ça ne marche pas avec des points du même ordre ce qui est normal. (9,6) et (9,7) sont les seuls à avoir un ordre différent: 3. Comme (9,6) ne peut pas être choisi j'ai pris (9,7) mais j'obtiens quand même des 0 qui posent problème.
Quelqu'un peut-il me dire ce que j'ai mal fait ou ce que je n'ai pas compris?


Merci

Voici le code:

def g(p, q, r, curve):
modulo = curve.p
if p.x is None and p.y is None:
 return (r.x - q.x) % modulo
if q.x is None and q.y is None:
 return (r.x - p.x) % modulo
if p!= q and p.x == q.x:
 return (r.x - p.x) % modulo
l = slope(p, q, curve)
num = (r.y - p.y - l*(r.x - p.x)) % modulo
denom = (r.x + p.x + q.x - l**2) % modulo
return (num * mult_inverse(denom, modulo)) % modulo
def miller_algorithm(p, q, m, curve):
f = 1
t = copy(p)
n = list(bin(m)[2:])
for i in range(1,len(n)):
 f = (f**2) * g(t, t, q, curve)
 t = t.double_and_add(2)
 if n[i] == '1':
 f = f * g(t, p, q, curve)
 t = t.add(p)
return f % curve.p
def weil_pairing(p, q, curve):
if p == q or (p.x is None and p.y is None) or (q.x is None and q.y is None):
 return 1
m = q.order()
s = curve.random_point()
while s == p or s == q.neg() or s == (p.sub(q)) or s.order() == m:
 s = curve.random_point()
fpnum = miller_algorithm(p, q.add(s), m, curve)
fpdenom = miller_algorithm(p, s, m, curve)
fqnum = miller_algorithm(q, p.sub(s), m, curve)
fqdenom = miller_algorithm(q, s.neg(), m, curve)
modulo = curve.p
num = (fpnum * mult_inverse(fpdenom, modulo)) % modulo
denom = (fqnum * mult_inverse(fqdenom, modulo)) % modulo
return (num * mult_inverse(denom, modulo)) % modulo

Solution du problème

Je ne peux pas vous dire ce que vous faites de mal. Mais, le programme python sagemath a une implémentation de l'algorithme de Miller et de tous les appariements, weil, tate et ate. Si vous l'installez, vous pouvez trouver le code source de miller et weil dans le fichier ell_point.py. L'algorithme est plus général, et donc plus complexe, que votre implémentation, mais vous devriez pouvoir traduire pour obtenir ce que vous voulez. Ou, vous pouvez simplement importer sagemath et utiliser ses implémentations.