# Integer Program for Multiplication of Large Numbers

Given two numbers in binary representation $$b_1,b_2$$ and let $$k_1, k_2$$ be the number of digits.

What would be an integer program that models the multiplication of these two numbers? The restriction is that the variables as well as the coefficients of the variables are not allowed to take huge values (that it is still solvable in floating point arithmetic for large numbers).

The integer program needs at least $$k_1+k_2$$ binary variables to model the result of the multiplication.

• Are $b_1$ and $b_2$ constant or variable? Is $2^{k_1+k_2-1}$ considered huge as a coefficient? – RobPratt Jul 7 at 15:24
• @RobPratt i would be interested in both version. Yes this is really large! I am looking for something that still works for $k_1=100$. – user3680510 Jul 7 at 16:05
• As a warmup, I recommend considering addition (with binary carryover variables) instead of multiplication. – RobPratt Jul 7 at 16:32

If the numbers are small enough, you can model the multiplication $$z=xy$$ in a quadratic program, and add the equality $$x = \sum2^i b_i$$ to relate each number $$x$$ to its binary representation.