shor26

Pojďme si představit, jak by kvantový počítač se Shorovým algoritmem prolomil zjednodušenou „osmibitovou“ verzi Bitcoinu s mod17.

Základní princip (silně zjednodušeno)

V Bitcoinu a dalších kryptoměnách se používá asymetrická kryptografie, například RSA nebo eliptické křivky.

Pro jednoduchost si představme, že náš „osmibitový Bitcoin“ používá RSA s malými čísly, kde veřejný klíč je dán modulem N a exponentem e.

Cílem útočníka je získat soukromý klíč, který je odvozen od prvočísel p a q, ze kterých vznikne

N = p * q

Jakmile známe p a q, můžeme spočítat Eulerovu funkci

phi(N) = (p − 1) * (q − 1)

a z ní soukromý exponent d.

Použití Shorova algoritmu s mod17

Pokud by se RSA používalo přímo s modulem 17, nebylo by co faktorizovat, protože 17 je prvočíslo.

Proto si pro ukázku vezmeme malé složené číslo

N = 15

což je

15 = 3 * 5

Cílem je faktorizovat N.

Kroky Shorova algoritmu pro N = 15

Vybereme náhodné číslo a takové, aby gcd(a, N) = 1

Zvolíme a = 7

protože gcd(7, 15) = 1

Hledáme periodu funkce f(x) = a^x mod N

tedy f(x) = 7^x mod 15

počítáme:

7^1 mod 15 = 7

7^2 mod 15 = 49 mod 15 = 4

7^3 mod 15 = 7 * 4 = 28 mod 15 = 13

7^4 mod 15 = 7 * 13 = 91 mod 15 = 1

dostali jsme 1

perioda je r = 4

protože 7^4 mod 15 = 1

Jak to udělá kvantový počítač

Kvantový počítač použije kvantovou Fourierovu transformaci (QFT) k nalezení periody r.

Postup:

vytvoří superpozici stavů

spočítá f(x) = a^x mod N

aplikuje QFT

změří výsledek

z výsledků dopočítá periodu r

Použití periody k nalezení faktorů

Podmínka 1) r musí být sudé

r = 4 → OK

Podmínka 2) a^(r/2) mod N nesmí být −1 mod N

počítáme a^(r/2) = 7^(4/2) = 7^2 = 49 mod 15 = 4

−1 mod 15 = 14

4 ≠ 14 → OK

Teď spočítáme gcd(a^(r/2) − 1, N)

gcd(49 − 1, 15) = gcd(48, 15) = 3

a gcd(a^(r/2) + 1, N)

gcd(49 + 1, 15) = gcd(50, 15) = 5

dostali jsme 3 a 5

tedy 15 = 3 * 5

Výpočet soukromého klíče

phi(15) = (3 − 1) * (5 − 1)

phi(15) = 2 * 4 = 8

zvolíme veřejný exponent

e = 7

musí platit

gcd(e, phi) = 1

gcd(7, 8) = 1 → OK

hledáme d takové, že

e * d mod phi = 1

7 * d mod 8 = 1

zkusíme

7 * 7 = 49 mod 8 = 1

tedy

d = 7

soukromý klíč je (d, N) = (7, 15)

Souvislost s osmibitovým Bitcoinem a mod17

Pokud by modul byl menší než 17, pak by N mohlo být jen malé číslo:

4, 6, 8, 9, 10, 12, 14, 15

všechna lze snadno rozložit.

Shorův algoritmus by je také rozložil, ale byl by zbytečně silný.

Princip ale zůstává stejný.

Souvislost s eliptickými křivkami (ECDLP)

Máme bod G a veřejný klíč Q

Q = d * G

chceme najít d

Shorův algoritmus vytvoří funkci f(a, b) = aG + bQ

dosadíme Q = dG

f(a, b) = aG + b d G = (a + b d) G

hledáme dvojici (a, b), pro kterou

a + b d = k * n

kde n je řád bodu G

kvantový počítač pomocí QFT najde periodu

perioda obsahuje vektor (d, −1)

z toho lze spočítat d

Shrnutí

Shorův algoritmus umí najít periodu funkce.

Z periody lze získat faktory N (RSA) nebo d (ECDLP).

Detailní přehled — logické vs fyzické

KřivkaBezpečnostLog. qubity (2026)Fyz. qubity (surface code)Toffoli brányReálnost
mod 251 (moje)~4 bit~16~100–500~2 000NISQ dnes?
P-19296 bit~850~500 tis.10³²~2028–30
P-224112 bit1 098~700 tis.10³⁸~2029–32
P-256 / secp256k1128 bit1 193~800 tis. – 1M2³⁸·¹ (×32 runs)~2030–33
P-384192 bit~1 500~1,5 M10⁵⁵2033+
P-521260 bit1 895~2 M2⁴⁸ (×32 runs)2035+

