Sieve of Eratosthenes for factorization: bitwise complexity?

Question

As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, whether one uses it for finding the primes up to $N$ or for factoring the numbers up to $N$. It is also well-known that the number of bit operations required by the sieve of Eratosthenes to find the primes up to $N$ is $O(N \log N \log \log N)$, assuming, that is, that accessing a bit in an array of size $N$ takes time $O(\log N)$.

It seems to me that the number of bit operations required by the sieve of Eratosthenes to factor the integers from $1$ to $N$ is also $O(N \log N \log \log N)$ (unless one goes about things in a deliberately stupid way - doing the multiplication at the end by multiplying by your large primes before multiplying by your small primes, say; but nobody would do that).

(Here I am assuming something that was long suspected and recently proved, viz., that two $n$-bit numbers can be multiplied in time $O(n \log n)$ (Harvey-van der Hoeven).)

Am I right, or have I overlooked something? Is there a standard reference (or is this too obvious to be written down)?

Answer 1

Newer multiplication algorithms aren't needed to show such a time bound in this model.

Given a precomputed multiplication table of size $O(p)$, multiplication $a \times b$ of $a, b \leq p^{O(1)}$ takes a constant number of additions and table accesses. For example, let $p = \Theta(N^{1/3})$ then the pre-computation step takes $o(N)$ time and a multiplication takes $O(\log N)$ time.

The division is similar and can be assumed to take $O(\log N)$ time after a precomputation. Therefore, even using a naive repeated division like while x != 1: x := x / factor[x], it is possible to factor all integers up to $N$ in $O(N \log N \log \log N)$ time.