Fatoração de inteiros

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

Em teoria dos números, o problema da factoração/ factorizaçã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.

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.

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

Quando os números são muito grandes não se conhece nenhum algoritmo que resolva eficientemente este problema; uma recente iniciativa de fatorar/ factorizar um número de 200 dígitos (RSA-200) demorou 18 meses e consumiu mais de meio século total de tempo de cálculo (cálculos em paralelo). 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 distribuida[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. Atualmente (2006) se considera que os casos mais difíceis são aqueles para os que os fatores são dois números primos, eleitos ao acaso, de aproximadamente o mesmo tamanho.

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 es:Factorización de enteros. 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.