Last active
August 18, 2022 21:04
-
-
Save arskiy/35f76c9b960871ad29a820ebd63d033b to your computer and use it in GitHub Desktop.
source code for https://www.youtube.com/watch?v=mKXu6f1slaM
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # here be dragons | |
| from manim import * | |
| import math | |
| import numpy as np | |
| config["background_color"] = "#301934" | |
| def point_addition(p, q): | |
| m = (q[1] - p[1]) / (q[0] - p[0]) | |
| xr = m * m - p[0] - q[0] | |
| yr = m * (p[0] - xr) - p[1] | |
| return np.array([xr, yr, 0]) | |
| def get_y_pos(x): | |
| return np.sqrt(x**3 - x + 1) | |
| def get_y_neg(x): | |
| return -np.sqrt(x**3 - x + 1) | |
| def update_r(p2, p0x, get_point): | |
| p2.move_to(get_point(point_addition([p0x, get_y_pos(p0x)], [0.4, 0.8149])[0])) | |
| def get_qubits(x: int) -> int: | |
| return 9 * x + math.ceil(math.log2(x)) + 10 | |
| class CurveGraph(Scene): | |
| def construct(self): | |
| ax = Axes( | |
| x_range=[-3, 3, 1], | |
| y_range=([-3, 3, 1]), | |
| axis_config={"include_numbers": False}, | |
| tips=False, | |
| color=BLACK, | |
| fill_color=BLACK, | |
| stroke_color=BLACK, | |
| ).to_edge(DOWN) | |
| posgraph = ax.plot( | |
| lambda x: get_y_pos(x), | |
| x_range=[-1.3244, 3], | |
| use_smoothing=True, | |
| discontinuities=[-1.325, -0.577, 0, 0.577], | |
| dt=0.001, | |
| color=YELLOW, | |
| fill_color=YELLOW, | |
| ) | |
| neggraph = ax.plot( | |
| lambda x: get_y_neg(x), | |
| x_range=[-1.3244, 3], | |
| use_smoothing=True, | |
| discontinuities=[-1.325, -0.577, 0, 0.577], | |
| dt=0.001, | |
| color=YELLOW, | |
| fill_color=YELLOW, | |
| ) | |
| title = Tex(r"Graph of $y^2 = x^3 - x + 1$", color=WHITE, font_size=54) | |
| title.to_edge(UP) | |
| dot_discontinuity = Dot( | |
| (ax.coords_to_point(-1.325, 0)), | |
| stroke_color=YELLOW, | |
| fill_opacity=0.0, | |
| stroke_width=3.0, | |
| ) | |
| self.wait(3) | |
| self.play(Create(ax, lag_ratio=0.01, run_time=1)) | |
| self.play(FadeIn(title, shift=DOWN), run_time=0.9) | |
| self.wait(8) | |
| self.play(Create(posgraph), Create(neggraph)) | |
| self.play(Create(dot_discontinuity, run_time=0.5)) | |
| self.wait(39) | |
| dotr = 0.06 | |
| p0start = -1.22 | |
| p0tracker = ValueTracker(p0start) | |
| p0 = Dot(posgraph.get_point_from_function(p0start), color=RED, radius=dotr) | |
| p0.add_updater( | |
| lambda m: m.move_to(posgraph.get_point_from_function(p0tracker.get_value())) | |
| ) | |
| p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) | |
| p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) | |
| update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) | |
| negP = Dot(neggraph.get_point_from_function(p0start), radius=dotr) | |
| p0.z_index = 2 | |
| p1.z_index = 2 | |
| p2.z_index = 2 | |
| negP.z_index = 2 | |
| line = Line(p0, p1) | |
| line.set_length(20) | |
| labelP = MathTex("P", color=WHITE).next_to(p0, UP) | |
| labelQ = MathTex("Q", color=WHITE).next_to(p1, UP) | |
| labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) | |
| labelNegP = MathTex("-P", color=WHITE).next_to(negP, DOWN) | |
| identity = Tex( | |
| r"Definition: $P + \mathcal{O} = P$ \\That is, $\mathcal{O}$ is the identity element.", | |
| font_size=42, | |
| ).to_edge(UP) | |
| addition = Tex(r"Definition: $P + Q + R = \mathcal{O}$", font_size=48).to_edge( | |
| UP | |
| ) | |
| addition_r = Tex(r"Definition: $P + Q + = -R$", font_size=48).to_edge(UP) | |
| negation = Tex( | |
| r"Definition: $(-P)$ is defined to be $P$, \\but symmetric over the $x$-axis", | |
| font_size=42, | |
| ).to_edge(UP) | |
| inverse = Tex( | |
| r"From the definition of negation, \\we can say that $P + (-P) = \mathcal{O}$", | |
| font_size=42, | |
| ).to_edge(UP) | |
| approaches = Tex( | |
| r"As $P$ approaches $Q$, they form a tangent line.", font_size=44 | |
| ).to_edge(UP) | |
| app = Tex( | |
| r"As $P$ approaches $Q$, \\then $P + Q$ becomes the same as $\underbrace{P + P}_{2P}$.", | |
| font_size=44, | |
| ).to_edge(UP) | |
| self.play( | |
| Create(p0), | |
| Create(p1), | |
| Create(p2), | |
| Write(labelP), | |
| Write(labelQ), | |
| Write(labelR), | |
| ) | |
| self.play(FadeTransform(title, identity)) | |
| self.wait(6) | |
| self.play(Write(line), run_time=1.5) | |
| self.play(FadeTransform(identity, addition)) | |
| self.wait(12) | |
| self.play(FadeTransform(addition, addition_r)) | |
| self.wait(14) | |
| self.play(Write(labelNegP), Uncreate(labelQ), Uncreate(labelR), FadeOut(line)) | |
| self.play(Uncreate(p1), Uncreate(p2), Create(negP)) | |
| P_to_negP = Line(p0, negP) | |
| extended_P_to_negP = P_to_negP.copy().set_length(5) | |
| self.play(Create(P_to_negP), FadeTransform(addition_r, negation)) | |
| self.wait(1) | |
| self.play(Flash(p0, color=YELLOW), Flash(negP, color=YELLOW)) | |
| self.wait(3) | |
| self.play( | |
| Transform(P_to_negP, extended_P_to_negP), | |
| Uncreate(labelP), | |
| Uncreate(labelNegP), | |
| FadeTransform(negation, inverse), | |
| ) | |
| p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) | |
| p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) | |
| update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) | |
| p2.add_updater( | |
| lambda m: update_r( | |
| m, p0tracker.get_value(), posgraph.get_point_from_function | |
| ) | |
| ) | |
| line2 = Line(p0, p1) | |
| line2.set_length(20) | |
| line2.add_updater( | |
| lambda m: ( | |
| m.set_points_by_ends(p0.get_center(), p1.get_center()), | |
| m.set_length(20), | |
| ) | |
| ) | |
| p1.z_index = 2 | |
| p2.z_index = 2 | |
| self.wait(8) | |
| self.play( | |
| Create(p1), | |
| Create(p2), | |
| # Write(line), | |
| FadeTransform(inverse, approaches), | |
| ) | |
| self.play(Uncreate(negP), FadeOut(P_to_negP), run_time=1) | |
| self.play(Write(line2)) | |
| self.wait(1) | |
| self.play(p0tracker.animate.set_value(0.399), run_time=6) | |
| self.wait(4) | |
| label2P = MathTex("2P", color=WHITE).next_to(p0, UP) | |
| labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) | |
| self.play( | |
| FadeTransform(approaches, app), | |
| Write(label2P), | |
| Write(labelR), | |
| ) | |
| graph = Group( | |
| ax, | |
| dot_discontinuity, | |
| p0, | |
| p1, | |
| p2, | |
| posgraph, | |
| neggraph, | |
| ) | |
| # transformedGraph = graph.copy().scale(0.25).to_edge(DR) | |
| self.wait(5) | |
| self.play(Uncreate(label2P), Uncreate(labelR)) | |
| self.play(FadeOut(line2), FadeOut(app, shift=UP)) | |
| self.wait(0.5) | |
| # self.play(Transform(graph, transformedGraph)) | |
| self.play(FadeOut(*graph)) | |
| self.wait(2) | |
| equations = Tex( | |
| r"Let's take a look at the equations we're going to use now." | |
| ).to_edge(UP) | |
| slope = Tex( | |
| r"We can calculate the slope of $P$ and $Q$ with\\$m = \frac{Q_y - P_y}{Q_x - P_x}$" | |
| ).next_to(equations, DOWN * 2) | |
| coordinatesR = Tex( | |
| r"And then we can calculate the coordinates of $R = P + Q$ with\\$R_x = m^2 - P_x - Q_x$\\$R_y = P_y + m(R_x - P_x)$" | |
| ).next_to(slope, DOWN * 2) | |
| if_p_equals_q = Tex(r"If $P = Q$, then").next_to(coordinatesR, DOWN) | |
| derivative = MathTex( | |
| r"\frac{\frac{d}{dx} (x^3 + ax + b)}{\frac{d}{dy} (y^2)}", font_size=40 | |
| ).next_to(if_p_equals_q, DOWN) | |
| new_slope = MathTex(r"\frac{3x^2 + a}{2y}", font_size=40).move_to(derivative) | |
| self.play(FadeIn(equations, shift=DOWN)) | |
| self.wait(2) | |
| self.play(Write(slope)) | |
| self.wait(4) | |
| self.play(Write(coordinatesR)) | |
| self.wait(5) | |
| self.play(Write(if_p_equals_q)) | |
| self.wait(0.5) | |
| self.play(Write(derivative)) | |
| self.wait(3) | |
| self.play(Transform(derivative, new_slope)) | |
| self.wait(10) | |
| self.play(FadeOut(*self.mobjects)) | |
| self.wait(16) | |
| class ModularArithmetic(Scene): | |
| def construct(self): | |
| circle = Circle(radius=3, color=BLUE_B) | |
| invisible_circle = ( | |
| Circle().set_stroke(GRAY, opacity=0).surround(circle, buffer_factor=0.6) | |
| ) | |
| center = Dot(circle.get_center(), color=WHITE, radius=0.1) | |
| self.wait(20) | |
| self.play(Create(circle), Create(invisible_circle), Create(center)) | |
| numbers_clock = VGroup() | |
| for (i, angle) in enumerate(reversed(range(90, 360 + 90, 30))): | |
| point = invisible_circle.point_at_angle((angle % 360) * DEGREES) | |
| text = Text(str(i + 1), font_size=24).move_to(point) | |
| numbers_clock += text | |
| self.play(Write(numbers_clock)) | |
| twelve = invisible_circle.point_at_angle(PI / 2) - np.array([0, 0.5, 0]) | |
| pointer = Line(center, twelve) | |
| self.play(Create(pointer)) | |
| self.wait(2) | |
| # Rotate to 14 h | |
| fourteen = MathTex( | |
| r"14 \equiv 2 \: (\textrm{mod} \, 12)", font_size=40 | |
| ).to_edge(UP) | |
| self.play(Write(fourteen)) | |
| self.play( | |
| Rotate(pointer, angle=(-2 * PI - PI / 3), about_point=ORIGIN), run_time=4 | |
| ) | |
| self.wait(3) | |
| self.play(Uncreate(fourteen)) | |
| self.wait(0.5) | |
| # Reset to 12 | |
| self.play(Rotate(pointer, angle=PI / 3, about_point=ORIGIN), run_time=1) | |
| self.wait(4.5) | |
| # Rotate to 11 h | |
| eleven = MathTex(r"-1 \equiv 11 \: (\textrm{mod} \, 12)", font_size=40).to_edge( | |
| UP | |
| ) | |
| self.play(Write(eleven)) | |
| self.play(Rotate(pointer, angle=PI / 6, about_point=ORIGIN)) | |
| self.wait(14) | |
| # Reset | |
| self.play( | |
| Uncreate(eleven), | |
| Uncreate(center), | |
| Uncreate(pointer), | |
| Uncreate(numbers_clock), | |
| Uncreate(circle), | |
| run_time=1, | |
| ) | |
| self.wait(14) | |
| mod_4 = Tex( | |
| r"$2 \cdot k \equiv 1 \: (\textrm{mod} \, 4)$ \\ $k \, \text{doesn't exist} \, (\nexists)$" | |
| ) | |
| self.play(Write(mod_4)) | |
| self.wait(12) | |
| self.play(FadeOut(mod_4)) | |
| self.wait() | |
| title_mod = Tex( | |
| r"List of multiplicative inverses in $n \: (\textrm{mod} \, 8)$" | |
| ).to_edge(UP) | |
| table = ( | |
| MobjectTable( | |
| [ | |
| [MathTex("1"), MathTex(r"1 \cdot 1 = 1 \equiv 1")], | |
| [MathTex("2"), MathTex(r"\nexists")], | |
| [MathTex("3"), MathTex(r"3 \cdot 3 = 9 \equiv 1")], | |
| [MathTex("4"), MathTex(r"\nexists")], | |
| [MathTex("5"), MathTex(r"5 \cdot 5 = 25 \equiv 1")], | |
| [MathTex("6"), MathTex(r"\nexists")], | |
| [MathTex("7"), MathTex(r"7 \cdot 7 = 49 \equiv 1")], | |
| ], | |
| col_labels=[MathTex("n"), MathTex("n^{-1}")], | |
| ) | |
| .scale(0.6) | |
| .to_edge(DOWN) | |
| ) | |
| cells = VGroup( | |
| table.get_cell((3, 1), color=RED_B), | |
| table.get_cell((3, 2), color=RED_B), | |
| table.get_cell((5, 1), color=RED_B), | |
| table.get_cell((5, 2), color=RED_B), | |
| table.get_cell((7, 1), color=RED_B), | |
| table.get_cell((7, 2), color=RED_B), | |
| ) | |
| self.play(table.create(), Write(title_mod)) | |
| self.wait(4) | |
| self.play(Create(cells), run_time=2.5) | |
| # for cell in cells: | |
| # self.play(Create(cell), run_time=0.75) | |
| self.wait(6) | |
| # for cell in cells: | |
| # self.play(Uncreate(cell), run_time=0.25) | |
| self.play(Uncreate(cells), run_time=2.5) | |
| self.wait() | |
| self.play(Uncreate(table), Uncreate(title_mod), run_time=2.5) | |
| self.wait() | |
| fraction = MathTex(r"\frac{3}{4}", r"\: (\textrm{mod} \, 5)") | |
| inverse = MathTex(r"3 \cdot ", r"4^{-1}", r"\: (\textrm{mod} \, 5)") | |
| result = MathTex(r"3 \cdot ", r"4", r" \equiv 2", r"\: (\textrm{mod} \, 5)") | |
| self.play(FadeIn(fraction, shift=UP)) | |
| self.wait(9) | |
| self.play(TransformMatchingTex(fraction, inverse)) | |
| self.wait(15) | |
| self.play(TransformMatchingTex(inverse, result)) | |
| self.wait(17) | |
| field = MathTex(r"\mathbb{F}_p").next_to(result, DOWN * 1.5) | |
| self.play(Write(field)) | |
| self.wait(5) | |
| self.play(Uncreate(field), Uncreate(result)) | |
| CHR = 31 | |
| def extended_euclidean_algorithm(a, b): | |
| s, old_s = 0, 1 | |
| t, old_t = 1, 0 | |
| r, old_r = b, a | |
| while r != 0: | |
| quotient = old_r // r | |
| old_r, r = r, old_r - quotient * r | |
| old_s, s = s, old_s - quotient * s | |
| old_t, t = t, old_t - quotient * t | |
| return old_r, old_s, old_t | |
| def inverse_of(n, p): | |
| gcd, x, y = extended_euclidean_algorithm(n, p) | |
| assert (n * x + p * y) % p == gcd | |
| if gcd != 1: | |
| # Either n is 0, or p is not a prime number. | |
| raise ValueError("{} has no multiplicative inverse " "modulo {}".format(n, p)) | |
| else: | |
| return x % p | |
| def get_y_pos(x): | |
| return np.sqrt(x**3 - x + 1) | |
| def get_y_field(x): | |
| square = (x**3 - x + 1) % CHR | |
| inverse = inverse_of(x, CHR) | |
| return (square * inverse) % CHR | |
| X_LIMIT = CHR | |
| X_RANGE = np.int32(get_y_pos(X_LIMIT)) | |
| class EllipticFiniteField(Scene): | |
| def construct(self): | |
| ax = Axes( | |
| x_range=[-1, X_LIMIT, 1], | |
| y_range=([-1, X_RANGE, 1]), | |
| axis_config={"include_numbers": False, "include_ticks": False}, | |
| tips=False, | |
| color=BLACK, | |
| fill_color=BLACK, | |
| stroke_color=BLACK, | |
| ).to_edge(DOWN) | |
| ax2 = Axes( | |
| x_range=[-1, CHR - 1, 1], | |
| y_range=[-1, CHR - 1, 1], | |
| axis_config={"include_numbers": False}, | |
| tips=False, | |
| color=BLACK, | |
| fill_color=BLACK, | |
| stroke_color=BLACK, | |
| ).to_edge(DOWN) | |
| posgraph = ax.plot( | |
| lambda x: get_y_pos(x), | |
| x_range=[-1.3244, X_LIMIT], | |
| use_smoothing=True, | |
| discontinuities=[-1.325, -0.577, 0, 0.577], | |
| dt=0.001, | |
| color=YELLOW, | |
| fill_color=YELLOW, | |
| ) | |
| title = MathTex(r"y^2 = x^3 - x + 1", font_size=44).to_edge(UP) | |
| title_field = MathTex( | |
| r"y^2 = x^3 - x + 1", r"\: (\textrm{mod} \, %d)" % CHR, font_size=44 | |
| ).to_edge(UP) | |
| title_fieldpm = MathTex( | |
| r"y = \pm\sqrt{x^3 - x + 1}", r"\: (\textrm{mod} \, %d)" % CHR, font_size=44 | |
| ).to_edge(UP) | |
| dots = [] | |
| field_dots = [] | |
| field_neg = [] | |
| for i in range(1, X_LIMIT): | |
| dots.append(Dot(posgraph.get_point_from_function(i), color=ORANGE)) | |
| field_dots.append(get_y_field(i)) | |
| field_neg.append(-get_y_field(i) % CHR) | |
| dots = VGroup(*dots) | |
| field_dots = ax2.plot_line_graph(range(1, CHR), field_dots).set_color(ORANGE) | |
| field_neg = ax2.plot_line_graph(range(1, CHR), field_neg).set_color(YELLOW) | |
| self.play(Create(ax, lag_ratio=0.01, run_time=1)) | |
| self.play(Create(posgraph), Create(dots), run_time=2) | |
| self.play(Write(title)) | |
| self.wait(2) | |
| self.play(Transform(ax, ax2, replace_mobject_with_target_in_scene=True)) | |
| self.play(FadeOut(posgraph)) | |
| self.wait(1) | |
| self.play(TransformMatchingTex(title, title_field)) | |
| self.wait(1) | |
| self.play( | |
| Transform( | |
| dots, | |
| field_dots["vertex_dots"], | |
| replace_mobject_with_target_in_scene=True, | |
| ), | |
| Create(field_neg["vertex_dots"]), | |
| ) | |
| self.wait(31.5) | |
| linep2 = Line( | |
| ax2.coords_to_point(0, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, CHR / 2, 0), | |
| color=WHITE, | |
| ) | |
| self.play(Create(linep2)) | |
| self.wait(5) | |
| upper_rect = Polygon( | |
| ax2.coords_to_point(0, 0, 0), | |
| ax2.coords_to_point(0, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, 0, 0), | |
| color=MAROON_B, | |
| fill_color=MAROON_B, | |
| fill_opacity=0.8, | |
| ) | |
| lower_rect = Polygon( | |
| ax2.coords_to_point(0, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, CHR, 0), | |
| ax2.coords_to_point(0, CHR, 0), | |
| color=MAROON_B, | |
| fill_color=MAROON_B, | |
| fill_opacity=0.8, | |
| ) | |
| self.play(FadeOut(lower_rect), run_time=1.5) | |
| self.wait(1) | |
| self.play(FadeOut(upper_rect), run_time=1.5) | |
| self.wait(4) | |
| self.play(Uncreate(linep2)) | |
| self.wait(5) | |
| graph = VGroup(ax2, field_dots["vertex_dots"], field_neg["vertex_dots"]) | |
| # transformedGraph = graph.copy().scale(0.25).to_edge(DR) | |
| self.play(TransformMatchingTex(title_field, title_fieldpm)) | |
| self.wait(15) | |
| self.play(FadeOut(title_fieldpm, shift=UP)) | |
| # self.play(Transform(graph, transformedGraph, replace_mobject_with_target_in_scene=True)) | |
| self.wait(14) | |
| ref_group_law = Tex( | |
| r"[1] An elementary proof of the group law for elliptic curves \\Friedl, Stefan\\ October 2017", | |
| font_size=24, | |
| ).to_edge(UR) | |
| self.play(FadeIn(ref_group_law, shift=LEFT)) | |
| self.wait(10) | |
| self.play(FadeOut(ref_group_law, shift=RIGHT)) | |
| self.wait(43) | |
| self.play(FadeOut(graph), run_time=2) | |
| self.wait() | |
| mult_of_p = MathTex( | |
| r"P &= (52, 14) \: (\textrm{mod} \, 61)", | |
| r"2P &= (4, 0)", | |
| r"3P &= (52, 47)", | |
| r"4P &= \mathcal{O}", | |
| r"5P &= (52, 14)", | |
| r"6P &= (4, 0)", | |
| r"&\;\;\vdots", | |
| arg_separator=r" \\", | |
| ) | |
| suborder = Tex(r"Order of P \\(or of the subgroup of P) = 4", font_size=36) | |
| curveorder = MathTex( | |
| r"&\text{Order of the curve} \\", | |
| "[", | |
| r"E: x^3 &- x + 1 \: (\textrm{mod} \, 61)", | |
| "]", | |
| "= 64", | |
| font_size=36, | |
| ).next_to(suborder, DOWN * 1.5) | |
| ref_schoofs = Tex( | |
| r"[2] Schoof's Algorithm for Counting Points on $E(\mathbb{F}_{k})$ \\Musiker, Gregg \\December 2005", | |
| font_size=24, | |
| ).to_edge(UR) | |
| orders = VGroup(suborder, curveorder).arrange(DOWN, buff=0.8).to_edge(RIGHT * 2) | |
| surr_rect = SurroundingRectangle(orders, color=RED_A, buff=0.4) | |
| p1 = ( | |
| mult_of_p.get_part_by_tex(r"P &= (52, 14)").get_edge_center(LEFT) | |
| + UP * 0.25 | |
| ) | |
| p5 = mult_of_p.get_part_by_tex(r"5P &= (52, 14)").get_edge_center( | |
| LEFT | |
| ) + np.array([-0.22, 0.88, 0]) | |
| self.play(Write(mult_of_p), run_time=4) | |
| self.wait(11) | |
| arrow = CurvedArrow(p5, p1, angle=-TAU / 4, color=RED_B) | |
| self.play(Create(arrow)) | |
| self.wait(24) | |
| self.play(Create(surr_rect), Write(orders)) | |
| self.wait(25) | |
| self.play(FadeIn(ref_schoofs, shift=LEFT)) | |
| self.wait(6) | |
| self.play(FadeOut(ref_schoofs, shift=RIGHT)) | |
| self.wait() | |
| all_mobjs = VGroup(orders, surr_rect, arrow, mult_of_p) | |
| self.play(FadeOut(all_mobjs)) | |
| class EllipticMultiplication(Scene): | |
| def construct(self): | |
| discrete_log = Tex("For $Q = nP$, given P and Q, find n") | |
| self.play(Write(discrete_log)) | |
| dlp = Text("The Discrete Logarithm Problem (DLP)").next_to( | |
| discrete_log, UP * 1.2 | |
| ) | |
| self.wait(10) | |
| self.play(FadeIn(dlp, shift=DOWN)) | |
| # self.play(FadeOut(dlp, shift=UP)) | |
| # self.play(FadeOut(discrete_log, shift=UP)) | |
| desirable = Text("Actually a desirable property!", font_size=36).next_to( | |
| discrete_log, DOWN * 1.2 | |
| ) | |
| self.wait(41) | |
| self.play(FadeIn(desirable, shift=UP)) | |
| self.wait(10) | |
| self.play(FadeOut(desirable, shift=DOWN)) | |
| factors = MathTex( | |
| r"\text{Factors of } 210 \Rightarrow 2 \cdot 3 \cdot 5 \cdot 7" | |
| ).next_to(discrete_log, DOWN * 1.2) | |
| self.play(FadeIn(factors, shift=UP)) | |
| self.wait(10) | |
| self.play(FadeOut(factors, shift=DOWN)) | |
| self.wait(23) | |
| iverunoutofnames = Tex( | |
| r"Computing $Q = nP$ knowing n and P is trivial, \\ while the DLP remains hard \\ (A trapdoor function!)", | |
| font_size=42, | |
| ).next_to(discrete_log, DOWN * 1.2) | |
| self.play(Write(iverunoutofnames)) | |
| self.wait(22) | |
| self.play(FadeOut(VGroup(iverunoutofnames, dlp, discrete_log))) | |
| self.wait(11) | |
| class BobAndGoogle(Scene): | |
| def construct(self): | |
| template = TexTemplate(preamble=r"\usepackage{hyperref}") | |
| bob = Text("Bob", font_size=34).to_edge(LEFT) | |
| google = Text( | |
| "Google", | |
| t2c={ | |
| "[:1]": "#3174f0", | |
| "[1:2]": "#e53125", | |
| "[2:3]": "#fbb003", | |
| "[3:4]": "#3174f0", | |
| "[4:5]": "#269a43", | |
| "[5:]": "#e53125", | |
| }, | |
| font_size=34, | |
| ).to_edge(RIGHT) | |
| self.play(Write(bob), Write(google)) | |
| self.wait(14) | |
| params = MathTex( | |
| r"\text{\Large{P-256}} \\ p &= \mathrm{0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff} \\ a &= \mathrm{0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc} \\ b &= \mathrm{0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b}", | |
| font_size=23, | |
| ).to_edge(UP * 3.5) | |
| paramsrect = SurroundingRectangle( | |
| params, color=RED_A, buff=0.3, fill_color=GRAY_A, fill_opacity=0.25 | |
| ) | |
| params_top = params.copy().to_edge(UP) | |
| params_rect_top = SurroundingRectangle( | |
| params_top, color=RED_A, buff=0.3, fill_color=GRAY_A, fill_opacity=0.25 | |
| ) | |
| ref_params = Tex( | |
| r"[3] OpenSSL Curve Definitions \\ \url{https://github.com/openssl/openssl/}", | |
| font_size=24, | |
| tex_template=template, | |
| ).to_edge(UR) | |
| self.play(Create(paramsrect), Write(params)) | |
| self.wait() | |
| self.play(FadeIn(ref_params, shift=LEFT)) | |
| self.wait(3) | |
| self.play(FadeOut(ref_params, shift=RIGHT)) | |
| self.play(Transform(paramsrect, params_rect_top), Transform(params, params_top)) | |
| random_number = Text(r"priv = rand(1, subgroup_order)", font_size=30) | |
| priv_bob = MathTex(r"\text{priv}_{\text{Bob}}", font_size=33).next_to( | |
| ORIGIN, LEFT | |
| ) | |
| priv_gogl = MathTex(r"\text{priv}_{\text{Google}}", font_size=33).next_to( | |
| ORIGIN, RIGHT | |
| ) | |
| self.play(Write(random_number)) | |
| self.wait(3) | |
| self.play(ShrinkToCenter(random_number)) | |
| self.play(GrowFromCenter(priv_bob), GrowFromCenter(priv_gogl)) | |
| self.wait(10) | |
| trans_priv_bob = priv_bob.copy().next_to(bob, DOWN) | |
| trans_priv_gogl = priv_gogl.copy().next_to(google, DOWN) | |
| self.play(Transform(priv_bob, trans_priv_bob)) | |
| self.play(Transform(priv_gogl, trans_priv_gogl)) | |
| self.wait(3) | |
| base_point = MathTex(r"\text{Base point: }", r"(x, y)") | |
| gen_point = MathTex(r"G = ", r"(x, y)") | |
| self.play(FadeIn(base_point, target_position=params.get_edge_center(DOWN))) | |
| self.wait(2) | |
| self.play(TransformMatchingTex(base_point, gen_point)) | |
| self.wait(1) | |
| gen_bob = MathTex(r"G = (x, y)").next_to(priv_bob, RIGHT * 0.05) | |
| gen_bob.font_size = 33 | |
| gen_gogl = MathTex(r"G = (x, y)").next_to(priv_gogl, LEFT * 0.05) | |
| gen_gogl.font_size = 33 | |
| priv_bob_with_gen = ( | |
| MathTex(r"\text{priv}_\text{Bob} \cdot ", r"G = (x, y)", font_size=33) | |
| .to_edge(LEFT) | |
| .shift(DOWN * 0.7) | |
| ) | |
| priv_gogl_with_gen = ( | |
| MathTex(r"G = (x, y)", r"\cdot \text{priv}_\text{Google}", font_size=33) | |
| .to_edge(RIGHT) | |
| .shift(DOWN * 0.7) | |
| ) | |
| self.play(FadeOut(priv_bob)) | |
| self.play( | |
| Transform( | |
| gen_point.copy(), | |
| priv_bob_with_gen, | |
| replace_mobject_with_target_in_scene=True, | |
| ), | |
| ) | |
| self.wait() | |
| self.play(FadeOut(priv_gogl)) | |
| self.play( | |
| Transform( | |
| gen_point, priv_gogl_with_gen, replace_mobject_with_target_in_scene=True | |
| ) | |
| ) | |
| self.wait() | |
| pub_bob = MathTex( | |
| r"\text{pub}_\text{Bob}", | |
| font_size=33, | |
| ).next_to(bob, DOWN) | |
| pub_gogl = MathTex(r"\text{pub}_{\text{Google}}", font_size=33).next_to( | |
| google, DOWN | |
| ) | |
| # self.play(ShrinkToCenter(gen_bob), ShrinkToCenter(priv_bob)) | |
| self.play(ShrinkToCenter(priv_bob_with_gen)) | |
| self.play(GrowFromCenter(pub_bob)) | |
| self.wait(1) | |
| # self.play(ShrinkToCenter(gen_gogl), ShrinkToCenter(priv_gogl)) | |
| self.play(ShrinkToCenter(priv_gogl_with_gen)) | |
| self.play(GrowFromCenter(pub_gogl)) | |
| self.wait(1.5) | |
| new_pub_gogl = pub_gogl.copy().next_to(bob, DOWN) | |
| new_pub_bob = pub_bob.copy().next_to(google, DOWN) | |
| self.play( | |
| Transform(pub_gogl, new_pub_gogl, path_arc=PI / 4), | |
| Transform(pub_bob, new_pub_bob, path_arc=-PI / 4), | |
| run_time=3, | |
| ) | |
| self.wait(4) | |
| self.play(Indicate(pub_gogl), Indicate(pub_bob), run_time=1.5) | |
| self.wait(24) | |
| shared_secret = MathTex( | |
| r"\text{Shared Secret}", | |
| r"&= \\ (S_x, S_y)", | |
| r"&= \\ \text{pub}_\text{Bob}", | |
| r"\cdot \text{priv}_\text{Google} &= \\", | |
| r"\text{pub}_\text{Google}", | |
| r"\cdot \text{priv}_\text{Bob}", | |
| font_size=33, | |
| organize_left_to_right=True, | |
| ) | |
| self.play( | |
| Transform( | |
| VGroup(pub_gogl, pub_bob), | |
| shared_secret, | |
| replace_mobject_with_target_in_scene=True, | |
| ) | |
| ) | |
| self.wait(52) | |
| process_secret = MathTex( | |
| r"\text{Shared Secret}", r"= (S_x, S_y)", r"\Rightarrow \text{Cipher}" | |
| ) | |
| p0 = bob.get_right() | |
| p1 = google.get_left() | |
| darrow = DoubleArrow(p0, p1, buff=1.5).next_to(process_secret, DOWN * 1.5) | |
| darrow_text = Tex( | |
| r"Encrypted data \\ (secure, even through an insecure channel!)", | |
| font_size=36, | |
| ).next_to(darrow, DOWN) | |
| self.play(TransformMatchingTex(shared_secret, process_secret)) | |
| self.wait() | |
| self.play(Create(darrow)) | |
| self.wait(1) | |
| self.play(Write(darrow_text), run_time=1.5) | |
| self.wait(32) | |
| self.play(FadeOut(*self.mobjects), run_time=3) | |
| self.wait(2) | |
| class RSAQubits(Scene): | |
| def construct(self): | |
| tablersa = Table( | |
| [ | |
| ["1024", "160"], | |
| ["2048", "224"], | |
| ["3072", "256"], | |
| ["7680", "384"], | |
| ["15360", "521"], | |
| ], | |
| col_labels=[Text("RSA"), Text("ECC")], | |
| ).scale(0.6) | |
| in_bits = Tex( | |
| r"Comparison of RSA and \\Elliptic Curves key sizes (in bits)", font_size=35 | |
| ) | |
| g = Group(tablersa, in_bits).arrange(DOWN, buff=0.6) | |
| tablequbits = Table( | |
| [ | |
| ["192", str(get_qubits(192))], | |
| ["256", str(get_qubits(256))], | |
| ["384", str(get_qubits(384))], | |
| ["512", str(get_qubits(512))], | |
| ], | |
| col_labels=[Text("Bits"), Text("Qubits")], | |
| ).scale(0.6) | |
| surr_rect = SurroundingRectangle( | |
| VGroup(in_bits, tablersa), color=RED_A, buff=0.5 | |
| ) | |
| self.play(Create(surr_rect), Create(tablersa), Write(in_bits), run_time=2.5) | |
| self.wait(75) | |
| self.play(Uncreate(surr_rect), Uncreate(tablersa), Uncreate(in_bits)) | |
| self.wait(3) | |
| self.play(Create(tablequbits)) | |
| self.wait(50) | |
| self.play(Uncreate(tablequbits)) | |
| self.wait(21.5) | |
| serge_lang = Tex( | |
| r"It is possible to write endlessly \\on elliptic curves. (This is not a threat.) \\ -- Serge Lang", | |
| font_size=42, | |
| ) | |
| self.play(Write(serge_lang)) | |
| self.wait(10) | |
| self.play(FadeOut(serge_lang)) | |
| self.wait(10) | |
| def get_y_neg(x): | |
| return -np.sqrt(x**3 - x + 1) | |
| def update_r(p2, p0x, get_point): | |
| p2.move_to(get_point(point_addition([p0x, get_y_pos(p0x)], [0.4, 0.8149])[0])) | |
| class CurveGraph(Scene): | |
| def construct(self): | |
| ax = Axes( | |
| x_range=[-3, 3, 1], | |
| y_range=([-3, 3, 1]), | |
| axis_config={"include_numbers": False}, | |
| tips=False, | |
| color=BLACK, | |
| fill_color=BLACK, | |
| stroke_color=BLACK, | |
| ).to_edge(DOWN) | |
| posgraph = ax.plot( | |
| lambda x: get_y_pos(x), | |
| x_range=[-1.3244, 3], | |
| use_smoothing=True, | |
| discontinuities=[-1.325, -0.577, 0, 0.577], | |
| dt=0.001, | |
| color=YELLOW, | |
| fill_color=YELLOW, | |
| ) | |
| neggraph = ax.plot( | |
| lambda x: get_y_neg(x), | |
| x_range=[-1.3244, 3], | |
| use_smoothing=True, | |
| discontinuities=[-1.325, -0.577, 0, 0.577], | |
| dt=0.001, | |
| color=YELLOW, | |
| fill_color=YELLOW, | |
| ) | |
| title = Tex(r"Graph of $y^2 = x^3 - x + 1$", color=WHITE, font_size=54) | |
| title.to_edge(UP) | |
| dot_discontinuity = Dot( | |
| (ax.coords_to_point(-1.325, 0)), | |
| stroke_color=YELLOW, | |
| fill_opacity=0.0, | |
| stroke_width=3.0, | |
| ) | |
| self.play(Create(ax, lag_ratio=0.01, run_time=1)) | |
| self.play(Create(posgraph), Create(neggraph)) | |
| self.play(Create(dot_discontinuity, run_time=0.5)) | |
| self.play(FadeIn(title, shift=DOWN), run_time=0.9) | |
| self.wait(5) | |
| dotr = 0.06 | |
| p0start = -1.22 | |
| p0tracker = ValueTracker(p0start) | |
| p0 = Dot(posgraph.get_point_from_function(p0start), color=RED, radius=dotr) | |
| p0.add_updater( | |
| lambda m: m.move_to(posgraph.get_point_from_function(p0tracker.get_value())) | |
| ) | |
| p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) | |
| p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) | |
| update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) | |
| negP = Dot(neggraph.get_point_from_function(p0start), radius=dotr) | |
| p0.z_index = 2 | |
| p1.z_index = 2 | |
| p2.z_index = 2 | |
| negP.z_index = 2 | |
| line = Line(p0, p1) | |
| line.set_length(20) | |
| labelP = MathTex("P", color=WHITE).next_to(p0, UP) | |
| labelQ = MathTex("Q", color=WHITE).next_to(p1, UP) | |
| labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) | |
| labelNegP = MathTex("-P", color=WHITE).next_to(negP, DOWN) | |
| identity = Tex( | |
| r"Definition: $P + \mathcal{O} = P$ \\That is, $\mathcal{O}$ is the identity element.", | |
| font_size=42, | |
| ).to_edge(UP) | |
| addition = Tex(r"Definition: $P + Q + R = \mathcal{O}$", font_size=48).to_edge( | |
| UP | |
| ) | |
| negation = Tex( | |
| r"Definition: $(-P)$ is defined to be $P$, \\but symmetric over the $x$-axis", | |
| font_size=42, | |
| ).to_edge(UP) | |
| inverse = Tex( | |
| r"From the definition of negation, \\we can say that $P + (-P) = \mathcal{O}$", | |
| font_size=42, | |
| ).to_edge(UP) | |
| approaches = Tex( | |
| r"As $P$ approaches $Q$, they form a tangent line.", font_size=44 | |
| ).to_edge(UP) | |
| app = Tex( | |
| r"As $P$ approaches $Q$, \\then $P + Q$ becomes the same as $2P$.", | |
| font_size=44, | |
| ).to_edge(UP) | |
| self.play( | |
| Create(p0), | |
| Create(p1), | |
| Create(p2), | |
| Write(labelP), | |
| Write(labelQ), | |
| Write(labelR), | |
| ) | |
| self.play(FadeTransform(title, identity)) | |
| self.wait(5) | |
| self.play(Write(line), run_time=1.5) | |
| self.play(FadeTransform(identity, addition)) | |
| self.wait(5) | |
| self.play(Write(labelNegP), Uncreate(labelQ), Uncreate(labelR), FadeOut(line)) | |
| self.play(Uncreate(p1), Uncreate(p2), Create(negP)) | |
| P_to_negP = Line(p0, negP) | |
| extended_P_to_negP = P_to_negP.copy().set_length(5) | |
| self.play(Create(P_to_negP), FadeTransform(addition, negation)) | |
| self.wait(5) | |
| self.play( | |
| Transform(P_to_negP, extended_P_to_negP), | |
| Uncreate(labelP), | |
| Uncreate(labelNegP), | |
| FadeTransform(negation, inverse), | |
| ) | |
| self.wait(5) | |
| p1 = Dot(posgraph.get_point_from_function(0.4), color=RED, radius=dotr) | |
| p2 = Dot([0, 0, 0], color=GREEN, radius=dotr) | |
| update_r(p2, p0tracker.get_value(), posgraph.get_point_from_function) | |
| p2.add_updater( | |
| lambda m: update_r( | |
| m, p0tracker.get_value(), posgraph.get_point_from_function | |
| ) | |
| ) | |
| line2 = Line(p0, p1) | |
| line2.set_length(20) | |
| line2.add_updater( | |
| lambda m: ( | |
| m.set_points_by_ends(p0.get_center(), p1.get_center()), | |
| m.set_length(20), | |
| ) | |
| ) | |
| p1.z_index = 2 | |
| p2.z_index = 2 | |
| self.play( | |
| Create(p1), | |
| Create(p2), | |
| # Write(line), | |
| FadeTransform(inverse, approaches), | |
| ) | |
| self.wait(2) | |
| self.play(Uncreate(negP), FadeOut(P_to_negP), run_time=1) | |
| self.play(Write(line2)) | |
| self.wait(1) | |
| self.play(p0tracker.animate.set_value(0.399), run_time=6) | |
| self.wait() | |
| label2P = MathTex("2P", color=WHITE).next_to(p0, UP) | |
| labelR = MathTex("R", color=WHITE).next_to(p2, UP * 1.5) | |
| self.play( | |
| FadeTransform(approaches, app), | |
| Write(label2P), | |
| Write(labelR), | |
| ) | |
| graph = Group( | |
| ax, | |
| dot_discontinuity, | |
| p0, | |
| p1, | |
| p2, | |
| posgraph, | |
| neggraph, | |
| ) | |
| # transformedGraph = graph.copy().scale(0.25).to_edge(DR) | |
| self.wait(5) | |
| self.play(Uncreate(label2P), Uncreate(labelR)) | |
| self.play(FadeOut(line2), FadeOut(app, shift=UP)) | |
| self.wait(0.5) | |
| #self.play(Transform(graph, transformedGraph)) | |
| self.play(Uncreate(graph)) | |
| self.wait(1) | |
| equations = Tex( | |
| r"Let's take a look at the equations we're going to use now." | |
| ).to_edge(UP) | |
| slope = Tex( | |
| r"We can calculate the slope of $P$ and $Q$ with\\$m = \frac{Q_y - P_y}{Q_x - P_x}$" | |
| ).next_to(equations, DOWN * 2) | |
| coordinatesR = Tex( | |
| r"And then we can calculate the coordinates of $R = P + Q$ with\\$R_x = m^2 - P_x - Q_x$\\$R_y = P_y + m(R_x - P_x)$" | |
| ).next_to(slope, DOWN * 2) | |
| dotdotdot = Tex("...") | |
| if_p_equals_q = Tex(r"If $P = Q$, then").next_to(coordinatesR, UP) | |
| derivative = MathTex( | |
| r"\frac{\frac{d}{dx} (x^3 + ax + b)}{\frac{d}{dy} (y^2)}", font_size=60 | |
| ).next_to(if_p_equals_q, DOWN) | |
| new_slope = MathTex(r"\frac{3x^2 + a}{2y}", font_size=60).move_to(derivative) | |
| self.play(FadeIn(equations, shift=DOWN)) | |
| self.wait(2) | |
| self.play(Write(slope)) | |
| self.wait(4) | |
| self.play(FadeOut(equations), run_time=1) | |
| self.play(Write(coordinatesR)) | |
| self.wait(5) | |
| self.play(FadeOut(slope), FadeOut(coordinatesR)) | |
| self.wait(1) | |
| self.play(FadeIn(dotdotdot)) | |
| self.wait(3) | |
| self.play(FadeOut(dotdotdot)) | |
| self.wait(0.5) | |
| self.play(Write(if_p_equals_q)) | |
| self.wait(0.5) | |
| self.play(Write(derivative)) | |
| self.wait(3) | |
| self.play(Transform(derivative, new_slope)) | |
| self.wait(3) | |
| self.play(Uncreate(if_p_equals_q), Uncreate(new_slope)) | |
| self.wait(1) | |
| class ModularArithmetic(Scene): | |
| def construct(self): | |
| circle = Circle(radius = 3, color=BLUE_B) | |
| invisible_circle = Circle().set_stroke(GRAY, opacity=0).surround(circle, buffer_factor=0.6) | |
| center = Dot(circle.get_center(), color=WHITE, radius=0.1) | |
| self.add(circle, invisible_circle, center) | |
| numbers_clock = VGroup() | |
| for (i, angle) in enumerate(reversed(range(90, 360 + 90, 30))): | |
| point = invisible_circle.point_at_angle((angle % 360) * DEGREES) | |
| text = Text(str(i + 1), font_size=24).move_to(point) | |
| numbers_clock += text | |
| self.play(Write(numbers_clock)) | |
| twelve = invisible_circle.point_at_angle(PI/2) - np.array([0, 0.5, 0]) | |
| pointer = Line(center, twelve) | |
| self.play(Create(pointer)) | |
| self.wait() | |
| # Rotate to 14 h | |
| fourteen = MathTex(r"14 \equiv 2 (\textrm{mod} 12)").to_edge(UP) | |
| self.play(Write(fourteen)) | |
| self.play(Rotate(pointer, angle=(-2 * PI - PI/3), about_point=ORIGIN), run_time=4) | |
| self.wait(3) | |
| self.play(Uncreate(fourteen)) | |
| self.wait(0.5) | |
| # Reset to 12 | |
| self.play(Rotate(pointer, angle=PI/3, about_point=ORIGIN), run_time=1) | |
| self.wait(3) | |
| # Rotate to 11 h | |
| eleven = MathTex(r"-1 \equiv 11 (\textrm{mod} 12)").to_edge(UP) | |
| self.play(Write(eleven)) | |
| self.play(Rotate(pointer, angle=PI/6, about_point=ORIGIN)) | |
| self.wait(3) | |
| # Reset | |
| self.play(Uncreate(eleven), Uncreate(center), Uncreate(pointer), Uncreate(numbers_clock), Uncreate(circle), run_time=1) | |
| self.wait(3) | |
| title_mod = Tex(r"List of multiplicative inverses in $n$ (\textrm{mod} 8)").to_edge(UP) | |
| table = MobjectTable([ | |
| [MathTex("1"), MathTex(r"1 \cdot 1 = 1 \equiv 1")], | |
| [MathTex("2"), MathTex(r"\nexists")], | |
| [MathTex("3"), MathTex(r"3 \cdot 3 = 9 \equiv 1")], | |
| [MathTex("4"), MathTex(r"\nexists")], | |
| [MathTex("5"), MathTex(r"5 \cdot 5 = 25 \equiv 1")], | |
| [MathTex("6"), MathTex(r"\nexists")], | |
| [MathTex("7"), MathTex(r"7 \cdot 7 = 49 \equiv 1")], | |
| ], | |
| col_labels=[MathTex("n"), MathTex("n^{-1}")]).scale(0.6).to_edge(DOWN) | |
| cells = VGroup(table.get_cell((3, 1), color=RED_B), | |
| table.get_cell((3, 2), color=RED_B), | |
| table.get_cell((5, 1), color=RED_B), | |
| table.get_cell((5, 2), color=RED_B), | |
| table.get_cell((7, 1), color=RED_B), | |
| table.get_cell((7, 2), color=RED_B)) | |
| self.play(table.create(), Write(title_mod)) | |
| self.wait(4) | |
| self.play(Create(cells), run_time=2.5) | |
| # for cell in cells: | |
| # self.play(Create(cell), run_time=0.75) | |
| self.wait(4) | |
| # for cell in cells: | |
| # self.play(Uncreate(cell), run_time=0.25) | |
| self.play(Uncreate(cells), run_time=2.5) | |
| self.wait() | |
| self.play(Uncreate(table), Uncreate(title_mod), run_time=2.5) | |
| self.wait() | |
| fraction = MathTex(r"\frac{3}{4}", r"\: (\textrm{mod} \, 5)") | |
| inverse = MathTex(r"3 \cdot ", r"4^{-1}", r"\: (\textrm{mod} \, 5)") | |
| result = MathTex(r"3 \cdot ", r"4", r" \equiv 2", r"\: (\textrm{mod} \, 5)") | |
| self.play(FadeIn(fraction, shift=UP)) | |
| self.wait() | |
| self.play(TransformMatchingTex(fraction, inverse)) | |
| self.wait() | |
| self.play(TransformMatchingTex(inverse, result)) | |
| self.wait() | |
| field = MathTex(r"\mathbb{F}_p").next_to(result, DOWN * 1.5) | |
| self.play(Write(field)) | |
| self.wait(3) | |
| self.play(Uncreate(field), Uncreate(result)) | |
| CHR = 31 | |
| def extended_euclidean_algorithm(a, b): | |
| s, old_s = 0, 1 | |
| t, old_t = 1, 0 | |
| r, old_r = b, a | |
| while r != 0: | |
| quotient = old_r // r | |
| old_r, r = r, old_r - quotient * r | |
| old_s, s = s, old_s - quotient * s | |
| old_t, t = t, old_t - quotient * t | |
| return old_r, old_s, old_t | |
| def inverse_of(n, p): | |
| gcd, x, y = extended_euclidean_algorithm(n, p) | |
| assert (n * x + p * y) % p == gcd | |
| if gcd != 1: | |
| # Either n is 0, or p is not a prime number. | |
| raise ValueError( | |
| '{} has no multiplicative inverse ' | |
| 'modulo {}'.format(n, p)) | |
| else: | |
| return x % p | |
| def get_y_pos(x): | |
| return np.sqrt(x**3 - x + 1) | |
| def get_y_field(x): | |
| square = (x ** 3 - x + 1) % CHR | |
| inverse = inverse_of(x, CHR) | |
| return (square * inverse) % CHR | |
| X_LIMIT = CHR | |
| X_RANGE = np.int32(get_y_pos(X_LIMIT)) | |
| class EllipticFiniteField(Scene): | |
| def construct(self): | |
| ax = Axes( | |
| x_range=[-1, X_LIMIT, 1], | |
| y_range=([-1, X_RANGE, 1]), | |
| axis_config={"include_numbers": False, "include_ticks": False}, | |
| tips=False, | |
| color=BLACK, | |
| fill_color=BLACK, | |
| stroke_color=BLACK, | |
| ).to_edge(DOWN) | |
| ax2 = Axes( | |
| x_range=[-1, CHR-1, 1], | |
| y_range=[-1, CHR-1, 1], | |
| axis_config={"include_numbers": False}, | |
| tips=False, | |
| color=BLACK, | |
| fill_color=BLACK, | |
| stroke_color=BLACK | |
| ).to_edge(DOWN) | |
| posgraph = ax.plot( | |
| lambda x: get_y_pos(x), | |
| x_range=[-1.3244, X_LIMIT], | |
| use_smoothing=True, | |
| discontinuities=[-1.325, -0.577, 0, 0.577], | |
| dt=0.001, | |
| color=YELLOW, | |
| fill_color=YELLOW, | |
| ) | |
| # title_pedantic = Tex("$\{(x, y) \\in \\mathbb{R} | y^2 = x^3 - x + 1$\}", font_size=32).to_edge(UP) | |
| # title_field_pedantic = Tex("$\{(x, y) \\in (\\mathbb{F}_{%d})^2 | y^2 = x^3 - x + 1 (\\mod %d)\}$" | |
| # % (CHR, CHR), | |
| # font_size=32).to_edge(UP) | |
| title = MathTex(r"y^2 = x^3 - x + 1", font_size=44).to_edge(UP) | |
| title_field = MathTex(r"y^2 = x^3 - x + 1", r"\: (\textrm{mod} \, %d)" % CHR, font_size=44).to_edge(UP) | |
| dots = [] | |
| field_dots = [] | |
| field_neg = [] | |
| for i in range(1, X_LIMIT): | |
| dots.append(Dot(posgraph.get_point_from_function(i), color=ORANGE)) | |
| field_dots.append(get_y_field(i)) | |
| field_neg.append(-get_y_field(i) % CHR) | |
| dots = VGroup(*dots) | |
| field_dots = ax2.plot_line_graph(range(1, CHR), field_dots).set_color(ORANGE) | |
| field_neg = ax2.plot_line_graph(range(1, CHR), field_neg).set_color(YELLOW) | |
| self.play(Create(ax, lag_ratio=0.01, run_time=1)) | |
| self.play(Create(posgraph), Create(dots), run_time=2) | |
| self.play(Write(title)) | |
| self.wait(1) | |
| self.play(Transform(ax, ax2, replace_mobject_with_target_in_scene=True)) | |
| self.play(FadeOut(posgraph)) | |
| self.wait(1) | |
| self.play(TransformMatchingTex(title, title_field)) | |
| self.wait(1) | |
| self.play(Transform(dots, field_dots["vertex_dots"], replace_mobject_with_target_in_scene=True), Create(field_neg["vertex_dots"])) | |
| self.wait(2) | |
| linep2 = Line(ax2.coords_to_point(0, CHR / 2, 0), ax2.coords_to_point(CHR, CHR / 2, 0), color=WHITE) | |
| self.play(Create(linep2)) | |
| self.wait(2) | |
| upper_rect = Polygon( | |
| ax2.coords_to_point(0, 0, 0), | |
| ax2.coords_to_point(0, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, 0, 0), | |
| color=MAROON_B, | |
| fill_color=MAROON_B, | |
| fill_opacity=0.8) | |
| lower_rect = Polygon( | |
| ax2.coords_to_point(0, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, CHR / 2, 0), | |
| ax2.coords_to_point(CHR, CHR, 0), | |
| ax2.coords_to_point(0, CHR, 0), | |
| color=MAROON_B, | |
| fill_color=MAROON_B, | |
| fill_opacity=0.8) | |
| self.play(FadeOut(lower_rect), run_time=1.5) | |
| self.wait(1) | |
| self.play(FadeOut(upper_rect), run_time=1.5) | |
| self.wait(1) | |
| self.play(Uncreate(linep2)) | |
| self.wait(5) | |
| graph = Group( | |
| ax2, | |
| field_dots["vertex_dots"], | |
| field_neg["vertex_dots"] | |
| ) | |
| # transformedGraph = graph.copy().scale(0.25).to_edge(DR) | |
| self.play(Uncreate(title_field)) | |
| # self.play(Transform(graph, transformedGraph, replace_mobject_with_target_in_scene=True)) | |
| self.wait(3) | |
| ref_group_law = Tex(r"[1] An elementary proof of the group law for elliptic curves \\Friedl, Stefan\\ October 2017", font_size=24).to_edge(UR) | |
| self.play(FadeIn(ref_group_law, shift=LEFT)) | |
| self.wait(3) | |
| self.play(FadeOut(ref_group_law, shift=RIGHT)) | |
| self.wait() | |
| self.play(Uncreate(graph)) | |
| self.wait() | |
| mult_of_p = MathTex(r"P = 30 \\ 2P = 312, \\ 3P = 3123") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment