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: sage-8.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:

Status badges

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 chapoton

  • Branch set to public/24844
  • Commit set to 3ebb1ce534ce42d002ba32625833fc35db871ef0
  • Status changed from new to needs_review

here is a naive tentative for a start, feel free to take over and enhance


New commits:

3ebb1cetrac 24844 setting the order of a point of known order on elliptic curve

comment:2 Changed 3 years ago by cremona

There are more cases where the order can be deduced with no work. At a minimum therefore I would do these:

  1. nothing if self's order not set;
  2. if self's order is infinity set order to infinity;
  3. 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 cremona

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 git

  • 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 cremona

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 git

  • 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 cremona

  • Authors set to John Cremona

comment:8 follow-up: Changed 3 years ago by chapoton

I think you should add a test for the infinite order case, please.

comment:9 in reply to: ↑ 8 Changed 3 years ago by cremona

  • Authors changed from John Cremona to Frederic Chapoton, John Cremona
  • 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 git

  • 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 cremona

  • Status changed from needs_work to needs_review

comment:12 Changed 3 years ago by chapoton

  • Authors changed from Frederic Chapoton, John Cremona to John Cremona
  • 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 vbraun

  • Branch changed from public/24844 to 5367558b6a6285a7e7f46780486447e9a2787505
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.