#4964: [with patch, needs review] Add Weil pairing to Sage
-------------------------------------+--------------------------------------
Reporter: dmhansen | Owner: mollerhansen
Type: enhancement | Status: reopened
Priority: minor | Milestone: sage-3.3
Component: algebraic geometry | Resolution:
Keywords: pairing, elliptic curve |
-------------------------------------+--------------------------------------
Comment (by dmhansen):
> I have one suggestion which should speed this up whenever the actual
orders of P or Q are strictly less than n: find the orders of P and Q,
say m1 and m2. (The generic function order_from_multiple might be useful
here.) Let d=gcd(m1,m2). Then it is clear that the result is a d'th
root of unity, and it can be computed by taking the pairing of (m1/d)*P
and (m2/d)*Q. [Proof: exercise.] This would save a lot when d is much
less than n.
Yes, I agree - for now the only thing implemented is for points of order
n, I check that they both are of order n, which actually will take some
time for large n. There is definitely room for improvement here!
> I also have a question: rather than wait for a division by zero error to
catch dependent input, why not do a discrete log calculation to test this?
Maybe that's much slower for large n; it would be nice to have this
decision justified.
Well, it is much slower for large n to do discrete log computations. Wrt.
to time complexity then I do not think we can do better since the miller
algorithm runs in linear time in the number of bits in the input n.
You're right the above argument should be noted in the code.
Replying to [comment:6 cremona]:
> This looks pretty good to me though I have not done any detailed
testing, I only looked at the code.
>
> I have one suggestion which should speed this up whenever the actual
orders of P or Q are strictly less than n: find the orders of P and Q,
say m1 and m2. (The generic function order_from_multiple might be useful
here.) Let d=gcd(m1,m2). Then it is clear that the result is a d'th
root of unity, and it can be computed by taking the pairing of (m1/d)*P
and (m2/d)*Q. [Proof: exercise.] This would save a lot when d is much
less than n.
>
> I also have a question: rather than wait for a division by zero error to
catch dependent input, why not do a discrete log calculation to test this?
Maybe that's much slower for large n; it would be nice to have this
decision justified.
>
> Sorry, that's all I have time for just now.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4964#comment:7>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
