# Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the $s$-th prime number.

Can this information be somehow incorporated in an algorithm to improve its efficiency?

Thanks.

• So, in other words, $n$ is squarefree and $P_s$-smooth. How big are $P_s$ and $k$? Being squarefree clearly doesn't help much (semiprimes are squarefree, after all) but the second condition seems to suggest that ECM would work very well on such $n$, since the prime factors are small and hence a random elliptic curve over $(\mathbb{Z}/p\mathbb{Z})^\times$ is very likely to have a smooth order. – Thomas May 15 '14 at 10:25
• Hi @Thomas, thanks! Basically, it is assumed that $k \approx \alpha s$ for small $\alpha \in (0, 1/10)$. Any other insight? – rodms May 17 '14 at 11:12
• Is this "small $\alpha$" uniformly distributed in this interval? If we take $s = 10^{20}$ (which is around the ballpark of the limits of ECM) then that would mean you can "efficiently" factor all of your integers up to $10^{20 \alpha 10^{20}}$ (putting that in quotes since the upper bound is superexponential), which to me looks pretty optimal! Could you give some concrete values of $n$ as a representative example of the average input? – Thomas May 17 '14 at 11:28
• Basically, the more prime factors the number has, the easier it becomes, very quickly. With a group-theoretic algorithm like ECM that can factor out 20-digit primes (for instance), you can partially factor any integer that has a 20-digit prime, regardless of its size - the size of the integer itself does not matter (beyond making calculations a bit slower). So by iteratively applying that algorithm, you can fully factor your $n$ efficiently. And "that algorithm" is going to be ECM, which is the fastest general purpose group-theoretic algorithm known. – Thomas May 17 '14 at 11:33

If $P_s$ is small compared to $n$, then you know that Lenstra's ECM algorithm will perform well compared to the sieve algorithms, which are needed to find larger prime factors.
But when factoring a general integer $n$ of unknown provenance, the first step is usually to run ECM, just in case $n$ happens to have small prime factors. So normally this general algorithm will work fine.
The only way I can see to exploit your knowledge of the prime factors of $n$ is to carry on with the ECM step longer than you would usually do. This might lead to faster factorisation in some cases, depending on the relative sizes of $P_s$ and $n$.