# How hard is it to find the length of multiplicative 2-partition?

Some terminology at first:

1. Multiplicative 2-partition for number $N$ - a pair of numbers $\{A, B\}$ such that $AB=N$.

2. Minimal multiplicative 2-partition length (denoted $l$) - minimal total number of bits needed to encode multiplicative one of 2-partitions.

Example:

Let $N = 36$. Then possible multiplicative 2-partitions are $\{2, 18\}, \{3, 12\}, \{4, 9\}, \{6, 6\}$. Their lengths are 7=2+5, 6=2+4, 7=3+4, 6=3+3 respectively. Minimal length here is 6, so $l=6$.

The input: non-prime $n$-bit number $N$.

The problem: find out if $n = l$.

YES-instance:

$N$ = 49, since $n$ = 6 and each multiplier takes 3 bits.

NO-instance:

$N$ = 25, since $n$ = 5 and each multiplier takes 3 bits.

The question: what is the complexity for this problem? It's trivial that it's not harder than factoring and I guess it's $PL$-hard. But is it even known to be in $P$?

• Sounds likely to be approximately as hard as factoring. If $N=PQ$ where $P,Q$ are two primes, factoring $N$ is hard, and it's probably hard to distinguish between the case where the smaller prime factor has $n/2$ bits vs where it has $n/2-1$ bits bits (say). – D.W. Feb 14 '18 at 7:43
• Is $l$ a fixed number? What about $36=4*9=6*6$? – Willard Zhan Feb 14 '18 at 19:57
• @WillardZhan gonna change definition now. Shortly, of all partitions we should choose shortest (6*6 here). – rus9384 Feb 14 '18 at 20:05