mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
hanzoskills.com/llms.txt now opens with the install line, the API reference index and the company index, so an agent that lands on any one of the three can find the rest. robots.txt claimed 537 documents while llms.txt counts 920. The number is gone from robots.txt; llms.txt derives it. public/ is regenerated from scripts/site.py, which it had fallen behind: the copy-prompt menu and agent bar were in the generator and not in the committed pages. tests/site.mjs passes against the result. Co-authored-by: Hanzo Dev <[email protected]>
669 lines
28 KiB
HTML
669 lines
28 KiB
HTML
<!doctype html>
|
||
<html lang="en"><head>
|
||
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
||
<title>number-theory</title>
|
||
<meta name="color-scheme" content="dark">
|
||
<style>
|
||
/* Committed to one visual world: a dark instrument panel. No light variant —
|
||
the dot field and the hairline rules only read on black, and a naive
|
||
inversion would wash both out. Every colour is painted explicitly so the page
|
||
never borrows a host background. */
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
|
||
|
||
:root{
|
||
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
|
||
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
|
||
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
|
||
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
|
||
--font-zen-pixel-square:'Zen Pixel Square',monospace;
|
||
--mono:var(--font-zen-mono);
|
||
--sans:var(--font-zen-sans);
|
||
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
|
||
--r:999px; --r-soft:14px;
|
||
}
|
||
*{box-sizing:border-box}
|
||
html{-webkit-text-size-adjust:100%}
|
||
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
|
||
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
|
||
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
|
||
|
||
/* The dot field. A halftone made of one repeating radial-gradient, faded out
|
||
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
|
||
/* No overflow clip here: the dot field is inset to the box already, and a clip
|
||
would cut off the copy-prompt menu. */
|
||
.hero{position:relative;border-bottom:1px solid var(--line)}
|
||
.hero::before{content:"";position:absolute;inset:0;
|
||
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
|
||
background-size:7px 7px;
|
||
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
pointer-events:none}
|
||
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
|
||
|
||
nav{border-bottom:1px solid var(--line)}
|
||
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
|
||
justify-content:space-between;align-items:center;gap:1rem}
|
||
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--ink);text-decoration:none;
|
||
display:inline-flex;align-items:center;gap:.6rem}
|
||
.brand i{font-style:normal;color:var(--faint)}
|
||
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
|
||
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--soft);text-decoration:none}
|
||
nav a.up:hover{color:var(--ink)}
|
||
|
||
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
|
||
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
|
||
h1 em{font-style:normal;color:var(--faint)}
|
||
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
|
||
|
||
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
|
||
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
|
||
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
|
||
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
|
||
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
|
||
line-height:1.2;font-weight:400}
|
||
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
|
||
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
|
||
.btn.solid:hover{background:#d8d8d4}
|
||
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
|
||
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
|
||
|
||
/* Copy-prompt selector. Each row copies the prompt for its own target. */
|
||
.copy{position:relative;display:inline-flex}
|
||
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
|
||
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
|
||
padding:.4rem;display:flex;flex-direction:column;
|
||
box-shadow:0 12px 32px rgba(0,0,0,.75)}
|
||
.menu[hidden]{display:none}
|
||
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
|
||
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
|
||
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
|
||
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
|
||
white-space:nowrap}
|
||
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
|
||
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
|
||
.mi:hover .mark{color:var(--ink)}
|
||
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
|
||
letter-spacing:.1em;text-transform:uppercase}
|
||
|
||
/* Works-with bar: one scrolling row, name and mark per agent. */
|
||
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
|
||
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
|
||
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
|
||
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
|
||
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
|
||
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
|
||
display:flex;align-items:center}
|
||
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
|
||
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
|
||
-webkit-overflow-scrolling:touch;
|
||
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
|
||
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
|
||
.bar::-webkit-scrollbar{display:none}
|
||
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
|
||
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
|
||
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
|
||
text-decoration:none;background:var(--ground)}
|
||
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
|
||
.agent .mark{width:.95rem;height:.95rem}
|
||
|
||
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
|
||
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
|
||
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
|
||
p{margin:0 0 1rem;max-width:70ch}
|
||
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
|
||
li{margin:.22rem 0}
|
||
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
|
||
text-decoration-color:var(--line-hi)}
|
||
a:hover{text-decoration-color:var(--ink)}
|
||
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
|
||
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
|
||
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
|
||
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
|
||
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
|
||
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
|
||
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
|
||
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
|
||
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
|
||
display:block;overflow-x:auto}
|
||
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
|
||
|
||
.curl{display:block;background:var(--panel);border:1px solid var(--line);
|
||
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
|
||
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
|
||
white-space:pre;line-height:1.9}
|
||
.curl b{color:var(--ink);font-weight:400}
|
||
.curl i{font-style:normal;color:var(--faint)}
|
||
|
||
/* index */
|
||
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
|
||
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
|
||
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
|
||
#q:focus{outline:none;border-color:var(--soft)}
|
||
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
|
||
text-transform:uppercase;margin:0 0 2rem}
|
||
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
|
||
padding-bottom:.45rem}
|
||
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
|
||
border-radius:var(--r-soft);text-decoration:none}
|
||
.row:hover{background:#0a0a0a}
|
||
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
|
||
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
|
||
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
|
||
color:var(--faint);font-size:.85rem}
|
||
footer a{color:var(--soft)}
|
||
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
|
||
margin:0 0 2rem;font-size:.85rem}
|
||
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
|
||
border-bottom:1px solid var(--line);padding-bottom:.4rem}
|
||
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
|
||
.fmap a:hover{text-decoration:underline}
|
||
.fmap div{color:var(--faint);line-height:1.5}
|
||
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
|
||
|
||
@media (max-width:640px){
|
||
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
|
||
.btns{gap:.5rem}
|
||
.btn{padding:.75rem 1.15rem;font-size:.68rem}
|
||
.copy,.copy .btn{width:100%;justify-content:center}
|
||
.menu{left:0;right:0;min-width:0}
|
||
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
|
||
.strip b{border-right:0;padding-right:0}
|
||
.bar{width:100%}
|
||
}
|
||
</style>
|
||
<link rel="alternate" type="text/markdown" href="/number-theory.md">
|
||
|
||
<link rel="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/number-theory">
|
||
</head>
|
||
<!-- Reading this with a machine? Every page here is also plain markdown.
|
||
This one: https://hanzoskills.com/number-theory.md
|
||
Index: https://hanzoskills.com/llms.txt
|
||
Corpus: https://hanzoskills.com/all.md
|
||
Append .md to any path for the markdown twin. -->
|
||
<body>
|
||
<nav><div class="in">
|
||
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
|
||
<a class="up" href="/">All skills</a>
|
||
</div></nav>
|
||
|
||
<div class="wrap">
|
||
<h1>number-theory</h1><p class="lede">Number theory including primes, modular arithmetic, Diophantine equations, and cryptographic applications</p><h1>Number Theory</h1>
|
||
<p><strong>Scope</strong>: Primes, divisibility, modular arithmetic, Diophantine equations, quadratic residues, cryptography <strong>Lines</strong>: ~400 <strong>Last Updated</strong>: 2025-10-25</p>
|
||
<h2>When to Use This Skill</h2>
|
||
<p>Activate this skill when:</p>
|
||
<ul><li>Working with prime numbers and factorization</li><li>Implementing modular arithmetic for cryptography</li><li>Solving Diophantine equations</li><li>Understanding RSA, Diffie-Hellman, elliptic curve crypto</li><li>Analyzing divisibility and congruences</li><li>Computing number-theoretic functions (φ, τ, σ)</li></ul>
|
||
<h2>Core Concepts</h2>
|
||
<h3>Divisibility and Primes</h3>
|
||
<p><strong>Division algorithm</strong>: For a, b ∈ ℤ with b > 0, ∃! q, r: a = bq + r with 0 ≤ r < b</p>
|
||
<p><strong>GCD and LCM</strong>:</p>
|
||
<pre><code class="lang-python">import math
|
||
from typing import Tuple
|
||
|
||
def gcd(a: int, b: int) -> int:
|
||
"""Euclidean algorithm for GCD"""
|
||
while b:
|
||
a, b = b, a % b
|
||
return abs(a)
|
||
|
||
def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
|
||
"""
|
||
Extended Euclidean algorithm
|
||
Returns (gcd, x, y) where gcd = ax + by
|
||
"""
|
||
if b == 0:
|
||
return abs(a), 1 if a >= 0 else -1, 0
|
||
|
||
gcd_val, x1, y1 = extended_gcd(b, a % b)
|
||
x = y1
|
||
y = x1 - (a // b) * y1
|
||
|
||
return gcd_val, x, y
|
||
|
||
def lcm(a: int, b: int) -> int:
|
||
"""LCM via gcd: lcm(a,b) = |ab|/gcd(a,b)"""
|
||
return abs(a * b) // gcd(a, b)
|
||
|
||
# Example
|
||
a, b = 48, 18
|
||
g = gcd(a, b)
|
||
print(f"gcd({a}, {b}) = {g}") # 6
|
||
|
||
g, x, y = extended_gcd(a, b)
|
||
print(f"{g} = {a}·{x} + {b}·{y}") # 6 = 48·(-1) + 18·3
|
||
print(f"Verify: {a*x + b*y}") # 6</code></pre>
|
||
<p><strong>Prime testing</strong>:</p>
|
||
<pre><code class="lang-python">def is_prime(n: int) -> bool:
|
||
"""Trial division primality test"""
|
||
if n < 2:
|
||
return False
|
||
if n == 2:
|
||
return True
|
||
if n % 2 == 0:
|
||
return False
|
||
|
||
# Check odd divisors up to √n
|
||
for i in range(3, int(n**0.5) + 1, 2):
|
||
if n % i == 0:
|
||
return False
|
||
return True
|
||
|
||
def miller_rabin(n: int, k: int = 5) -> bool:
|
||
"""
|
||
Miller-Rabin primality test (probabilistic)
|
||
k: number of rounds (higher = more accurate)
|
||
Error probability: 4^(-k)
|
||
"""
|
||
if n < 2:
|
||
return False
|
||
if n == 2 or n == 3:
|
||
return True
|
||
if n % 2 == 0:
|
||
return False
|
||
|
||
# Write n-1 = 2^r · d
|
||
r, d = 0, n - 1
|
||
while d % 2 == 0:
|
||
r += 1
|
||
d //= 2
|
||
|
||
# Miller-Rabin test
|
||
import random
|
||
for _ in range(k):
|
||
a = random.randint(2, n - 2)
|
||
x = pow(a, d, n) # a^d mod n
|
||
|
||
if x == 1 or x == n - 1:
|
||
continue
|
||
|
||
for _ in range(r - 1):
|
||
x = pow(x, 2, n)
|
||
if x == n - 1:
|
||
break
|
||
else:
|
||
return False # Composite
|
||
|
||
return True # Probably prime
|
||
|
||
# Example
|
||
print(f"Is 97 prime? {is_prime(97)}") # True
|
||
print(f"Is 1009 prime (Miller-Rabin)? {miller_rabin(1009)}") # True</code></pre>
|
||
<p><strong>Sieve of Eratosthenes</strong>:</p>
|
||
<pre><code class="lang-python">def sieve_of_eratosthenes(limit: int) -> list[int]:
|
||
"""Generate all primes up to limit"""
|
||
if limit < 2:
|
||
return []
|
||
|
||
is_prime = [True] * (limit + 1)
|
||
is_prime[0] = is_prime[1] = False
|
||
|
||
for i in range(2, int(limit**0.5) + 1):
|
||
if is_prime[i]:
|
||
# Mark multiples as composite
|
||
for j in range(i*i, limit + 1, i):
|
||
is_prime[j] = False
|
||
|
||
return [i for i in range(limit + 1) if is_prime[i]]
|
||
|
||
# Example
|
||
primes = sieve_of_eratosthenes(100)
|
||
print(f"Primes up to 100: {primes[:10]}...") # [2, 3, 5, 7, 11, 13, ...]</code></pre>
|
||
<h3>Modular Arithmetic</h3>
|
||
<p><strong>Congruences</strong>: a ≡ b (mod n) iff n | (a - b)</p>
|
||
<p><strong>Modular inverse</strong>:</p>
|
||
<pre><code class="lang-python">def mod_inverse(a: int, n: int) -> int:
|
||
"""
|
||
Compute a^(-1) mod n (multiplicative inverse)
|
||
Exists iff gcd(a, n) = 1
|
||
"""
|
||
gcd_val, x, _ = extended_gcd(a, n)
|
||
|
||
if gcd_val != 1:
|
||
raise ValueError(f"No inverse: gcd({a}, {n}) = {gcd_val} ≠ 1")
|
||
|
||
return x % n
|
||
|
||
def chinese_remainder_theorem(moduli: list[int], remainders: list[int]) -> int:
|
||
"""
|
||
Solve system: x ≡ a_i (mod n_i)
|
||
Requires moduli pairwise coprime
|
||
"""
|
||
if len(moduli) != len(remainders):
|
||
raise ValueError("Moduli and remainders must have same length")
|
||
|
||
# Check coprimality
|
||
for i in range(len(moduli)):
|
||
for j in range(i + 1, len(moduli)):
|
||
if gcd(moduli[i], moduli[j]) != 1:
|
||
raise ValueError(f"Moduli not coprime: gcd({moduli[i]}, {moduli[j]}) ≠ 1")
|
||
|
||
# Compute solution
|
||
N = 1
|
||
for n in moduli:
|
||
N *= n
|
||
|
||
x = 0
|
||
for n_i, a_i in zip(moduli, remainders):
|
||
N_i = N // n_i
|
||
M_i = mod_inverse(N_i, n_i)
|
||
x += a_i * N_i * M_i
|
||
|
||
return x % N
|
||
|
||
# Example
|
||
moduli = [3, 5, 7]
|
||
remainders = [2, 3, 2]
|
||
solution = chinese_remainder_theorem(moduli, remainders)
|
||
print(f"Solution to CRT system: x ≡ {solution} (mod {3*5*7})") # x = 23
|
||
|
||
# Verify
|
||
for n, a in zip(moduli, remainders):
|
||
print(f"{solution} ≡ {solution % n} (mod {n}), expected {a}")</code></pre>
|
||
<p><strong>Euler's totient function</strong>:</p>
|
||
<pre><code class="lang-python">def euler_phi(n: int) -> int:
|
||
"""
|
||
φ(n) = |{k : 1 ≤ k ≤ n, gcd(k,n) = 1}|
|
||
Number of integers coprime to n
|
||
"""
|
||
result = n
|
||
p = 2
|
||
|
||
# Factor n and apply φ(p^k) = p^(k-1)(p-1)
|
||
while p * p <= n:
|
||
if n % p == 0:
|
||
# Remove factor p
|
||
while n % p == 0:
|
||
n //= p
|
||
# Multiply by (1 - 1/p)
|
||
result -= result // p
|
||
p += 1
|
||
|
||
if n > 1:
|
||
# n is prime
|
||
result -= result // n
|
||
|
||
return result
|
||
|
||
# Examples
|
||
print(f"φ(9) = {euler_phi(9)}") # 6 (1,2,4,5,7,8 coprime to 9)
|
||
print(f"φ(12) = {euler_phi(12)}") # 4 (1,5,7,11)
|
||
|
||
# Euler's theorem: a^φ(n) ≡ 1 (mod n) if gcd(a,n)=1
|
||
n = 10
|
||
a = 3
|
||
assert pow(a, euler_phi(n), n) == 1
|
||
print(f"{a}^φ({n}) ≡ {pow(a, euler_phi(n), n)} (mod {n})")</code></pre>
|
||
<h3>Quadratic Residues</h3>
|
||
<p><strong>Legendre symbol</strong>: (a/p) = 1 if a is quadratic residue mod p, -1 otherwise</p>
|
||
<pre><code class="lang-python">def legendre_symbol(a: int, p: int) -> int:
|
||
"""
|
||
Compute (a/p) using Euler's criterion:
|
||
(a/p) ≡ a^((p-1)/2) (mod p)
|
||
"""
|
||
if not is_prime(p) or p == 2:
|
||
raise ValueError("p must be odd prime")
|
||
|
||
a = a % p
|
||
if a == 0:
|
||
return 0
|
||
|
||
result = pow(a, (p - 1) // 2, p)
|
||
return -1 if result == p - 1 else result
|
||
|
||
def tonelli_shanks(n: int, p: int) -> int:
|
||
"""
|
||
Find r such that r² ≡ n (mod p)
|
||
Tonelli-Shanks algorithm for modular square root
|
||
"""
|
||
if legendre_symbol(n, p) != 1:
|
||
raise ValueError(f"{n} is not a quadratic residue mod {p}")
|
||
|
||
# Factor p-1 = Q · 2^S
|
||
Q, S = p - 1, 0
|
||
while Q % 2 == 0:
|
||
Q //= 2
|
||
S += 1
|
||
|
||
# Find quadratic non-residue
|
||
z = 2
|
||
while legendre_symbol(z, p) != -1:
|
||
z += 1
|
||
|
||
# Initialize
|
||
M = S
|
||
c = pow(z, Q, p)
|
||
t = pow(n, Q, p)
|
||
R = pow(n, (Q + 1) // 2, p)
|
||
|
||
while True:
|
||
if t == 0:
|
||
return 0
|
||
if t == 1:
|
||
return R
|
||
|
||
# Find least i: t^(2^i) = 1
|
||
i = 1
|
||
temp = (t * t) % p
|
||
while temp != 1:
|
||
temp = (temp * temp) % p
|
||
i += 1
|
||
|
||
# Update
|
||
b = pow(c, 1 << (M - i - 1), p)
|
||
M = i
|
||
c = (b * b) % p
|
||
t = (t * c) % p
|
||
R = (R * b) % p
|
||
|
||
# Example: Solve x² ≡ 10 (mod 13)
|
||
p = 13
|
||
n = 10
|
||
print(f"Legendre({n}/{p}) = {legendre_symbol(n, p)}") # 1 (is quadratic residue)
|
||
sqrt_mod = tonelli_shanks(n, p)
|
||
print(f"√{n} ≡ {sqrt_mod} (mod {p})") # 6
|
||
print(f"Verify: {sqrt_mod}² ≡ {(sqrt_mod**2) % p} (mod {p})") # 10</code></pre>
|
||
<h3>Diophantine Equations</h3>
|
||
<p><strong>Linear Diophantine</strong>: ax + by = c</p>
|
||
<pre><code class="lang-python">def linear_diophantine(a: int, b: int, c: int) -> Tuple[int, int]:
|
||
"""
|
||
Solve ax + by = c
|
||
Solution exists iff gcd(a, b) | c
|
||
Returns one particular solution (x0, y0)
|
||
General solution: x = x0 + (b/d)t, y = y0 - (a/d)t
|
||
"""
|
||
g = gcd(a, b)
|
||
|
||
if c % g != 0:
|
||
raise ValueError(f"No solution: gcd({a},{b})={g} does not divide {c}")
|
||
|
||
# Solve ax' + by' = g
|
||
_, x0, y0 = extended_gcd(a, b)
|
||
|
||
# Scale to ax + by = c
|
||
x = x0 * (c // g)
|
||
y = y0 * (c // g)
|
||
|
||
return x, y
|
||
|
||
# Example: 12x + 18y = 6
|
||
x, y = linear_diophantine(12, 18, 6)
|
||
print(f"Solution to 12x + 18y = 6: x={x}, y={y}")
|
||
print(f"Verify: 12·{x} + 18·{y} = {12*x + 18*y}")</code></pre>
|
||
<p><strong>Pell's equation</strong>: x² - Dy² = 1</p>
|
||
<pre><code class="lang-python">def solve_pell(D: int, limit: int = 100) -> Tuple[int, int]:
|
||
"""
|
||
Find smallest solution to x² - Dy² = 1
|
||
Using continued fraction of √D
|
||
"""
|
||
if int(D**0.5)**2 == D:
|
||
raise ValueError("D must not be a perfect square")
|
||
|
||
# Continued fraction expansion of √D
|
||
m, d, a0 = 0, 1, int(D**0.5)
|
||
|
||
# Convergents
|
||
p_prev, p = 0, 1
|
||
q_prev, q = 1, 0
|
||
|
||
a = a0
|
||
for _ in range(limit):
|
||
p, p_prev = a * p + p_prev, p
|
||
q, q_prev = a * q + q_prev, q
|
||
|
||
# Check if (p, q) is solution
|
||
if p*p - D*q*q == 1:
|
||
return p, q
|
||
|
||
# Next continued fraction term
|
||
m = d * a - m
|
||
d = (D - m*m) // d
|
||
a = (a0 + m) // d
|
||
|
||
raise ValueError("No solution found within limit")
|
||
|
||
# Example: x² - 2y² = 1
|
||
x, y = solve_pell(2)
|
||
print(f"Smallest solution to x² - 2y² = 1: ({x}, {y})") # (3, 2)
|
||
print(f"Verify: {x}² - 2·{y}² = {x*x - 2*y*y}") # 1</code></pre>
|
||
<h3>Cryptographic Applications</h3>
|
||
<p><strong>RSA encryption</strong>:</p>
|
||
<pre><code class="lang-python">def generate_rsa_keys(p: int, q: int, e: int = 65537):
|
||
"""
|
||
Generate RSA key pair
|
||
p, q: distinct primes
|
||
e: public exponent (commonly 65537)
|
||
"""
|
||
if not (is_prime(p) and is_prime(q)):
|
||
raise ValueError("p and q must be prime")
|
||
|
||
n = p * q
|
||
phi_n = (p - 1) * (q - 1)
|
||
|
||
if gcd(e, phi_n) != 1:
|
||
raise ValueError(f"e={e} not coprime to φ(n)={phi_n}")
|
||
|
||
d = mod_inverse(e, phi_n)
|
||
|
||
return {
|
||
'public_key': (n, e),
|
||
'private_key': (n, d),
|
||
'p': p,
|
||
'q': q,
|
||
'phi_n': phi_n
|
||
}
|
||
|
||
def rsa_encrypt(message: int, public_key: Tuple[int, int]) -> int:
|
||
"""Encrypt: c = m^e mod n"""
|
||
n, e = public_key
|
||
return pow(message, e, n)
|
||
|
||
def rsa_decrypt(ciphertext: int, private_key: Tuple[int, int]) -> int:
|
||
"""Decrypt: m = c^d mod n"""
|
||
n, d = private_key
|
||
return pow(ciphertext, d, n)
|
||
|
||
# Example
|
||
p, q = 61, 53
|
||
keys = generate_rsa_keys(p, q)
|
||
print(f"Public key: (n={keys['public_key'][0]}, e={keys['public_key'][1]})")
|
||
print(f"Private key: (n={keys['private_key'][0]}, d={keys['private_key'][1]})")
|
||
|
||
message = 123
|
||
ciphertext = rsa_encrypt(message, keys['public_key'])
|
||
decrypted = rsa_decrypt(ciphertext, keys['private_key'])
|
||
|
||
print(f"Original message: {message}")
|
||
print(f"Encrypted: {ciphertext}")
|
||
print(f"Decrypted: {decrypted}")
|
||
assert message == decrypted</code></pre>
|
||
<hr>
|
||
<h2>Patterns</h2>
|
||
<h3>Pattern 1: Prime Factorization</h3>
|
||
<pre><code class="lang-python">def prime_factorization(n: int) -> dict:
|
||
"""Return prime factorization as {prime: exponent}"""
|
||
factors = {}
|
||
d = 2
|
||
|
||
while d * d <= n:
|
||
while n % d == 0:
|
||
factors[d] = factors.get(d, 0) + 1
|
||
n //= d
|
||
d += 1
|
||
|
||
if n > 1:
|
||
factors[n] = factors.get(n, 0) + 1
|
||
|
||
return factors
|
||
|
||
# Example
|
||
n = 360
|
||
factors = prime_factorization(n)
|
||
print(f"{n} = {' · '.join(f'{p}^{e}' if e > 1 else str(p) for p, e in factors.items())}")
|
||
# 360 = 2^3 · 3^2 · 5</code></pre>
|
||
<h3>Pattern 2: Fermat's Little Theorem</h3>
|
||
<p><strong>Theorem</strong>: If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p)</p>
|
||
<pre><code class="lang-python">def fermat_primality_test(n: int, k: int = 5) -> bool:
|
||
"""
|
||
Probabilistic primality test using Fermat's Little Theorem
|
||
k: number of rounds
|
||
"""
|
||
if n < 2:
|
||
return False
|
||
if n == 2 or n == 3:
|
||
return True
|
||
|
||
import random
|
||
for _ in range(k):
|
||
a = random.randint(2, n - 2)
|
||
if pow(a, n - 1, n) != 1:
|
||
return False # Definitely composite
|
||
|
||
return True # Probably prime (may fail for Carmichael numbers)</code></pre>
|
||
<hr>
|
||
<h2>Quick Reference</h2>
|
||
<h3>Number-Theoretic Functions</h3>
|
||
<p>| Function | Definition | Example | |----------|-----------|---------| | φ(n) | Euler's totient | φ(12) = 4 | | τ(n) | Number of divisors | τ(12) = 6 | | σ(n) | Sum of divisors | σ(12) = 28 | | ω(n) | Number of distinct prime factors | ω(12) = 2 | | Ω(n) | Number of prime factors (with multiplicity) | Ω(12) = 4 |</p>
|
||
<h3>Important Theorems</h3>
|
||
<pre><code>Fermat's Little Theorem: p prime, gcd(a,p)=1 ⟹ a^(p-1) ≡ 1 (mod p)
|
||
Euler's Theorem: gcd(a,n)=1 ⟹ a^φ(n) ≡ 1 (mod n)
|
||
Wilson's Theorem: p prime ⟺ (p-1)! ≡ -1 (mod p)
|
||
Chinese Remainder Theorem: System of congruences has unique solution mod N</code></pre>
|
||
<hr>
|
||
<h2>Anti-Patterns</h2>
|
||
<p>❌ <strong>Using trial division for large primes</strong>: O(√n) too slow ✅ Use Miller-Rabin or other probabilistic tests</p>
|
||
<p>❌ <strong>Assuming Fermat test is conclusive</strong>: Carmichael numbers pass but aren't prime ✅ Use Miller-Rabin which handles Carmichael numbers</p>
|
||
<p>❌ <strong>Computing a^b mod n naively</strong>: Overflow for large numbers ✅ Use built-in <code>pow(a, b, n)</code> with modular exponentiation</p>
|
||
<p>❌ <strong>Forgetting coprimality requirement</strong>: CRT needs pairwise coprime moduli ✅ Verify gcd(n_i, n_j) = 1 before applying CRT</p>
|
||
<hr>
|
||
<h2>Related Skills</h2>
|
||
<ul><li><code>abstract-algebra.md</code> - Rings ℤ/nℤ, fields, Galois theory</li><li><code>set-theory.md</code> - Cardinality of ℕ, ℤ, ℚ</li><li><code>formal/z3-solver-basics.md</code> - Solving number-theoretic constraints</li><li><code>cryptography.md</code> - RSA, Diffie-Hellman, elliptic curves (if exists)</li></ul>
|
||
<hr>
|
||
<p><strong>Last Updated</strong>: 2025-10-25 <strong>Format Version</strong>: 1.0 (Atomic)</p>
|
||
<footer>
|
||
<div class="fmap">
|
||
<div><b>Build</b>
|
||
<a href="https://hanzo.app">hanzo.app</a> app builder
|
||
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
|
||
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
|
||
<div><b>Run</b>
|
||
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
|
||
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
|
||
<div><b>Account</b>
|
||
<a href="https://hanzo.id">hanzo.id</a> sign in
|
||
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
|
||
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
|
||
<div><b>Company</b>
|
||
<a href="https://hanzo.ai">hanzo.ai</a> canonical
|
||
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
|
||
</div>
|
||
<div class="fend"><a href="/number-theory.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
||
</footer>
|
||
</div></body></html> |