pro ess251:

╔══════════════════════════════════════════════════════════╗
║   ECDLP Solver - Shorův algoritmus (kvantová simulace)  ║
║   Křivka: y² = x³ + 7  (mod 251)                       ║
╚══════════════════════════════════════════════════════════╝

[SETUP] Ověřuji parametry...
  Křivka: y² ≡ x³ + 0x + 7  (mod 251)
  ✓ G = (10, 76) leží na křivce

[SETUP] Počítám řád grupy #E(F_251)...
  ✓ #E(F_251) = 252
     Faktorizace: {2: 2, 3: 2, 7: 1}

────────────────────────────────────────────────────────────
Zadej veřejný klíč K = k*G:
(nebo stiskni Enter pro demo s náhodným k)
  Kx = 114
  Ky = 20

============================================================
  SHORŮV ALGORITMUS PRO ECDLP (kvantová simulace)
============================================================
  Křivka:  y² ≡ x³ + 0x + 7  (mod 251)
  G     =  (10, 76)
  K     =  (114, 20)
  Řád n =  252

[1/4] Příprava kvantového registru...
  Generujeme tabulku f(a,b) = a*G + b*K pro a,b ∈ [0,251]
  ✓ Registr připraven: 252 stavů v superpozici

[2/4] Aplikace QFT - hledání periody...
  Na skutečném QC: Hadamard + U_f + QFT brány
  Simulujeme kvantovou interferenci...

  [QFT] Nejvyšší frekvenční špičky: [0, 1, 2, 3, 4]
  [QFT] Odpovídající pravděpodobnosti: ['0.004', '0.004', '0.004', '0.004', '0.004']
  [QFT] Nalezená perioda: r = 252

[3/4] Klasické zpracování - odvození privátního klíče...
  Pohlig-Hellman: n = 252 = {2: 2, 3: 2, 7: 1}
  ✓ Privátní klíč nalezen: k = 111

[4/4] Ověření výsledku...
  k*G = (114, 20)
  K   = (114, 20)
  Shoda: ✅ ANO

════════════════════════════════════════════════════════════
  🔑 PRIVÁTNÍ KLÍČ: k = 111
  📌 Ověření: 111*G = (114, 20)
  📌 Veřejný klíč K  = (114, 20)
════════════════════════════════════════════════════════════

ypy potřebných bran

Typ brányRole v ECDLPNáročnost
Hadamard (H)Inicializace superpozice registrutriviální
CNOTEntanglement, kopírování hodnotsnadná
Toffoli (CCX)Reverzibilní aritmetika, modulární násobenínákladná
T-gate1 Toffoli = 7 T-gates (Clifford+T dekompozice)nejdražší
QFT brányKvantová Fourierova transformace, hledání periodynákladná
Magic state distillacePříprava T-gate na fault-tolerant HW~1000× overhead

Dominantní náklad = T-gates. Jeden Toffoli vyžaduje 7 T-gates. Pro P-256: ~2³⁸ Toffoli = ~2⁴¹ T-gates. Každý T-gate na fault-tolerant HW potřebuje magic state factory (desítky fyzických qubitů navíc).

CoKdyHWVýsledek
Shorův alg. — faktorizace 152001NMR (7 qubitů)úspěch — Vandersypen et al., Nature
Faktorizace 212012Josephsonovy fázové qubityúspěch — Lucero et al., Nat. Phys.
Simulace ECDLP obvodu (klasická)2017–2026Klasický počítač (LIQUi|⟩, Qrisp)simulace — ověřena korektnost obvodů
ECDLP na malé křivce mod 72025 (paper)Simulátor (Qrisp)simulace — p=7, G=(3,2), celý Shorův alg.
Reálné ECDLP na QC hardware——neprovedeno — chybí logické qubity

Moje křivka (mod 251): Řád grupy je 252 = 2²·3²·7, což je „hladké“ číslo — Pohlig-Hellman to rozkládá na tři malé podproblémy. Takže místo plného Shorova algoritmu by stačilo jen pár desítek qubitů. Tohle je přesně ta třída, kde simulace na klasickém počítači (jako náš program) je rychlejší a jednodušší než kvantový hardware.

