Нижние границы периода в целочисленной факторизации?

11

В 1975 году Миллер показал, как уменьшить факторизацию целого числа чтобы найти период функции такой, что f (x + r) = f (x) с некоторым случайно выбранным <N . Хорошо известно, что алгоритм Шора может эффективно найти r на квантовом компьютере, в то время как считается, что классическому компьютеру трудно найти r .Nrf(x)=axmodNf(x+r)=f(x)a<Nrr

Мой вопрос сейчас: есть ли известные нижние оценки для для случайного ? Есть ли какие-либо границы для если выбрано, как в RSA? Ясно, что должно быть как в противном случае можно просто вычислить на последовательных точках, чтобы вычислить классически. Достаточно ли было бы сломать RSA, если бы существовал классический алгоритм факторинга, который работает только при некотором предположении о распределении , например, или ?rNrN=pqrΩ(log(N))f(x)O(log(N))rrrΘ(N/log(N))rΘ(N)

В презентации Карла Померанса « Мультипликативный порядок mod n в среднем » приводятся доказательства того, что r равно O(N/log(N)) в среднем по всем N , но я не уверен, является ли классический алгоритм, который может учитывать N по предположению rO(N/log(N)) окончательно нарушит RSA. Может ли N быть неблагоприятно выбран, чтобы иметь rO(N)) или rO(N) ?

(Примечание: есть связанный вопрос по факторингу против факторинга RSA)

Мартин Шварц
источник

Ответы:

17

Если , период всегда будет делителем . Если вы выберете и для штрих, то, если вам не повезет, у нас будет . Я также считаю, что мы можем эффективно найти простые числа с , выбирая кандидатов случайным образом и проверяя их (это верно, если события, которые иN=pqrϕ(N)=lcm(p1,q1)p1=2pq1=2qp,qrpqN/4pp=2p+1ppпростые являются примерно независимыми; Я не знаю, было ли это доказано). Таким образом, благодаря тщательному выбору простых чисел RSA будет по-прежнему защищен от атак даже при наличии дополнительной гипотезы о простом факторинге.

Я подозреваю, что случайные числа или случайные крайне маловероятны, чтобы иметь , но у меня нет доказательства этого от руки. Гипотеза чрезвычайно сильна, и я не удивлюсь, если эффективный алгоритм факторинга уже известен для этого случая.NN=pqrO(N)rO(N)

Питер Шор
источник