Počet záznamů: 1
Integer factoring and modular square roots
- 1.0451577 - MÚ 2016 RIV US eng J - Článek v odborném periodiku
Jeřábek, Emil
Integer factoring and modular square roots.
Journal of Computer and System Sciences. Roč. 82, č. 2 (2016), s. 380-394. ISSN 0022-0000. E-ISSN 1090-2724
Grant CEP: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: integer factoring * quadratic residue * PPA
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.678, rok: 2016
http://www.sciencedirect.com/science/article/pii/S0022000015000768
Buresh-Oppenheim proved that the NP search problem to find nontrivial factors of integers of a special form belongs to Papadimitriou's class PPA, and is probabilistically reducible to a problem in PPP. In this paper, we use ideas from bounded arithmetic to extend these results to arbitrary integers. We show that general integer factoring is reducible in randomized polynomial time to a PPA problem and to the problem WEAKPIGEON in PPP. Both reductions can be derandomized under the assumption of the generalized Riemann hypothesis. We also show (unconditionally) that PPA contains some related problems, such as square root computation modulo n, and finding quadratic nonresidues modulo n.
Trvalý link: http://hdl.handle.net/11104/0252707
Název souboru Staženo Velikost Komentář Verze Přístup Jerabek.pdf 1 416.5 KB Vydavatelský postprint vyžádat
Počet záznamů: 1