Dlaczego modułowe potęgowanie Montgomery nie jest rozważane do stosowania w faktorowaniu kwantowym?

Powszechnie wiadomo, że potęgowanie modułowe (główna część operacji RSA) jest drogie obliczeniowo i, o ile rozumiem, preferowaną metodą jest potęgowanie modułowe Montgomery'ego . Modułowe potęgowanie jest również wyraźnie widoczne w algorytmie faktoringu kwantowego i tam również jest drogie.

Więc: dlaczego modułowe potęgowanie Montgomery'ego najwyraźniej nie występuje w obecnych szczegółowych podprogramach faktoringu kwantowego?

Mogę sobie tylko wyobrazić, że z jakiegoś nieoczywistego powodu istnieje wysoki narzut kubitowy.

Uruchamianie kwantowego „modułowego potęgowania” montgomery przez Google Scholar nie daje żadnych użytecznych wyników. Zdaję sobie sprawę z pracy Van Metera i innych nad dodawaniem kwantowym i potęgowaniem modularnym, ale analiza ich odniesień (muszę jeszcze przeczytać tę pracę) nie wykazuje, że metody Montgomery są tam rozważane.

Jedyne odniesienie , które wydaje się omawiać na ten temat, jest w języku japońskim, którego żałośnie nie mogę przeczytać, chociaż najwyraźniej pochodzi ono z materiałów konferencyjnych z 2002 roku. Tłumaczenie maszynowe dostarcza bryłki dołączone poniżej, które wskazują, że może być coś przydatnego. Nie mogę jednak znaleźć żadnych wskazówek, że podjęto działania następcze, co sprawia, że ​​uważam, że pomysł został a) rozważony, a następnie b) odrzucony.

Obwód kwantowy w wykonywaniu arytmetyki Noboru Kunihiro

... W tym badaniu, ale wymaga stosunkowo dużego kubitu, proponujemy modułowy czas obliczeń kwantowych obwodu wykładniczego jest krótki. Redukcja Montgomery'ego [8] i prawa metoda binarna [9] W połączeniu tworzą obwód Ru. Redukcja Montgomery jest losowo wybierana jako liczba naturalna, mod 2m przez operację, wykonaj resztę operacji If, modn operacji w eliminacji. Doprowadzi to do skrócenia czasu obliczeń ...

Zastosowanie 3.2 Montgomery Reduction Montgomery Reduction [8] jest sformułowany w następujący sposób ... Ten algorytm może zwrócić prawidłowe wartości, które można łatwo potwierdzić. MR (Y) prosi o prawo Wielomian 2m z 2 milionami punktów jest ważny i wymaga tylko podziału przez. Ponadto, Redukcja Montgomery w, istnieją różne metody obliczania ... Ogólnie rzecz biorąc, Redukcja Montgomery nie jest funkcją jeden do jednego ...

... Proponowana metoda wykorzystuje właściwą metodę binarną, Montgomery Reducton ma przyjętą funkcję. Niż konwencjonalna metoda, charakteryzująca się małą składową obwodu. błąd qubit, który musi mieć wiele oczekiwań, można obliczyć w krótszym czasie obliczeniowym Be. Przyszłość, redukcja Montgomery i obwody sterujące, NIE opisane w rzeczywistości przez kubit, naprawdę potrzebne. Oszacuj, że liczba ma oszacować czas obliczeń. Ponadto, korzystając z wyników badań, nie tylko arytmetyka modularna (potęga euklidesowa itp.), Także w odniesieniu do planowanej konfiguracji wydajnego obwodu kwantowego.

... [8] PL Montgomery, „Modular Multiplication Without Trial Division”, Mathematics of Computation, 44, 170, str. 519-521, 1985 ...

Czy możesz zamieścić oryginalny japoński tytuł / odniesienie?

Możesz również rozważyć napisanie do autora - zakładając, że jest to ten sam facet, który jest profesorem na Uniwersytecie w Tokio:

http://www.it.ku-tokyo.ac.jp/~kunihiro/

i prawie na pewno by odpowiedział.

Przepraszam, że opublikowałem to jako odpowiedź, powinien to być komentarz, ale najwyraźniej nie mam jeszcze przedstawiciela ...

EDYCJA: Więc spojrzałem na oryginalnego Japończyka. Na wstępie jestem obecnie doktorantem na wydziale EE w U. Tokyo, pochodzącym z USA i wykonuję techniczne tłumaczenia JA-> EN jako pracę w niepełnym wymiarze godzin. Jednak ten obszar tematyczny znajduje się poza moją strefą komfortu, dlatego proszę o opinię z odrobiną soli!

Zasadniczo wniosek (4) mówi:

Inary き 乗 剰 余 演算 を 行 う 量子 回路 を を 提案 提案 方式 は 、 、 右 向 向 き Metoda binarna を 採用 し 、 Montgomery Reduction を 採用 す る と い よ よ よ よ よ よ よ 従 従 従 従 従 従 従 従て い る 。qubit が 多 く 必要 と な る と い う 欠 点 は 持 つ が が 、 よ り 少 な い 計算 時間 で 計算 計算 が で き る と 期待 期待 さ れ れ る。

[W tym artykule] Zaproponowaliśmy nowy obwód kwantowy do obliczania potęgowania modularnego. Proponowana metoda wykorzystuje metodę binarną LR, a także charakteryzuje się zastosowaniem redukcji Montgomery'ego. W porównaniu z poprzednimi metodami proponowana metoda wymaga mniejszej liczby komponentów do zbudowania obwodu. Proponowana metoda ma jednak tę wadę, że wymaga dużej liczby kubitów, ale jesteśmy przekonani, że będzie wydajna obliczeniowo (świeci: wymaga bardzo małego czasu obliczeń).

Próbowałem wyszukać pokrewne artykuły w języku angielskim i japońskim, ale bezskutecznie. Domyślam się, że podejście okazało się nieskuteczne lub profesor zajął się czymś innym (wygląda na to, że było to po zmianie uniwersytetów).

Myślę, że najlepszym rozwiązaniem w tym momencie, zakładając, że chcesz kontynuować resztę drogi i uzyskać konkretną odpowiedź, jest napisanie profesora Kunihiro bezpośrednio (po angielsku!)

Zastanawiałem się również nad tym pytaniem, ponieważ obecne podejścia do mnożenia modułowego w faktorowaniu kwantowym wykorzystują albo odejmowanie próbne, jeśli występuje przepełnienie po każdym dodaniu, albo podejście dzielenie / odejmowanie na końcu. Oba wydają się marnotrawstwem.

Pracuję teraz nad architekturą kwantową do wykonywania modexp przy użyciu mnożenia Montgomery'ego. Nie sądzę, że przestrzeń kosmiczna powinna być większa niż poprzednie podejścia, ale nie widzę obecnie potrzeby używania mnożenia Karatsuba.

Mnożenie Montgomery'ego w systemie binarnym jest dość wydajne (przesuwanie bitów i dodawanie). Dodanie modułu i przesuniętych sum zależy od najmniej znaczącego bitu (LSB) na każdym etapie, więc wydaje się, że wymaga to szeregowo, aby uzyskać czas O (n).

Można jednak zrównoleglić tę zależność od LSB, używając tabel funkcji i komponując / zawężając je podobnie do podejść typu carry-lookahead lub opisu równoległych automatów skończonych Kitaeva w jego książce (Kitaev, Shen, Vyalyi 2002). Ten krok prawie na pewno wymaga dużej liczby pomocników, ale asymptotycznie można by zrobić O (log n) -depth.