Mixing
A simple method of factorization $ 2^30+1 $
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
How can you factor $ 2^30 + 1 $? This task was supposed to be at one interview, there is an assumption that there should be a simple solution.
number-theory elementary-number-theory prime-factorization
edited Aug 6 at 0:31
David G. Stork
7,7012929
asked Aug 6 at 0:27
Vladislav Kharlamov
572216
add a comment |Â
up vote
3
down vote
favorite
How can you factor $ 2^30 + 1 $? This task was supposed to be at one interview, there is an assumption that there should be a simple solution.
number-theory elementary-number-theory prime-factorization
edited Aug 6 at 0:31
David G. Stork
7,7012929
asked Aug 6 at 0:27
Vladislav Kharlamov
572216
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
How can you factor $ 2^30 + 1 $? This task was supposed to be at one interview, there is an assumption that there should be a simple solution.
number-theory elementary-number-theory prime-factorization
edited Aug 6 at 0:31
David G. Stork
7,7012929
asked Aug 6 at 0:27
Vladislav Kharlamov
572216
How can you factor $ 2^30 + 1 $? This task was supposed to be at one interview, there is an assumption that there should be a simple solution.
number-theory elementary-number-theory prime-factorization
edited Aug 6 at 0:31
David G. Stork
7,7012929
asked Aug 6 at 0:27
Vladislav Kharlamov
572216
edited Aug 6 at 0:31
David G. Stork
7,7012929
edited Aug 6 at 0:31
David G. Stork
7,7012929
edited Aug 6 at 0:31
David G. Stork
7,7012929
7,7012929
asked Aug 6 at 0:27
Vladislav Kharlamov
572216
asked Aug 6 at 0:27
Vladislav Kharlamov
572216
asked Aug 6 at 0:27
Vladislav Kharlamov
572216
572216
add a comment |Â
add a comment |Â
5 Answers
5
active
oldest
votes
up vote
8
down vote
I would note it is a sum of cubes and fifth powers, so $2^10+1=1025$ and $2^6+1=65$ are both factors. In terms of primes that gives us $5^2cdot 13 cdot 41$ as factors. At this point in an interview (depending on the position) I would declare success and move on. Getting the remaining $80581$ would take a bunch of hand calculation and finding $61cdot 1321$ doesn't seem reasonable either.
answered Aug 6 at 0:59
Ross Millikan
276k21187352
1
$61equiv 5 bmod 8$ so $(2|61)equiv 2^30equiv -1bmod 61$.
– Oscar Lanzi
Aug 6 at 1:44
add a comment |Â
up vote
8
down vote
Observe that $$x^k+1=fracx^2k-1x^k-1=fracprod_dmid 2kPhi_d(x)prod_dmid kPhi_d(x)=prod_dmid 2k, dnmid kPhi_d(x)$$ With $Phi_n(x)$ being the $n^textth$ cyclotomic polynomial. It follows that $$2^30+1=Phi_4(2)Phi_12(2)Phi_20(2)Phi_60(2)$$
With the individual factors computed as $$Phi_4(2)=2^2+1=5$$ $$Phi_12(2)=2^4-2^2+1=13$$ $$Phi_20(2)=2^8-2^6+2^2-2^2+1=5times 41$$ $$Phi_60(2)=2^16+2^14-2^10-2^8-2^6+2^2+1=61times 1321$$
Giving an overall factorization of $boxed2^30+1=5^2times 13times 41times 61times 1321$
answered Aug 6 at 1:47
Rafay A.
1165
This is very elegant.
– Lubin
Aug 6 at 1:58
1
Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :)
– Rafay A.
Aug 6 at 2:01
Again, computing $Phi_60(2) = 61 times 1321$ is not really something to do in an interview.
– Robert Israel
Aug 6 at 7:26
Perhaps they wanted to see the way to a solution, not the solution itself.
– Vladislav Kharlamov
Aug 6 at 11:43
1
@RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $Phi_60(2)$, it is enough to check the primes $equiv 1pmod60$. Since the order of $2$ in $mathbbZ/(61mathbbZ)^*$ is what it is, $61$ is a prime divisor of $Phi_60(2)$ and the problem boils down to checking that $1321$ is a prime".
– Jack D'Aurizio♦
Aug 6 at 16:45
 |Â
