LAUSR

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