Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
Given 2^100 = 1,267,650,600,228,229,401,496,703,205,376, would that mean there are 100 possible factors? –  Raheel Khan Jul 29 '12 at 21:08
1  
$101$ ${}{}{}{}{}{}{}{}{}$ –  André Nicolas Jul 29 '12 at 21:17
    
@RaheelKhan Simpler example: $2^5.$ There are 6 divisors: $2^0 = 1,$ $2^1 = 2,$ $2^2 = 4,$ $2^3 = 8,$ $2^4 = 16,$ and $2^5 = 32.$ The numbers $1$ and $2^k$ itself are counted in. –  user2468 Jul 29 '12 at 21:22
    
Thanks. I'm presuming 101 includes the number 1. –  Raheel Khan Jul 29 '12 at 21:23
    
Yes, $101$ includes both $1$ and $2^{100}.$ –  user2468 Jul 29 '12 at 21:23
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Yes we will know N and can assume it to be 2 in this case. –  Raheel Khan Jul 29 '12 at 20:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.