show 2 more comments
up vote
3
down vote
Hint: $a^k+1$ is divisible by $a+1$ if $k$ is odd.
edited Aug 6 at 1:08
peterh
2,14531631
answered Aug 6 at 0:29
Robert Israel
304k22201443
Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 times 13 times 41 times 61 times 1321 $. (Doesn't seem so simple that it could be done in an interview session...)
– David G. Stork
Aug 6 at 0:37
add a comment |Â
up vote
1
down vote
Firstly, in an interview there is often a difference between showing that there is a simple solution (existence) and outlining the approach, versus actually finding the solution.
That is, it might suffice to outline a standard prime factorising algorithm and show that it could be computed in trivial time.
One of the simplest classic approaches is that to factor $x$, you only need to test the primes that are less than $sqrtx$. If $x=2^30+1$, then $sqrtx+1 simeq 32768$. There are less than 3000 primes that satisfy this constraint, so it is very feasible on any computing platform.
Once each prime factor was found, one would divide that factor out, and
then only need to search for primes up to an even smaller upper bound.
Thus after the finding that 5 is a prime, one need only search for other prime factors less than 14654.
Thus, you have an algorithm that would find all the factors of $2^30+1$ in ascending order.
That is, $2^30+1 = 5 times 5 times 13 times 41 times 61 times 1321$.
The key to nearly any sensible prime factorization approach is to efficiently find the first factor. Thus, in some ways it could be said that factoring $2^30+1$ is easy because it has lots of prime factors, and most of them are very small. (Contrast this to encryption are based on numbers that are very hard to factor, because they typically one have 2 factors and each of them are very very large.)
Anyway, as @Robert indicated, the key to solving this directly is to realise that if $k$ is odd, then $x^k+1$ can be elegantly factorised, as $(x+1)$ is a factor.
For example,
$$x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1)$$
Note that $z^30+1 = (z^2)^15+1$ and so $z^2+1 $ is a factor.
Letting $z=1$ shows that 5 is a factor of $2^30+1$.
Similarly, you could use the well-known sum of cubes factorisation.
$x^3+1 = (x+1)(x^2-x+1)$, to show that
$$2^30+1 = (2^10+1)(2^20-2^10+1) = 1025 times 1047553$$
and continue from there.
answered Aug 6 at 1:19
Martin Roberts
1,189318
Your early complete factorization is missing $61$
– Ross Millikan
Aug 6 at 1:59
add a comment |Â
up vote
0
down vote
Yet another easy observation: since $4X^4+1=(2X^2+2X+1)(2X^2-2X+1)$, we get $4cdot2^28+1=(2cdot2^14+2cdot2^7+1)(2cdot2^14-2cdot2^7+1)$.
answered Aug 6 at 1:52
Lubin
41k34184
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
I would note it is a sum of cubes and fifth powers, so $2^10+1=1025$ and $2^6+1=65$ are both factors. In terms of primes that gives us $5^2cdot 13 cdot 41$ as factors. At this point in an interview (depending on the position) I would declare success and move on. Getting the remaining $80581$ would take a bunch of hand calculation and finding $61cdot 1321$ doesn't seem reasonable either.
answered Aug 6 at 0:59
Ross Millikan
276k21187352
1
$61equiv 5 bmod 8$ so $(2|61)equiv 2^30equiv -1bmod 61$.
– Oscar Lanzi
Aug 6 at 1:44
add a comment |Â
up vote
8
down vote
I would note it is a sum of cubes and fifth powers, so $2^10+1=1025$ and $2^6+1=65$ are both factors. In terms of primes that gives us $5^2cdot 13 cdot 41$ as factors. At this point in an interview (depending on the position) I would declare success and move on. Getting the remaining $80581$ would take a bunch of hand calculation and finding $61cdot 1321$ doesn't seem reasonable either.
answered Aug 6 at 0:59
Ross Millikan
276k21187352
1
$61equiv 5 bmod 8$ so $(2|61)equiv 2^30equiv -1bmod 61$.
– Oscar Lanzi
Aug 6 at 1:44
add a comment |Â
up vote
8
down vote
up vote
8
down vote
I would note it is a sum of cubes and fifth powers, so $2^10+1=1025$ and $2^6+1=65$ are both factors. In terms of primes that gives us $5^2cdot 13 cdot 41$ as factors. At this point in an interview (depending on the position) I would declare success and move on. Getting the remaining $80581$ would take a bunch of hand calculation and finding $61cdot 1321$ doesn't seem reasonable either.
answered Aug 6 at 0:59
Ross Millikan
276k21187352
I would note it is a sum of cubes and fifth powers, so $2^10+1=1025$ and $2^6+1=65$ are both factors. In terms of primes that gives us $5^2cdot 13 cdot 41$ as factors. At this point in an interview (depending on the position) I would declare success and move on. Getting the remaining $80581$ would take a bunch of hand calculation and finding $61cdot 1321$ doesn't seem reasonable either.
answered Aug 6 at 0:59
Ross Millikan
276k21187352
edited Aug 6 at 1:58
answered Aug 6 at 0:59
Ross Millikan
276k21187352
answered Aug 6 at 0:59
Ross Millikan
276k21187352
answered Aug 6 at 0:59
Ross Millikan
276k21187352
276k21187352
1
$61equiv 5 bmod 8$ so $(2|61)equiv 2^30equiv -1bmod 61$.
– Oscar Lanzi
Aug 6 at 1:44
add a comment |Â
1
$61equiv 5 bmod 8$ so $(2|61)equiv 2^30equiv -1bmod 61$.
– Oscar Lanzi
Aug 6 at 1:44
1
1
$61equiv 5 bmod 8$ so $(2|61)equiv 2^30equiv -1bmod 61$.
– Oscar Lanzi
Aug 6 at 1:44
$61equiv 5 bmod 8$ so $(2|61)equiv 2^30equiv -1bmod 61$.
– Oscar Lanzi
Aug 6 at 1:44
add a comment |Â
up vote
8
down vote
Observe that $$x^k+1=fracx^2k-1x^k-1=fracprod_dmid 2kPhi_d(x)prod_dmid kPhi_d(x)=prod_dmid 2k, dnmid kPhi_d(x)$$ With $Phi_n(x)$ being the $n^textth$ cyclotomic polynomial. It follows that $$2^30+1=Phi_4(2)Phi_12(2)Phi_20(2)Phi_60(2)$$
With the individual factors computed as $$Phi_4(2)=2^2+1=5$$ $$Phi_12(2)=2^4-2^2+1=13$$ $$Phi_20(2)=2^8-2^6+2^2-2^2+1=5times 41$$ $$Phi_60(2)=2^16+2^14-2^10-2^8-2^6+2^2+1=61times 1321$$
Giving an overall factorization of $boxed2^30+1=5^2times 13times 41times 61times 1321$
answered Aug 6 at 1:47
Rafay A.
1165
This is very elegant.
– Lubin
Aug 6 at 1:58
1
Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :)
– Rafay A.
Aug 6 at 2:01
Again, computing $Phi_60(2) = 61 times 1321$ is not really something to do in an interview.
– Robert Israel
Aug 6 at 7:26
Perhaps they wanted to see the way to a solution, not the solution itself.
– Vladislav Kharlamov
Aug 6 at 11:43
1
@RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $Phi_60(2)$, it is enough to check the primes $equiv 1pmod60$. Since the order of $2$ in $mathbbZ/(61mathbbZ)^*$ is what it is, $61$ is a prime divisor of $Phi_60(2)$ and the problem boils down to checking that $1321$ is a prime".
– Jack D'Aurizio♦
Aug 6 at 16:45
 |Â
