Fatoração de inteiros

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em teoria dos números, o problema da fatoração/ fatoração de inteiros consiste em encontrar um divisor não trivial de um número composto; Por exemplo dado o número 91, o objetivo é encontrar um número tal como 7 que o divida. Se esses inteiros estão restritos a números primos, este processo é chamado de fatoração por números primos/fatoração prima.

O problema computacional que é a fatoração/ fatoração de inteiros para números extremamente grandes tem motivado diversos estudos devido a sua aplicação em sistemas de criptografia.[1]

A imagem mostra a decomposição principal do número 864 Um método rápido de escrever o resultado em números primos 2^5 \times 3^3.

Quando os números são muito grandes não se conhece nenhum algoritmo que resolva eficientemente este problema; uma recente iniciativa de diversos pesquisadores concluída em 2009, de fatorar/ fatorar um número de 232 dígitos (RSA-768) utilizando centenas de maquinas demorou 3 anos e os pesquisadores estimaram que um modulo RSA de 1024 bits demoraria mais ou menos 3000 anos. Apesar disso, não foi provado que nenhum algoritmo eficiente exista. A suposta dificuldade é o núcleo de certos algoritmos criptográficos, como o RSA. Muitas áreas da matemática e da ciência da computação, como a teoria algébrica dos números, as curvas elípticas, a computação distribuída[2] ou a computação quântica, estão relacionadas com este problema.

Decompor-se dois números de igual comprimento não tem porque ter a mesma complexidade. As instancias mais difíceis destes problemas ( para as técnicas conhecidas atualmente) são semi-primos, o produto entre números primos. Quando os dois números são grandes, mais que 2000 bits, por exemplo, escolhidos aleatoriamente, e mais ou menos do mesmo tamanho (Mas não muito perto, temos que tentar evitar o método de fatoração de Fermat), até os algoritmos mais rápidos de fatoração prima nos computadores mais rápidos podem levar tempo suficiente para fazer a busca ser impraticável. Sendo assim, a medida que o numero de dígitos dos primos a ser fatorados aumenta, o numero de operações requisitadas para concluir a fatoração em qualquer computador aumenta drasticamente.

Vários protocolos criptográficos são baseados na dificuldade de fatorar grandes inteiros compostos ou outro problema parecido — por exemplo, O problema RSA. Um algoritmo que fatora eficientemente um inteiro arbitrário iria tornar insegura a criptografia de chave publica baseada em RSA.

Decomposição em fatores primos[editar | editar código-fonte]

Pelo teorema fundamental da aritmética, cada inteiro positivo tem uma única decomposição em números primos. Dado um algoritmo para a fatoração de inteiros, pode-se fatorar/ factorizar qualquer número inteiro a seus fatores primos mediante aplicação repetitiva deste algoritmo.

Fatoração de números inteiros em tempo polinomial[editar | editar código-fonte]

O problema de fatorar números inteiros em tempo polinomial ainda não foi resolvido. Se alguém tem, seria de grande interesse no campo da criptografia, como muitos sistemas criptográficos dependem de sua impossibilidade. Na academia, a existência de tal desenvolvimento seria uma grande notícia; em outros círculos, seria um grande segredo, por razões óbvias.

Aplicações práticas[editar | editar código-fonte]

A dificuldade deste problema, se encontra no núcleo de vários sistemas criptográficos importantes. Um algoritmo veloz para a fatoração de interos significaria que o algoritmo de chave pública RSA é inseguro. Alguns sistemas criptográficos, como o algoritmo de chave pública Rabin e o gerador de números pseudoaleatórios Blum Blum Shub garantiriam uma melhora em sua segurança; qualquer método que consiga quebrá-los pode ser utilizado para criar um algoritmo de fatorização mais veloz; se a fatorização de inteiros é veloz, estes se tornam de solução mais difícil. Em contraste, podem existir ataques mais eficientes ao problema RSA, mas não se conhece nenhum.

Um problema difícil similar com aplicações criptográficas é o problema do logaritmo discreto.

Algoritmos de fatoração[editar | editar código-fonte]

De uso geral[editar | editar código-fonte]

O tempo de execução de um algoritmo de finalidade geral factoring depende apenas do tamanho do número inteiro para ser tomada. Este é o tipo de algoritmo utilizado para levar números RSA. A maioria dos algoritmos de fatorização são quadrados baseados uso geral método de correspondência. Alguns dos algoritmos mais conhecidos de uso geral estão listados abaixo:

Para fins especiais[editar | editar código-fonte]

O tempo de execução de um propósito específico algoritmo factoring depende das propriedades de seus fatores desconhecidos: tamanho, forma especial, etc Estes factores de mudar de um algoritmo para outro.

Otros algoritmos importantes[editar | editar código-fonte]

Referências

  1. Adriana Betania de Paula Molgora; Uma implementacão do método das curvas elípticas para fatoração/ factorização de números inteiros; Dissertação de Mestrado; www.cbc.ufms.br
  2. Humberto Nigri, Paulo José Lage Alvarenga; Fatoração de Inteiros por meio de Computação Distribuída; Universidade Federal de Minas Gerais - Departamento de Ciência da Computação - homepages.dcc.ufmg.br

Ligações externas[editar | editar código-fonte]


Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido de «Factorización de enteros» na Wikipédia em espanhol. Ajude e colabore com a tradução.
Portal A Wikipédia possui o
Portal da Matemática.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.