For Question 1, you can turn division by a known constant into multiplications + bitshifts using a library like `libdivide`[1]. Then, we could use the regular rejection sampling algorithm mentioned in the annotated code [2].
I'd be curious how the naive rejection sampling algorithm's performance compares to Lemire's algorithm's when both are updated to use libdivide...
[2] https://github.com/colmmacc/s2n/blob/7ad9240c8b9ade0cc3a403a...