Хорошо известно, что модульное возведение в степень (основная часть операции RSA) является вычислительно дорогим, и, насколько я понимаю, метод модульного возведения в степень Монтгомери является предпочтительным методом. Модульное возведение в степень также заметно присутствует в алгоритме квантового факторинга, и это также дорого.
Итак: почему модульное возведение в степень Монтгомери явно не присутствует в текущих подробных подпрограммах для квантового факторинга?
Единственное, что я могу себе представить, это высокие издержки на кубит по какой-то неочевидной причине.
Запуск квантового «модульного возведения в степень» Монтгомери через Google Scholar не дает никаких полезных результатов. Мне известна работа Ван Метера и других авторов по квантовому сложению и модульному возведению в степень, но изучение их ссылок (я еще не читал эту работу) не показывает никаких признаков того, что методы Монтгомери рассматриваются там.
Единственное упоминание, которое я обнаружил для обсуждения этого вопроса, на японском языке, который, к сожалению, я не могу прочитать, хотя, очевидно, это из материалов конференции 2002 года. Машинный перевод приводит к добавлению самородков, которые указывают, что может быть что-то полезное. Тем не менее, я не могу найти никаких признаков того, что за этим следили, что заставляет меня думать, что идея была a) рассмотрена и затем b) отклонена.
Квантовая схема в выполнении арифметики Нобору Кунихиро
... В этом исследовании, но требует относительно большого кубита, мы предлагаем модульную схему возведения в степень времени квантовых вычислений. Редукция Монтгомери [8] и правобинарный метод [9] В сочетании они образуют схему Ru. Сокращение Монтгомери, m случайным образом выбирается как натуральное число, mod 2m с помощью операции, выполнить оставшуюся операцию If, mod n операций при устранении. Это приведет к сокращению времени вычислений ...
Применение 3.2 редукции Монтгомери Редукция Монтгомери [8] сформулирована следующим образом ... Этот алгоритм может возвращать правильные значения, что может быть легко подтверждено. MR (Y) он просит закон 2m Полиномы с 2m точками важны и требуют только деления на. Кроме того, сокращение Монтгомери, есть разные методы расчета .... В общем, сокращение Монтгомери не является функцией один-к-одному ...
... Предлагаемый метод использует правильный двоичный метод, Монтгомери Редуктон имеет особенность, которая принята. Чем обычный метод, характеризующийся небольшим компонентом схемы. ошибка кубита, которая требует больших ожиданий, может быть вычислена за меньшее вычислительное время Be. Будущее, схемы сокращения и управления Монтгомери, специально НЕ описанные в самом необходимом кубите. Оценка числа, как ожидается, оценивает время вычислений. Кроме того, каждый из них использует результаты исследований, больше, чем модульное возведение в степень Неарифметическое (взаимное деление Евклида и т. Д.) Также в отношении запланированной конфигурации эффективной квантовой цепи.
... [8] П. Л. Монтгомери, «Модульное умножение без деления на пробу», Математика вычислений, 44, 170, с. 519-521, 1985 ...
источник
Ответы:
Не могли бы вы опубликовать оригинальное японское название / ссылку?
Кроме того, вы можете подумать о том, чтобы просто написать автору - если предположить, что это тот же парень, которого он профессор в Токийском университете:
http://www.it.ku-tokyo.ac.jp/~kunihiro/
и почти наверняка ответит.
Извините, что опубликовал это как ответ, это должен быть комментарий, но у меня пока нет представителя для этого ...
РЕДАКТИРОВАТЬ: Итак, я взглянул на оригинальный японский. В качестве предисловия я в настоящее время являюсь аспирантом кафедры ЭЭ в Токио, родом из США, и я делаю технический перевод JA-> EN в качестве работы с частичной занятостью. Тем не менее, эта тематическая область находится далеко за пределами моей зоны комфорта, поэтому, пожалуйста, примите мое мнение с долей соли!
В основном вывод (4) гласит:
Я пытался найти соответствующие документы на английском и японском языках, но безуспешно. Я полагаю, что этот подход оказался неудачным, или профессор занялся чем-то другим (похоже, это было вокруг, когда он сменил университет).
Я думаю, что ваша лучшая ставка на данный момент, если вы хотите продолжить работу и получить конкретный ответ, это написать профессору Кунихиро напрямую (на английском языке!)
источник
Я также задавался вопросом об этом вопросе, поскольку современные подходы к модульному умножению для квантового факторинга используют либо пробное вычитание, если есть переполнение после каждого сложения, либо подход деления / вычитания в конце. Оба из них кажутся расточительными.
Я сейчас работаю над квантовой архитектурой для выполнения modexp с использованием умножения Монтгомери. Я не думаю, что затраты пространства должны быть больше, чем в предыдущих подходах, но я не вижу необходимости использовать умножение Карацубы в настоящее время.
Умножение Монтгомери в двоичном коде достаточно эффективно (сдвиг битов и сложение). Добавление модуля и сдвинутых сумм зависит от младшего значащего бита (LSB) на каждом шаге, поэтому, по-видимому, перед ними последовательно требуется получить O (n) времени.
Тем не менее, вы можете распараллелить эту зависимость от LSB, используя таблицы функций и составляя / сужая их подобно подходам с переносом взглядов или описанию Китаевом параллельных конечных автоматов в своей книге (Китаев, Шен, Вялый, 2002). Этот шаг почти наверняка требует много вспомогательных, но асимптотически он может быть сделан O (log n) -depth.
источник