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.

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.

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.

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.

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