Introducere
La începutul acestui an, Claus Peter Schnorr a susținut că a „rupt RSA”. Lucrarea originală a fost discutată în Metoda de factoring 2021 a lui Schnorr arată că criptosistemul RSA nu este sigur?. A versiune revizuită din lucrarea sa a fost postată pe iacr în urmă cu aproximativ o săptămână și, conform comentariului lui @fgrieu, cineva a încercat să înceapă o discuție în jurul ei: Este âFast Factoring Integers by SVP Algorithms, corectedâ corect?.
Am decis să încerc și m-am trezit complet nedumerit de o afirmație timpurie din ziar. Consideră o permutare $f$ de $\{1,\puncte,n\}$ și definește vectorii coloană $b_1,\dots,b_n,b_{n+1}$ ca mai jos
Unde $p_1=2,p_2=3,\dots$ sunt primii $n$ numere prime și $N'$ este irelevant pentru problema mea (presupun). El consideră o combinație liniară cu coeficienți întregi $e_1,\dots,e_n$ din primul $n$ vectori
$${\bf b}=\sum_{i=1}^n e_i{\bf b}_i \in \mathcal{L}(R'_{n,f})$$
seturi
$$u=\prod_{e_i>0} p_i^{e_i}, v=\prod_{e_i<0}p_i^{-e_i}\in {\mathbb{N}}$$
si scrie
$$\hat{z}_{{\bf b}}=N'\ln{(u/v)}$$
pentru $b$ultimul (adică $(n+1)$-th) coordonată.
Problema
Problema pe care o am este cu estimarea unei limite inferioare pentru $\|b\|^2$ care urmează. scrie Schnorr
Acest lucru pare să fie fals la prima vedere: afirmă că
$$\sum_i e_i^2f(i)^2 \geq\sum_i |e_i|\ln(p_i)$$
Dar dacă permutarea $f$ este ales astfel încât, să zicem, $f(n)=1$ apoi alegerea $e_n=1$ si toate celelalte $e_i=0$ randamente
$$1\geq\ln(p_n)$$
care, cu excepția cazului în care îmi scapa ceva, este evident fals.
În plus, dacă nu $e$ este vectorul zero, nu există nicio posibilitate ca inegalitatea pretinsă să poată fi vreodată o egalitate, deoarece, la eliminarea $\hat{z}_b^2$ termen din ambele părți, partea dreaptă $\ln(uv)$ este irațional, fiind logul natural al unui număr întreg $uv\geq 2$, în timp ce partea stângă, $\sum_i e_i^2f(i)^2$, este un întreg pozitiv.
Am pierdut ceva? Poate cineva să ghicească afirmația corectă pe care încearcă să o demonstreze?
