В 1975 году Миллер показал, как уменьшить факторизацию целого числа чтобы найти период функции такой, что f (x + r) = f (x) с некоторым случайно выбранным <N . Хорошо известно, что алгоритм Шора может эффективно найти r на квантовом компьютере, в то время как считается, что классическому компьютеру трудно найти r .
Мой вопрос сейчас: есть ли известные нижние оценки для для случайного ? Есть ли какие-либо границы для если выбрано, как в RSA? Ясно, что должно быть как в противном случае можно просто вычислить на последовательных точках, чтобы вычислить классически. Достаточно ли было бы сломать RSA, если бы существовал классический алгоритм факторинга, который работает только при некотором предположении о распределении , например, или ?
В презентации Карла Померанса « Мультипликативный порядок mod в среднем » приводятся доказательства того, что равно в среднем по всем , но я не уверен, является ли классический алгоритм, который может учитывать по предположению окончательно нарушит RSA. Может ли быть неблагоприятно выбран, чтобы иметь или ?
(Примечание: есть связанный вопрос по факторингу против факторинга RSA)
источник