Computing (quickly) the multiplicity of a (prime) divisor

Question

Question

I have a fixed, prime d and an n < 2⁶⁴, and I want not only to compute whether d divides n, but also its multiplicity (i.e. the max i s.t. dⁱ | n).

I'm already using a fast division, which costs one multiplication and one comparison to check whether d | k (and if so, get the quotient), but I still need to iterate that check i times if I do it naïvely.

Is there a solution that is sublinear in i ?

Context

I am trying to speed up an integer factorization tool, and after switching to faster modular arithmetic (using the Montgomery transform), the table-based search for small factors uses >30% of the runtime (measured when factoring all integers from 2 to 10⁷; obviously, a good factoring tool should be fast on much larger numbers, but I'm trying to first squeeze out the obvious inefficiencies).

Answer 1

For $p=2$, this is easy: On typical architectures n & (-n) is the largest power $2^i$ dividing $n$ and (n & (-n)) % 67 uniquely determines $i$ (from a precalculated table).

For $p=3$, you might try to divide out repeated powers of $9$ and perhaps one additional $3$ in the end. This almost halves the time you spend with $p=3$, but in $\frac23$ of the (uniformly random?) cases you make two tests (though I think that you can get along with one common multiplication for $9$ and $3$ and only a second compare for $3$?)

For $p\ge 5$, I guess that divisibility by higher powers is unlikely enough to allow you to gain with a complex method compared to a well-cachable short piece of code.