faktorizace

Groku (2512) – ověř, ozdrojuj, doplň:

Největší číslo faktorizované pomocí obecné kvantové metody (hybrid / QAOA)

Číslo: 261 980 999 226 229 Velikost: 48 bitů Metoda: Hybridní přístup (převod problému faktorizace na mřížkový problém) Zařízení: Supervodivý kvantový procesor – 10 qubitů Kdo / kdy: Čínský výzkumný tým, publikováno v roce 2023 Toto je největší reálné číslo dosud faktorizované na kvantovém zařízení v praxi pomocí obecné metody.

Ověření a zdroje k tvrzení:

Ano, uvedené informace jsou přesné a pocházejí z vědecké publikace čínského týmu z prosince 2022 (publikováno na arXiv, později citováno v roce 2023).

Primární zdroj: Yan, B. et al. „Factoring integers with sublinear resources on a superconducting quantum processor“ (arXiv:2212.12372). Autoři zde explicitně uvádějí: „The 48-bit integer, 261980999226229, also refreshes the largest integer factored by a general method in a real quantum device.“

Další citace: Discover Magazine (2023), The Quantum Insider (2023), Cryptography Stack Exchange.

Doplňující informace (stav k prosinci 2025):

Tento rekord stále platí jako největší číslo faktorizované na kvantovém hardwaru pomocí obecné (univerzální) metody na gate-based (univerzálním) kvantovém počítači. Žádný novější experiment na supervodivých nebo iontových kvantových procesorech nepřekonal 48 bitů obecnou hybridní/QAOA metodou.

Tvrzení, že jde o „největší reálné číslo dosud faktorizované na kvantovém zařízení v praxi pomocí obecné metody„, je tedy správné i v roce 2025. Metoda je hybridní (kombinuje klasické a kvantové kroky), ale kvantová část (QAOA) je klíčová pro úspěch na reálném hardwaru.

Přeskočit na obsah

Historie chatu

Řekl/a jsi:

jaké největší číslo se podařilo faktorizovat na kvantovém počítači? kdy a kde? vyhledej na webu, ozdrojuj

ChatGPT řekl:

Tady je ověřený přehled největších čísel, která byla zatím faktorizována pomocí kvantových počítačů, včetně informací kdy, kde a jakým způsobem to bylo provedeno (včetně zdrojů):

1) Největší číslo faktorizované pomocí obecné kvantové metody (hybrid / QAOA)

Číslo: 261 980 999 226 229
Velikost: 48 bitů
Metoda: Hybridní přístup (převod problému faktorizace na mřížkový problém)
Zařízení: Supervodivý kvantový procesor – 10 qubitů
Kdo / kdy: Čínský výzkumný tým, publikováno v roce 2023
Toto je největší reálné číslo dosud faktorizované na kvantovém zařízení v praxi pomocí obecné metody. Reddit+1

2) Největší číslo faktorizované v experimentálních publikacích

Existují různé historické experimenty s různými přístupy:

a) Faktorizace čísla 56 153

b) Faktorizace 291 311 a podobně

3) Rekordy pro Shorův algoritmus (původní kvantový algoritmus)

Shorův algoritmus je skutečný kvantový algoritmus pro faktorizaci, ale doposud se prakticky nerealizoval pro větší čísla, protože to vyžaduje více qubitů a spolehlivost:

Shrnutí rekordů

Experiment / metodaNejvětší faktorizované čísloPoznámky
Hybridní kvantně-klasický přístup / QAOA261 980 999 226 229 (48 bitů)Největší praktický záznam kvantového faktorizování
Experimenty NMR / jiné fyzické systémy56 153Starší rekordy mimo čistý Shorův algoritmus
Shorův algoritmus (kvantový algoritmus)21Největší faktorizace přímo Shorovým algoritmem

Poznámka

Chceš stručné časové shrnutí vývoje rekordů faktorizace na kvantových počítačích včetně použitých metod a zařízení?

Řekl/a jsi:

