Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
作者： Alexander May , Maike Ritzenhofen
DOI: 10.1007/978-3-642-00468-1_1
关键词: Time complexity 、 Oracle 、 Factor (programming language) 、 Moduli 、 Discrete mathematics 、 Factoring 、 Mathematics 、 NP-easy
摘要: We address the problem of polynomial time factoring RSA moduli N 1 = p q with help an oracle. As opposed to other approaches that require oracle explicitly outputs bits , we use gives only implicit information about . Namely, our a different 2 such and share t least significant bits. Surprisingly, this is already sufficient efficiently factor provided large enough. then generalize approach more than one query.
springer.com
core.ac.uk
sci-hub.st 参考文章(34)
Daniele Micciancio, S. Goldwasser, Complexity of lattice problems : a cryptographic perspective Springer. ,(2002)
Carl D. Meyer, Matrix Analysis and Applied Linear Algebra ,(2010)
Daniele Micciancio, S. Goldwasser, Complexity of lattice problems ,(2002)
Carl Pomerance, The quadratic sieve factoring algorithm theory and application of cryptographic techniques. pp. 169- 182 ,(1985) , 10.1007/3-540-39757-4_17
Claude Crépeau, Alain Slakmon, Simple Backdoors for RSA Key Generation Topics in Cryptology — CT-RSA 2003. pp. 403- 416 ,(2003) , 10.1007/3-540-36563-X_28
Phong Q. Nguên, Damien Stehlé, Floating-Point LLL revisited theory and application of cryptographic techniques. pp. 215- 233 ,(2005) , 10.1007/11426639_13
H. Minkowski, Geometrie der Zahlen B.G. Teubner. ,(1896)
Johannes Blömer, Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices international colloquium on automata languages and programming. pp. 248- 259 ,(2000) , 10.1007/3-540-45022-X_22
Ronald L. Rivest, Adi Shamir, Efficient factoring based on partial information theory and application of cryptographic techniques. pp. 31- 34 ,(1986) , 10.1007/3-540-39805-8_3
Ueli M. Maurer, Factoring with an oracle theory and application of cryptographic techniques. pp. 429- 436 ,(1992) , 10.1007/3-540-47555-9_35