Efficient factorization of numbers with unique prime factors

Question

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.

Answer 1

Not really.

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$.