Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits
Mathias Herrmann, Alexander May
In Advances in Cryptology (Asiacrypt 2008), Lecture Notes in Computer Science, Springer-Verlag, 2008.
Abstract:
We study the problem of finding solutions to linear equations modulo an unknown divisor p of a known composite integer N. An important application of this problem is factorization of N with given bits of p. It is well-known that this problem is polynomial-time solvable if at most half of the bits of p are unknown and if the unknown bits are located in one consecutive block. We introduce an heuristic algorithm that extends factoring with known bits to an arbitrary number n of blocks. Surprisingly, we are able to show that ln(2) 70% of the bits are sufficient for any n in order to find the factorization. The algorithm’s running time is however exponential in the parameter n. Thus, our algorithm is polynomial time only for n = O(log logN) blocks.
BibTex:
@INPROCEEDINGS{DBLP:conf/asiacrypt/HerrmannM08,
author = {Herrmann, Mathias and May, Alexander},
title = {Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits},
booktitle = {ASIACRYPT},
year = {2008},
pages = {406-424},
doi = {10.1007/978-3-540-89255-7_25},
crossref = {DBLP:conf/asiacrypt/2008},
bibsource={DBLP, http://dblp.uni-trier.de},
}
crossreferenced publications:
@PROCEEDINGS{DBLP:conf/asiacrypt/2008,
editor = {Pieprzyk, Josef},
title = {Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings},
booktitle = {ASIACRYPT},
series = {Lecture Notes in Computer Science},
volume = {5350},
year = {2008},
publisher = {Springer},
isbn = {978-3-540-89254-0},
bibsource={DBLP, http://dblp.uni-trier.de},
}