ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 19 Aug 2020 21:09:43 +0200elliptic curve scalar multiplicationhttps://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/ kindly provide me the code for left to right double and add scalar multiplication for following characteristics of elliptic curve for the following parameter. prime field P=37, A=7 B=25 G=(33,9) n=21Thu, 29 Mar 2018 07:31:23 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/Comment by santoshi for <p>kindly provide me the code for left to right double and add scalar multiplication for following characteristics of elliptic curve for the following parameter. prime field P=37, A=7 B=25 G=(33,9) n=21</p>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41823#post-id-41823tx for your reply but i want the compution using above algorithm. also by defining function point_mul(k,p)
where k is scalar and p is the point.Thu, 29 Mar 2018 17:06:09 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41823#post-id-41823Comment by dan_fulea for <p>kindly provide me the code for left to right double and add scalar multiplication for following characteristics of elliptic curve for the following parameter. prime field P=37, A=7 B=25 G=(33,9) n=21</p>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41819#post-id-41819In a dialog with the sage interpreter, by "coincidence", the following data ould be digested:
sage: E = EllipticCurve( GF(37), [7, 25] )
sage: G = E.point( [33, 9] )
sage: 21*G
(0 : 1 : 0)
sage: E.order().factor()
2 * 3 * 7
(I was trying to rather guess the framework.)
What is/are in this context the "left to right double and add scalar multiplication"?
(As seen, sage simply computes the multiplication `21*G`.)Thu, 29 Mar 2018 14:59:04 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41819#post-id-41819Comment by santoshi for <p>kindly provide me the code for left to right double and add scalar multiplication for following characteristics of elliptic curve for the following parameter. prime field P=37, A=7 B=25 G=(33,9) n=21</p>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41836#post-id-41836left to right double and add scalar multiplication algorithm for above parameter
KP=k_0*p+k_1*2p+K_2*4P+.........+K_l*2^l-1*P
I/P point P which is on elliptic curve , K=(k_l-1K_l-2.....K_0)_2 (that is binary representation of scalar)
output KP
uses P and Q
Q= infinity
for i=l-1 to 0 do
Q=2Q
if k_i=1 then
Q=Q+P
return QFri, 30 Mar 2018 17:07:33 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41836#post-id-41836Comment by dan_fulea for <p>kindly provide me the code for left to right double and add scalar multiplication for following characteristics of elliptic curve for the following parameter. prime field P=37, A=7 B=25 G=(33,9) n=21</p>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41826#post-id-41826Which algorithm should be used? (There is no description of an algorithm, no reference for a specific one.) Why not simply use the already implemented sage algorithm?
Note that `21*G` is computed above by using the class method `__mul__` for the class of the instance `G`.
For instance:
sage: G
(33 : 9 : 1)
sage: G.__class__
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: G.__mul__(7)
(1 : 25 : 1)
sage: 7*G
(1 : 25 : 1)
sage: G.__mul__(7) == 7*G
TrueThu, 29 Mar 2018 22:20:03 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41826#post-id-41826Answer by dan_fulea for <p>kindly provide me the code for left to right double and add scalar multiplication for following characteristics of elliptic curve for the following parameter. prime field P=37, A=7 B=25 G=(33,9) n=21</p>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?answer=41840#post-id-41840The following answer does not implement the two functions "add" and "double" on an elliptic curve, instead, it uses the already existing functionality of sage. (It would be too much to implement also these basic functions depending on the form of the elliptic curve and the base field characteristic.)
Code:
def left_to_right_double_and_add(n, G):
"""n is a positive integer number,
G is a rational point of an elliptic curve E,
defined over some finite field F.
This routine computes
n*G
in an ad-hoc manner.
We use the standard add, and doubling on E,
and do not implemented them here.
"""
digits = ZZ(n).digits(base=2)
E = G.curve()
# F = E.base_field()
P = G # this corresponds to 1*G, init
nG = E(0) # and we add further contributions
for digit in digits:
if digit:
nG = nG.__add__(P) # or simply nG += P
P = P.__mul__(2) # or simply P *= 2
# print "\tdigit=%s P=%s nG=%s" % (digit, P, nG)
return nG
# quick test on the given curve with the given poing:
E = EllipticCurve( GF(37), [7, 25] )
G = E.point( [33, 9] )
for n in [1..9]:
nG = left_to_right_double_and_add(n, G)
print ( "sage %s*G = %13s | ad-hoc %s*G = %13s | Are they equal? %s"
% ( n, n*G, n, nG, n*G == nG ) )
This gives in the test:
sage 1*G = (33 : 9 : 1) | ad-hoc 1*G = (33 : 9 : 1) | Are they equal? True
sage 2*G = (9 : 15 : 1) | ad-hoc 2*G = (9 : 15 : 1) | Are they equal? True
sage 3*G = (2 : 11 : 1) | ad-hoc 3*G = (2 : 11 : 1) | Are they equal? True
sage 4*G = (35 : 15 : 1) | ad-hoc 4*G = (35 : 15 : 1) | Are they equal? True
sage 5*G = (15 : 8 : 1) | ad-hoc 5*G = (15 : 8 : 1) | Are they equal? True
sage 6*G = (30 : 22 : 1) | ad-hoc 6*G = (30 : 22 : 1) | Are they equal? True
sage 7*G = (1 : 25 : 1) | ad-hoc 7*G = (1 : 25 : 1) | Are they equal? True
sage 8*G = (31 : 27 : 1) | ad-hoc 8*G = (31 : 27 : 1) | Are they equal? True
sage 9*G = (17 : 32 : 1) | ad-hoc 9*G = (17 : 32 : 1) | Are they equal? True
Fri, 30 Mar 2018 19:29:37 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?answer=41840#post-id-41840Comment by santoshi for <p>The following answer does not implement the two functions "add" and "double" on an elliptic curve, instead, it uses the already existing functionality of sage. (It would be too much to implement also these basic functions depending on the form of the elliptic curve and the base field characteristic.)</p>
<p>Code:</p>
<pre><code>def left_to_right_double_and_add(n, G):
"""n is a positive integer number,
G is a rational point of an elliptic curve E,
defined over some finite field F.
This routine computes
n*G
in an ad-hoc manner.
We use the standard add, and doubling on E,
and do not implemented them here.
"""
digits = ZZ(n).digits(base=2)
E = G.curve()
# F = E.base_field()
P = G # this corresponds to 1*G, init
nG = E(0) # and we add further contributions
for digit in digits:
if digit:
nG = nG.__add__(P) # or simply nG += P
P = P.__mul__(2) # or simply P *= 2
# print "\tdigit=%s P=%s nG=%s" % (digit, P, nG)
return nG
# quick test on the given curve with the given poing:
E = EllipticCurve( GF(37), [7, 25] )
G = E.point( [33, 9] )
for n in [1..9]:
nG = left_to_right_double_and_add(n, G)
print ( "sage %s*G = %13s | ad-hoc %s*G = %13s | Are they equal? %s"
% ( n, n*G, n, nG, n*G == nG ) )
</code></pre>
<p>This gives in the test:</p>
<pre><code>sage 1*G = (33 : 9 : 1) | ad-hoc 1*G = (33 : 9 : 1) | Are they equal? True
sage 2*G = (9 : 15 : 1) | ad-hoc 2*G = (9 : 15 : 1) | Are they equal? True
sage 3*G = (2 : 11 : 1) | ad-hoc 3*G = (2 : 11 : 1) | Are they equal? True
sage 4*G = (35 : 15 : 1) | ad-hoc 4*G = (35 : 15 : 1) | Are they equal? True
sage 5*G = (15 : 8 : 1) | ad-hoc 5*G = (15 : 8 : 1) | Are they equal? True
sage 6*G = (30 : 22 : 1) | ad-hoc 6*G = (30 : 22 : 1) | Are they equal? True
sage 7*G = (1 : 25 : 1) | ad-hoc 7*G = (1 : 25 : 1) | Are they equal? True
sage 8*G = (31 : 27 : 1) | ad-hoc 8*G = (31 : 27 : 1) | Are they equal? True
sage 9*G = (17 : 32 : 1) | ad-hoc 9*G = (17 : 32 : 1) | Are they equal? True
</code></pre>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41844#post-id-41844in the above code how the addition and doubling is obtained.Sat, 31 Mar 2018 19:14:55 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41844#post-id-41844Comment by santoshi for <p>The following answer does not implement the two functions "add" and "double" on an elliptic curve, instead, it uses the already existing functionality of sage. (It would be too much to implement also these basic functions depending on the form of the elliptic curve and the base field characteristic.)</p>
<p>Code:</p>
<pre><code>def left_to_right_double_and_add(n, G):
"""n is a positive integer number,
G is a rational point of an elliptic curve E,
defined over some finite field F.
This routine computes
n*G
in an ad-hoc manner.
We use the standard add, and doubling on E,
and do not implemented them here.
"""
digits = ZZ(n).digits(base=2)
E = G.curve()
# F = E.base_field()
P = G # this corresponds to 1*G, init
nG = E(0) # and we add further contributions
for digit in digits:
if digit:
nG = nG.__add__(P) # or simply nG += P
P = P.__mul__(2) # or simply P *= 2
# print "\tdigit=%s P=%s nG=%s" % (digit, P, nG)
return nG
# quick test on the given curve with the given poing:
E = EllipticCurve( GF(37), [7, 25] )
G = E.point( [33, 9] )
for n in [1..9]:
nG = left_to_right_double_and_add(n, G)
print ( "sage %s*G = %13s | ad-hoc %s*G = %13s | Are they equal? %s"
% ( n, n*G, n, nG, n*G == nG ) )
</code></pre>
<p>This gives in the test:</p>
<pre><code>sage 1*G = (33 : 9 : 1) | ad-hoc 1*G = (33 : 9 : 1) | Are they equal? True
sage 2*G = (9 : 15 : 1) | ad-hoc 2*G = (9 : 15 : 1) | Are they equal? True
sage 3*G = (2 : 11 : 1) | ad-hoc 3*G = (2 : 11 : 1) | Are they equal? True
sage 4*G = (35 : 15 : 1) | ad-hoc 4*G = (35 : 15 : 1) | Are they equal? True
sage 5*G = (15 : 8 : 1) | ad-hoc 5*G = (15 : 8 : 1) | Are they equal? True
sage 6*G = (30 : 22 : 1) | ad-hoc 6*G = (30 : 22 : 1) | Are they equal? True
sage 7*G = (1 : 25 : 1) | ad-hoc 7*G = (1 : 25 : 1) | Are they equal? True
sage 8*G = (31 : 27 : 1) | ad-hoc 8*G = (31 : 27 : 1) | Are they equal? True
sage 9*G = (17 : 32 : 1) | ad-hoc 9*G = (17 : 32 : 1) | Are they equal? True
</code></pre>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41845#post-id-41845what are the standard add and doubling on ESat, 31 Mar 2018 19:24:42 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41845#post-id-41845Comment by santoshi for <p>The following answer does not implement the two functions "add" and "double" on an elliptic curve, instead, it uses the already existing functionality of sage. (It would be too much to implement also these basic functions depending on the form of the elliptic curve and the base field characteristic.)</p>
<p>Code:</p>
<pre><code>def left_to_right_double_and_add(n, G):
"""n is a positive integer number,
G is a rational point of an elliptic curve E,
defined over some finite field F.
This routine computes
n*G
in an ad-hoc manner.
We use the standard add, and doubling on E,
and do not implemented them here.
"""
digits = ZZ(n).digits(base=2)
E = G.curve()
# F = E.base_field()
P = G # this corresponds to 1*G, init
nG = E(0) # and we add further contributions
for digit in digits:
if digit:
nG = nG.__add__(P) # or simply nG += P
P = P.__mul__(2) # or simply P *= 2
# print "\tdigit=%s P=%s nG=%s" % (digit, P, nG)
return nG
# quick test on the given curve with the given poing:
E = EllipticCurve( GF(37), [7, 25] )
G = E.point( [33, 9] )
for n in [1..9]:
nG = left_to_right_double_and_add(n, G)
print ( "sage %s*G = %13s | ad-hoc %s*G = %13s | Are they equal? %s"
% ( n, n*G, n, nG, n*G == nG ) )
</code></pre>
<p>This gives in the test:</p>
<pre><code>sage 1*G = (33 : 9 : 1) | ad-hoc 1*G = (33 : 9 : 1) | Are they equal? True
sage 2*G = (9 : 15 : 1) | ad-hoc 2*G = (9 : 15 : 1) | Are they equal? True
sage 3*G = (2 : 11 : 1) | ad-hoc 3*G = (2 : 11 : 1) | Are they equal? True
sage 4*G = (35 : 15 : 1) | ad-hoc 4*G = (35 : 15 : 1) | Are they equal? True
sage 5*G = (15 : 8 : 1) | ad-hoc 5*G = (15 : 8 : 1) | Are they equal? True
sage 6*G = (30 : 22 : 1) | ad-hoc 6*G = (30 : 22 : 1) | Are they equal? True
sage 7*G = (1 : 25 : 1) | ad-hoc 7*G = (1 : 25 : 1) | Are they equal? True
sage 8*G = (31 : 27 : 1) | ad-hoc 8*G = (31 : 27 : 1) | Are they equal? True
sage 9*G = (17 : 32 : 1) | ad-hoc 9*G = (17 : 32 : 1) | Are they equal? True
</code></pre>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41846#post-id-41846the above code gives me following error when run it on sagemath cloud
Error in lines 13-16
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute
exec compile(block+'\n', '', 'single') in namespace, locals
File "<string>", line 4
salvus.execute_with_code_decorators(*_salvus_parsing.dec_args[Integer(3)])
^
SyntaxError: invalid syntaxSat, 31 Mar 2018 19:29:50 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=41846#post-id-41846Comment by klx for <p>The following answer does not implement the two functions "add" and "double" on an elliptic curve, instead, it uses the already existing functionality of sage. (It would be too much to implement also these basic functions depending on the form of the elliptic curve and the base field characteristic.)</p>
<p>Code:</p>
<pre><code>def left_to_right_double_and_add(n, G):
"""n is a positive integer number,
G is a rational point of an elliptic curve E,
defined over some finite field F.
This routine computes
n*G
in an ad-hoc manner.
We use the standard add, and doubling on E,
and do not implemented them here.
"""
digits = ZZ(n).digits(base=2)
E = G.curve()
# F = E.base_field()
P = G # this corresponds to 1*G, init
nG = E(0) # and we add further contributions
for digit in digits:
if digit:
nG = nG.__add__(P) # or simply nG += P
P = P.__mul__(2) # or simply P *= 2
# print "\tdigit=%s P=%s nG=%s" % (digit, P, nG)
return nG
# quick test on the given curve with the given poing:
E = EllipticCurve( GF(37), [7, 25] )
G = E.point( [33, 9] )
for n in [1..9]:
nG = left_to_right_double_and_add(n, G)
print ( "sage %s*G = %13s | ad-hoc %s*G = %13s | Are they equal? %s"
% ( n, n*G, n, nG, n*G == nG ) )
</code></pre>
<p>This gives in the test:</p>
<pre><code>sage 1*G = (33 : 9 : 1) | ad-hoc 1*G = (33 : 9 : 1) | Are they equal? True
sage 2*G = (9 : 15 : 1) | ad-hoc 2*G = (9 : 15 : 1) | Are they equal? True
sage 3*G = (2 : 11 : 1) | ad-hoc 3*G = (2 : 11 : 1) | Are they equal? True
sage 4*G = (35 : 15 : 1) | ad-hoc 4*G = (35 : 15 : 1) | Are they equal? True
sage 5*G = (15 : 8 : 1) | ad-hoc 5*G = (15 : 8 : 1) | Are they equal? True
sage 6*G = (30 : 22 : 1) | ad-hoc 6*G = (30 : 22 : 1) | Are they equal? True
sage 7*G = (1 : 25 : 1) | ad-hoc 7*G = (1 : 25 : 1) | Are they equal? True
sage 8*G = (31 : 27 : 1) | ad-hoc 8*G = (31 : 27 : 1) | Are they equal? True
sage 9*G = (17 : 32 : 1) | ad-hoc 9*G = (17 : 32 : 1) | Are they equal? True
</code></pre>
https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=53108#post-id-53108Without the $[n \bmod order]G$ check this code will fail as [see on Stackoverflow : order of a point is not regular in Hessian Curve implementation](https://stackoverflow.com/q/63457732/1820553)Wed, 19 Aug 2020 21:09:43 +0200https://ask.sagemath.org/question/41813/elliptic-curve-scalar-multiplication/?comment=53108#post-id-53108