[_alternator_]

> You might be able to come up with a more efficient algorithm.

Challenge accepted. Suppose we want to know the answer to 3 decimal places (so we'd match the headline). And suppose I allow my algorithm to be wrong one in a thousand times ("probably approximately correct").

Then sample some constant number C of random 64 bit integers. Run the following algorithm which separates each random sample into one of three classes: Y (has 32 but factors), N (does not have 32 bit factors), U (unknown).

Check if prime using probabilistic miller rabin. (Error prob goes to zero exponentially fast). If prime, return N. If it's not a prime, then run T steps of pollard rho to determine whether the number has 32 but factors; return Y,N, or U depending of the factors found up to step T.

The key observation is that T can be chosen to make the UNKNOWN class very small (with high probability), and so our estimate should rapidly converge to 17%Y, 83%N, ~0.001%U

For fixed error tolerance, this would run in roughly a constant number of iterations, independent of N.

[bonzini]

Even if you have 32-bit factors the number may not be the product of two 32-bit numbers. For example 2^62*3 cannot be split as either (2^32, 2^30*3) or (2^31, 2^31*3). In both cases one factor does not fit in 32 bits.

[_alternator_]

Ah, yes, this is true, but it's not really a counterexample, since this would show up in the N or U bucket. But I think the issue is that my sketch algorithm is, well, pretty sketchy.

Working on coding it up... it converges to 17±0.5%for N=64 bits in a javascript implementation relatively quickly, but for N=96, it really slows down as Pollard's Rho starts with large factors. This means my fast-and-loose assumption that "a constant number of iterations of Pollard Rho would work" isn't actually true!

[_alternator_]

Ok, chatting with Claude and I found a way to salvage the approach! (Also, it's apparently in the paper that's referenced in the post, kinda cool that my sketchy algorithm got halfway to the published result).

Basically, replace the Pollard Rho partial factorization with a method of Kalai [1] for generating random numbers _together with their prime factors_.

I'm able to run this at about 30 samples per second at 160bits, giving an estimate of ~14.1% of 160-bit numbers factoring into two 80-bit numbers.

[1]: https://link.springer.com/article/10.1007/s00145-003-0051-5

[svat]

I think by "have 32 bit factors" the GP actually means "has a factorization as a product of two 32-bit numbers", rather than the natural meaning that doesn't work, as you pointed out.