Factoring extremely large integers.

Question

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so would appreciate a verbose description of equations.

The Problem:

The integer in question will ALWAYS be a power of N and will be known to us to calculate against. So let's assume N = 2 for example. That will give us a sequence of numbers like:

2, 4, 8, 16... up to hundreds of thousands of digits.

I need to find all possible factors (odd, even, prime, etc.) as efficiently as possible.

The Question:

What is the solution and how could I understand this from mathematical and computational perspectives?

EDIT:

Does the fact that each number to be factored is a power of 2 help in eliminating any complexity or computational time?

Answer 1

If $N = 2$ (or any prime) and you can get $k$ as Ross indicated, then the divisors of $A$ are $\{1, N, N^2, \ldots, N^i, \ldots, N^{k} \}.$ If $N$ is a composite, then you will incur extra time complexity in computing the prime factorization of $N = \prod_{i = 1}^{\ell} p_i^{e_i}$ and the divisors of $A$ are all possible numbers of the form $\prod_{i=1}^{\ell} p_i^{r_i}$ where $\mathbf{0} \le r_i \le ke_i.$ Notice $r_i$ can be zero for some terms. There are $\prod_{i=1}^{\ell}(ke_i + 1)$ such possible divisors.

Answer 2

Are you given $N$? Then if the number to be factored is $A$, you have $A=N^k$ and only have to find $k$. Taking logs, $k=\frac {\log A}{\log N}$. So, yes, if you know $N$ it helps a lot.

If $N$ is prime, all the possible factors of $A$ are of the form $N^m$ for $0 \le m \le k$ so you have them. If $N$ is composite, factor it as $N=p_1^{q_1}p_2^{q_2}\ldots p_n^{q_n}$. Then all the factors are of the form $p_1^{m_1}p_2^{m_2}\ldots p_n^{m_n}$ where $0 \le m_1 \le kq_1$ etc.

Answer 3

If the number in question is known to be a power of 2, you are just trying to find $n$ such that $N=2^n$. If the input number is in decimal notation, just count the digits, subtract 1, multiply by 3.3219, and round up. Then add 1 if the initial digit is 2 or 3, 2 if the initial digit is 4, 5, 6, or 7, and 3 if the initial digit is 8 or 9.

For example, suppose $N=1267650600228229401496703205376$. This has 31 digits; $30\cdot3.3219 = 99.657$, so $N=2^{100}$. Or take $N=$

43699499387321412970609716695670835099367888141129535719972915195176
79444176163354392285807163181819981286546206512408458617685052043667
09906692902245553277900892247131030458103436298545516643924637451297
481464347472084863384057367177715867713536

which has 246 digits. $245\cdot3.3219 = 813.872383$; we round up to 814, add 2 because the first digit is 4, so this number is $2^{816}$.

The magic constant 3.3219 is actually $\log 10 / \log 2$. For input numbers in the hundreds of thousands of digits you will need a more accurate version, say 3.3219281.