I'm currently working on a project, where I need to store products of multiple integers. These integers are stored in a list. It should be possible to factor the product at a later point and retrieving the original factors. The product is relatively small, nothing that can't be factored by a computer by brute-force.
Ideally the product should be as small as possible.
So far the product $p$ is always in a from of:
$p = {f_1}^1 \times {f_2}^1 \times \ldots \times {f_n}^1$
All factors, unfortunately, need to be in the form of $f^1$, meaning no factors can occur multiple times.
I thought of using prime numbers as factors because I would obviously get the factors back by simply factoring the product.
I also noticed that I can use squares as a source of factors instead of only prime numbers. This way I can avoid creating a product that is too large, provided the square is smaller than one prime number.
So instead of using a set of only primes $S = \{2, 3, 5, 7, 11, 13, \ldots\}$ I could also use squared numbers, i.e. $4$, since they would also just occur once as a factor in the prodcut: $S = \{2, 3, 4, 5, 7, 9, 11, 13, 16, \ldots\}$.
As an example I would create a product $p = 2 \times 3 \times 7 \times 9 = 378$.
From just the number $378$ I could then clearly reconstruct the original factors again:
$378 = 2 \times 3^3 \times 7 = 2 \times 3 \times 7 \times 9$.
The problem I had without using prime numbers and squares was i.e. for the product $p = 12$:
Was $12$ created as $3 \times 4$ or $2 \times 6$?
My questions are:
- Do I need to use a list of prime numbers and squares or are there other numbers that can also fit in this list?
- Is there a different / better approach to achieve this?