(Криптографические) задачи, решаемые за полиномиальное число арифметических шагов

9

В работе Ади Шамира [1] за 1979 г. он показывает, что факторинг можно выполнить за полиномиальное число арифметических шагов . Этот факт был вновь подтвержден и поэтому привлек мое внимание в недавней работе Borwein and Hobart [2] в контексте программ прямой линии связи (SLP).

Поскольку я был довольно удивлен, прочитав это, у меня возник следующий вопрос: существуют ли другие криптографические проблемы или, возможно, также другие соответствующие проблемы, которые могут быть решены за полиномиальное число шагов с помощью SLP и которые в настоящее время не известны как разрешимые эффективно на "нормальном" классическом компьютере?

[1] Ади Шамир, Факторинг чисел вO(logn)арифметические шаги . Письма обработки информации 8 (1979) с. 28–31

[2] Питер Борвейн, Джо Хобарт, «Исключительная сила деления в прямых программах» , Американский математический ежемесячный том. 119, № 7 (август ‒ сентябрь 2012 г.), с. 584-592

Etsch
источник
Что означает «разрешимый в полиномиальном числе арифметических шагов»? Лучшие алгоритмы факторинга, доступные в настоящее время, занимают субэкспоненциальное время (но суперполиномиальное). Я нигде не могу найти бумагу Шамира.
mikeazo
Я бы посоветовал опубликовать это на Crypto.SE, так как вы не получили много ответов здесь.
mikeazo
Есть соответствующая запись в блоге Липтона: rjlipton.wordpress.com/2012/10/16/… Эта модель вычислений является своего рода обманом, потому что вы разрешаете вычисления с произвольной длинной точностью. Я не знаю других проблем, связанных с криптографией, которые были решены в этой модели. Но модель настолько мощная, что стоит попробовать.
минар
@minar проблема мошенничества не с точностью aribtrary. обман здесь с операциями пола и потолка.
T ....

Ответы:

-2

Я также не читал статью, но в реферате, кажется, говорится, что требуется экспоненциальное число битовых операций.

Работа Чебышева о конгруэнциях и ее переформулировке в алгоритме AKS показывает, что первичное поколение находится в P. Поэтому пробное деление дает нетривиальные факторы. В этом случае для некоторого числа N можно ожидать плотность простых чисел 1 / ln (N).

Кроме того, вы можете взглянуть на докторскую диссертацию Тьюринга 1937 года по этому вопросу.

Фил
источник
3
Привет Фил. Добро пожаловать в историю. За короткое время вы публиковали ответы на многие вопросы, что здесь не обычно. Сообщения, которые действительно являются комментариями, а не ответами на вопрос, не должны публиковаться как ответы. Возможно, вы захотите осмотреться и проверить другие вопросы, а также то, как все работает, прежде чем публиковать дополнительные ответы.
Каве