a co v české republice? tam prý také mají kvantový počítač a faktorizovali nějaké číslo

ChatGPT řekl:

Shrnutí: v České republice zatím není potvrzeno, že by někdo na fyzickém českém kvantovém počítači faktorizoval nějaké číslo jako rekordní demonstraci.
Existují spíše informace o instalaci a zprovoznění kvantového počítače, ne o konkrétním faktorizování čísel jako výsledku experimentů.

🇨🇿 Kvantový počítač v ČR — co je pravda

První český kvantový počítač:

❗Fact-checking: faktorizace na VLQ

🤔 Co se v českém prostředí skutečně děje

⚠️ Závěr

V ČR je nyní funkční kvantový počítač (VLQ), ale:

Pokud chceš, mohu vyhledat konkrétní vědecké publikace nebo projekty, které zkoušely nebo plánují faktorizovat čísla pomocí VLQ nebo jiných kvantových metod v ČR.

Řekl/a jsi:

jak ohrožuje faktorizace kvantovými počítači RSA šifrování?

ChatGPT řekl:

Jak faktorizace na kvantových počítačích ohrožuje RSA

1) Proč je RSA dnes bezpečné

RSA stojí na předpokladu, že rozklad velkého čísla N=p⋅qN=p⋅q (součin dvou velkých prvočísel) je na klasických počítačích výpočetně neproveditelný v rozumném čase.
Veřejný klíč obsahuje NN, soukromý klíč vyžaduje znalost pp a qq.

2) Co mění kvantové počítače

Shorův algoritmus (1994) umí:

To je zásadní rozdíl oproti klasickým algoritmům (např. GNFS), které mají subexponenciální, ale stále extrémně náročnou složitost.

👉 Dostatečně velký a stabilní kvantový počítač by dokázal z veřejného RSA klíče spočítat soukromý klíč.

3) Praktický dopad na RSA

Pokud by existoval kvantový počítač schopný spustit Shorův algoritmus v potřebném měřítku:

Všechny délky klíčů jsou kvalitativně stejně zranitelné – delší klíč pouze oddaluje útok, neřeší problém.

4) Kolik qubitů by bylo potřeba

Odhady pro RSA-2048:

➡️ Takový stroj zatím neexistuje, ale je považován za technicky dosažitelný v horizontu desítek let.

5) „Harvest now, decrypt later“

I dnes existuje reálné riziko:

To je kritické pro:

6) Dopad na digitální podpisy

Kvantová faktorizace:

To je často větší problém než samotné šifrování.

7) Proč se dnes RSA nahrazuje

Kvůli této hrozbě probíhá přechod na post-quantum kryptografii (PQC):

NIST už standardizoval náhrady (např. CRYSTALS-Kyber, Dilithium).

Shrnutí jednou větou

Kvantové počítače ohrožují RSA tím, že pomocí Shorova algoritmu mění faktorizaci z prakticky nemožného problému na efektivně řešitelný, čímž ruší samotný bezpečnostní základ RSA – bez ohledu na délku klíče.

Pokud chceš, mohu to navázat:

Řekl/a jsi:

přibliž mi trochu více RSA, jak tam ty prvočísla fungují

ChatGPT řekl:

RSA: jak v něm fungují prvočísla (krok za krokem)

RSA je založeno přímo na vlastnostech prvočísel a aritmetice modulo velkého čísla. Bez nich by algoritmus nefungoval.

1) Volba dvou velkých prvočísel

Vyberou se dvě náhodná velká prvočísla:p,  qp,q

Prvočísla jsou klíčová proto, že:

2) Vznik modulu NN

Spočítá se:N=p⋅qN=p⋅q

Každý zná NN, ale nikdo (snad) nezná pp a qq.

3) Eulerova funkce a „tajná struktura“

Spočítá se Eulerova funkce:φ(N)=(p−1)(q−1)φ(N)=(p−1)(q−1)

To je zásadní bod:

4) Veřejný exponent ee

Zvolí se malé číslo ee, typicky:e=65537e=65537

