# Scalar Multiplication over extension field

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 close merge delete

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

( 2018-09-11 09:17:26 +0200 )edit

Sort by ยป oldest newest most voted

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.

more