Skip to content

Instantly share code, notes, and snippets.

@arskiy
Last active August 18, 2022 21:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save arskiy/35f76c9b960871ad29a820ebd63d033b to your computer and use it in GitHub Desktop.
Save arskiy/35f76c9b960871ad29a820ebd63d033b to your computer and use it in GitHub Desktop.
# 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