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?


  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas May 15 '14 at 10:25
  • $\begingroup$ Hi @Thomas, thanks! Basically, it is assumed that $k \approx \alpha s$ for small $\alpha \in (0, 1/10)$. Any other insight? $\endgroup$ – rodms May 17 '14 at 11:12
  • $\begingroup$ 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? $\endgroup$ – Thomas May 17 '14 at 11:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas May 17 '14 at 11:33

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.