[_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