[Math] Factoring extremely large integers.

arithmeticcomputational complexitydivisibilityfactoringnumber theory

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=$

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.

Related Question