Engineering / Mathematics — Probabilistic Algorithms
Generating a Random Factored Number
Producing a uniformly random integer together with its complete factorisation, in polynomial time, without factoring.
Executive summary
Generating a random integer and then factoring it is infeasible. Generating a random integer together with its factorisation is easy, and the algorithm that does so is one of the more elegant results in the subject.
The construction builds a candidate from a random non-increasing sequence and applies an acceptance rule that corrects the distribution to uniform.
Learning objectives
- State the problem and why it is not equivalent to factoring.
- Describe the construction and its acceptance rule.
- Identify where such an object is needed.
01The problem
Random factored number
Produce a pair (n, F) where n is uniform on {1, ..., N} and F is the complete prime factorisation of n, in expected polynomial time.
02The construction
Random factored number
bound Nuniform n in {1,...,N} with its full factorisation- Generate a random non-increasing sequence s₁ ≥ s₂ ≥ ... ≥ 1 bounded by N.
- Retain the terms that are prime, testing each with a primality test.
- Form n as the product of the retained primes.
- If n > N, reject and restart.
- Accept n with probability n/N; otherwise restart.
- Return n together with the list of retained primes.
expected polynomial in len(N)The two rejection steps do different jobs. The first discards products that overshoot the range. The second corrects the distribution: without it, smaller integers would be over-represented, and accepting with probability proportional to n exactly compensates.
03Where it is needed
Complexity-theoretic reductions
Some proofs require sampling from a distribution of integers with known structure, which is impossible if the factorisation is inaccessible.
Average-case analysis
Studying the behaviour of algorithms on random integers with known factorisation, without the circularity of needing to factor first.
Testing factoring implementations
Generating test cases with known answers at arbitrary sizes, which cannot be done by factoring random numbers.
The last application is the most practical. Validating a factoring implementation needs inputs whose correct output is known, and generating those by factoring is self-defeating. This algorithm supplies them at any size.
A cryptographic caution: the output is a random integer with known factorisation, which is precisely what an RSA modulus must not be. The algorithm is a tool for analysis and testing, not for key generation.
04Frequently asked questions
Why does accepting with probability n/N give uniformity?
Because the construction produces each n with probability proportional to 1/n before the acceptance step. Multiplying by n/N flattens the distribution, and the constant is absorbed by the restart.
Is the expected running time genuinely polynomial?
Yes, though the analysis is delicate — both rejection steps must be shown to succeed with sufficient probability, and the expected sequence length must be bounded. The result is polynomial in the length of N.
Does this threaten RSA?
No. It produces a random modulus whose factorisation the generator already knows, which is useless to an attacker facing a modulus generated by someone else. It says nothing about factoring a given number.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 170-174.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.