Opened 3 years ago
Closed 3 years ago
#24844 closed defect (fixed)
Some elliptic curve functions do not set a point's order
Reported by:  cremona  Owned by:  

Priority:  minor  Milestone:  sage8.2 
Component:  elliptic curves  Keywords:  points order 
Cc:  erkan.tairi@…  Merged in:  
Authors:  John Cremona  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  5367558 (Commits, GitHub, GitLab)  Commit:  5367558b6a6285a7e7f46780486447e9a2787505 
Dependencies:  Stopgaps: 
Description
sage: p=next_prime(1000000) sage: E=EllipticCurve(GF(p), 123, 456) sage: pts = E(0).division_points(3) sage: P=pts[1]; P (389063 : 124244 : 1) sage: sage: P._order ... AttributeError: 'EllipticCurvePoint_finite_field' object has no attribute '_order' sage: P.order() 3 sage: P._order 3 sage:
Here one might expect the point P's _order attribute to be set to 3 on construction since this can be deduced from what is known.
Change History (13)
comment:1 Changed 3 years ago by
 Branch set to public/24844
 Commit set to 3ebb1ce534ce42d002ba32625833fc35db871ef0
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
There are more cases where the order can be deduced with no work. At a minimum therefore I would do these:
 nothing if self's order not set;
 if self's order is infinity set order to infinity;
 if self's order=n and m=1 then set order=n (obvious special case).
Otherwise the order is n*k where k divides m and all possibilities are possible. [Note that the first version in commit 3ebb1c is not quite correct since one of the returned points is 0.] It would be possible to find the order k of n*Q for each returned point Q and set the order of Q to n*k, given that k is known to divide m.
comment:3 Changed 3 years ago by
More thoughts: we currently never set the order of a point computed via addition, subtraction or even negation. The latter is uncontroversial! The general case is probably too much since if you add two points of infinite order the result in principle could have any finite order, and even if the summands both have finite order then the sum could have any order dividing the lcm of those.
Hence I am now inclined to do less than was suggested in comment 2, but a little more than is in the first commit, namely if you divide E(0) by m then (since it safe to assume that m is easily factorisable when that succeeds) all points returned can have their actual order (dividing m) computed and set, using the generic order_from_multiple() function.
comment:4 Changed 3 years ago by
 Commit changed from 3ebb1ce534ce42d002ba32625833fc35db871ef0 to 939fdc54209dbafecd969f1d6034282847e4a0b6
Branch pushed to git repo; I updated commit sha1. New commits:
939fdc5  #24844: more general version

comment:5 Changed 3 years ago by
Despite comment 3 I put in an implementation in all cases where the original point's order is already known (or if it 0 in which case we set its order to 1). This is quite simple and cheap. Note that m must be small or earlier steps in the division_points() function will already take too long so the additional step is negligible.
I just thought of one more thing to add before setting to "needs review".
comment:6 Changed 3 years ago by
 Commit changed from 939fdc54209dbafecd969f1d6034282847e4a0b6 to 39c54806f0233e899b0d754963f474ae2bcf21fe
Branch pushed to git repo; I updated commit sha1. New commits:
39c5480  #24844: small tweak to avoid repeat factoring of m

comment:7 Changed 3 years ago by
comment:8 followup: ↓ 9 Changed 3 years ago by
I think you should add a test for the infinite order case, please.
comment:9 in reply to: ↑ 8 Changed 3 years ago by
 Status changed from needs_review to needs_work
Replying to chapoton:
I think you should add a test for the infinite order case, please.
OK  will do. (I'll also add you as an author, sorry if I deleted you by mistake.)
comment:10 Changed 3 years ago by
 Commit changed from 39c54806f0233e899b0d754963f474ae2bcf21fe to 5367558b6a6285a7e7f46780486447e9a2787505
Branch pushed to git repo; I updated commit sha1. New commits:
5367558  #24844: added more tests

comment:11 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:12 Changed 3 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, thanks. No need to list me as an author.
comment:13 Changed 3 years ago by
 Branch changed from public/24844 to 5367558b6a6285a7e7f46780486447e9a2787505
 Resolution set to fixed
 Status changed from positive_review to closed
here is a naive tentative for a start, feel free to take over and enhance
New commits:
trac 24844 setting the order of a point of known order on elliptic curve