Ask Your Question

Calculating the order of an Elliptic Curve fails.

asked 2018-09-25 18:05:43 -0500

pottzman gravatar image

updated 2018-10-05 04:03:25 -0500

FrédéricC gravatar image

Hi. I would like to calculate the order of the base point on an Elliptic Curve. Some curves are successful while some fail. Here are two examples and their parameters. The first example is successful, the second is not.

Example 1.

p = 10562920556476600174223203553624763158759224241690200395609486946570543757980521851146458516500451409335864053457189473296570712977858859585999979839497081

a = 1

b = 0

E = EllipticCurve(GF(p), [a, b])

Gx = 7001153264502603531568809091006890066238093206490706740054133060198019760090859987689015805782317128823647585142349315457499198272662472818714043462452903

Gy = 5379780378477219053711555876878459214243674711784518156355184015695786277532464885846858297098947964642836892714492422913471742703229817151186461774623684

G = E(Gx, Gy)

Q = G.order()

Q = 5532044755580494717

Example 2.

p = 8245498483844445086274997696534494324318871629323439587180432555305925857658196874670618312457436840885370130522487176480691396150486059031119600012524801

a = 1

b = 0

E = EllipticCurve(GF(p), [a, b])

Gx = 7273571546843413099993191994471155206649636421268389195048812757571665656628711965470673099293494650775090608549703675296316887753017258939382696588767431

Gy = 3529068830277582088596828423990199939817342479929127252014627303069162247307070606247527579307935679046819531543049464667736359244475241042487530444236684

G = E(Gx, Gy)

Q = G.order()

* Warning: MPQS: number too big to be factored with MPQS, giving up.

both these two curves are working curves. but why does sage fail to calculate the second curves order of G? Is it a limitation of sage itself? Is there any other way to calculate the order without using MPQS method?

edit retag flag offensive close merge delete


sorry. think I got some parameters mixed up. it looks right now

pottzman gravatar imagepottzman ( 2018-09-28 05:12:43 -0500 )edit

1 answer

Sort by » oldest newest most voted

answered 2020-05-28 11:21:33 -0500

John Cremona gravatar image

In the second example the curve has cardinality 8245498483844445086274997696534494324318871629323439587180432555305925857658038158971493931464052751511244450366220997579222992221013001791913941608268032 which is hard to factor. The computation of the order of a point will be trying to factor it.

How would you find the order of the point? Suppose the group order is n=a*b where a and b are primes, but you do not know this factorization, and I give you a point of order a. How could you find that order more easily than factoring n?

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2018-09-25 18:05:43 -0500

Seen: 185 times

Last updated: May 28