show 2 more comments
up vote
8
down vote
Observe that $$x^k+1=fracx^2k-1x^k-1=fracprod_dmid 2kPhi_d(x)prod_dmid kPhi_d(x)=prod_dmid 2k, dnmid kPhi_d(x)$$ With $Phi_n(x)$ being the $n^textth$ cyclotomic polynomial. It follows that $$2^30+1=Phi_4(2)Phi_12(2)Phi_20(2)Phi_60(2)$$
With the individual factors computed as $$Phi_4(2)=2^2+1=5$$ $$Phi_12(2)=2^4-2^2+1=13$$ $$Phi_20(2)=2^8-2^6+2^2-2^2+1=5times 41$$ $$Phi_60(2)=2^16+2^14-2^10-2^8-2^6+2^2+1=61times 1321$$
Giving an overall factorization of $boxed2^30+1=5^2times 13times 41times 61times 1321$
answered Aug 6 at 1:47
Rafay A.
1165
This is very elegant.
– Lubin
Aug 6 at 1:58
1
Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :)
– Rafay A.
Aug 6 at 2:01
Again, computing $Phi_60(2) = 61 times 1321$ is not really something to do in an interview.
– Robert Israel
Aug 6 at 7:26
Perhaps they wanted to see the way to a solution, not the solution itself.
– Vladislav Kharlamov
Aug 6 at 11:43
1
@RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $Phi_60(2)$, it is enough to check the primes $equiv 1pmod60$. Since the order of $2$ in $mathbbZ/(61mathbbZ)^*$ is what it is, $61$ is a prime divisor of $Phi_60(2)$ and the problem boils down to checking that $1321$ is a prime".
– Jack D'Aurizio♦
Aug 6 at 16:45
 |Â
