Timeline for Generating random smooth numbers (or, "What do random smooth numbers look like?")
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2010 at 7:53 | comment | added | Charles | @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. | |
| Sep 29, 2010 at 7:17 | comment | added | Harrison Brown | 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... | |
| Sep 29, 2010 at 7:10 | history | asked | Charles | CC BY-SA 2.5 |