Podmínka:gcd⁡(e,φ(N))=1gcd(e,φ(N))=1

5) Soukromý exponent dd

Spočítá se číslo dd tak, aby:e⋅d≡1(modφ(N))e⋅d≡1(modφ(N))

Jinými slovy:

➡️ Tady je přímo „zakódovaná“ znalost prvočísel p,qp,q.

6) Proč to funguje (kouzlo prvočísel)

Pro libovolnou zprávu m<Nm<N:

c=me mod Nc=memodN

m=cd mod Nm=cdmodN

To funguje díky Eulerově větě:mφ(N)≡1(modN)mφ(N)≡1(modN)

která platí právě proto, že NN je součinem dvou prvočísel.

7) Kde je bezpečnost

Útočník zná:

Nezná:

A platí:

➡️ Celá bezpečnost RSA = obtížnost faktorizace NN.

8) Malý číselný příklad (zjednodušený)

Pouze pro ilustraci:

Zpráva:m=42m=42

Šifrování:c=427 mod 187=15c=427mod187=15

Dešifrování:1523 mod 187=421523mod187=42

9) Proč kvantové počítače RSA ničí

Kvantový počítač:

Nejde o slabinu implementace, ale o matematický základ.

Jednověté shrnutí

Prvočísla v RSA fungují jako „skrytá struktura“ čísla NN: jejich znalost umožní vrátit exponenciální operaci zpět, a bezpečnost stojí čistě na tom, že tuto strukturu neumíme bez faktorizace odhalit.

Pokud chceš, mohu navázat:

Řekl/a jsi:

a jak je ohrožena kryptografie na ECC? když je to jen získání rozkladu na prvočísla?

ChatGPT řekl:

ECC není založena na rozkladu na prvočísla, ale kvantové počítače ji přesto ohrožují – jiným, ale stejně zásadním způsobem.

Níže je přesné vysvětlení, bez zjednodušování.

1) Na čem stojí ECC (na rozdíl od RSA)

ECC (Elliptic Curve Cryptography) je založena na problému:

ECDLP – Elliptic Curve Discrete Logarithm Problem

Zjednodušeně:

To není faktorizace a nepracuje se zde s prvočísly jako tajemstvím.

Prvočísla se v ECC používají jen:

2) Co přesně kvantový počítač v ECC láme

Shorův algoritmus neumí jen faktorizovat. Umí obecně:

řešit problém diskrétního logaritmu v libovolné konečné grupě

A eliptické křivky jsou konečné grupy.

➡️ Kvantový počítač:

Stejně „snadno“, jako rozloží N=pqN=pq v RSA.

3) Praktický dopad na ECC

Jakmile je k dispozici dostatečně velký kvantový počítač:

SystémCo útočník získá
ECDHsoukromý klíč
ECDSAmožnost padělat podpisy
Schnorrpadělat podpisy
Bitcoinkrást UTXO z odhalených pubkey

To je okamžitý kolaps bezpečnosti.

4) Kolik qubitů by bylo potřeba (řádově)

Pro ECC-256 (např. secp256k1):

To je:

5) Proč to mate: „vždyť tam nejsou prvočísla“

Správná intuice je tato:

Na klasickém počítači:

Kvantový počítač:

6) Proč nepomůže „větší křivka“

Stejně jako u RSA:

➡️ ECC-384, ECC-521 také padnou, jen o něco později.

7) Dopad na Bitcoin (konkrétně)

Bitcoin používá:

Rizika:

  1. UTXO s odhaleným pubkey
    – po prvním utracení je veřejný klíč viditelný
    – kvantový útočník může dopočítat privkey
  2. Staré adresy (P2PK)
    – veřejný klíč je zveřejněn trvale
    – okamžitě ohrožené

8) Proč se přechází na post-quantum kryptografii

Protože:

PQC algoritmy:

Jednověté shrnutí

ECC není ohrožena faktorizací, ale tím, že Shorův algoritmus umí efektivně řešit diskrétní logaritmus na eliptických křivkách, což umožní přímo získat soukromý klíč z veřejného – stejně fatálně jako u RSA.