show 2 more comments
up vote
8
down vote
up vote
8
down vote
Observe that $$x^k+1=fracx^2k-1x^k-1=fracprod_dmid 2kPhi_d(x)prod_dmid kPhi_d(x)=prod_dmid 2k, dnmid kPhi_d(x)$$ With $Phi_n(x)$ being the $n^textth$ cyclotomic polynomial. It follows that $$2^30+1=Phi_4(2)Phi_12(2)Phi_20(2)Phi_60(2)$$
With the individual factors computed as $$Phi_4(2)=2^2+1=5$$ $$Phi_12(2)=2^4-2^2+1=13$$ $$Phi_20(2)=2^8-2^6+2^2-2^2+1=5times 41$$ $$Phi_60(2)=2^16+2^14-2^10-2^8-2^6+2^2+1=61times 1321$$
Giving an overall factorization of $boxed2^30+1=5^2times 13times 41times 61times 1321$
answered Aug 6 at 1:47
Rafay A.
1165
Observe that $$x^k+1=fracx^2k-1x^k-1=fracprod_dmid 2kPhi_d(x)prod_dmid kPhi_d(x)=prod_dmid 2k, dnmid kPhi_d(x)$$ With $Phi_n(x)$ being the $n^textth$ cyclotomic polynomial. It follows that $$2^30+1=Phi_4(2)Phi_12(2)Phi_20(2)Phi_60(2)$$
With the individual factors computed as $$Phi_4(2)=2^2+1=5$$ $$Phi_12(2)=2^4-2^2+1=13$$ $$Phi_20(2)=2^8-2^6+2^2-2^2+1=5times 41$$ $$Phi_60(2)=2^16+2^14-2^10-2^8-2^6+2^2+1=61times 1321$$
Giving an overall factorization of $boxed2^30+1=5^2times 13times 41times 61times 1321$
answered Aug 6 at 1:47
Rafay A.
1165
edited Aug 6 at 2:02
answered Aug 6 at 1:47
Rafay A.
1165
answered Aug 6 at 1:47
Rafay A.
1165
answered Aug 6 at 1:47
Rafay A.
1165
1165
This is very elegant.
– Lubin
Aug 6 at 1:58
1
Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :)
– Rafay A.
Aug 6 at 2:01
Again, computing $Phi_60(2) = 61 times 1321$ is not really something to do in an interview.
– Robert Israel
Aug 6 at 7:26
Perhaps they wanted to see the way to a solution, not the solution itself.
– Vladislav Kharlamov
Aug 6 at 11:43
1
@RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $Phi_60(2)$, it is enough to check the primes $equiv 1pmod60$. Since the order of $2$ in $mathbbZ/(61mathbbZ)^*$ is what it is, $61$ is a prime divisor of $Phi_60(2)$ and the problem boils down to checking that $1321$ is a prime".
– Jack D'Aurizio♦
Aug 6 at 16:45
 |Â
