The Cartesian Unit Circle
Descartes' invention of the coordinate plane in the 17th century gave us the unit circle — the set of all points at distance 1 from the origin. This single equation x² + y² = 1 quietly underpins nearly every major idea in cryptography.
S¹ = { (x, y) ∈ ℝ² : x² + y² = 1 }
Parametrized by angle θ: (x, y) = (cos θ, sin θ)
As a complex number: z = e^(iθ) = cos θ + i sin θ (|z| = 1)
The Circle as an Algebraic Group
Points on the unit circle form a group under angle addition. Two points combine not by adding coordinates but by adding their angles — and this group law is what generalises into every cryptographic primitive:
René Descartes introduced analytic geometry in his 1637 appendix La Géométrie. By placing the circle x²+y²=r² in a coordinate system, he made geometry computable — the same move that centuries later allowed cryptographers to turn geometric objects like elliptic curves into arithmetic algorithms.
%% The Unit Circle as an Algebraic Group %% Points: (cos θ, sin θ); Law: add angles function C = circle_add(A, B) % Group operation: (x1,y1) ★ (x2,y2) = (x1x2-y1y2, x1y2+x2y1) C = [A(1)*B(1) - A(2)*B(2), A(1)*B(2) + A(2)*B(1)]; end function A = circle_inv(P) A = [P(1), -P(2)]; % reflection in x-axis = angle negation end function R = circle_pow(P, n) % Scalar multiplication = repeated angle addition (n copies) R = [1,0]; % identity (angle 0) for k = 1:n R = circle_add(R, P); end end % Demo: A = 40°, B = 65° → A★B = 105° A = [cosd(40), sind(40)]; B = [cosd(65), sind(65)]; C = circle_add(A, B); angle_C = atan2d(C(2), C(1)); printf('A★B angle = %.4f° (expect 105°)\n', angle_C); printf('|A★B| = %.6f (must be 1)\n', norm(C)); % n-th power = n·θ = angle multiplication P = [cosd(30), sind(30)]; % 30° point P12= circle_pow(P, 12); % 12×30° = 360° = identity printf('12 × 30° point → (%.6f, %.6f) ≈ (1,0)\n', P12(1), P12(2)); % The group axioms verified: % Closure: |A★B| = 1 ✓ % Associativity: (A★B)★C = A★(B★C) ✓ (follows from angle addition) % Identity: (1,0) ✓ % Inverse: (x,-y) ✓
Euler's Formula — The Circle as an Exponential
In 1748, Euler revealed that the unit circle and the exponential function are the same object in disguise. This identity transforms all circular reasoning into algebraic computation — and underpins every use of roots of unity in cryptography.
Every use of "roots of unity" in the DFT, NTT, and cyclotomic rings is just evaluating e^(2πik/n) — points evenly spaced on the circle. The NTT (which runs Kyber and Dilithium) is exactly the DFT with e^(2πi/n) replaced by its modular analogue: a number ω in ℤ_q with ω^n ≡ 1 (mod q).
%% Euler's formula: the circle as a complex exponential % Verify Euler's formula numerically theta = linspace(0, 2*pi, 7); printf('θ(deg) e^(iθ) computed cos+i·sin\n'); for t = theta euler = exp(1i*t); trig = cos(t) + 1i*sin(t); printf('%6.1f° %+.4f%+.4fi %+.4f%+.4fi match:%d\n', ... rad2deg(t), real(euler), imag(euler), ... real(trig), imag(trig), abs(euler-trig)<1e-10); end % Encryption as rotation: multiply by e^(iθ) rotates the complex plane % This is the Cayley-Klein parameterization of rotations — same algebra as RSA msg = 3 + 4*1i; % complex message key = exp(1i*pi/3); % rotation by 60° enc = msg * key; dec = enc * conj(key); % rotate back (inverse = conjugate on unit circle) printf('\nMessage: %+.4f%+.4fi\n', real(msg), imag(msg)); printf('Encrypted: %+.4f%+.4fi (rotated 60°)\n', real(enc), imag(enc)); printf('Decrypted: %+.4f%+.4fi (back to start)\n', real(dec), imag(dec));
Roots of Unity — The Circle's Integer Children
The n-th roots of unity are the n equally-spaced points where the unit circle intersects itself when you "visit every nth stop." They are simultaneously the most natural objects on the circle and the engine of the fast Fourier transform — and, via the NTT, of post-quantum cryptography.
From Continuous to Discrete: DFT and NTT
The Discrete Fourier Transform evaluates a polynomial f(x) at all n-th roots of unity simultaneously. The NTT does the same, but replaces the complex roots e^(2πi/n) with modular roots — numbers ω ∈ ℤ_q where ω^n ≡ 1 (mod q). The circle does not vanish; it moves from ℂ into a finite field.
%% Roots of Unity: the circle's arithmetic children % Generate all n-th roots of unity function W = roots_of_unity(n) W = exp(2*pi*1i * (0:n-1) / n); end % DFT = evaluate polynomial at all n-th roots of unity function F = dft_via_circle(f) n = length(f); W = roots_of_unity(n); F = zeros(1, n); for k = 0:n-1 F(k+1) = polyval(fliplr(f), W(k+1)); % f(ωᵏ) end end f = [1, 2, 3, 4]; % polynomial 1 + 2x + 3x² + 4x³ F_circle = dft_via_circle(f); F_fft = fft(f); printf('Circle evaluation DFT: '); disp(round(real(F_circle))); printf('Built-in FFT: '); disp(round(real(F_fft))); printf('Max error: %.2e\n', max(abs(F_circle - F_fft))); % Show that primitive roots generate all others n = 12; W = roots_of_unity(n); printf('\nPrimitive 12th roots (gcd(k,12)=1):\n'); for k = 0:n-1 if gcd(k, n) == 1 printf(' ω^%2d = e^(2πi·%2d/12): angle=%5.1f°\n', k, k, k*360/n); end end printf('φ(12) = %d primitive roots\n', sum(arrayfun(@(k) gcd(k,12)==1, 0:11)));
Cyclic Groups — The Digital Circle
A cyclic group ℤ/nℤ is the exact discrete analogue of the circle: n equally-spaced points, arranged in a ring, where "addition" means stepping clockwise. The entire structure of Diffie-Hellman, DSA, and RSA lives inside this abstraction.
%% Cyclic Groups — the Digital Circle function modpow = mpow(b,e,m) modpow=1; b=mod(b,m); while e>0 if bitand(e,1); modpow=mod(modpow*b,m); end e=bitshift(e,-1); b=mod(b^2,m); end end function orbit = group_orbit(g, p) % All powers of g mod p: g^0, g^1, ..., until cycle orbit = []; cur = 1; do orbit = [orbit, cur]; cur = mod(cur*g, p); until cur == 1 end p = 23; % prime modulus printf('Orbits in ℤ/%d (the discrete circle with %d points):\n\n', p, p-1); for g = [2, 3, 4, 5] orb = group_orbit(g, p); printf('g=%-2d: order=%-3d generator? %d\n', g, length(orb), length(orb)==p-1); end % Discrete logarithm = "how many steps around the circle?" function x = dlog_brute(g, h, p) % Find x: g^x ≡ h (mod p) — the DH hardness assumption cur = 1; for x = 0:p-2 if cur == h; return; end cur = mod(cur*g, p); end; x = -1; end g = 5; secret = 11; pub = mpow(g, secret, p); % go 11 steps around the circle recovered = dlog_brute(g, pub, p); % find how many steps (hard for large p) printf('\nDH: g=%d, p=%d, secret=%d → g^s=%d → dlog=%d\n', g,p,secret,pub,recovered);
Rational Points on the Circle — & the Road to Elliptic Curves
The unit circle has infinitely many rational points — points (a/c, b/c) where a² + b² = c². These are Pythagorean triples. The method of finding them by drawing rational lines through a known point is exactly the technique that, one degree higher, produces the group law on elliptic curves.
The circle is a genus-0 curve — it has a rational point, so rational parameterization is possible. Elliptic curves are genus-1 — no such global parameterization exists, which is exactly why finding discrete logs is hard. But the same "chord through two known points" geometric idea produces the group law on an elliptic curve, directly generalising the circle law above.
%% Rational Points on the Unit Circle = Pythagorean Triples function [x,y] = rational_circle_point(p, q) % Parameterization: t = p/q → (x,y) on unit circle t = p / q; x = (1 - t^2) / (1 + t^2); y = 2*t / (1 + t^2); end function [a,b,c] = pythag_triple(p, q) % Primitive Pythagorean triple from p > q > 0, gcd(p,q)=1, p-q odd a = p^2 - q^2; b = 2*p*q; c = p^2 + q^2; end printf('Rational points on unit circle via t = p/q:\n'); printf('%-6s %-20s %-8s %-18s\n','t=p/q','(x, y)','x²+y²','triple (a,b,c)'); printf('%s\n',repmat('-',62,1)); params = [1,1; 2,1; 3,2; 4,1; 5,2; 5,4; 7,2]; for i = 1:rows(params) p = params(i,1); q = params(i,2); [x,y] = rational_circle_point(p,q); [a,b,c] = pythag_triple(p,q); printf('%d/%d (%7.4f, %7.4f) %.4f (%d,%d,%d)\n', ... p,q, x,y, x^2+y^2, a,b,c); end % (3,4,5), (5,12,13), (8,15,17), (15,8,17), (20,21,29), (40,42,58)... % All arise from the unit circle with rational slope lines % This same "rational line through known point" method gives the elliptic curve group law!
The Circle over a Finite Field 𝔽_p
Move the unit circle from ℝ to the finite field 𝔽_p — replace all real arithmetic with arithmetic mod a prime p. The result is a finite group of points that is itself a valid cryptographic group, closely related to Gaussian integers.
%% The Unit Circle over a Finite Field function pts = circle_mod_p(p) % All (x,y) in F_p with x²+y² ≡ 1 (mod p) pts = []; for x = 0:p-1 for y = 0:p-1 if mod(x^2 + y^2, p) == 1 pts = [pts; x, y]; end end end end function C = cmod_add(A, B, p) C = mod([A(1)*B(1)-A(2)*B(2), A(1)*B(2)+A(2)*B(1)], p); end printf('Prime p p mod 4 |C_p| p±1 match\n'); printf('%s\n',repmat('-',42,1)); for p = [5,7,11,13,17,19,23,29,31] pts = circle_mod_p(p); cnt = rows(pts); pm4 = mod(p,4); expected = if(pm4==1, p-1, p+1); printf('%5d %d %4d %d %d\n', p,pm4,cnt,expected,cnt==expected); end % Verify the group law: pick two random points, add, check still on circle p = 29; pts = circle_mod_p(p); A = pts(5,:); B = pts(11,:); C = cmod_add(A, B, p); printf('\n(%d,%d) ★ (%d,%d) = (%d,%d) on circle: %d\n', ... A(1),A(2),B(1),B(2),C(1),C(2), mod(C(1)^2+C(2)^2,p)==1);
The Torus — An Elliptic Curve is a Circle × Circle
Over the complex numbers, every elliptic curve is topologically a torus — the product of two circles S¹ × S¹. This is not just a curiosity: the lattice periods of the torus encode the curve's arithmetic, and the theory of complex multiplication (where imaginary quadratic fields act as endomorphisms) arises precisely from the symmetry of the torus.
Circle (genus 0)
x² + y² = 1 over ℝ is topologically S¹ (one circle). Rational parameterization exists. The group law is just angle addition. DLP is easy — just compute an inverse trig.
Elliptic Curve (genus 1)
y² = x³ + ax + b over ℝ is topologically S¹ × S¹ (a torus). No rational parameterization. Group law requires solving cubics. DLP is hard — 256-bit ECC ≈ RSA-3072.
%% The Circle-to-Torus progression: group laws compared % Circle group law (angle addition) function R = circle_law(P,Q) R = [P(1)*Q(1)-P(2)*Q(2), P(1)*Q(2)+P(2)*Q(1)]; end % Elliptic curve group law over ℝ: y² = x³ - x (a=-1, b=0) function R = ec_law(P,Q,a) if P(1)==Q(1) && P(2)==Q(2) % doubling lam = (3*P(1)^2+a)/(2*P(2)); else lam = (Q(2)-P(2))/(Q(1)-P(1)); end x3 = lam^2 - P(1) - Q(1); y3 = lam*(P(1)-x3) - P(2); R = [x3, y3]; end % Circle: 10 × 36° = 360° = identity P36 = [cosd(36), sind(36)]; acc = [1,0]; for k=1:10; acc=circle_law(acc,P36); end printf('Circle: 10 × 36° = (%.4f, %.4f) [expect (1,0)]\n', acc(1),acc(2)); % Elliptic curve y²=x³-x: the group law is the "chord-and-tangent" rule a_ec=-1; P_ec=[-1,0]; Q_ec=[0,0]; % two points with y=0 (order 2) R_ec=[1.5, sqrt(1.5^3-1.5)]; % point on curve R2 = ec_law(R_ec,R_ec,a_ec); printf('EC 2P: P=(%.3f,%.3f) → 2P=(%.3f,%.3f)\n',R_ec(1),R_ec(2),R2(1),R2(2)); printf('On curve: y²-x³+x = %.6f (expect 0)\n', R2(2)^2-R2(1)^3+R2(1));
Circular & Negacyclic Convolution
When you multiply polynomials, the natural result "overflows" in degree. Two ways to wrap that overflow back around a circle — and the choice between them creates the algebraic difference between the old NTT and the post-quantum NTT.
The equation xⁿ = −1 means x²ⁿ = 1 — so x is a primitive 2n-th root of unity. In terms of angle: a 2n-th root sits at angle π/n, so taking the n-th power lands at angle π — the point (−1, 0) on the unit circle. Negation is literally a half-rotation. Every sign flip in the negacyclic NTT is a half-turn on the circle.
%% Circular vs Negacyclic Convolution — the two ways to wrap around a circle function r = cyclic_conv(a, b, q) % Polynomial mult mod (x^n - 1): overflow wraps +1 n=length(a); r=zeros(1,n); for i=0:n-1; for j=0:n-1 r(mod(i+j,n)+1) += a(i+1)*b(j+1); % sign = +1 always end; end r = mod(r, q); end function r = negacyclic_conv(a, b, q) % Polynomial mult mod (x^n + 1): overflow wraps with -1 [RING-LWE / KYBER] n=length(a); r=zeros(1,n); for i=0:n-1; for j=0:n-1 deg = i+j; sign = 1 - 2*(floor(deg/n)); % +1 if no wrap; -1 if wrap (half-circle flip!) r(mod(deg,n)+1) += sign*a(i+1)*b(j+1); end; end r = mod(r, q); end a = [1,2,3,4]; b = [4,3,2,1]; q = 97; printf('Polynomial a: [%d %d %d %d] (1+2x+3x²+4x³)\n', a); printf('Polynomial b: [%d %d %d %d] (4+3x+2x²+x³)\n\n', b); cyc = cyclic_conv(a,b,q); nega = negacyclic_conv(a,b,q); printf('mod x^4−1 (full circle, sign=+1): [%d %d %d %d]\n', cyc); printf('mod x^4+1 (half circle, sign=−1): [%d %d %d %d]\n', nega); % The difference: overflow in x^4−1 adds back unchanged; % in x^4+1 (Kyber/Ring-LWE), it SUBTRACTS (180° rotation on circle)
The Weil Bounds — Eigenvalues on the Circle
The deepest theorem connecting circles to cryptography is the Weil Conjectures (proved by Deligne in 1974). For any curve over a finite field, the "error" in the point count is controlled by eigenvalues that always lie on a circle of radius √q in the complex plane. This provides tight bounds used in proving PRG security and in the analysis of hash functions.
%% Weil bounds: eigenvalues of Frobenius lie on a circle of radius √p function n = count_ec_points(a, b, p) n = 1; % point at infinity for x = 0:p-1 rhs = mod(x^3+a*x+b,p); if rhs==0; n+=1; elseif mod(rhs^((p-1)/2),p)==1; n+=2; end end end % For each elliptic curve, compute the Frobenius eigenvalue α = (t/2) ± i√(p-t²/4) % where t = p+1-#E is the trace. |α|² = p (circle of radius √p) printf('Curve #E t=p+1-#E |α|²=? |α|=? Weil OK?\n'); printf('%s\n',repmat('-',62,1)); p = 101; for [a,b] = [[1;0],[0;1],[3;5],[-1;3],[2;7],[5;11]] cnt = count_ec_points(mod(a,p),mod(b,p),p); t = p+1-cnt; alpha = t/2 + 1i*sqrt(max(0, p-(t/2)^2)); printf('y²=x³%+dx%+d %4d t=%+4d |α|²=%-5.1f |α|=%-5.3f %d\n', ... a,b,cnt,t, abs(alpha)^2,abs(alpha), abs(abs(alpha)^2-p)<1); end printf('\nHasse bound: |t| ≤ 2√p = %.3f\n', 2*sqrt(p)); % Every |α|² = p exactly ← eigenvalue on the √p-circle
Descartes' Circle Theorem & Integer Packings
Beyond the coordinate circle, Descartes proved a remarkable theorem about four mutually tangent circles. The resulting Apollonian gasket has deep connections to quadratic forms, integer lattices, and the arithmetic that underlies lattice-based cryptography.
Integer Apollonian packings are governed by the quadratic form Q(k₁,k₂,k₃,k₄) = (k₁+k₂+k₃+k₄)² − 2(k₁²+k₂²+k₃²+k₄²) = 0. This is exactly the type of quadratic form studied in lattice-based cryptography (LWE), where security reduces to the hardness of finding short vectors in lattices defined by quadratic forms. The Apollonian group — the group of moves on the gasket — is a subgroup of GL(4,ℤ), the same group of integer matrix operations at the heart of NTRU.
%% Descartes' Circle Theorem and Integer Apollonian Packings function k4s = descartes_k4(k1,k2,k3) % Solve (k1+k2+k3+k4)² = 2(k1²+k2²+k3²+k4²) for k4 % Equivalent: k4 = k1+k2+k3 ± 2*sqrt(k1*k2+k2*k3+k3*k1) s = k1+k2+k3; rad = k1*k2 + k2*k3 + k3*k1; if rad < 0 k4s = [s+2*1i*sqrt(-rad), s-2*1i*sqrt(-rad)]; else k4s = [s+2*sqrt(rad), s-2*sqrt(rad)]; end end % Classic starter: k = (-1, 2, 2, 3) — outer circle r=1 encloses three tangent circles [k1,k2,k3,k4] = deal(-1, 2, 2, 3); printf('Starting packing: k = (%d, %d, %d, %d)\n', k1,k2,k3,k4); lhs = (k1+k2+k3+k4)^2; rhs = 2*(k1^2+k2^2+k3^2+k4^2); printf('Descartes check: (Σkᵢ)² = %d, 2Σkᵢ² = %d, OK: %d\n', lhs,rhs,lhs==rhs); % Generate next level of packing printf('\nApollonian generation from (%d,%d,%d,%d):\n',k1,k2,k3,k4); triples = {[k2,k3,k4],[k1,k3,k4],[k1,k2,k4],[k1,k2,k3]}; for t = triples tr = t{1}; new_k = descartes_k4(tr(1),tr(2),tr(3)); printf(' triple (%d,%d,%d) → new circles with k = %.0f, %.0f\n', ... tr(1),tr(2),tr(3), real(new_k(1)), real(new_k(2))); end % Verify: the Apollonian matrix group acts on integer packings % The 4 generators of the Apollonian group (in GL(4,ℤ)): % S1 maps (k1,k2,k3,k4) → (-k1+2k2+2k3+2k4, k2, k3, k4) etc. S1 = [-1,2,2,2; 0,1,0,0; 0,0,1,0; 0,0,0,1]; v = [k1;k2;k3;k4]; printf('\nS1·v = [%d %d %d %d] (GL(4,Z) action on integer packing)\n', S1*v);
The Poincaré Disk — Circles Inside Circles
The Poincaré disk model places the entire hyperbolic plane inside the open unit disk. Straight lines become circular arcs. Every symmetry of the hyperbolic plane is a Möbius transformation — a complex rational function that maps circles to circles. This model has found recent applications in graph-based cryptography and expander constructions.
Ramanujan Graphs
Optimal expander graphs (used in hash functions and ZK proofs) are constructed using PSL(2,𝔽_p) — the Poincaré disk symmetry group but over a finite field. The LPS construction gives k-regular Ramanujan graphs with spectral gap approaching the theoretical maximum.
Hyperbolic Embeddings
Some cryptographic protocols use the exponential volume growth of hyperbolic space: a circle of radius r in ℍ² has circumference 2π sinh(r) — exponential in r vs linear in ℝ². This underlies hyperbolic neural network cryptanalysis and certain lattice problems.
%% Poincaré Disk and Möbius Transformations function w = mobius(z, a, theta) % Poincaré disk isometry: rotate by theta and shift by a (|a|<1) w = exp(1i*theta) .* (z - a) ./ (1 - conj(a).*z); end function d = poincare_dist(z, w) % Hyperbolic distance between z, w in the Poincaré disk d = 2 * atanh(abs(z-w) ./ abs(1 - conj(w).*z)); end % Verify isometry: Möbius maps preserve hyperbolic distances z = 0.3+0.2*1i; w = -0.5+0.4*1i; a = 0.6+0.1*1i; theta = pi/4; z2 = mobius(z,a,theta); w2 = mobius(w,a,theta); printf('d(z,w) before = %.6f\n', poincare_dist(z,w)); printf('d(z,w) after = %.6f (isometry: must be equal)\n', poincare_dist(z2,w2)); % Hyperbolic vs Euclidean circumference (exponential vs linear) printf('\nCircumference in ℍ² vs ℝ²:\n'); printf('r C_hyp=2π·sinh(r) C_eucl=2π·r\n'); for r = [1,2,3,4,5] printf('%-3d %-20.4f %.4f\n', r, 2*pi*sinh(r), 2*pi*r); end % The exponential growth = why hyperbolic geometry gives optimal expanders