Suppose we have two sets A, B of size n, k respectively, which are sets of non-negative integers each coded with N bits, and which we would like to form a set of bit strings of length 3N and [maximum] size n * k such that they represent all possible multiplications of integers, one taken from A and the other from B. Thus, if one of the sets is { 1,2} and the other {3,4} (in bits), the result set must be {1 * 3, 1 * 4, 2 * 3, 2 * 4}.

Assume that A, B are given as binary decision diagrams (BDD) and that we would like to compute the multiplication set also in the form of a binary decision diagram, representing the bit strings of all the multiplication results.

Now, it is well known that the BDDs representing the multiplication, even if A, B were of size 1 each, have an exponential size. Otherwise, we could factor integers in polynomial time.

My question is whether the multiplication set can be calculated in polynomial time, but by iterating BDD operations until reaching a fixed point. In this way, we will not be able to factor integers (at least not easily). For example, it is well known that we can calculate the addition of binary numbers by iterating AND and XOR until a fixed point is reached (each step gives an intermediate addition and a holdback, to be added until that the postponement is null).

I need this for the practical implementation of mine, where indeed I have two sets of integers at fixed bit widths represented in BDDs, and I would like to calculate their multiplication, without having to "decompress" BDDs into real numbers, each BDD can encode many numbers.