show 2 more comments
This is very elegant.
– Lubin
Aug 6 at 1:58
1
Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :)
– Rafay A.
Aug 6 at 2:01
Again, computing $Phi_60(2) = 61 times 1321$ is not really something to do in an interview.
– Robert Israel
Aug 6 at 7:26
Perhaps they wanted to see the way to a solution, not the solution itself.
– Vladislav Kharlamov
Aug 6 at 11:43
1
@RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $Phi_60(2)$, it is enough to check the primes $equiv 1pmod60$. Since the order of $2$ in $mathbbZ/(61mathbbZ)^*$ is what it is, $61$ is a prime divisor of $Phi_60(2)$ and the problem boils down to checking that $1321$ is a prime".
– Jack D'Aurizio♦
Aug 6 at 16:45
This is very elegant.
– Lubin
Aug 6 at 1:58
This is very elegant.
– Lubin
Aug 6 at 1:58
1
1
Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :)
– Rafay A.
Aug 6 at 2:01
Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :)
– Rafay A.
Aug 6 at 2:01
Again, computing $Phi_60(2) = 61 times 1321$ is not really something to do in an interview.
– Robert Israel
Aug 6 at 7:26
Again, computing $Phi_60(2) = 61 times 1321$ is not really something to do in an interview.
– Robert Israel
Aug 6 at 7:26
Perhaps they wanted to see the way to a solution, not the solution itself.
– Vladislav Kharlamov
Aug 6 at 11:43
Perhaps they wanted to see the way to a solution, not the solution itself.
– Vladislav Kharlamov
Aug 6 at 11:43
1
1
@RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $Phi_60(2)$, it is enough to check the primes $equiv 1pmod60$. Since the order of $2$ in $mathbbZ/(61mathbbZ)^*$ is what it is, $61$ is a prime divisor of $Phi_60(2)$ and the problem boils down to checking that $1321$ is a prime".
– Jack D'Aurizio♦
Aug 6 at 16:45
@RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $Phi_60(2)$, it is enough to check the primes $equiv 1pmod60$. Since the order of $2$ in $mathbbZ/(61mathbbZ)^*$ is what it is, $61$ is a prime divisor of $Phi_60(2)$ and the problem boils down to checking that $1321$ is a prime".
– Jack D'Aurizio♦
Aug 6 at 16:45
 |Â
