CoCalc Public FilesElliptic Curve Examples.sagewsOpen with one click!
Author: Paul Jenkins
Views : 157
Compute Environment: Ubuntu 18.04 (Deprecated)
#1 Plot an Elliptic Curve
E1 = EllipticCurve([-1,0]) plot(E1)
#2 - Add points on an Elliptic Curve
E2 = EllipticCurve(IntegerModRing(29),[24,13])
P1 = E2(1,3) P2 = E2(3,5) P1 + P2
(26 : 1 : 1)
#3 - Add to the point at infinity
P3 = E2(0,1,0) P1 + P3
(1 : 3 : 1)
#4 - Multiplication
7*P1
(15 : 6 : 1)
#5 - List multiples of a point
for i in range(40): print (i,i*P1)
0 (0 : 1 : 0) 1 (1 : 3 : 1) 2 (11 : 10 : 1) 3 (23 : 28 : 1) 4 (0 : 10 : 1) 5 (19 : 7 : 1) 6 (18 : 19 : 1) 7 (15 : 6 : 1) 8 (20 : 24 : 1) 9 (4 : 12 : 1) 10 (4 : 17 : 1) 11 (20 : 5 : 1) 12 (15 : 23 : 1) 13 (18 : 10 : 1) 14 (19 : 22 : 1) 15 (0 : 19 : 1) 16 (23 : 1 : 1) 17 (11 : 19 : 1) 18 (1 : 26 : 1) 19 (0 : 1 : 0) 20 (1 : 3 : 1) 21 (11 : 10 : 1) 22 (23 : 28 : 1) 23 (0 : 10 : 1) 24 (19 : 7 : 1) 25 (18 : 19 : 1) 26 (15 : 6 : 1) 27 (20 : 24 : 1) 28 (4 : 12 : 1) 29 (4 : 17 : 1) 30 (20 : 5 : 1) 31 (15 : 23 : 1) 32 (18 : 10 : 1) 33 (19 : 22 : 1) 34 (0 : 19 : 1) 35 (23 : 1 : 1) 36 (11 : 19 : 1) 37 (1 : 26 : 1) 38 (0 : 1 : 0) 39 (1 : 3 : 1)
#6 - Work with a composite modulus
E3 = EllipticCurve(IntegerModRing(209),[-5,13])
P4 = E3(1,3)
12*P4
Error in lines 1-1 Traceback (most recent call last): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 674, in _add_ m = (y1-y2)/(x1-x2) File "sage/structure/element.pyx", line 1735, in sage.structure.element.Element.__truediv__ (build/cythonized/sage/structure/element.c:13147) return (<Element>left)._div_(right) File "sage/rings/finite_rings/integer_mod.pyx", line 2539, in sage.rings.finite_rings.integer_mod.IntegerMod_int._div_ (build/cythonized/sage/rings/finite_rings/integer_mod.c:28002) raise ZeroDivisionError(f"inverse of Mod({right}, {self.__modulus.sageInteger}) does not exist") ZeroDivisionError: inverse of Mod(76, 209) does not exist During handling of the above exception, another exception occurred: Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 1, in <module> File "sage/rings/integer.pyx", line 1982, in sage.rings.integer.Integer.__mul__ (build/cythonized/sage/rings/integer.c:14017) return coercion_model.bin_op(left, right, operator.mul) File "sage/structure/coerce.pyx", line 1194, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10181) return (<Action>action)._act_(x, y) File "sage/structure/coerce_actions.pyx", line 759, in sage.structure.coerce_actions.IntegerMulAction._act_ (build/cythonized/sage/structure/coerce_actions.c:9633) return fast_mul_long(a, n_long) File "sage/structure/coerce_actions.pyx", line 923, in sage.structure.coerce_actions.fast_mul_long (build/cythonized/sage/structure/coerce_actions.c:11275) sum += pow2a File "sage/structure/element.pyx", line 1229, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10948) return (<Element>left)._add_(right) File "sage/structure/element.pyx", line 2365, in sage.structure.element.ModuleElement._add_ (build/cythonized/sage/structure/element.c:15559) cpdef _add_(self, other): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 681, in _add_ raise ZeroDivisionError("Inverse of %s does not exist (characteristic = %s = %s*%s)" % (x1-x2, N, N1, N2)) ZeroDivisionError: Inverse of 76 does not exist (characteristic = 209 = 19*11)
for i in range(12): print (i*P4)
(0 : 1 : 0) (1 : 3 : 1) (91 : 27 : 1) (118 : 133 : 1) (148 : 182 : 1) (20 : 35 : 1)
Error in lines 1-2 Traceback (most recent call last): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 674, in _add_ m = (y1-y2)/(x1-x2) File "sage/structure/element.pyx", line 1735, in sage.structure.element.Element.__truediv__ (build/cythonized/sage/structure/element.c:13147) return (<Element>left)._div_(right) File "sage/rings/finite_rings/integer_mod.pyx", line 2539, in sage.rings.finite_rings.integer_mod.IntegerMod_int._div_ (build/cythonized/sage/rings/finite_rings/integer_mod.c:28002) raise ZeroDivisionError(f"inverse of Mod({right}, {self.__modulus.sageInteger}) does not exist") ZeroDivisionError: inverse of Mod(152, 209) does not exist During handling of the above exception, another exception occurred: Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 2, in <module> File "sage/structure/element.pyx", line 1526, in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12309) return (<Element>right)._mul_long(value) File "sage/structure/element.pyx", line 2408, in sage.structure.element.ModuleElement._mul_long (build/cythonized/sage/structure/element.c:16117) return coercion_model.bin_op(self, n, mul) File "sage/structure/coerce.pyx", line 1196, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10205) return (<Action>action)._act_(y, x) File "sage/structure/coerce_actions.pyx", line 759, in sage.structure.coerce_actions.IntegerMulAction._act_ (build/cythonized/sage/structure/coerce_actions.c:9633) return fast_mul_long(a, n_long) File "sage/structure/coerce_actions.pyx", line 923, in sage.structure.coerce_actions.fast_mul_long (build/cythonized/sage/structure/coerce_actions.c:11275) sum += pow2a File "sage/structure/element.pyx", line 1229, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10948) return (<Element>left)._add_(right) File "sage/structure/element.pyx", line 2365, in sage.structure.element.ModuleElement._add_ (build/cythonized/sage/structure/element.c:15559) cpdef _add_(self, other): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 681, in _add_ raise ZeroDivisionError("Inverse of %s does not exist (characteristic = %s = %s*%s)" % (x1-x2, N, N1, N2)) ZeroDivisionError: Inverse of 152 does not exist (characteristic = 209 = 19*11)
E4 = EllipticCurve(IntegerModRing(19),[-5,13]) P5 = E4(1,3) for i in range(20): print (i,i*P5)
0 (0 : 1 : 0) 1 (1 : 3 : 1) 2 (15 : 8 : 1) 3 (4 : 0 : 1) 4 (15 : 11 : 1) 5 (1 : 16 : 1) 6 (0 : 1 : 0) 7 (1 : 3 : 1) 8 (15 : 8 : 1) 9 (4 : 0 : 1) 10 (15 : 11 : 1) 11 (1 : 16 : 1) 12 (0 : 1 : 0) 13 (1 : 3 : 1) 14 (15 : 8 : 1) 15 (4 : 0 : 1) 16 (15 : 11 : 1) 17 (1 : 16 : 1) 18 (0 : 1 : 0) 19 (1 : 3 : 1)
E5 = EllipticCurve(IntegerModRing(11),[-5,13]) P6 = E5(1,3) for i in range(20): print (i,i*P6)
0 (0 : 1 : 0) 1 (1 : 3 : 1) 2 (3 : 5 : 1) 3 (8 : 1 : 1) 4 (5 : 6 : 1) 5 (9 : 2 : 1) 6 (6 : 10 : 1) 7 (2 : 0 : 1) 8 (6 : 1 : 1) 9 (9 : 9 : 1) 10 (5 : 5 : 1) 11 (8 : 10 : 1) 12 (3 : 6 : 1) 13 (1 : 8 : 1) 14 (0 : 1 : 0) 15 (1 : 3 : 1) 16 (3 : 5 : 1) 17 (8 : 1 : 1) 18 (5 : 6 : 1) 19 (9 : 2 : 1)
#7 - Factor 193279 using Elliptic Curves
E7a = EllipticCurve(IntegerModRing(193279),[-10,28]) P7a = E7a(2,4) E7b = EllipticCurve(IntegerModRing(193279),[11,-11]) P7b = E7b(1,1) E7c = EllipticCurve(IntegerModRing(193279),[17,-14]) P7c = E7c(1,2)
factorial(12)*P7a
Error in lines 1-1 Traceback (most recent call last): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 674, in _add_ m = (y1-y2)/(x1-x2) File "sage/structure/element.pyx", line 1735, in sage.structure.element.Element.__truediv__ (build/cythonized/sage/structure/element.c:13147) return (<Element>left)._div_(right) File "sage/rings/finite_rings/integer_mod.pyx", line 3345, in sage.rings.finite_rings.integer_mod.IntegerMod_int64._div_ (build/cythonized/sage/rings/finite_rings/integer_mod.c:33996) return self._new_c((self.ivalue * mod_inverse_int64((<IntegerMod_int64>right).ivalue, File "sage/rings/finite_rings/integer_mod.pyx", line 3693, in sage.rings.finite_rings.integer_mod.mod_inverse_int64 (build/cythonized/sage/rings/finite_rings/integer_mod.c:36105) raise ZeroDivisionError(f"inverse of Mod({x}, {n}) does not exist") ZeroDivisionError: inverse of Mod(96466, 193279) does not exist During handling of the above exception, another exception occurred: Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 1, in <module> File "sage/rings/integer.pyx", line 1982, in sage.rings.integer.Integer.__mul__ (build/cythonized/sage/rings/integer.c:14017) return coercion_model.bin_op(left, right, operator.mul) File "sage/structure/coerce.pyx", line 1194, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10181) return (<Action>action)._act_(x, y) File "sage/structure/coerce_actions.pyx", line 759, in sage.structure.coerce_actions.IntegerMulAction._act_ (build/cythonized/sage/structure/coerce_actions.c:9633) return fast_mul_long(a, n_long) File "sage/structure/coerce_actions.pyx", line 923, in sage.structure.coerce_actions.fast_mul_long (build/cythonized/sage/structure/coerce_actions.c:11275) sum += pow2a File "sage/structure/element.pyx", line 1229, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10948) return (<Element>left)._add_(right) File "sage/structure/element.pyx", line 2365, in sage.structure.element.ModuleElement._add_ (build/cythonized/sage/structure/element.c:15559) cpdef _add_(self, other): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 681, in _add_ raise ZeroDivisionError("Inverse of %s does not exist (characteristic = %s = %s*%s)" % (x1-x2, N, N1, N2)) ZeroDivisionError: Inverse of 96466 does not exist (characteristic = 193279 = 347*557)
factorial(12)*P7b
(13862 : 35249 : 1)
factorial(12)*P7c
Error in lines 1-1 Traceback (most recent call last): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 674, in _add_ m = (y1-y2)/(x1-x2) File "sage/structure/element.pyx", line 1735, in sage.structure.element.Element.__truediv__ (build/cythonized/sage/structure/element.c:13147) return (<Element>left)._div_(right) File "sage/rings/finite_rings/integer_mod.pyx", line 3345, in sage.rings.finite_rings.integer_mod.IntegerMod_int64._div_ (build/cythonized/sage/rings/finite_rings/integer_mod.c:33996) return self._new_c((self.ivalue * mod_inverse_int64((<IntegerMod_int64>right).ivalue, File "sage/rings/finite_rings/integer_mod.pyx", line 3693, in sage.rings.finite_rings.integer_mod.mod_inverse_int64 (build/cythonized/sage/rings/finite_rings/integer_mod.c:36105) raise ZeroDivisionError(f"inverse of Mod({x}, {n}) does not exist") ZeroDivisionError: inverse of Mod(94133, 193279) does not exist During handling of the above exception, another exception occurred: Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 1, in <module> File "sage/rings/integer.pyx", line 1982, in sage.rings.integer.Integer.__mul__ (build/cythonized/sage/rings/integer.c:14017) return coercion_model.bin_op(left, right, operator.mul) File "sage/structure/coerce.pyx", line 1194, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10181) return (<Action>action)._act_(x, y) File "sage/structure/coerce_actions.pyx", line 759, in sage.structure.coerce_actions.IntegerMulAction._act_ (build/cythonized/sage/structure/coerce_actions.c:9633) return fast_mul_long(a, n_long) File "sage/structure/coerce_actions.pyx", line 923, in sage.structure.coerce_actions.fast_mul_long (build/cythonized/sage/structure/coerce_actions.c:11275) sum += pow2a File "sage/structure/element.pyx", line 1229, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10948) return (<Element>left)._add_(right) File "sage/structure/element.pyx", line 2365, in sage.structure.element.ModuleElement._add_ (build/cythonized/sage/structure/element.c:15559) cpdef _add_(self, other): File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 681, in _add_ raise ZeroDivisionError("Inverse of %s does not exist (characteristic = %s = %s*%s)" % (x1-x2, N, N1, N2)) ZeroDivisionError: Inverse of 94133 does not exist (characteristic = 193279 = 557*347)
#8 - ElGamal with EllipticCurves
E8 = EllipticCurve(IntegerModRing(8831),[3,45]) P8 = E8(4,11)
P9 = 3*P8 P10 = E8(5,1743)
C1 = 8*P8 print(C1)
(5415 : 6321 : 1)
C2 = P10+8*P9 print(C2)
(6626 : 3576 : 1)
C2 - 3*C1
(5 : 1743 : 1)
#9 - Diffie Hellman
E9 = EllipticCurve(IntegerModRing(7211),[1,7206])
G = E9(3,5)
S1 = 12*G print(S1)
(1794 : 6375 : 1)
S2 = 23*G print(S2)
(3861 : 1242 : 1)
23*S1
(1472 : 2098 : 1)
12*S2
(1472 : 2098 : 1)