Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What is a good method for generating random b-bit, S-smooth numbers?

For S large and b not too large, it may be feasible to generate random numbers and test if they are smooth enough. If S is too small, the S-smooth numbers are too sparse; if b is too large, deciding if a number is S-smooth is too difficult.

When the above is infeasible (say, b = 10 000, S = $10^{100}$) it seems that generating smooth numbers requires understanding their properties. Consider generating random semiprimes near n: take s = 1/2 + 1/3 + 1/5 + ... + $1/\sqrt n$, then choose a prime $p\le\sqrt n$ with probability $s/p$ and finally choose a random prime $q$ near $n/p$, yielding $pq$ as the semiprime.

Is there a similar procedure for smooth numbers?

Alternate, non-algorithmic approach

A random integer* has about $\log k$ prime factors between $m$ and $m^k$ (in a Poisson sense). What can be said about the distribution of prime factors of an S-smooth integer instead, with $m^k < S$? (Presumably, unlike in the first case, $b$ matters.)

Similarly, for small primes p, what is the distribution of the p-adic valuation of random S-smooth b-bit numbers?

* "Random integer" is, of course, meaningless. But in this context I'm looking mod a fixed set of primes, and in that context it's well-defined. (In Pari terminology, random intmods are OK.)

share|improve this question
    
I'm confused here -- why can't you just do the following? Take a = 1; as long as a has fewer than b bits, multiply it by a random prime number less than S. That'll get you an S-smooth number with about b bits; if you want exactly b bits, I suspect that it terminates with a smooth number with exactly b bits with probability that drops to 0 fairly slowly in S, so it should be feasible too... –  Harrison Brown Sep 29 '10 at 7:17
1  
@Harrison: That wouldn't give me numbers with distribution similar to the uniform distribution on S-smooth numbers. If I chose primes p with weight 1/p it might work -- but I'm not sure that this would have the same distribution overall. I've heard, anecdotally, that for sufficiently small S the numbers look very nearly like random numbers times high powers of two... this may be incorrect, but I'd like confirmation. –  Charles Sep 29 '10 at 7:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.