3 ms·
Integer factorization is also reducible to Knapsack: To factorize integer N invoke a Knapsack solver with knapsack size of log(N) and items of size logarithm o
by hiker 7y ago
Integer factorization is also reducible to Knapsack:
To factorize integer N invoke a Knapsack solver with knapsack size of log(N) and items of size logarithm of all prime numbers up to sqrt(N): [log 2, log 3, log 5, ...].
If N=pq (say p and q are prime) then log(N)=log(p)+log(q).
So from all possible items in the item set, only log(p) and log(q) will fill the knapsack as tight as possible leaving zero empty space in it.
- stevefan1999 7y agoWell, you mentioned integer factorization, that immediately leads me to RSA, which then leads me to PKI, and then leads me to cryptosystem. Combining it with the Knapsack problem, I was ultimately there for MH knapsack cryptosystem, which is unfortunately cracked [1]. [1]: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...