#10523: Make Weil pairing polynomial time
-------------------------------+--------------------------------------------
Reporter: djao | Owner: somebody
Type: defect | Status: new
Priority: major | Milestone: sage-4.6.1
Component: elliptic curves | Keywords: Weil pairing, elliptic curves
Author: David Jao | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
The Weil pairing implementation in Sage is horribly inefficient when the
group order n is a cryptographically large composite integer.
The implementation is based on Miller's algorithm, which in its original
version is a polynomial time algorithm, capable of handling large
composite values of n. However, the Sage implementation attempts to
determine the order of the input points P and Q. The problem of
determining the order of a point on an elliptic curve of large composite
order is conjectured to be computationally infeasible (Boneh-Goh-Nissim
TCC'05), and all known methods for solving this problem require factoring
n.
Therefore, by adding the order computation, the Weil pairing calculation
is transformed from a polynomial time algorithm to a superpolynomial time
algorithm requiring the factorization of n.
I propose to delete the code block that contains the order computation,
since the order computation is not useful when n is prime, and is
inefficient when n is composite. Note that we still check to ensure P and
Q are n-torsion -- this patch simply deletes the code to compute their
exact order. The attached file implements this change.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10523>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
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.