Pokud chceš, mohu to navázat:

Řekl/a jsi:

jak souvisí „problém diskrétního logaritmu v libovolné konečné grupě“ s faktorizací? matematické vysvětlení

ChatGPT řekl:

Níže je čistě matematické vysvětlení, bez metafor a bez aplikačních odboček.

1) Dva zdánlivě různé problémy

Faktorizace (RSA)

Je dáno:N=pqN=pq

kde p,qp,q jsou neznámá prvočísla.

Cíl:najıˊt p,qnajıˊt p,q

Diskrétní logaritmus (DLP)

Je dána konečná grupa (G,⋅)(G,⋅), generátor g∈Gg∈G a prvek:h=gxh=gx

Cíl:najıˊt xnajıˊt x

Na první pohled:

2) Klíčové spojení: struktura grupy modulo NN

Uvažuj grupu:(Z/NZ)×(Z/NZ)×

To je multiplikativní grupa invertibilních prvků modulo NN.

Její řád:

∣(Z/NZ)×∣=φ(N)∣(Z/NZ)×∣=φ(N)

A platí:φ(N)=(p−1)(q−1)φ(N)=(p−1)(q−1)

➡️ Řád grupy přímo kóduje faktorizaci NN.

3) Redukce: faktorizace ⇄ struktura grupy

Znalost faktorizace ⇒ znalost grupy

Pokud znáš p,qp,q:

(Z/NZ)×≅(Z/pZ)××(Z/qZ)×(Z/NZ)×≅(Z/pZ)××(Z/qZ)×

Znalost struktury grupy ⇒ faktorizace

Naopak platí hluboký fakt:

Umět efektivně pracovat se strukturou (Z/NZ)×(Z/NZ)× implikuje faktorizaci NN.

Konkrétně:

⇒ lze z toho dopočítat p,qp,q

4) Diskrétní logaritmus „obsahuje“ faktorizaci

Uvažuj, že máš algoritmus:DLOG(Z/NZ)×DLOG(Z/NZ)×​

To znamená:

Co z toho plyne?

  1. Z DLOG lze určit řád prvku gg
  2. Z řádu prvků lze určit φ(N)φ(N)
  3. Ze znalosti φ(N)φ(N) lze spočítat:

p+q=N−φ(N)+1p+q=N−φ(N)+1pq=Npq=N

⇒ řešíš kvadratickou rovnici ⇒ získáš p,qp,q

➡️ Faktorizace se redukuje na DLP.

5) Proč Shor řeší obojí stejným mechanismem

Shorův algoritmus řeší problém řádu prvku:najdi r takoveˊ, zˇe ar≡1(modN)najdi r takoveˊ, zˇe ar≡1(modN)

To je:

Faktorizace:

DLP:

➡️ Stejný kvantový nástroj: hledání periody.

6) Eliptické křivky: stejný abstraktní problém

ECC pracuje v grupě:(E(Fp),+)(E(Fp​),+)

A Shor platí obecně:

Diskrétní logaritmus v libovolné konečné abelovské grupě je řešitelný v polynomiálním čase.

Proto:

jsou z pohledu kvantových algoritmů projevy téhož problému:
zjištění skryté periodické struktury grupy.

7) Přesná matematická věta (neformálně)

Faktorizace celých čísel je redukovatelná na diskrétní logaritmus v multiplikativní grupě modulo NN.

A kvantově:

Oba problémy jsou instancemi problému hledání skryté podgrupy.

8) Shrnutí v jedné větě

Faktorizace a diskrétní logaritmus nejsou různé problémy, ale dva různé způsoby, jak zvenku nahlédnout do skryté grupové struktury; Shorův algoritmus tuto strukturu odhaluje jednotným matematickým mechanismem.

Pokud chceš, mohu navázat:

ChatGPT může dělat chyby. Doporučujeme kontrolovat důležité informace. Viz předvolby cookies.