Ha a ma ismert legjobb algoritmust és a leggyorsabb számítógépeket használjuk, egy ilyen kb. 125 jegyű RSA kulcs megfejtése, Rivest becslése szerint körülbelül 40 quadrillió évet venne igénybe! Ez azt jelenti, hogy praktikusan a belátható jövőben reménytelen a többszáz jegyű RSA kulcsok faktorizáció útján történő megfejtése.
Ugyanakkor maga Rivest és kollégái is elismerik, hogy semmiféle elméleti bizonyítékuk nincs arra, hogy az RSA titkosítási eljárás megfejthetetlen.”
T.D.T.: Balázs, általános prímfaktorizációs polinomiális algoritmus nincs, de speciális osztályokkal érdekes lehet foglalkozni. Például a fenti kedvenc képletedet (n2-re) jól használhatod ha N=a2-b2 alakú, vagyis a két prímtényezője: p=a+b, q=a-b

T.D.T.: Más! Fermat karácsonyi tétele azt mondja ki, hogy ha p=4k+1 alakú prím, akkor egyértelműen felírható két négyzetszám összegeként.
T.D.T.: Itt találsz egy másik érdekes lehetőséget a faktorizációra: http://www.titoktan.hu/_raktar/_e_vilagi_gondolatok/CPSmagy.htm