Обычно генерация идёт так: генерируем случайно число заданного размера, проверяем его тестом Миллера-Рабина с кол-вом раундов ln(m), если число составное, то добавляем единицу и проверяем вновь полученное число, в противном случае алгоритм завершён, искомое число получено. Встаёт вопрос, а вдруг полученное число составное? Тест Миллера-Рабина с указанным выше числом раундов даёт надёжность в 4^(-ln(m)), а 100% гарантию на 1024 битное число вы не получите за приемлемое время. m — текущее число.