Случайное число относительно простого к входу

Question

Как вычислительно вменяемый способ, учитывая натуральное число n, генерировать случайное число, относительно простое относительно n?

Я готов пожертвовать некоторой случайностью и охватить все возможности для скорости. То есть, если я только когда-либо достигну, возможно, 75% возможных (меньших) относительных простых чисел, это нормально.

Answer 1

«Я готов пожертвовать случайностью и охватить все возможности для скорости».Учитывая n, выберите n + 1.

Вам нужно быть более конкретным.

Answer 2

Вероятность того, что два случайных целых числа взаимно просты относительно друг друга, составляет 6 / pi ^ 2 (в пределе для большого N) или примерно 61%. Так что генерация и тестирование должны быть жизнеспособной стратегией - вычисление GCD о O (log n), и вы, вероятно, получить результат в 2 или 3 испытаниях.

Answer 3

простыми словами:

unsigned random_prime(unsigned n){
     unsigned r = rand(), t;
     while ((t = gcd(r, n)) > 1)
         r /= t;
     return r;
}