Page 46 - Telebrasil - Novembro/Dezembro 1986

um problema sem solução ou se é apenas

um problema NP-completo.

Criptografia

Se a discussão sobre problemas NPe

P parece exotérica, suas aplicações, não

obstante, são da maior importância.

Uma delas é a criptografia ou a arte de

como enviar segredos que só o destina­

tário possa interpretar.

Na criptografia convencional, apli­

ca-se à mensagem uma chave (ou código

de transcrição) e tem-se na saída a men­

sagem codificada. Na recepção aplica-se

novamente a chave e decodifica-se a

mensagem. E qual o problema do sigilo

convencional? O receptor e o transmis­

sor precisam atualizar suas senhas pe­

riodicamente — um momento delicado

para a perda de sigilo, ressaltou Richard

Karp.

Porém em 76, um "Ovo de Colombo”

contornaria a situação: foi a idéia de

chave pública. Neste sistema, a mensa­

gem é codificada através de uma chave

que muda diariamente e que é tornada

pública. O texto cifrado, no entanto, só A explosão
dos números
pode ser decodificado, com o auxílio de pode ser algo

uma chave privada do destinatário, incontrolável,

combinada com esta chave pública. até mesmo para

Em termos práticos, isto significa o computador.

que o sistema de codificação-decodifica-

ção muda diariamente, bastando que o

suposto espião (se for este o caso) leia quanto achar os fatores primos de n. exemplo de como se conquistam os céti­

(num jornal) a nova chave pública e a Mas, a chave pública criptográfica cos, neste caso.

combine com sua chave pessoal. Achar tem ainda outras aplicações, explicou Sejam 5 pontos (A, B, C, D, E) for­

os componentes das chaves — explicou o Karp, dentre elas, possibilita que diver­ mando um polígono. Como provar que é

conferencista — recai num problema sos transmissores enviem mensagens possível, partindo de um vértice, voltar

tão difícil (mesmo com computador), diferentes com a mesma chave públi­ a ele, visitando todos os demais, apenas

ca — mas de modo que apenas um recep­ uma só vez. Seja a seqüência A, C, B, D.

tor possa decodificá-las. E, além disto, E, A a solução encontrada. Para revelar

este sistema pode ser empregado para a se existe uma solução, bastaria aplicar a

Um desafio assinatura digital, bastando empregar seguinte chave — e dar como prova do

uma combinação de chave privada e de
aparentemente chave pública. problema — a seqüência A, B, C, D, E.
Esta é uma prova, mas não a solução en­

simples Se a criptografia permite importante contrada, que só seria conhecida, ao se

e vitais aplicações práticas, também conhecer a chave: (A = A; C = B; B = C;

Seja o conjunto: ACD; AC; AB; serve para resolver problemas teóricos. D = D; E = E).

AD; BC. Em 1972, Yao aplicou com sucesso o pro­ Em termos matemáticos mais preci­

A procurada solução é um con­ cesso ciptográfico ao problema dos sos, o enunciado da prova interativa é o

junto de 5 letras, retiradas uma de milionários. Este consiste em ter um seguinte: "qualquer teorema, possível

cada linha. Mas atenção! Foram cha­ grupo de pessoas de renda muita alta e de prova, tem uma prova interativa de

mados de antagônicos as letras A e Á; transmitir, com sigilo, esta informação conhecimento zero (não é revelada ao

B e B; C e C. O resultado poderá ser de modo que o público fique sabendo público), cujo comprimento é limitado

qualquer combinação de símbolos, qual o mais rico, mas não seu nível de por uma prova do tipo polinomial (que

desde que não contenham antagô­ renda. Outro problema, que recai na pode ser resolvido num tempo exe-

nicos. mesma categoria, é o da votação secreta, qüível)”.

Existirá uma solução para este onde existem dois candidatos e eleitores Desde Pitágoras, matemáticos, filó­

problema?* Pode-se provar â priori têm direito apenas a um voto. Quer se sofos e políticos elocubram tentando re­

se há ou não solução? Encontran­ divulgar quem é o vencedor, mas prote­ solver problemas. Com a chegada dos

do-se uma solução, existirão outras? gendo o segredo do eleitor. Outro proble­ computadores e das máquinas de cal­

Quantas? Quais são? ma, ainda, do mesmo tipo e que a técnica cular, poderia pensar o leigo que a guer­

Como se verifica, este é um pro­ criptográfica auxilia a resolver é o do ra está terminada: é só apertar um bo­

blema aparentemente simples, mas jogo sigiloso de pôquer, via telefone. tão e, depois de um certo tempo, tem-se a

que pode levar a problema combina­ resposta a qualquer problema. Da

tório, bastante complexo. E com tais Interativa palestra de Richard Karp ficou evidente

tipos de problemas que se defrontam que a solução de problemas, — aparen­

os que lidam com problemas estraté­ A situação da prova interativa, de co­ temente teóricos — podem ter grande

gicos. nhecimento zero, é a seguinte: o interlo­ aplicação na prática, e que está em

cutor saberá que existe prova para solu­ tempo de melhor apreendermos o justo

cionar um problema, mas não saberá limite destas máquinas sensacionais,

* Eia uma solução: A. C. A, I), B. qual. Impossível? Richard Karp deu um que processam a informação iJCFl