(Încrucișat pe math stackexchange, nu a primit răspunsuri)
Pentru context, aceasta este o întrebare pentru acasă dintr-o temă deja predată. Caut o mai bună înțelegere a conceptelor implicate, în principal teoria complexității, deoarece nu am mai văzut-o înainte în afara acestei clase (și s-au presupus cunoștințe anterioare).
Mi se cere să evaluez complexitatea decriptării RSA cu și fără utilizarea CRT, fără a utiliza complexitatea asimptotică. În schimb folosiți $c_1$ ca constantă pentru înmulțirea modulară, $c_2$ pentru exponentiație modulară și $c_3$ pentru găsirea inversului multiplicativ.
Încercarea mea: Lasă $s_1$ fi lungimea de $p$, $s_2$ fi lungimea de $q$, $s$ lungimea de $n$, și $x$ lungimea de $d$. Luați în considerare următoarele complexități:
| calcul |
complexitate |
| $m_1=c^d\mod p$ |
$c_2s_1^2x$ |
| $m_2=c^d\mod q$ |
$c_2s_2^2x$ |
| $q^{-1}\mod p$ |
$c_3s_1$ |
| $p^{-1}\mod q$ |
$c_3s_2$ |
Deci, complexitatea utilizării CRT pentru a calcula $m=m_1(q^{-1}\mod p)q+m_2(p^{-1}\mod q)p\mod n$ este $c_1^2c_2c_3s_1^3x+c_1^2c_2c_3s_2^3x=c_1^2c_2c_3x(s_1^3+s_2^3)$.
Între timp, complexitatea de a calcula $m=c^d\mod n$ este $c_2s^2x$, deci diferența este $c_2x(s^2-c_1^2c_3(s_1^3+s_2^3))$.
Cred că acest lucru este greșit, deoarece nu cred că este adevărat în general $s^2\geq s_1^3+s_2^3$ (CRT ar trebui să facă decriptarea mai rapidă) și nu știu dacă putem face presupuneri despre constante.
