Ask Your Question
0

How to convert coordinates of a point from y^2=x^3+7 curve to y^2=x^3+4 curve?

asked 2020-08-25 15:32:10 -0500

Duglas gravatar image

updated 2020-08-25 16:03:39 -0500

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

E4 = EllipticCurve(GF(p), [0,4])

E7 = EllipticCurve(GF(p), [0,7])

base_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

base_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

#Basepoint of $y^2=x^3+7$

BP = E7(base_x, base_y, 1)$

#Point on $y^2=x^3+7$

Q=BP * x

Q = E([81119306557295043947776230900539651493257160932663731932698523086255548483211,69833235478127881789123626297864036834549011744885041054439092651501655231589])

#base point of $y^2=x3+4$

BasePoint2( [44959049921401095561708555029356671875656137150174062590365663013295388555357, 83434812528180346320431259926231725911951822121210091498845843183726829396473])

  • How to convert coordinates of $Q(x,y)$ on $y^2=x3+7$ to coordinates in $y^2=x3+4$ ? Code needed(SAGE, Python etc.).
edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2020-09-04 20:03:08 -0500

dan_fulea gravatar image

The question is "not well defined" to have a mild answer.

Here i suppose that "converting" a point from one elliptic curve to an other one should be given by some structural map between the curves. However the two curves are not isomorphic. (There is also no map from one curve to the other one preserving the addition on both curves.) To see this let us observe some facts.

  • The curve $E_7$ given by the (affine) equation $y^2=x^3+7$ over $\Bbb F_p$, $p$ being the prime $p=2^{256}-2^{32}-977$, is known and related with the bitcoin avatar. Here is a link where we also have the order of $E(\Bbb F_p)$:

http://www.math.canterbury.ac.nz/~f.voloch/Pdfs/bittalk.pdf

  • This order is $N = 2^{256} - 432420386565659656852420866394968145599$.
  • This is a prime number. But it is not the order of the other curve from the OP, $E_4$ given by the (affine) equation $y^2=x^3+4$ over $\Bbb F_p$.

  • The following pieces of code support the above claims.

    p = 2^256 - 4294968273
    E4 = EllipticCurve(GF(p), [0, 4])
    E7 = EllipticCurve(GF(p), [0, 7])
    
    base_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
    base_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
    
    P7 = E7.point( (base_x, base_y) )
    P4 = E4.random_point()
    
    N = 2^256 - 432420386565659656852420866394968145599
    NP7 = N*P7
    
    print(f"Is N prime? {N.is_prime()}")
    print(f"N * P7 = {NP7}")
    print("Is N * P4 = 0 on E4? {}".format(N*P4 == E4(0)))
    
  • The above delivers:

    Is N prime? True
    N * P7 = (0 : 1 : 0)
    Is N * P4 = 0 on E4? False
    
  • Note also the following:

    sage: E7.is_isomorphic(E4)
    False
    sage: E7.is_isogenous(E4)
    False
    

A final note, motivated by the question in:

https://crypto.stackexchange.com/questions/83542/how-to-convert-coordinates-o-a-point-from-y2-x37-to-y2-x34

(This question is also hard to understand, but it mentions the elliptic curves over the same field $\Bbb F_p$ with equations $y^2=x^3+k$ for "small" values of $k$, say $k=1,2,3,4$...)

Among these curves some are isomorphic to $E_7$. This happens for the following values of $k$:

sage: for k in range(1, 30):
....:     if E7.is_isomorphic(EllipticCurve(GF(p), [0, k])):
....:         print(k)
....: 
7
12
20
23
26
sage:

Note that these are exactly the values of $k$ such that there exists in the multiplicative group $\Bbb F_p^\times$ a root of order $6$ of the quotient $7/k$.

sage: for k in range(1, 30):
....:     v = GF(p)(k)/7
....:     print(f"{k}/7 has order {v.multiplicative_order().factor()}")
....: 
1/7 has order 2 * 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
2/7 has order 2 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
3/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
4/7 has order 2 * 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
5/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
6/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
7/7 has order 1
8/7 has order 2 * 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
9/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
10/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
11/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
12/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
13/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
14/7 has order 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
15/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
16/7 has order 2 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
17/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
18/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
19/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
20/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
21/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
22/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
23/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
24/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
25/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
26/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
27/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
28/7 has order 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
29/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
sage:

(Exactly those $k$ lead to isomorphic curves for which the order of $k/7$ is lacking the factors $2$ and $3$.)

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

1 follower

Stats

Asked: 2020-08-25 15:32:10 -0500

Seen: 50 times

Last updated: Sep 04