How do I solve/factor a^8+b^8=c

Sep 2011
2
0
For a crypto contest (no prizes) I have a very large integer that is the sum of two integers to the 8th power and I need to find the original factors. I've written a brute-force program but I think that will take a very long time to run. I'm looking at FFM to see if I can modify it. I also wonder if lattices may be the solution, or an LLL could help me find the answer. However, I know nothing at all about lattices, nor even how to set them up in any math software and perform an LLL, though I did find some notes online and have been trying to learn.

I know there is a simple solution as other solved this quickly, but I lack the background in mathematics and was hoping for some pointers. Thanks in advance.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Do you know a and b, or just that they exist? How large is a^8 + b^8? What's FFM?
 
Sep 2011
2
0
The number is 161 digits long, we know it factors to two integers a^8 + b^8 = 17223507887602526420151651536619310810581211968884712600471622453277672311605232817186376770608196483963283605920702226380449555021499188148868557483176337161377

I was thinking Fermat's Factoring Method might help, but now I'm not so sure.

Factoring is the first stage of the problem. My friend's hint is "you can solve it within 5 minutes on maple if you turn the problem into something easier." Still mulling that over.

But he is a number theorist. I am a hobbiest.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
That number has small prime factors. It's pretty easy to split with ECM or SQFOF/rho.
 
Apr 2011
352
0
Recife, BR
Here I got:

2526 420151 651536 619310 810581 211968 884712 600471 622453 277672 311605 232817 186376 770608 196483 963283 605920 702226 380449 555021 499188 148868 557483 176337 161377 = 3 ^ 2 x 13 x 337 x 359 x 673 x 16 948397 x 403 182919 587991 x 181344 360239 846269 x 214 015630 961743 736716 146375 230130 398658 104307 856285 898843 805259 929845 167429 314678 811961 029034 455093

using:

http://www.alpertron.com.ar/ECM.HTM
 
Nov 2019
4
1
Buenos Aires, Argentina
Using my Web application Integer factorization calculator , we get n=p^2 + q^2
p = 99115805326372179547892799368633881951938463313893857066732046242690539066423761
q = 86020724375624846877311592006144228462254725647739682846197148720765370512118016

From the original request, n=a^8 + b^8, so a = p^(1/4) and b = q^(1/4)

Thus we get:

a = 99778214590404624163
b = 96305429813873971636
 

skipjack

Forum Staff
Dec 2006
21,205
2,337
The number factorized is only the last 148 digits of the original 161-digit number. The values of a and b are correct for the original 161-digit number.