@article {26355,
	title = {Factorization using binary decision diagrams},
	journal = {Cryptography and Communications},
	volume = {11},
	year = {2018},
	month = {2018},
	pages = {1-18},
	publisher = { Springer},
	abstract = {We address the factorization problem in this paper: Given an integer\&nbsp;N=pq, find two factors\&nbsp;p\&nbsp;and\&nbsp;q\&nbsp;of\&nbsp;N\&nbsp;such that\&nbsp;p\&nbsp;and\&nbsp;q\&nbsp;are of same bit-size. When we say integer multiplication of\&nbsp;N, we mean expressing\&nbsp;N\&nbsp;as a product of two factors\&nbsp;p\&nbsp;and\&nbsp;q\&nbsp;such that\&nbsp;p\&nbsp;and\&nbsp;q\&nbsp;are of\&nbsp;same bit-size. We work on this problem in the light of Binary Decision Diagrams (BDD). A Binary Decision Diagram is an acyclic graph which can be used to represent Boolean functions. We represent integer multiplication of\&nbsp;N\&nbsp;as product of factors\&nbsp;p\&nbsp;and\&nbsp;q\&nbsp;using a BDD. Using various operations on the BDD we present an algorithm for factoring\&nbsp;N. All calculations are done over\&nbsp;GF(2). We show that the number of nodes in the constructed BDD is\&nbsp;O(n3)\&nbsp;where\&nbsp;n\&nbsp;is the number of bits in\&nbsp;p\&nbsp;or\&nbsp;q. We do factoring experiments for the case when\&nbsp;p\&nbsp;and\&nbsp;q\&nbsp;are primes as in the case of RSA modulus\&nbsp;N, and report on the observed complexity. The multiplication of large RSA numbers (that cannot be factored fast in practice) can still be easily represented as a BDD.},
	keywords = {Binary decision diagrams, Integer factorization, RSA},
	issn = {1936-2447},
	doi = {10.1007/s12095-018-0304-7},
	url = {https://link.springer.com/article/10.1007/s12095-018-0304-7},
	author = {Raddum, H{\r a}vard and Varadharajan, Srimathi}
}
