Ask Your Question
0

Scalar Multiplication over extension field

asked 2018-09-06 10:16:19 -0600

santoshi gravatar image

updated 2018-09-09 17:26:23 -0600

slelievre gravatar image

I want to perform scalar multiplication but when i will take some random point and order of that point as scalar it gives me error.

import time
import sys
from sage.all import *
p = (2^113); p

F1.<x, y> = GF(2)[]

F.<a> = GF(2^113, 'a', modulus=x^113+x^9+1); F.modulus(); F
A = F.fetch_int(0x003088250CA6E7C7FE649CE85820F7); A
B = F.fetch_int(0x00E8BEE4D3E2260744188BE0E9C723); B

E = EllipticCurve(F, (1, A, 0, 0, B)); E
G = E.random_point()
n = E.order()
K = randint(1, n - 1)
R = K*G
edit retag flag offensive close merge delete

Comments

Did you mean n = G.order() instead of n = E.order()?

slelievre gravatar imageslelievre ( 2018-09-11 02:17:26 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2018-09-06 16:02:30 -0600

dan_fulea gravatar image

updated 2018-09-06 16:04:16 -0600

Let us consider only the needed lines of code, so we introduce

  • the polynomial ring R$=\Bbb F_2[x]$ in the indeterminate $x$,
  • then the field $F=\Bbb F_2(a)=\Bbb F_2[x]/(x^{113}+x^9+1)$,
  • then some very special elliptic curve $E$ over $F$.

It is well known that computing the order of an elliptic curve over some large field is time consuming. So the line computing the order

E.order()

takes too much time. (Please state the question clearly next time. It is also a good practice to introduce only variables and imports that matter for the issue. Providing "clean code" is a big help for potential helpers.)

R.<x> = GF(2)[]

F.<a> = GF(2^113, modulus=x^113+x^9+1)
A = F.fetch_int( 0x003088250CA6E7C7FE649CE85820F7 )
B = F.fetch_int( 0x00E8BEE4D3E2260744188BE0E9C723 )

E = EllipticCurve(F, (1,A,0,0,B))
G = E.random_point()
# n = E.order()    # takes a looong time...

(Note: The question should be part of the text, not part of the title (only).)

The problem with the "scalar multiplication" does not exist. Of course, we do not have the n, and also do not need it for the scalar multiplication issue. Instead, let us take for K some random integer from $1$ to $2^{113}$.

# K = randint(1,n-1)    # we do not have n...
K = randint( 1, 2^113 )
print K
print G
print K*G

And this time i've got a mess of the shape:

5495233727832544069405938042720667
(a^112 + a^111 + a^110 + a^108 + a^105 + a^98 + a^96 + a^94 + a^92 + a^91 + a^89 + a^88 + a^86 + a^85 + a^83 + a^80 + a^79 + a^77 + a^74 + a^72 + a^71 + a^69 + a^68 + a^67 + a^66 + a^65 + a^60 + a^58 + a^57 + a^55 + a^54 + a^53 + a^52 + a^51 + a^50 + a^48 + a^46 + a^45 + a^44 + a^41 + a^40 + a^39 + a^38 + a^37 + a^35 + a^34 + a^33 + a^28 + a^27 + a^26 + a^25 + a^23 + a^22 + a^18 + a^17 + a^16 + a^12 + a^11 + a^10 + a^8 + a^6 + a^2 + a : a^112 + a^110 + a^107 + a^106 + a^104 + a^102 + a^101 + a^100 + a^96 + a^93 + a^92 + a^91 + a^86 + a^84 + a^83 + a^81 + a^79 + a^78 + a^76 + a^75 + a^74 + a^73 + a^72 + a^67 + a^65 + a^64 + a^54 + a^52 + a^51 + a^47 + a^46 + a^44 + a^43 + a^42 + a^38 + a^36 + a^33 + a^32 + a^28 + a^27 + a^23 + a^22 + a^21 + a^17 + a^13 + a^12 + a^11 + a^10 + a^9 + a^8 + a^7 + a^6 + a^5 + a^4 + a^2 + a + 1 : 1)
(a^112 + a^110 + a^109 + a^108 + a^104 + a^101 + a^98 + a^96 + a^95 + a^93 + a^92 + a^91 + a^89 + a^84 + a^82 + a^80 + a^73 + a^69 + a^67 + a^63 + a^61 + a^58 + a^54 + a^53 + a^52 + a^50 + a^48 + a^47 + a^46 + a^45 + a^43 + a^42 + a^39 + a^38 + a^37 + a^35 + a^33 + a^31 + a^28 + a^22 + a^21 + a^19 + a^18 + a^17 + a^16 + a^13 + a^9 + a^8 + a^7 + a^5 + a^4 + a^3 : a^109 + a^106 + a^105 + a^104 + a^103 + a^98 + a^96 + a^95 + a^94 + a^93 + a^91 + a^89 + a^87 + a^86 + a^85 + a^82 + a^81 + a^80 + a^78 + a^76 + a^75 + a^74 + a^73 + a^68 + a^67 + a^65 + a^64 + a^63 + a^61 + a^60 + a^58 + a^56 + a^53 + a^52 + a^51 + a^50 + a^48 + a^46 + a^42 + a^41 + a^40 + a^39 + a^38 + a^37 + a^33 + a^31 + a^29 + a^28 + a^27 + a^24 + a^23 + a^22 + a^20 + a^17 + a^16 + a^15 + a^11 + a^10 + a^9 + a^7 + a^5 + a^4 + a^3 + a^2 + a + 1 : 1)

Note: Please try next time(s) to provide code in a "minimal situation" that produces the same error.

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

Stats

Asked: 2018-09-06 10:16:19 -0600

Seen: 63 times

Last updated: Sep 09