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?
Best Answer
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=$
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.