CODIFICA
Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.
Resolução do problema CODIFICA proposto no CNPL'98.
Consideremos os números naturais e a ideia muito simples de número primo: um número que não se pode obter pela multiplicação de dois números mais pequenos onde não se inclui a unidade. Sabia-se desde tempos remotos, como um facto empírico, que todos os números se exprimem, de forma única, como um produto de primos; e os Gregos conseguiram prová-lo. Algumas perguntas sobre primos surgem naturalmente. Por exemplo: Quantos primos existem e como estão os primos distribuídos entre os outros naturais? Como se determinam primos? Como é que se mostra que um dado natural é, ou não, um primo? Como se factoriza, num produto de primos, um natural arbitrário? Mesmo com tão simples matéria-prima, a matemática fez uma obra espantosa e, se questões como as acima colocadas, podem ser olhadas numa perspectiva abstracta e como um ramo da matemática inaplicável, a verdade é que estas questões têm um significado crucial para a criptografia; tanto mais que têm havido sérias tentativas de classificar alguns dos resultados desta área como segredos militares. Tudo indica que são os métodos de codificação baseados em números primos que constituirão a parte central do sistema de segurança da futura auto-estrada da informação.
Implemente em Prolog um codificador de mensagens e o respectivo descodificador. O codificador deve substituir o código ASCII de cada caracter da mensagem por um outro de acordo com o algoritmo de encriptação descrito pelos seguintes passos:
Lembramos que o código ASCII é um número entre 0 e 255 e que é preciso ter o cuidado de garantir que os códigos ASCII codificados também estão nesta gama! Mais uma vez, deve usar a noção de circularidade: por exemplo, se estamos a somar o primo 3, o código ASCII 33 será transformado no 36 enquanto o 254 será transformado no 1.
O algoritmo de descodificação deverá proceder à operação inversa do de codificação.
Implemente um predicado em Prolog para gerar números primos segundo o algoritmo designado por Crivo de Eratóstenes. Esse método permite-nos construir uma lista de todos os primos até um limite dado, de acordo com a seguinte descrição2:
``Escrevemos os naturais desde 2 até ao limite desejado; por exemplo 200:
2, 3, 4, 5, 6, 7, ¼, 198, 199, 200. Começando no princípio da lista, o primeiro número que encontramos é 2, um primo. Deixamos 2 de lado, e passamos à frente marcando os números de 2 em 2, isto é, marcamos 4, 6, 8, 10, ¼. Depois de ter marcado todos os números pares até 200, voltamos ao princípio da lista para encontrar o primeiro número depois de 2 que não foi marcado: é 3. Deixamos 3 de lado (é primo), e passamos à frente marcando os números de 3 em 3: marcamos 6, 9, 12, 15, ¼. Prosseguimos assim. Depois de fazermos este jogo repetidamente para 2, 3, ¼, N, onde N é o maior natural não marcado tal que N £ [Ö200], então os números da lista que ainda não foram marcados são os primos até 2003.''
O único dado necessário para a resolução da tarefa principal deste problema é a mensagem a codificar. Essa mensagem será um parâmetro do predicado encode/2 que tem de desenvolver, como se explica na secção seguinte.
Para a subtarefa de geração de números primos também precisa de conhecer à partida apenas um dado: o valor do limite superior da lista a gerar.
O seu programa deve ser invocado através dos predicados:
encode/2
que recebe a mensagem e retorna no segundo argumento a lista dos códigos ASCII da mensagem codificada
decode/2
que recebe a lista dos códigos ASCII da mensagem codificada e devolve no segundo argumento a mensagem original.
primos/2
que recebe como primeiro argumento um número natural N e devolve no segundo argumento a lista de todos os primos até N.
Exemplos:
?- primos(100,L).
L = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
67,71,73,79,83,89,97]
?- encode('Ola malta',C), decode(C,D).
C = [79,110,100,37,116,108,121,133,116]
D = 'Ola malta'
%% Realizado por Delfim F. Marado Torres -- 30/Mar,co/1998
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% primos/2
%% primos(N,L) - L 'e a lista de todos os primos =< N
%%
%% Exemplo:
%% ?- primos(200,L).
%% L = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,
%% 89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
%% 179,181,191,193,197,199]
%% yes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
primos(N,P) :-
cria_lista2N(N,L),
eratostenes(N,L,[],[],PI), % No in'icio a lista de marcados 'e vazia
inverte(PI,P),!. % assim como a de primos
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Predicados auxiliares normalmente disponibilizados
%% nos interpretadores de Prolog
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
membro(X,[X|_]).
membro(X,[_|R]) :-
membro(X,R).
concatena([],L,L).
concatena([X|R],L,[X|C]) :-
concatena(R,L,C).
nao_e_verdade(P) :- call(P), !, fail ; true.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% cria_lista2N/2
%% cria_lista2N(N,L) - L 'e a lista de naturais de 2 at'e N
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
c_lista(2,[2]).
c_lista(N,[N|R]) :-
N1 is N-1,
c_lista(N1,R).
inverte([],[]).
inverte([X|R],I) :-
inverte(R,RI),
concatena(RI,[X],I).
cria_lista2N(N,[]) :-
N < 2.
cria_lista2N(N,L) :-
c_lista(N,I),
inverte(I,L).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% eratostenes/5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
eratostenes(_,[],_,P,P).
eratostenes(N,[X|L],M,P,R) :-
membro(X,M),
eratostenes(N,L,M,P,R).
eratostenes(N,[X|L],M,P,R) :-
X2 is X * X,
X2 =< N,
marca(X,X,L,M1),
concatena(M,M1,NM),
eratostenes(N,L,NM,[X|P],R).
eratostenes(N,[X|L],M,P,R) :-
eratostenes(N,L,M,[X|P],R).
marca(_,I,L,[]) :-
nao_e_verdade(esimo_elemento(I,L,_)).
marca(N,I,L,[X|M]) :-
esimo_elemento(I,L,X),
NI is I + N,
marca(N,NI,L,M).
esimo_elemento(1,[X|_],X).
esimo_elemento(N,[_|R],X) :-
N1 is N-1,
esimo_elemento(N1,R,X).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% encode/2 - codifica strings
%% decode/2 - descodifica as strings codificadas com encode/2
%%
%% Exemplo:
%% ?- encode('Encontra-me ao anoitecer',C), decode(C,D).
%%
%% D = 'Encontra-me ao anoitecer'
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
encode(M,C) :-
name(M,[X|L]),
primos(X,P),
codifica(L,P,C).
decode([X|L],M) :-
primos(X,P),
descodifica(L,P,LD),
name(M,[X|LD]).
cod(N,X,Y) :- Y is (X + N) mod 256.
dec(N,Y,X) :- X is (256 + Y - N) mod 256.
codifica(L,P,LC) :-
transforma(cod,L,P,LC).
descodifica(L,P,LD) :-
transforma(dec,L,P,LD).
transforma(_,[],_,[]).
transforma(T,[X|R],[P1|P],[XT|RT]) :-
C =.. [T,P1,X,XT],
call(C),
concatena(P,[P1],NP),
transforma(T,R,NP,RT).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Realizado por Delfim F. Marado Torres
% 13/Maio/1999
% Testado no SWI-Prolog
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
primos(N,P) :- % N inteiro >= 2
listaAte(L,N),
eratostenes(L,[],P). % ListaMarcados = []
listaAte([2],2).
listaAte(L,N) :-
N1 is N-1,
listaAte(R,N1),
append(R,[N],L).
eratostenes([],_,[]). % Aplicamos o processo ate' 'a lista vazia
% Nao aplicamos o criterio =< sqrt(N)
eratostenes([X|R],M,P) :-
member(X,M),
eratostenes(R,M,P).
eratostenes([X|R],M,[X|P]) :-
marca(X,X,[X|R],MX),
append(MX,M,NM), % nao faz mal haver repetidos
eratostenes(R,NM,P).
marca(_,_,[],[]).
marca(X,0,[Y|R],[Y|M]) :-
marca(X,X,[Y|R],M).
marca(X,P,[_|R],M) :-
P1 is P-1,
marca(X,P1,R,M).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
encode(M,L) :-
name(M,L1),
transforma(soma,L1,L).
decode(L,M) :-
transforma(subtrai,L,L1),
name(M,L1).
transforma(T,[X|R],[X|L]) :-
primos(X,P),
codifica(T,R,P,L).
codifica(_,[],_,[]).
codifica(T,[X|R],[A|RA],[C|RC]) :-
G =.. [T,X,A,C],
call(G),
append(RA,[A],P),
codifica(T,R,P,RC).
soma(X,Y,R) :-
R is (X + Y) mod 256.
subtrai(X,Y,R) :-
R is (X - Y + 256) mod 256.
1 Sugere-se o uso do predicado pré-definido name/2.
2 B. Owen, Teoria Elementar dos Números I, Boletim da SPM, 33, (1995), p. 17-36.
3 Sugerimos que evitem o cálculo da raiz quadrada. Na situação apresentada, o teste N £ [Ö200] pode ser substituído por N2 £ 200.