Scalar Multiplication over extension field

edit

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.