show 2 more comments
up vote
3
down vote
Hint: $a^k+1$ is divisible by $a+1$ if $k$ is odd.
edited Aug 6 at 1:08
peterh
2,14531631
answered Aug 6 at 0:29
Robert Israel
304k22201443
Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 times 13 times 41 times 61 times 1321 $. (Doesn't seem so simple that it could be done in an interview session...)
– David G. Stork
Aug 6 at 0:37
add a comment |Â
up vote
3
down vote
Hint: $a^k+1$ is divisible by $a+1$ if $k$ is odd.
edited Aug 6 at 1:08
peterh
2,14531631
answered Aug 6 at 0:29
Robert Israel
304k22201443
Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 times 13 times 41 times 61 times 1321 $. (Doesn't seem so simple that it could be done in an interview session...)
– David G. Stork
Aug 6 at 0:37
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Hint: $a^k+1$ is divisible by $a+1$ if $k$ is odd.
edited Aug 6 at 1:08
peterh
2,14531631
answered Aug 6 at 0:29
Robert Israel
304k22201443
Hint: $a^k+1$ is divisible by $a+1$ if $k$ is odd.
edited Aug 6 at 1:08
peterh
2,14531631
answered Aug 6 at 0:29
Robert Israel
304k22201443
edited Aug 6 at 1:08
peterh
2,14531631
edited Aug 6 at 1:08
peterh
2,14531631
edited Aug 6 at 1:08
peterh
2,14531631
2,14531631
answered Aug 6 at 0:29
Robert Israel
304k22201443
answered Aug 6 at 0:29
Robert Israel
304k22201443
answered Aug 6 at 0:29
Robert Israel
304k22201443
304k22201443
Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 times 13 times 41 times 61 times 1321 $. (Doesn't seem so simple that it could be done in an interview session...)
– David G. Stork
Aug 6 at 0:37
add a comment |Â
Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 times 13 times 41 times 61 times 1321 $. (Doesn't seem so simple that it could be done in an interview session...)
– David G. Stork
Aug 6 at 0:37
Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 times 13 times 41 times 61 times 1321 $. (Doesn't seem so simple that it could be done in an interview session...)
– David G. Stork
Aug 6 at 0:37
Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 times 13 times 41 times 61 times 1321 $. (Doesn't seem so simple that it could be done in an interview session...)
– David G. Stork
Aug 6 at 0:37
add a comment |Â
up vote
1
down vote
Firstly, in an interview there is often a difference between showing that there is a simple solution (existence) and outlining the approach, versus actually finding the solution.
That is, it might suffice to outline a standard prime factorising algorithm and show that it could be computed in trivial time.
One of the simplest classic approaches is that to factor $x$, you only need to test the primes that are less than $sqrtx$. If $x=2^30+1$, then $sqrtx+1 simeq 32768$. There are less than 3000 primes that satisfy this constraint, so it is very feasible on any computing platform.
Once each prime factor was found, one would divide that factor out, and
then only need to search for primes up to an even smaller upper bound.
Thus after the finding that 5 is a prime, one need only search for other prime factors less than 14654.
Thus, you have an algorithm that would find all the factors of $2^30+1$ in ascending order.
That is, $2^30+1 = 5 times 5 times 13 times 41 times 61 times 1321$.
The key to nearly any sensible prime factorization approach is to efficiently find the first factor. Thus, in some ways it could be said that factoring $2^30+1$ is easy because it has lots of prime factors, and most of them are very small. (Contrast this to encryption are based on numbers that are very hard to factor, because they typically one have 2 factors and each of them are very very large.)
Anyway, as @Robert indicated, the key to solving this directly is to realise that if $k$ is odd, then $x^k+1$ can be elegantly factorised, as $(x+1)$ is a factor.
For example,
$$x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1)$$
Note that $z^30+1 = (z^2)^15+1$ and so $z^2+1 $ is a factor.
Letting $z=1$ shows that 5 is a factor of $2^30+1$.
Similarly, you could use the well-known sum of cubes factorisation.
$x^3+1 = (x+1)(x^2-x+1)$, to show that
$$2^30+1 = (2^10+1)(2^20-2^10+1) = 1025 times 1047553$$
and continue from there.
answered Aug 6 at 1:19
Martin Roberts
1,189318
Your early complete factorization is missing $61$
– Ross Millikan
Aug 6 at 1:59
add a comment |Â
up vote
1
down vote
Firstly, in an interview there is often a difference between showing that there is a simple solution (existence) and outlining the approach, versus actually finding the solution.
That is, it might suffice to outline a standard prime factorising algorithm and show that it could be computed in trivial time.
One of the simplest classic approaches is that to factor $x$, you only need to test the primes that are less than $sqrtx$. If $x=2^30+1$, then $sqrtx+1 simeq 32768$. There are less than 3000 primes that satisfy this constraint, so it is very feasible on any computing platform.
Once each prime factor was found, one would divide that factor out, and
then only need to search for primes up to an even smaller upper bound.
Thus after the finding that 5 is a prime, one need only search for other prime factors less than 14654.
Thus, you have an algorithm that would find all the factors of $2^30+1$ in ascending order.
That is, $2^30+1 = 5 times 5 times 13 times 41 times 61 times 1321$.
The key to nearly any sensible prime factorization approach is to efficiently find the first factor. Thus, in some ways it could be said that factoring $2^30+1$ is easy because it has lots of prime factors, and most of them are very small. (Contrast this to encryption are based on numbers that are very hard to factor, because they typically one have 2 factors and each of them are very very large.)
Anyway, as @Robert indicated, the key to solving this directly is to realise that if $k$ is odd, then $x^k+1$ can be elegantly factorised, as $(x+1)$ is a factor.
For example,
$$x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1)$$
Note that $z^30+1 = (z^2)^15+1$ and so $z^2+1 $ is a factor.
Letting $z=1$ shows that 5 is a factor of $2^30+1$.
Similarly, you could use the well-known sum of cubes factorisation.
$x^3+1 = (x+1)(x^2-x+1)$, to show that
$$2^30+1 = (2^10+1)(2^20-2^10+1) = 1025 times 1047553$$
and continue from there.
answered Aug 6 at 1:19
Martin Roberts
1,189318
Your early complete factorization is missing $61$
– Ross Millikan
Aug 6 at 1:59
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Firstly, in an interview there is often a difference between showing that there is a simple solution (existence) and outlining the approach, versus actually finding the solution.
That is, it might suffice to outline a standard prime factorising algorithm and show that it could be computed in trivial time.
One of the simplest classic approaches is that to factor $x$, you only need to test the primes that are less than $sqrtx$. If $x=2^30+1$, then $sqrtx+1 simeq 32768$. There are less than 3000 primes that satisfy this constraint, so it is very feasible on any computing platform.
Once each prime factor was found, one would divide that factor out, and
then only need to search for primes up to an even smaller upper bound.
Thus after the finding that 5 is a prime, one need only search for other prime factors less than 14654.
Thus, you have an algorithm that would find all the factors of $2^30+1$ in ascending order.
That is, $2^30+1 = 5 times 5 times 13 times 41 times 61 times 1321$.
The key to nearly any sensible prime factorization approach is to efficiently find the first factor. Thus, in some ways it could be said that factoring $2^30+1$ is easy because it has lots of prime factors, and most of them are very small. (Contrast this to encryption are based on numbers that are very hard to factor, because they typically one have 2 factors and each of them are very very large.)
Anyway, as @Robert indicated, the key to solving this directly is to realise that if $k$ is odd, then $x^k+1$ can be elegantly factorised, as $(x+1)$ is a factor.
For example,
$$x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1)$$
Note that $z^30+1 = (z^2)^15+1$ and so $z^2+1 $ is a factor.
Letting $z=1$ shows that 5 is a factor of $2^30+1$.
Similarly, you could use the well-known sum of cubes factorisation.
$x^3+1 = (x+1)(x^2-x+1)$, to show that
$$2^30+1 = (2^10+1)(2^20-2^10+1) = 1025 times 1047553$$
and continue from there.
answered Aug 6 at 1:19
Martin Roberts
1,189318
Firstly, in an interview there is often a difference between showing that there is a simple solution (existence) and outlining the approach, versus actually finding the solution.
That is, it might suffice to outline a standard prime factorising algorithm and show that it could be computed in trivial time.
One of the simplest classic approaches is that to factor $x$, you only need to test the primes that are less than $sqrtx$. If $x=2^30+1$, then $sqrtx+1 simeq 32768$. There are less than 3000 primes that satisfy this constraint, so it is very feasible on any computing platform.
Once each prime factor was found, one would divide that factor out, and
then only need to search for primes up to an even smaller upper bound.
Thus after the finding that 5 is a prime, one need only search for other prime factors less than 14654.
Thus, you have an algorithm that would find all the factors of $2^30+1$ in ascending order.
That is, $2^30+1 = 5 times 5 times 13 times 41 times 61 times 1321$.
The key to nearly any sensible prime factorization approach is to efficiently find the first factor. Thus, in some ways it could be said that factoring $2^30+1$ is easy because it has lots of prime factors, and most of them are very small. (Contrast this to encryption are based on numbers that are very hard to factor, because they typically one have 2 factors and each of them are very very large.)
Anyway, as @Robert indicated, the key to solving this directly is to realise that if $k$ is odd, then $x^k+1$ can be elegantly factorised, as $(x+1)$ is a factor.
For example,
$$x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1)$$
Note that $z^30+1 = (z^2)^15+1$ and so $z^2+1 $ is a factor.
Letting $z=1$ shows that 5 is a factor of $2^30+1$.
Similarly, you could use the well-known sum of cubes factorisation.
$x^3+1 = (x+1)(x^2-x+1)$, to show that
$$2^30+1 = (2^10+1)(2^20-2^10+1) = 1025 times 1047553$$
and continue from there.
answered Aug 6 at 1:19
Martin Roberts
1,189318
edited Aug 6 at 2:08
answered Aug 6 at 1:19
Martin Roberts
1,189318
answered Aug 6 at 1:19
Martin Roberts
1,189318
answered Aug 6 at 1:19
Martin Roberts
1,189318
1,189318
Your early complete factorization is missing $61$
– Ross Millikan
Aug 6 at 1:59
add a comment |Â
Your early complete factorization is missing $61$
– Ross Millikan
Aug 6 at 1:59
Your early complete factorization is missing $61$
– Ross Millikan
Aug 6 at 1:59
Your early complete factorization is missing $61$
– Ross Millikan
Aug 6 at 1:59
add a comment |Â
up vote
0
down vote
Yet another easy observation: since $4X^4+1=(2X^2+2X+1)(2X^2-2X+1)$, we get $4cdot2^28+1=(2cdot2^14+2cdot2^7+1)(2cdot2^14-2cdot2^7+1)$.
answered Aug 6 at 1:52
Lubin
41k34184
add a comment |Â
up vote
0
down vote
Yet another easy observation: since $4X^4+1=(2X^2+2X+1)(2X^2-2X+1)$, we get $4cdot2^28+1=(2cdot2^14+2cdot2^7+1)(2cdot2^14-2cdot2^7+1)$.
answered Aug 6 at 1:52
Lubin
41k34184
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Yet another easy observation: since $4X^4+1=(2X^2+2X+1)(2X^2-2X+1)$, we get $4cdot2^28+1=(2cdot2^14+2cdot2^7+1)(2cdot2^14-2cdot2^7+1)$.
answered Aug 6 at 1:52
Lubin
41k34184
Yet another easy observation: since $4X^4+1=(2X^2+2X+1)(2X^2-2X+1)$, we get $4cdot2^28+1=(2cdot2^14+2cdot2^7+1)(2cdot2^14-2cdot2^7+1)$.
answered Aug 6 at 1:52
Lubin
41k34184
answered Aug 6 at 1:52
Lubin
41k34184
answered Aug 6 at 1:52
Lubin
41k34184
answered Aug 6 at 1:52
Lubin
41k34184
41k34184
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873457%2fa-simple-method-of-factorization-2301%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password