Faktorado de entjero: Malsamoj inter versioj
[nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
→Malfacileco: Korektis lingvaĵon de unu alineo Etikedoj: Poŝtelefona redakto Redakto de poŝaparata retejo Altnivela poŝaparata redaktado |
→Malfacileco: Korektis lingvaĵon de unu alineo Etikedoj: Poŝtelefona redakto Redakto de poŝaparata retejo Altnivela poŝaparata redaktado |
||
Linio 11:
Se la nombroj estas tre grandaj, ne estas konata bona faktoriga [[algoritmo]]. La supozebla malfacileco de ĉi tiu problemo estas je la koro de certaj [[ĉifriko|ĉifrikaj]] algoritmoj, ekzemple [[RSA]]. Multaj branĉoj de [[matematiko]] kaj [[komputiko]] estas ligitaj al tiu ĉi problemo, ekzemple [[elipsaj kurboj]], [[algebra nombroteorio]] kaj [[kvantuma komputado]].
Ne
Se granda, ''b''-[[bito|bita]] nombro estas produto de du primoj kiuj estas de proksimume sama amplekso, do ne estas publikigita algoritmo kiu povas faktorigi en [[polinoma tempo]], kio estas, kiu povas faktori en tempo ''[[granda O skribmaniero|O]](b<sup>k</sup>)'' por iu konstanto ''k''. Estas publikigitaj algoritmoj kiuj estas pli rapidaj ol ''O((1+ε)<sup>b</sup>)'' por ĉiu pozitiva ε, ''kio estas'', sub-eksponenta funkcio.
|