Kalai's algorithm can be used to uniformly generate a random integer $x$ in the range $[1,N]$ with its prime factorization $f=\{p_1,p_2,...,p_k\}$. More info about it here (Page 1).
I'm trying to modify it to generate numbers in a specific range $[2^y,2^{y+1}-1]$. For example $Kalai(5)$ would work on range $[2^4,2^5-1]$ and might return a random integer $x=15 \in [16,31]$ with its factorization $f=\{3,5\}$.
Since the original version only works with range $[1,K]$, I was thinking about using it to generate $(x,f)$ in $[1,2^x]$ then mapping it back to the required range, but this will ruin the obtained factorization.
Is there another way to modify the algorithm to make it work on ranges of the mentioned form?
Thanks!
Half the integers in the range $[1,2^{y+1}-1]$ are in the desired range $[2^y, 2^{y+1}-1]$. So you can simply generate a random factored integer in the first range, and then reject and start over if it's not in the second, adding only a constant factor to the expected running time.