2
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ Are you looking for the 'average' behavior of this function with respect to a multiple variables, or strict upper and lower bounds? $\endgroup$ – Ethan Jul 3 '13 at 8:08
  • $\begingroup$ @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. $\endgroup$ – fgrieu Jul 3 '13 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.