Počet záznamů: 1  

Integer factoring and modular square roots

  1. 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 souboruStaženoVelikostKomentářVerzePřístup
    Jerabek.pdf1416.5 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.