Logické vs fyzické qubity: Logický qubit je chybami chráněná výpočetní jednotka — encode se do stovek fyzických qubitů pomocí surface code nebo cat code. Při chybovosti fyzického qubitu ~10⁻³ potřebuješ zhruba 1 000 fyzických na 1 logický. Google Willow (105 fyzických qubitů) by zvládl nanejvýš ~0,1 logického — nestačí ani na naši mod 251 křivku s opravou chyb.

Typy bran a proč jsou drahé: Nejdražší jsou T-gates — na fault-tolerant hardwaru se musí vyrábět přes „magic state distillation“, což je obrovský overhead. Jeden Toffoli = 7 T-gates = desítky operací na fyzické úrovni.

Reálné experimenty: Shorův faktorizační algoritmus byl experimentálně realizován na NMR procesoru (faktorizace 15, 2001) a na Josephsonových fázových qubitech (faktorizace 21, 2012). Springer Pro ECDLP konkrétně: existuje end-to-end simulace Shorova algoritmu pro ECDLP na malé křivce (p=7, G=(3,2)) pomocí frameworku Qrisp, ale pouze jako klasická simulace kvantového obvodu. arXiv Na reálném hardwaru to dosud nikdo neprovedl.

Nejnovější vývoj (2026): Tým z INRIA Rennes publikoval na EUROCRYPT 2026 metodu řešení ECDLP na 256-bitové křivce pouze s 1 193 logickými qubity — zhruba polovinou oproti předchozímu odhadu 2 124. PostQuantum Ve stejném časovém horizontu 18 měsíců tentýž tým snížil počet qubitů pro RSA faktorizaci o polovinu, přičemž v kombinaci s Gidneyho optimalizacemi klesly odhady fyzických qubitů pro RSA-2048 z 20 milionů na méně než jeden milion. PostQuantum

Pro tvůj výzkum v rámci kurzu ESS251 se Toffoliho brána (často označovaná jako CCNOT – Controlled-Controlled-NOT) skvěle hodí. Je to totiž jeden ze základních stavebních kamenů, které propojují klasickou informatiku s tou kvantovou.

Pojďme se na ni podívat detailně a strukturovaně.

1. Účel (Proč ji vůbec máme?)

V klasických počítačích běžně používáme brány jako AND, OR nebo NAND. Tyto brány jsou ale nevratné (ireverzibilní). Když znáš výstup klasické brány AND (např. 0), nemůžeš s jistotou říct, jaké byly vstupy (mohly to být kombinace 0,0, 0,1 nebo 1,0). Při této ztrátě informace se podle Landauerova principu uvolňuje teplo.

Toffoliho brána byla navržena tak, aby byla univerzální a zároveň reverzibilní (vratná).

2. Funkce (Jak funguje?)

Toffoliho brána pracuje se třemi qubity (nebo bity v klasickém pojetí). Označme si vstupy jako $a, b, c$ a výstupy jako $a‘, b‘, c’$.

Brána provede operaci NOT (otočí hodnotu) na cílovém qubitu $c$ pouze tehdy, pokud jsou oba řídicí qubyty $a$ i $b$ ve stavu $|1\rangle$. V opačném případě zůstane $c$ beze změny.

Matematický zápis a tabulka pravdivosti

Pokud použijeme symbol $\oplus$ pro sčítání modulo 2 (operace XOR), můžeme funkci zapsat jako:

Zde je kompletní tabulka pravdivosti:

Vstup (a,b,c)Výstup (a′,b′,c′)
$0, 0, 0$$0, 0, 0$
$0, 0, 1$$0, 0, 1$
$0, 1, 0$$0, 1, 0$
$0, 1, 1$$0, 1, 1$
$1, 0, 0$$1, 0, 0$
$1, 0, 1$$1, 0, 1$
$1, 1, 0$$1, 1, 1$ (změna $c$)
$1, 1, 1$$1, 1, 0$ (změna $c$)

3. Realizace (Jak ji poskládat?)

V čisté kvantové fyzice je přímá realizace interakce tří částic (qubitů) naráz extrémně náročná. Proto se Toffoliho brána v praxi rozkládá na jednodušší operace.

Rozklad na jedno- a dvouqubitové brány

Standardně se Toffoliho brána skládá ze:

K vytvoření jediné Toffoliho brány je potřeba celkem 6 bran CNOT a několik jednoqubitových bran. To je důležité vědět pro optimalizaci kvantových algoritmů, protože CNOT brány jsou náchylné k chybám.

Fyzické platformy

Toffoliho brána již byla úspěšně demonstrována na různých typech kvantových hardwarů:

4. Omezení (V čem je háček?)

5. Výhled do budoucna