is there a general method for finding $a$ in a number of form $X=B^a*Y$ given $X$, and $B$

Question

As an example

$X=17825792$ and $B=2$

I'm wanting to see if there's a method to find that $X$, in this example 17825792, has $B^a$ as a factor, in this example $2^{20}$.

A method that has a computation time less than linear is what I'm curious about.

Answer 1

There is an algorithm that goes faster than linear. Iteratively square the value of B until it does not divide X anymore and store the values in every step.

Then go backwards with that list and divide the X with that value, if that value divides X. And add a corresponding power of two to the resulting exponent. To better show this, it goes like this:

$2$ divides $X$, store $2$

$4$ divides $X$, store $4$

$16$ divides $X$, store $16$

$\vdots$

$2^{16}$ divides $X$, store $2^{16}$

$2^{32}$ does not divide $X$

set exponent to zero

$2^{16}$ divides $X$, divide $X$ by $2^{16}$, add $16$ to exponent

$2^{8}$ does not divide $X$ anymore

$2^{4}$ divides $X$, divide $X$ by $2^{4}$, add $4$ to exponent

$2^{2}$ does not divide $X$ anymore

$2$ does not divide $X$ anymore

return value of exponent, which is 20