3
$\begingroup$

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}$:

$\endgroup$
  • $\begingroup$ If you want to factor numbers $< 2^{56}$, the primes $< 2^{28}$ would suffice. Usually, the smaller memory footprint of that table would speed things up (how much depends on various things, like available memory). Also, after trial division by some small primes (perhaps up to $1000$ or $10000$), it may be a good idea to insert a fast primality check like BPSW or Miller-Rabin with fixed bases (small sets of bases that make M-R exact for numbers $< 2^{64}$ are known, BPSW is known to be exact in that range). $\endgroup$ – Daniel Fischer Dec 21 '17 at 13:10
  • $\begingroup$ Another question is whether you need the individual $\sigma(n)$ or whether you need something like $\sum_{n = 1}^N \sigma(n)$. $\endgroup$ – Daniel Fischer Dec 21 '17 at 13:13
  • $\begingroup$ See also github.com/freebsd/freebsd/tree/master/usr.bin/factor $\endgroup$ – lhf Dec 21 '17 at 13:24
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It is a beautiful formula. Thanks. In term of algorithmic complexity I think it is useless. I think the complexity is something like the naive approach (if $n$ is not a perfect square) : $\sigma(n) = \sum\limits_{\stackrel{d \backslash n}{d \leq \left\lfloor\sqrt(n)\right\rfloor}} \left(d + \frac{n}{d}\right)$ $\endgroup$ – Olivier Pirson Nov 12 '17 at 15:29
  • $\begingroup$ Yes it is probably useless. But I think that there might be some optimization making this useful. I will try to find some documents describing this. $\endgroup$ – Gevorg Hmayakyan Nov 12 '17 at 18:05

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.