 |
gildot |
 |
| |
 | Contribuído por Tintim em 22-08-02 15:49
do departamento deterministico_polinomial_e_sem_conjunturas | |  | |  | | |  Os mais atentos já devem ter reparado no frenesim no sci.crypt e no sci.math.
Três matemáticos indianos (dois deles ainda a terminar a licenciatura :-)) ), propuseram um novo teste de primalidade que é o primeiro teste deterministico que baseia a sua prova matemática *apenas* em teoremas já provados, e não em conjunturas.
| | | | | | Alguns dos mais destacados investigadores em Teoria dos Números (Lenstra, Pomerance,...) já validaram os resultados.
As implicações práticas, em termos de segurança não são imediatas, mas...
Ver mais informações em Math World e The prime pages. < Matemática | Developing and Testing a Complete "Hello World" J2 > | | gildot Login | | | Referências | | |
| Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário. | | | Aqui ficam algumas observações ao que tem sido dito:
1 - a novidade deste algoritmo é que sendo deterministico, tem a sua prova matemática baseada apenas em teoremas já demonstrados (e principalmente no Fermat's Little Theorem).
Existem outras soluções deterministicas para o teste de primalidade de um número, mas baseiam-se em conjunturas, que mais tarde se podem provar falsas.
2 - outro pormenor interessante é que a complexidade assimptótica do algoritmo é (ln^12 n).f(log log n), mas que se uma determinada conjuntura entretanto se verificar verdadeira, essa complexidade pode baixar para ln^3 n.
3 - > A segurança na Internet ainda não está sob ameaça. "A solução provavelmente
> terá um impacto muito pequeno, pois ela não oferece nenhuma vantagem real
> sobre os algoritmos probabilísticos já usados no setor", afirma Ben Hadley
> da nCipher, uma empresa de segurança por criptografia baseada em Cambridge.
Como é dito, na verdade o algoritmo pode a vir ter poucas consequências práticas na utilização de certificados X.509. Provavelmente, na geração do par de chave pública/privada (RSA, PGP,...) para certificados continuará a ser utilizado um algoritmo probabílistico como o Rabin-Miller com uma complexidade inferior.
Do que li, pareceu-me a complexidade desta solução é superior à dos actualmente utilizados e, portanto, maior consumidora de tempo no momento da geração da chave.
4- > Mas Pomerance acredita que a existência da prova deixará os criptologistas
> preocupados. "Se há um teste simples para saber se um número é primo, também
> pode haver uma forma simples de determinar os fatores primos que estamos
> atualmente investigando", disse ele. (New Scientist)
Por outro lado, IMHO esta solução não torna os actuais algoritmos de factorização (que são a verdadeira ameaça à segurança de transacções) mais eficazes.
Tanto o ECM (elliptic curve method) ideal para factorização de números compostos com menos de 40 digitos, como o MPQS (para menos de 105 digitos), como o NFS (Number Field Sieve) não vêm a sua complexidade computacional aumentada pela utilização de testes de primalidade.
Quando muito, a construção do "factor base" no NFS (antes da fase de sieving) realizada através da selecção de primos abaixo de um determinada fronteira (B1 - Bound) podia utilizá-lo.
O(s) Lenstra e o Pomerance (parecem) ver nesta descoberta, uma esperança para a descoberta de uma algoritmo que resolva o problema da factorização e de logaritmo discreto de uma forma deterministica em tempo polinomial (passando-os de NP para P).
Depois da prova do Fermat's last theorem por Wiles em 1994, esta é uma ideia que vem mostrar que a Teoria dos Números ainda pode trazer algumas surpresas..:-)) pelo sim, pelo não, vou gerar uma nova chave com 2048 bits.
|
| | | | | | | No entanto, neste processo ainda pode ser encontrado um método para 'acelerar' a desencriptação de chaves. Se calhar ainda poderá ser mais influente nos certificados do que se está a imaginar...IMHO claro
Vx
----------------------------------------
Accept that some days you are the pigeon and some days the statue.
------------------------------
|
| | | | Correcção: "conjunturas" -> "conjecturas"
|
| | | | | | Tens toda a razão.
Fiquei a pensar nisso depois de escrever o artigo...
"Conjuntura" de facto existe, mas tem um significado completamente diferente.
É o que dá as nossas leituras não serem em português...
|
| | | | | É verdade, não ha nenhuma publicação científica lusófona pois não? Pelo menos digna desse nome. Seria interessante haver um canal onde as Universidades e investigadores podessem publicar resultados já que temos algumas personalidades tão brilhantes. Mas pronto, assim se vai andando :).
Vx
----------------------------------------
Accept that some days you are the pigeon and some days the statue.
------------------------------ |
| | | | Só que o latim actual é o inglês... Escrever artigos científicos em português iria normalmente duplicar o trabalho de escrita já que poucos se escusariam a publicar o mesmo em inglês também. Até a Portugaliæ Mathematica funciona em inglês. Assim o material em português escrito pelos mesmos autores acaba por ser principalmente ou para ensino ou para divulgação (para ganhar mais uns tostões ou para o "nacional-prestígio" a la Colóquio Ciência).
|
| | | | | Às vezes também ajuda o facto de estarmos a falar de um assunto que nos é mais ou menos familiar, ou termos uma formação matemática mais extensa na faculdade - que apesar de a haver com fartura em muitos cursos de engenharia, ou de informática, não creio ser a suficiente para habilitar alguém a escrever artigos desta natureza (como aliás se comprova, mas mais ainda ... existem outros testes para descobrir se um número é primo ou não, e baseados em teoremas comprovados a novidade deste é que é o único do tipo "polinomial" que possui neste momento uma base sustentada (comprovada), que é o pequeno Teorema de Fermat) ... a não ser que se seja um estudioso do assunto -. Já agora e para um maior conhecimento do assunto recomendo as seguintes leituras: - P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, 1995. (QA246 .R472).
- P. Ribenboim, The little book of big primes, Springer-Verlag, New York, 1991.
- The Primes Pages
Beijocas
|
| | | | Não percebi bem aonde querias chegar...
Se era eu não estava habilitado a fazer o comentário, ou se eram os autores que não deviam ter escrito o artigo.
mas mais ainda .. existem outros testes para descobrir se um número é primo ou não
Penso que isso fica claro no artigo original..(...propuseram um novo teste de primalidade)
é o único do tipo "polinomial" que possui neste momento uma base sustentada (comprovada)
Penso que isto tb ficou claro no comentario inicial: utiliza apenas teoremas e não conjecturas.
|
| | | | Tendo em conta os últimos artigos do gildot, grande tópico para uma lufada de ar fresco. Obrigado 300!
|
| |
|
