# Odds that a random $m$-bit integer has an at-least $n$-bit divisor with all its factors at most $k$ bits

Related to this cryptographic question, I'd like a rough numerical estimate of the odds that a random $m$-bit integer has an at-least $n$-bit divisor with all its factors at most $k$ bits. I'm interested in $m\approx 3n$, $n\approx 1024$, $k\approx 200$ (so that at-most $k$-bit factors of the $m$-bit integer can be found in practice).

I have the intuition that the odds I am interested in are almost independent of $m$, given my parameters. Clearly, theses odds are low: a large random integer is expected to have about $\log k$ prime factors less than $k$ bits, building-up to a divisor of about $k$ bits, much less than my $n$. However there is a large variation on that average behavior.

If we note $Θ(x,y,z)$ the number of integers at most $x$ with a $y$-smooth divisor greater than $z$, as studied in:
W. D. Banks and I. E. Shparlinski, Integers with a large smooth divisor
G. Tenenbaum, Integers with a large friable component
what I need is a formula leading to a simple numerical approximation of $${Θ(2^m, 2^k, 2^{n-1})-Θ(2^{m-1}, 2^k, 2^{n-1})}\over{2^{m-1}}$$ (ignoring adjustments for exact vs. strict inequalities, in the interest of legibility).

• Are you looking for the 'average' behavior of this function with respect to a multiple variables, or strict upper and lower bounds? – Ethan Jul 3 '13 at 8:08
• @Ethan: average behavior, or even an heuristic approximation of that (based on approximation of the density of primes), would be fine. Notice that my $m,n,k$ are number of bits, not the integers themselves as are the $m,n,k$ in your second comment. – fgrieu Jul 3 '13 at 9:29