É sabido que a exponenciação modular (a parte principal de uma operação RSA) é computacionalmente cara e, até onde eu entendi, a técnica da exponenciação modular de Montgomery é o método preferido. A exponenciação modular também é destaque no algoritmo de fatoração quântica, e também é cara lá.
Então: por que a exponenciação modular de Montgomery aparentemente não está presente nas atuais sub-rotinas detalhadas para fatoração quântica?
A única coisa que posso imaginar é que há um alto custo adicional por um motivo não óbvio.
A execução da "exponenciação modular" quântica montgomery através do Google Scholar não produz resultados úteis. Estou ciente do trabalho de Van Meter e outros sobre adição quântica e exponenciação modular, mas examinar suas referências (ainda não li este trabalho) não mostra indicação de que os métodos de Montgomery sejam considerados lá.
A única referência que descobri que parece discutir isso está em japonês, que lamentavelmente não consigo ler, embora aparentemente seja de um processo de conferência de 2002. Uma tradução automática gera pepitas anexadas abaixo que indicam que pode haver algo útil. No entanto, não consigo encontrar nenhuma indicação de que isso tenha sido seguido, o que me faz pensar que a idéia foi a) considerada e depois b) descartada.
Circuito quântico na execução aritmética de Noboru Kunihiro
... Neste estudo, mas requer um qubit relativamente grande, propomos que o tempo de computação quântica do circuito de exponenciação modular seja curto. Redução de Montgomery [8] e método binário direito [9] Combinados, eles constituem um circuito Ru. Redução Montgomery é, m escolhido aleatoriamente como um número natural, mod 2m pela operação, executar a operação restante Se, mod n, operações na eliminação. Isso levará à redução do tempo de computação ...
Aplicação de 3.2 Redução de Montgomery A Redução de Montgomery [8] é formulada da seguinte forma ... Este algoritmo pode retornar os valores corretos que podem ser facilmente confirmados. MR (Y) ele pede uma lei 2m Polinômios com 2m pontos são importantes e requer apenas divisão por. Além disso, em Redução de Montgomery, existem diferentes métodos de cálculo ... Em geral, a Redução de Montgomery não é uma função individual ...
... O método proposto usa um método binário correto, Montgomery Reducton possui um recurso que é adotado. Do que o método convencional, caracterizado por um pequeno componente do circuito. falha de qubit necessária para ter muitas expectativas pode ser calculada em menos tempo computacional. Futuro, circuitos de controle e redução de Montgomery, NÃO especificamente descritos pelo qubit realmente necessário. Avalie o número esperado para avaliar o tempo de computação. Além disso, cada um aproveitando os resultados da pesquisa, mais do que a exponenciação modular Não-aritmética (divisão mútua Euclides etc.) também com relação à configuração planejada de um circuito quântico eficiente.
[8] PL Montgomery, "Multiplicação Modular Sem Divisão de Julgamentos", Matemática da Computação, 44, 170, pp. 519-521, 1985 ...
fonte
Respostas:
Você poderia postar o título / referência original em japonês?
Além disso, você pode escrever apenas para o autor - supondo que seja o mesmo cara que ele é professor da Universidade de Tóquio:
http://www.it.ku-tokyo.ac.jp/~kunihiro/
e quase certamente responderia.
Desculpe postar isso como resposta, deve ser um comentário, mas ainda não tenho o representante para isso ...
EDIT: Então, dei uma olhada no japonês original. Como prefácio, atualmente sou estudante de doutorado no departamento de EE da Universidade de Tóquio, nos EUA, e faço tradução técnica da JA-> EN como um emprego de meio período. No entanto, esta área de tópicos está bem fora da minha zona de conforto, por isso, tome minha opinião com um grão de sal!
Basicamente, a conclusão (4) diz:
Tentei procurar artigos relacionados em inglês e japonês, mas não obtive sucesso. Meu palpite é que a abordagem não teve êxito ou o professor ficou ocupado com outra coisa (parece que isso existia quando ele mudou de universidade).
Eu acho que sua melhor aposta neste momento, supondo que você queira acompanhar o resto do caminho e obter uma resposta concreta, é escrever diretamente para o professor Kunihiro (em inglês!)
fonte
Também me perguntei sobre essa questão, já que as abordagens atuais da multiplicação modular para fatoração quântica usam uma subtração experimental, se houver um estouro após cada adição, ou uma abordagem de divisão / subtração no final. Ambos parecem um desperdício.
Estou trabalhando em uma arquitetura quântica para executar modexp usando multiplicação de Montgomery agora. Não acho que a sobrecarga de espaço deva ser maior que as abordagens anteriores, mas não vejo necessidade de usar a multiplicação do Karatsuba atualmente.
A multiplicação de Montgomery em binário é bastante eficiente (troca de bits e adição). A adição do módulo e as somas deslocadas dependem do bit menos significativo (LSB) em cada etapa, portanto isso parece exigir diante deles serialmente, para obter tempo O (n).
No entanto, você pode paralelizar essa dependência no LSB usando tabelas de funções e compondo / restringindo-as de maneira semelhante às abordagens de carry-lookahead ou à descrição de Kitaev dos autômatos finitos paralelos em seu livro (Kitaev, Shen, Vyalyi 2002). Essa etapa quase certamente requer muitas ancilares, mas, assintoticamente, pode ser feita uma profundidade de O (log n).
fonte