Finding the upper bound for a number's factors length

Question

Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be?

For example:

$X = 10000$

I want $3$ and $3$ (as in $100 \cdot 100$) not $4$ and $2$ (as in $1000 \cdot 10$). Is there a way to calculate these lengths without calculating the factors themselves? I need these lengths because I have found a way to factorise huge numbers very efficiently but my algorithm requires these lengths to calculate the factors..

Answer 1

I don't think there's a general way to find the length without also find the factors, but don't that stop you. If you have a "very efficient" algorithm to answer questions like

What are the two primes with 232 and 269 digits whose product is such-and-such?

then you can factor 500-digit semiprimes fast in general -- just run your algorithm 250 times in parallel, trying all the possible combinations of lengths the factors can have.

A 250-fold increase in running time is nothing compared to the gap between "very efficient" and the currently best known factoring algorithms, so you'll be famous either way.

Answer 2

As Henning Makholm said, there is no general way to find the size of the factors. Indeed, if it were possible to efficiently extract this information to an arbitrary base, it would be possible to reconstruct the factorization in at most a logarithmic number of queries, so this does not appear likely.

To address your claim of an efficient factoring algorithm given this information, I generated random primes with 300 and 317 digits, respectively, such that their product is this 2048-bit number:

21279219566254389308166752547567079894155956724663643608660601467894020997654033512063689142868924580279170320271764614879149713751942503658236686096505477139658747642151065213255234834719734092972960617101404366463757484189231718609007575411830503373062342932764298718391072364527123399519860588923934793023541272997882036513859823770256253927113052490646103353524325569726232043935667333299610202485174897340342883688686610744742445811839581892399399720031995216701440209212303269668588156416060110246881815214741950035093818290970782678137302765577041903045627809929443937883795428741882814884536260362427317965217

If you are able to factor this number, I would be happy to publicize your algorithm for you, providing testimony that the number was generated randomly and that I did not share its factorization. Of course, you may prefer to factor RSA-2048:

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

which is widely known to be generated properly, but the size of its factors is unknown. Probably it's either a 309-digit number times a 309-digit number, but it may be a 308-digit number times a 309- or 310-digit number or even something else.