How to Generate Factored Random Numbers

This paper presents an efficient method for generating a random integer with known factorization. When given a positive integer N, the algorithm produces the prime factorization of an integer x drawn uniformly from N / 2 < x N. The expected running time is that required for O(log N) prime tests on integers less than or equal to N. If there is a fast deterministic algorithm for primality testing, this is a polynomial-time process. The algorithm can also be implemented with randomized primality testing; in this case, the distribution of correctly factored outputs is uniform, and the possibility of an incorrectly factored output can in practice be disregarded.