Several fast algorithms are available to factorize big numbers, but what is the best algorithm to factorize a lot of "little" numbers? I need to factorize a lot of odd numbers $< \mathbf{2^{56}}$. I want to do that only with 64 bits arithmetic.
I use a combination of that:
- A table of all prime $< 2^{16}$.
- A "offset technics" to iterate on possible prime numbers bigger than $2^{16}$.
- The Pollard's rho heuristic to (probably) find a divisor. I implemented the version presented in "Introduction to Algorithms" (Cormen, Leiserson, Rivest and Stein), with added a maximum number of iterations something like $n^{1/2}$ or $n^{1/4}$.
In fact I want to compute the sum of odd divisors $\sigma_{\text{odd}}$ of these numbers. To check that $\forall n \in \mathbb{N}, n > 1, \exists k : \sigma_{\text{odd}}^k(n) < n$. Maybe there is a better way to do that than use the complete factorization in prime numbers?
And what about all these considerations in a parallel context?
Answer: Finally I use an unique big table with all prime numbers $<2^{32}$:
- prime32.7z (165 MiB): https://mega.nz/#!jQtWGY5Y!jHj0PXwJ52Rd69cSuFzo_X_3lk-N5GJHC5JiiR0K7wE
- prime32.bin.gz (272 MiB): https://mega.nz/#!jU9FDRBK!wLfU4YncXYR5fZbUTqRGNZX7eL_j6BlG2j4mSr3YHBM
In order to calculate the sum of divisors of definite number you may use the Euler pentagonal number theorem application for divisors sum $\sigma(n)$.
$$\sigma(n)=\sigma(n-1)+\sigma(n-2)-\sigma(n-5)-\sigma(n-7)+...$$ The ${1,2},{5,7},...$ are generalized pentagonal numbers.
$\sigma(n)=0$ if $n<0$
$\sigma(n-n) = 0$ if $n$ is not a generalized pentagonal number and $\sigma(n-n) = n$ otherwise.
The generalized pentagonal numbers can be found:
https://oeis.org/A001318
There are some other articles:
http://euler.genepeer.com/eulers-pentagonal-number-theorem/ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.538.6485&rep=rep1&type=pdf