AuthorsH. Raddum and S. Varadharajan
TitleFactorization using binary decision diagrams
Project(s)Cryptography Section
Publication TypeJournal Article
Year of Publication2018
JournalCryptography and Communications
Date Published2018
Publisher Springer
KeywordsBinary decision diagrams, Integer factorization, RSA

We address the factorization problem in this paper: Given an integer N=pq, find two factors p and q of N such that p and q are of same bit-size. When we say integer multiplication of N, we mean expressing N as a product of two factors p and q such that p and q are of 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 N as product of factors p and q using a BDD. Using various operations on the BDD we present an algorithm for factoring N. All calculations are done over GF(2). We show that the number of nodes in the constructed BDD is O(n3) where n is the number of bits in p or q. We do factoring experiments for the case when p and q are primes as in the case of RSA modulus 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.

Citation Key26355

Contact person