Factorizable huge semiprime

402 Views Asked by At

I'm trying to understand how the number decimal

The correct decimal number is:

163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013

or in hex:

0x00e8953849f11e932e9127af35e1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051f8eb7d0556e09ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffbad55

Could be factorized.

This is supposed to be a semiprime and although the sequence of "0"s and "F"s seems to help this problem to be solved, I cannot figure out how can i do it.

Edit 1: I have pasted the wrong number. Now this is the correct one.

Edit 2: This is supposed to be solvable

1

There are 1 best solutions below

3
On BEST ANSWER
163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013

is the product of

12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453

and

12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521

and according to WolframAlpha both of these factors are prime.

I used Fermat's factorization method which works very quickly for this number because the factors differ from $\sqrt{n}$ by only $534$.

The hex representation gave me a clue that this might work, can you see why?