Voi răspunde mai întâi la întrebarea dvs. (care are un răspuns destul de simplu de care ați putea fi dezamăgit), înainte de a discuta o extensie ușoară a problemei dvs. despre care credem că sunt computere cuantice nu poti rezolva, care te poate interesa.
Ca o notă secundară rapidă cu privire la comentariu
Cel puțin în cazul factoring dacă $\log_2(p)=\log_2(q)=\log_2(k)$ atunci rezolvarea ecuației este informațional imposibilă teoretic, deoarece este practic un bloc unic.
În general, modul în care este gestionat acest lucru înseamnă că un adversar câștigă dacă își revine orice solutie la $x^2+y^2\bmod k$, mai degrabă decât o soluție specifică.
Acest lucru se poate vedea în lucruri precum
- jocul consecvent de recuperare a cheii (mai degrabă decât jocul de recuperare a cheii țintă) și
- modul în care funcțiile unidirecționale trebuie să recupereze orice preimagine a $y$, de exemplu. orice $x$ astfel încât $f(x) = y$, mai degrabă decât unele „exacte” $x'$ care este ales intern în timpul jocului.
Voi descrie lucrurile în acești termeni, deoarece este standard.
Dacă acest lucru nu este potrivit pentru aplicația dvs., poate ar trebui să încercați să descrieți mai mult aplicația dvs.
Această întrebare este simplă: poate algoritmul lui Shor să rezolve aceste ecuații în timp polinomial atunci când sunt efectuate cu aritmetică finită în loc de peste numere întregi?
Înțeleg că algoritmul lui Shor este descris peste $\mathbb{Z}$ Decat $\mathbb{Z}_n$ nu este o problemă serioasă cu implementarea sa în „lumea reală”. În special, deși trebuie să aveți grijă ca reprezentările cu precizie finită cu care se lucrează să nu fie prea „cu pierderi”, înțeleg că aceste detalii sunt mult mai ușor de rezolvat decât lucruri precum construirea unui computer cuantic.
Cu condiția ca această înțelegere să fie corectă, răspunsul la ambele întrebări este aproximativ banal --- rezolvați diferitele ecuații peste $\mathbb{Z}$, iar apoi reduceți răspunsurile $\bmod k$ pentru a obține soluții peste $\mathbb{Z}_k$. După cum subliniază Poncho în comentarii, problema rezolvării $n = xy\bmod k$ pentru $x, y$ este chiar clasic ușor, așa că morala poveștii este că impunerea unor constrângeri modulare poate face problemele (poate) dramatic mai ușoare, dar pentru aceste probleme nu îngreunează problemele.
Există o extindere uşoară a problemei rezolvării pt $n = xy \bmod k$ despre care se crede că este cuantic dur.
Rezolvarea acestei congruențe poate fi văzută ca rezolvarea unei ecuații liniare cu o singură variabilă (exact).
Există două moduri naturale de a generaliza acest lucru
- mai mult de o variabilă și
- mai mult de o ecuație.
De exemplu, schimbați problema acolo unde este dată $\vec b = A\vec s\bmod k$ Unde $\vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n$.
Totuși, este încă banal de „rezolvat” --- dacă alegeți $A$ să fie matricea identităţii, atunci $\vec s = \vec b$ lucrări.
Mai general, dacă alegi $A$ a fi inversabil peste $\mathbb{Z}_k$, atunci $\vec s = \vec A^{-1}\vec b$ lucrări.
Chiar dacă $\vec A$ nu este inversabilă (să spunem că nu este pătrată) există lucruri pe care le puteți face folosind tehnici generale liniar-algebrice.
Toate acestea sunt atât eficiente, cât și clasice, de ex. Shor este încă exagerat.
În general, modul în care se oprește atacurile de mai sus este dublu
specificați o matrice $A$ trebuie folosit (deci nu se poate seta $A$ să fie identitatea sau o matrice inversabilă aleatorie) și
injectați ceva zgomot în problemă.
Rețineți că primul punct este suficient (atacul lui Poncho încă funcționează), așa că al doilea punct ar trebui văzut ca fundamental.
Concret, problema este următoarea
Învățarea cu erori: Lăsa $A\in\mathbb{Z}_k^{n\ori n}$ să fie uniform aleatoriu și să fie $\vec s\in\mathbb{Z}_k^n$ fi un vector „secret”.
Pentru o distribuție fixă $\chi$ sprijinit pe $\mathbb{Z}_k$, spunem noi caută învățarea cu erori problema este sa te recuperezi $\vec s$, dat $(A, A\vec s + \vec e)$, Unde $\vec e \gets \chi^n$.
În funcție de parametrizare, problema LWE este unul dintre candidații principali pentru o ipoteză de duritate care este sigură împotriva computerelor cuantice.
Adică, pentru o generalizare adecvată a rezolvării $n \equiv xy\bmod k$, se crede că algoritmul lui Shor nu poti rezolva problema.
Totuși, așa cum am văzut mai sus, generalizarea reprezintă mulți pași eliminați din problema dumneavoastră inițială.
Există și alte generalizări similare în această direcție (Paritatea de învățare cu problema zgomotului sau problema GCD aproximativă) --- asemănarea fundamentală cu toate acestea este că aveți o variantă „zgomotoasă” a unei probleme liniare.
Există în plus o generalizare a $x^2+y^2\bmod k$ problemă despre care se crede că este sigură cuantică, dar nu știu atâtea detalii, așa că voi scrie mai puțin.
În general, se înlocuiește polinomul pătratic $f(x, y) = x^2+y^2\bmod k$ cu un arbitrar polinom pătratic (sau colecție de polinoame) în $n$ variabile.
Apoi, problema refacerii $(x_1,\puncte, x_n)$ care sunt zerouri (simultane) ale polinoamelor pătratice multivariate $p_0, \dots,p_m$ este (aproximativ) legat de spargerea „Criptosistemelor multivariate”.
Rețineți că insistența că se recuperează zerourile polinoamelor (mai degrabă decât $p(x_0,\dots,x_n) = N$, așa cum cereți) vine fără pierderi de generalitate, deoarece se poate recupera acest lucru uitându-se la un zero de $p(x_0,\dots,x_n) - N$.
Toate acestea sunt pentru a spune că
- Se crede că Shor's îți sparge ambele probleme, dar
- Există generalizări ale ambelor probleme despre care se crede că sunt sigure din punct de vedere cuantic. De fapt, multe dintre ipotezele „conductoare” sigure cuantice (tot ceea ce știu, cu excepția lucrurilor de izogenie și a codurilor de rang-metric) pot fi văzute ca generalizări ale problemelor tale.
