1
$\begingroup$

Consider the elliptic curve $E_1: y^2 = x^3+7$ over $\mathbb F_{17}$ with the base point $G=(15, 13)$
and the second elliptic curve $E_2: y^2 = x^3+7$ over $\mathbb F_{31}$ with the same base point $G=(15, 13)$.

My question is: is there any way to calculate the equivalent point of $\mathbb F_{31}$ based on $\mathbb F_{17}$?

For example: with $7G = (10, 15)$ of curve $\mathbb F_{17}$, how to calculate $7G$ of $\mathbb F_{31}$? The result should be $7G = (12, 14)$ on $\mathbb F_{31}$.

Below are all points of the two curves:

#----Curve F17-------#
  1G       2G       3G       4G       5G       6G       7G       8G       9G      10G      11G      12G      13G      14G      15G      16G     17G
(15,13)  ( 2,10)  ( 8, 3)  (12, 1)  ( 6, 6)  ( 5, 8)  (10,15)  ( 1,12)  ( 3, 0)  ( 1, 5)  (10, 2)  ( 5, 9)  ( 6,11)  (12,16)  ( 8,14)  ( 2, 7)  (15, 4)

#----Curve F31-------#
  1G       2G       3G       4G       5G       6G       7G       8G       9G      10G      11G      12G      13G      14G      15G      16G      17G      18G      19G      20G      21G      22G      23G      24G      25G      26G      27G      28G      29G      30G      31G
(15,13)  (29,17)  ( 1,22)  (20,19)  (21,17)  (23,23)  (12,14)  (11,27)  (25,22)  ( 7,19)  (27,27)  ( 5, 9)  ( 0,24)  ( 4,12)  (22,23)  ( 3,13)  (13,18)  (17,23)  (24, 4)  (24,27)  (17, 8)  (13,13)  ( 3,18)  (22, 8)  ( 4,19)  ( 0, 7)  ( 5,22)  (27, 4)  ( 7,12)  (25, 9)  (11, 4)
$\endgroup$
5
  • 1
    $\begingroup$ The second basepoint seems wrong. One has isomorphic to $Z/18$ the other one $Z/21$. How do you expect this? Where did you get this results? $\endgroup$ – kelalaka Apr 13 at 9:27
  • $\begingroup$ E = EllipticCurve(GF(31),[0,7]) print(E) print(E.order()) print(E.abelian_group()) G = E(25,15) for i in (1..E.order()): print(i*G) $\endgroup$ – kelalaka Apr 13 at 9:41
  • $\begingroup$ G = E.lift_x(15) ValueError: No point with x-coordinate 15 on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 31 $\endgroup$ – kelalaka Apr 13 at 9:42
  • $\begingroup$ Indeed the question's $G$ is not on curve $E_2$, and the question's curves have no common point (save for the identity). Also their order is not prime, contrary to the customary choice in crypto for curves on prime fields in Weierstrass form. We can fix this with $E_1$ on $\mathbb F_{43}$ of order $31$, $E_2$ on $\mathbb F_{67}$ of order $79$, sharing the point $G=(21,25)$. If the answer is "yes", I want to know! $\endgroup$ – fgrieu Apr 13 at 10:45
  • $\begingroup$ Hi there, I just started to learn elliptic curves, so probably I had chosen the wrong prime number. Now, if I follow your pattern " E1 on F43 of order 31, E2 on F67 of order 79, sharing the point G=(21,25)". could you please teach me how to map point between E1 and E2. $\endgroup$ – Roland Apr 13 at 11:35
0
$\begingroup$

I wrote this since it is too long to comment;

First the SageMath code

K =  GF(43)
E = EllipticCurve(K,[0,7])
print(E)
print(E.order())
print(E.abelian_group())

G = E(21,25)

With $K$ one can use different fields, the $[a=0,b=7]$ is for $y^2 = x^3 + ax + b$.

This codes give us a lot of information about the curve

  1. print(E) : The curve information:

    Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43

  2. E.order() : Print the number of the rational points on the curve: 31

  3. E.abelian_group(): The group structure of the curve: Additive abelian group isomorphic to Z/31 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43

The last one is important since to exactly map a point $g$ and its multiples, they must have the same order in each group.

Actually, to map a curve to another, or a subgroup, one doesn't need the same $G$ to happen in both. The order is enough. We have to look for orders of the elements.

Let's look at your curves;

  1. EllipticCurve(GF(17),[0,7])

    • Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 17
    • 18
    • Additive abelian group isomorphic to Z/18 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 17
  2. E = EllipticCurve(GF(31),[0,7])

    • Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 31
    • 21
    • Additive abelian group isomorphic to Z/21 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 31
  3. E = EllipticCurve(GF(43),[0,7])

    • Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43
    • 31
    • Additive abelian group isomorphic to Z/31 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43
  4. E = EllipticCurve(GF(67),[0,7])

    • Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 67
    • 79
    • Additive abelian group isomorphic to Z/79 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 67

They are all isomorphic to $Z/18,Z/21,Z/31,$and $Z/79$, respectively.

The orders;

for i in (1..E.order()):
    print(E[i], E[i].order())
  • In the first curve, the orders of the elements are $1,3,2,6,9,18$
  • In the second curve, the orders of the elements are $1,3,7,21$

So, we have common order of $3$, then we can map these elements (5,8) and $(0,10)$ to each other.


A sample curve that is not isomorphic Z/n

E = EllipticCurve(GF(25, 'x'), [1, 1])

  • Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 5^2
  • 27
  • Additive abelian group isomorphic to Z/9 + Z/3 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 5^2

Birational Equivalent is another story!

$\endgroup$
7
  • $\begingroup$ I don't get what follows "then" in "So, we have common order of 3, then we can map these elements (5,8) and (0,10) to each other." $\endgroup$ – fgrieu Apr 13 at 13:18
  • $\begingroup$ @fgrieu these two points have order 3 in their curve group, then we can map these; $G=(5,8)$ and $H=(0,10)$ then $[2]G$ to $[2]H$ and $[3]G=\mathcal{O}$ $\endgroup$ – kelalaka Apr 13 at 13:24
  • $\begingroup$ I am very grateful for all of your support. $\endgroup$ – Roland Apr 13 at 14:20
  • $\begingroup$ @kelalaka Could you please show me the formula to calculate (0,10) from (5,8) ? Thank you very much for your help. $\endgroup$ – Roland Apr 13 at 14:35
  • $\begingroup$ Nothing special, just map (0,10) to (5,8), the (0,10) is a point in the second curve, (5,8) is in the first. There is no special structure here. Maybe you are asking the wrong question? Maybe are you looking the biratinal equivalence of the curve like the Montgomery and Twisted Edward curves? $\endgroup$ – kelalaka Apr 13 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.