Por que os algoritmos genéticos não funcionam em problemas como fatorar RSA?
https://stackoverflow.com/questions/5456483
-
12-11-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Há algum tempo eu estava bastante interessado em GAs e estudei bastante sobre eles.Usei C++ GAlib para escrever alguns programas e fiquei bastante impressionado com sua capacidade de resolver problemas de outra forma difíceis de calcular, em questão de segundos.Eles pareciam uma ótima técnica de força bruta que funciona de maneira muito inteligente e se adapta.
Eu estava lendo um livro de Michalewitz, se bem me lembro o nome e tudo parecia baseado no Teorema do Esquema, comprovado pelo MIT.
Também ouvi dizer que ele realmente não pode ser usado para abordar problemas como fatoração de chaves privadas RSA.
Alguém poderia explicar por que esse é o caso?
Solução
algoritmo genético não são inteligentes em todos os , eles são algoritmos de otimizador muito gananciosos. Todos eles trabalham em torno da mesma ideia. Você tem um grupo de pontos ('uma população de indivíduos'), e você transforma esse grupo em outro com operador estocástico, com um viés na direção da melhor melhoria ('mutação + crossover + seleção'). Repita até que ela converge ou você esteja cansado disso, nada inteligente lá.
Para um algoritmo genético para trabalhar, uma nova população de pontos deve se apresentar perto da população anterior de pontos. Pouca perturbação deve cria pouca mudança. Se, após uma pequena perturbação de um ponto, você obtém um ponto que representa uma solução com desempenho completamente diferente, então, o algoritmo não é nada melhor do que a pesquisa aleatória, um algoritmo geralmente não um bom otimização. No caso RSA, se seus pontos forem diretamente os números, é sim ou não, apenas vindo um pouco ... assim usando um algoritmo genético não é melhor que pesquisa aleatória, se você representa o problema RSA sem muito pensar "Vamos Pontos de pesquisa de código como os bits dos números "
Outras dicas
Eu diria porque a fatoração das chaves não é um problema de otimização, mas um problema exato.Esta distinção não é muito precisa, então aqui estão os detalhes. Os algoritmos genéticos são ótimos para resolver problemas onde são os mínimos (local / global), mas não há nenhum problema de fatoração.Algoritmo genético como DCA ou o recozimento simulado precisa de uma medida de "Quão perto eu sou para a solução", mas você não pode dizer isso para o nosso problema.
Para um exemplo de problema genética é bom, há o problema de escalada na colina.
Gás são baseados na avaliação de aptidão das soluções candidatas.
Você basicamente tem uma função de fitness que leva em uma solução candidata como entrada e lhe dá de volta um escalar dizendo o quão bom é o candidato.Você então continua e permite que os melhores indivíduos de uma determinada geração acasalar com maior probabilidade do que o resto, de modo que o descendente será (espero) mais "adequado" em geral, e assim por diante .
.Não há como avaliar a aptidão (quão boa é uma solução candidata em comparação com o resto) no cenário de fatoração RSA, por isso você não pode usá-los.
GAs não são de força bruta, são apenas um algoritmo de busca.Cada GA se parece essencialmente com isto:
candidates = seed_value;
while (!good_enough(best_of(candidates))) {
candidates = compute_next_generation(candidates);
}
Onde good_enough e best_of são definidos em termos de função de fitness.Uma função de condicionamento físico diz quão bem um determinado candidato resolve o problema.Essa parece ser a questão central aqui:como você escreveria uma função de aptidão para fatoração?Por exemplo 20 = 2*10 ou 4*5.As tuplas (2,10) e (4,5) são claramente vencedoras, mas e as outras?Quão “adequado” é (1,9) ou (3,4)?
indiretamente, você pode use um algoritmo genético para fatorar um método de fatoração de inteiro de n. dixon usa equações envolvendo poderes do primeiro k primos, módulo n. esses produtos de poderes de pequenos primos são chamados de "suave". Se estivermos usando os primeiros k= 4 primos - {2,3,5,7} - 42= 2x3x7 é suave e 11 não é (por falta de um termo melhor, 11 é "bruto" ). O método de Dixon requer uma matriz invertida k k consistindo dos expoentes que definem esses números suaves. Para mais informações sobre o método de Dixon, veja https://en.wikipedia.org/wiki/dixon%27s_factorization_method .
Pensando melhor, a melhor maneira de chegar aos coeficientes suaves x, y na rede ax = por mod N é com regressão, não com um algoritmo genético.
Duas regressões são realizadas, uma com vetor de resposta R0 consistindo em valores de x de soluções escolhidas aleatoriamente de ax = por mod N;e o outro com vetor de resposta R1 consistindo em valores de y das mesmas soluções.Ambas as regressões utilizam a mesma matriz explicativa X.Em X estão colunas que consistem nos restos dos divisores suaves do módulo dos valores x e outras colunas que consistem nos restos dos divisores suaves do módulo dos valores y.
A melhor escolha de divisores suaves é aquela que minimiza os erros de cada regressão:
E0 = R0 - X (inverso de (transposição X) (X)) (transposição X) (R0)
E1 = R1 - X (inverso de (transposição X) (X)) (transposição X) (R1)
O que se segue são operações de linha para aniquilar X.Em seguida, aplique o resultado z dessas operações de linha aos valores x e y das soluções originais a partir das quais X foi formado.
z R0 = z R0 - 0
= z R0 - zX (inverse of (X-transpose)(X)) (X-transpose) (R0)
= z E0
Da mesma forma, z R1 = z E1
Três propriedades são agora combinadas em z R0 e z R1:
- Eles são múltiplos de grandes números suaves, porque z aniquila os restos do módulo de números suaves.
- Eles são relativamente pequenos, pois E0 e E1 são pequenos.
- Como qualquer combinação linear de soluções para ax = por mod N, z R0 e z R1 são eles próprios soluções para essa equação.
Um múltiplo relativamente pequeno de um grande número suave pode ser apenas o próprio número suave.Ter uma solução suave de ax = por mod N produz uma entrada para o método de Dixon.
Duas otimizações tornam isso particularmente rápido:
- Não há necessidade de adivinhar todos os números suaves e colunas de X de uma só vez.Você pode executar regressões continuamente, adicionando uma coluna a X por vez, escolhendo colunas que reduzam mais E0 e E1.Em nenhum momento serão selecionados quaisquer dois números suaves com um fator comum.
- Você também pode começar com muitas soluções aleatórias de zx = por mod N e remover aquelas com maiores erros entre as seleções de novas colunas para X.
