FAMAT em Revista - Número 12 - Abril de 2009
83
Teoria dos Números e suas aplicações
Luis Armando dos Santos Júnior1 e Antônio Carlos Nogueira2
Universidade Federal de Uberlândia
Abril- 2009
1:Orientando Programa de Educação tutorial do curso de Matemática.
E-mail: [email protected]
2: Orientador. E-mail: [email protected]
Resumo
Este trabalho tem como objetivo mostrar através de demonstrações, exposição de
definições e exemplos algumas aplicações de Teoria dos Números, em particular aplicações
na criptografia e calendários.
Considerações Preliminares
Para a aplicação de Teoria dos Números em Criptografia é necessário que se relembre
algumas definições e teoremas importantes para entendimento do processo.
Definição 1: Seja n um número inteiro positivo. Dois inteiros a e b são ditos congruentes
módulo n, simbolizado por
a ≡ b(mod n)
se n divide a diferença a − b ; ou seja, a − b = kn para algum inteiro k.
Definição 2: Uma equação da forma ax ≡ b(mod n) , com a, b e n inteiros é chamada de
congruência linear, e como solução desta equação dizemos que é um inteiro x 0 para o qual
ax 0 ≡ b(mod n) .
Função ϕ de Euler: Para n ≥ 1 , existe φ(n) que denota o número de inteiros positivos que são
relativamente primos de n e que não são maiores que n .
Teorema 1: Se p é um primo e k > 0 , então
1
φ( p k ) = p k − p k −1 = p k (1 − )
p
Demonstração: Claro que, mdc(n, p k ) = 1 se e somente se p não divide n. Existem p k −1
inteiros entre 1 e p k divisíveis por p , ou seja,
p , 2 p , 3 p , ...., ( p k −1 ) p
Já que {1,2,..., p k } contêm exatamente p k − p k −1 inteiros que são relativamente primos com
p k , então pela definição da função φ , φ( p k ) = p k − p k −1 .
Teorema 2: Se o inteiro n > 1 tem uma fatoração em primos n = p1k1 p 2k 2 ... p rk r , então
φ(n) = ( p1k1 − p1k1 −1 )( p 2k 2 − p 2k 2 −1 )...( p rk r − p rk r −1 ) =

1 
1  
1 
...1 −

= n1 − 1 −
p
p
p

1 
2  
r 
84
FAMAT em Revista - Número 12 - Abril de 2009
Demonstração: Pretende-se usar indução em r o número de fatores primos distintos de n .
Pelo Teorema 1, o resultado é verdadeiro para r = 1 . Suponha que é verdadeiro para r = i . Já
que
mdc( p1k1 p 2k 2 ... p iki , p ik+i 1+1 ) = 1
Da definição de função multiplicativa, temos
φ(( p1k1 p 2k 2 ... p iki ) p ik+i1+1 ) = φ( p1k1 ... p iki )φ( p ik+i 1+1 ) =
= φ( p1k1 ... p iki )φ( p ik+i1+1 − p ik+i 1+1 −1 )
Através da indução têm-se então que
φ( p1k1 p 2k 2 ... p iki ) = ( p1k1 − p1k1 −1 )( p 2k 2 − p 2k 2 −1 )...( p iki − p iki −1 )
Concluiu-se os passos da indução e a demonstração do teorema.
Lema 1: Seja n > 1 e mdc(a, n) = 1 . Se a1 , a 2 ,..., a φ( n ) são os inteiros positivos menores que
n que são relativamente primos com n , então
aa1 , aa 2 ,..., aa φ( n )
são congruentes módulo n com a1 , a 2 ,..., a φ ( n ) em qualquer ordem.
Demonstração: Observe que não há dois inteiros aa1 , aa 2 ,..., aa φ( n ) que são congruentes
módulo n . Para aa i ≡ aa j (mod n) , com 1 ≤ i < j ≤ φ(n) , então a lei do cancelamento
permite que a i ≡ a j (mod n) , daí a i = a j
que é um absurdo. Além disso, como
mdc(a i , n) = 1 para todo i e mdc(a, n) = 1 , o fato de φ ser uma função multiplicativa garante
que cada aa i é relativamente primo de n.
Para um aa i particular existe um único inteiro b , onde 0 ≤ b < n , para o qual
aa i ≡ b(mod n) . Como
mdc(b, n) = mdc(aa i , n) = 1
b deve ser um dos inteiros a1 , a 2 ,..., a φ( n ) .
Teorema 3 (Teorema de Euler): Se n ≥ 1 e mdc(a, n) = 1 , então a φ( n ) ≡ 1(mod n) .
Demonstração: Não há problema em pegar n > 1 . Seja a1 , a 2 ,..., a φ( n ) os inteiros positivos
menores que n que são relativamente primos com n . Como mdc(a, n) = 1 , segue do lema
que aa1 , aa 2 ,..., aa φ( n ) são congruentes, não necessariamente em ordem de aparência, com
a1 , a 2 ,..., a φ ( n ) . Logo
aa1 ≡ a1' (mod n)
aa 2 ≡ a 2' (mod n)
M
M
'
aa φ( n ) ≡ a φ( n ) (mod n)
onde a1' , a 2' ,..., a φ' ( n ) são os inteiros a1 , a 2 ,..., a φ ( n ) em alguma ordem qualquer. Fazendo o
produto dessas φ(n) congruências, têm-se
(aa1 )(aa 2 )...(aa φ( n ) ) ≡ a1' a 2' ...a φ' ( n ) (mod n)
≡ a1 a 2 ...a φ( n ) (mod n)
e então
a φ( n ) (a1 a 2 ...a φ( n ) ) ≡ a1 a 2 ...a φ( n ) (mod n)
FAMAT em Revista - Número 12 - Abril de 2009
85
Como o mdc(a i , n) = 1 para cada i , então pela função φ ser multiplicativa implica que
mdc(a1 a 2 ...a φ ( n ) , n) = 1 . Logo, pode-se dividir os dois lados da congruência pelo fator comum
a1 , a 2 ,..., a φ ( n ) , deixando apenas
a φ( n ) ≡ 1(mod n)
Definição 3: Para um número real arbitrário x , nós denotamos por [x ] o maior inteiro menor
ou igual a x ; ou seja, [x ] é o único inteiro que satisfaz x − 1 < [x] ≤ x .
Aplicação na Criptografia
Criptografia: Do grego Kryptos significando “escondido” e graphein significando “escrever”,
ou seja, é a ciência de fazer as comunicações ininteligíveis para todos exceto órgãos
autorizados.
Na linguagem de criptografia, os códigos são as cifras e a informação neles escondidos é
chamado texto plano. Após a transformação do texto plano em sua forma secreta, este passa
a ser chamado texto cifrado.
Criptografia de Júlio César: Um dos primeiros sistemas de criptografia, usado pelo grande
imperador romano Júlio César por volta de 50 anos A.C. Este sistema usava uma substituição
rudimentar de cifras, o qual consistia de apenas de substituir cada letra do alfabeto pela letra
3 posições abaixo no alfabeto, com as últimas 3 letras correspondentes as 3 primeiras
respectivamente, ou seja, em ciclo. Representando o texto plano e o texto cifrado
correspondente, têm-se:
Texto plano:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Texto cifrado:
DEFGHIJKLMNOPQRSTUVWXYZABC
Por exemplo, a mensagem
FAMAT EM REVISTA
é transformada no texto cifrado
IDPDW HP UHYMVWD
O método de César pode facilmente ser descrito usando-se teoria das congruências.
Expressando o texto plano numericamente transferindo os caracteres do texto em dígitos
através da seguinte relação
A
B
C
D
E
F
G
H
I
J
K
L
M
00
01
02
03
04
05
06
07
08
09
10
11
12
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
13
14
15
16
17
18
19
20
21
22
23
24
25
Se P é o dígito equivalente a uma letra do texto plano e C é o dígito equivalente a letra no
texto cifrado, então
C ≡ P + 3(mod 26)
Por exemplo, convertendo-se as letras da mensagem para seus correspondentes numéricos
05 00 12 00 19 04 12 17 04 21 08 18 19 00
Usando-se a congruência acima, obtêm-se
08 03 15 03 22 07 15 20 07 24 11 21 22 03
Para recuperar a mensagem a partir de um texto cifrado, basta usar a congruência
P ≡ C − 3 ≡ C + 23(mod 26)
O método de César é muito simples e extremamente inseguro. Um sistema de criptografia no
qual cada letra é substituída por uma mesma cifra é conhecido como cifra monoalfabética.
Este tipo de criptografia é extremamente vulnerável aos métodos estatísticos de ataque já que
o método preserva a freqüência de letras individuais. Um sistema polialfabético seria aquele
86
FAMAT em Revista - Número 12 - Abril de 2009
que uma mesma letra do texto plano corresponde a diferentes cifras inclusive em uma mesma
mensagem.
Método da palavra chave: Este método foi publicado pelo Criptográfo Blaise de Vigenère
(1523-1596) em Traicté de Chiffres de 1586. O método de Blaise é um sistema polialfabético
, para implementar este sistema ambas partes comunicantes combinariam o uso de uma
palavra ou frase de fácil recordação. Com o alfabeto transformado em dígitos conforme a
tabela anterior, os dígitos equivalentes a “palavra-chave” é repetido quantas vezes
necessárias sob os dígitos correspondentes ao texto plano. A mensagem então seria
codificada através da adição, módulo 26, de cada número do texto plano com o número
imediatamente abaixo dele. Para ilustrar o processo usa-se a palavra-chave MAT, a qual tem
versão numérica 12 00 19. Seja a mensagem
CRIPTOGRAFIA
Cujo equivalente numérico é 02 17 08 15 19 14 06 17 00 05 08 00, usando-se do método
têm-se
02 17 08 15 19 14 06 17 00 05 08 00
12 00 19 12 00 19 12 00 19 12 00 19
quando as colunas são adicionadas módulo 26 têm-se
14 17 01 01 19 07 18 17 19 17 08 19
convertendo em cifras
ORBBTHSRTRIT
Note que uma mesma letra do texto plano é representada por mais de uma letra diferente no
texto cifrado (observe o I), o fato de que para o A e R repetiram foram meras coincidências,
tudo depende da escolha da palavra chave.
Em geral, qualquer seqüência de n letras com equivalentes numéricos b1 , b2 ,..., bn
(00 ≤ bi ≤ 25)
servirá como palavra-chave. O texto plano da mensagem é representado como
blocos sucessivos P1 P2 ...Pn de n inteiros de dois dígitos Pi , e então convertido para o texto
cifrado cujos blocos são C1C 2 ...C n por meio das congruências
C i ≡ Pi + bi (mod 26) 1 ≤ i ≤ n
A decodificação é pelas relações
Pi ≡ C i − bi (mod 26) 1 ≤ i ≤ n
Por causa da distribuição das letras do texto cifrado em relação ao texto plano ser tão
obscura o sistema foi pensado como “inquebrável”, porém a fraqueza no métode de Vigenère
é que uma vez determinado o tamanho n da palavra-chave, uma mensagem criptografada
pode ser recuperada como sendo feita de n cifras monoalfabéticas, sendo feito a análise de
freqüência de cada uma.
Método de Lester Hill: Em 1929, Lester Hill, um professor de matemática assistente no
Colégio Hunter criou um método de Criptografia que se baseava em dividir o texto plano em
blocos de n letras (possivelmente completando o último bloco por letras determinadas, X
por exemplo), e então codificar bloco por bloco usando um sistema linear de n congruências
com n variáveis. Numa forma simples ( n = 2 ) o procedimento seleciona duas letras
sucessivas e transforma seus equivalentes numéricos P1 P2 em um bloco C1C 2 de números
do texto cifrado através do par de congruências
C1 ≡ aP1 + bP2 (mod 26)
C 2 ≡ cP1 + dP2 (mod 26)
Para permitir a decodificação, os 4 coeficientes a, b, c, d devem ser selecionados de modo
que mdc(ad − bc,26) = 1 .
Para ilustrar o método de Hill, considere as congruências
FAMAT em Revista - Número 12 - Abril de 2009
87
C1 ≡ 2 P1 + 3P2 (mod 26)
C 2 ≡ 5 P1 + 8 P2 (mod 26)
para codificar a mensagem BUY NOW. O primeiro bloco BU de duas letras é
numericamente equivalente a 01 20, de acordo com o quadro anterior. Substituindo
2(01) + 3(20 ) ≡ 62 ≡ 10(mod 26)
5(01) + 8(20) ≡ 165 ≡ 09(mod 26)
Continuando duas letras por vez, encontram-se os números do texto cifrado
10 09 09 16 16 12
que pode ser expresso alfabeticamente por KJJ QQM.
Decodificação requer a resolução do sistema original de congruências para P1 e P2 em
termos de C1 e C 2 . Logo
P1 ≡ 8C1 − 3C 2 (mod 26)
P2 ≡ −5C1 + 2C 2 (mod 26)
Para o bloco 10 09 do código, calcula-se
P1 ≡ 8(10) − 3(09) ≡ 53 ≡ 01(mod 26)
P2 ≡ −5(10) + 2(09) ≡ −32 ≡ 20(mod 26)
Que correspondem as letras originais BU. O restante do texto plano pode ser restaurado de
maneira similar.
Criptografia de chave-pública: Nos métodos anteriores o emissor e o receptor da mensagem
conheciam o código secreto da codificação, a chave do método, e somente eles. No método
de chave pública existem duas chaves, uma pública liberada para qualquer um que desejar
enviar a mensagem ao receptor conseguir codificar e uma secreta para decodificação que
apenas o receptor conhece.
Método RSA de Criptografia: Em 1977, R. Rivest, A. Shamir e L. Adleman propuseram um
método de chave pública que usa somente idéias elementares de teoria dos números. A
segurança do método depende da corrente tecnologia computacional, a fatoração de números
compostos com grandes números primos é com certeza cansativa.
Cada usuário do sistema RSA escolhe um par de primos distintos, p e q , grandes o
suficiente para que a fatoração de seu produto n = pq , chamado de módulo codificador, vai
além de qualquer capacidade computacional. Por exemplo, pode-se escolher p e q com 200
dígitos cada, deste modo n terá em torno de 400 dígitos. Selecionado n , o usuário escolhe
um inteiro positivo qualquer k , o expoente codificador, de modo que satisfaça
mdc(k , φ(n)) = 1 . O par (n, k ) é colocado em um arquivo público, análogo a uma lista
telefônica, como chave de codificação para os usuários. Isto permite que qualquer um, na
rede de comunicação, codifique uma mensagem e envie ao receptor. Note que apesar de n ser
acessível a todos, isto não significa que os fatores p e q sejam, p e q fatores primos de n .
O processo de codificação se inicia com a conversão da mensagem em um inteiro M por
meio do alfabético digital abaixo no qual cada letra, número ou símbolos do texto plano é
substituído por um inteiro de dois dígitos.
88
FAMAT em Revista - Número 12 - Abril de 2009
A=00
K=10
U=20
1=30
B=01
L=11
V=21
2=31
C=02
M=12
W=22
3=32
D=03
N=13
X=23
4=33
E=04
O=14
Y=24
5=34
F=05
P=15
Z=25
6=35
G=06
Q=16
,=26
7=36
H=07
R=17
.=27
8=37
I=08
S=18
?=28
9=38
J=09
T=19
0=29
!=39
com 99 indicando espaço entre palavras. Neste esquema, a mensagem
THE BROWN FIX IS QUICK
é transformada para o número inteiro
M = 1907049901171422139905142399081899162008021027
Assume-se que M < n , onde n é módulo codificador. Do contrário seria impossível
distinguir M de qualquer inteiro maior que seja congruente a ele módulo n . Quando a
mensagem é muito longa para ser analisada como um único número M < n , então M é
quebrado em blocos de dígitos M 1 , M 2 ,..., M s de tamanho apropriado. Cada bloco é
codificado separadamente.
Usando da chave pública (n, k ) , o emissor codifica a mensagem do número M (que
representa o texto plano) e transforma em número do texto cifrado r elevando M a k -ésima
potência e reduzindo o resultado módulo n , ou seja
M k ≡ r (mod n)
Uma mensagem de 200 caracteres pode ser codificada em segundos em um computador de
alta velocidade. Lembrando que o expoente codificador k foi originalmente selecionado pela
condição mdc(k , φ(n)) = 1 . Apesar de existir muitas escolhas boas para k , uma sugestão
óbvia é de escolher k como sendo um número primo maior que p e q .
Por outro lado, para determinação da chave de codificação, primeiro determina-se o inteiro
j , o expoente de recuperação secreto, para o qual
kj ≡ 1(mod φ(n))
Já que mdc(k , φ(n)) = 1 , esta congruência linear tem uma solução única módulo φ(n) . De
fato, o algoritmo euclidiano produz j como solução da equação
kx + φ(n) y = 1
O expoente de recuperação pode somente ser calculado por alguém que conhece p e q ,
fatores primos de n . Logo, j é desconhecido para todos com exceção do receptor. Logo,
com a chave de decodificação determinada pode se recuperar o número M à partir de r
simplesmente calculando r j módulo n . Já que kj = 1 + φ(n)t para algum inteiro t , segue-se
que
( )
j
(
)
t
r j ≡ M k ≡ M 1+ φ( n ) t ≡ M M φ( n ) ≡ M ⋅ 1t ≡ M (mod n)
de acordo com o Teorema 3 acima e sempre que mdc( M , n) = 1 . Em outras palavras,
elevando-se o número do texto cifrado a j -ésima potência e reduzindo módulo n recuperase o número original M correspondente ao texto plano.
Teve-se que assumir que mdc( M , n) = 1 para poder usar o Teorema 3 (Teorema de Euler).
No caso em que M e n não sejam relativamente primos, um argumento similar estabelece
FAMAT em Revista - Número 12 - Abril de 2009
que
r j ≡ M (mod p )
e
89
r j ≡ M (mod q ) , o que nos dá a congruência desejada
r j ≡ M (mod n) .
A maior vantagem deste método é que a codificação de uma mensagem não requer o
conhecimento dos dois primos p e q , mas somente de seu produto n , ou seja, não há
necessidade de ninguém além do receptor da mensagem saber os fatores primos essenciais
para a decodificação.
O método direto de ataque ao método seria a tentativa de fatoração de n , um inteiro de
grande magnitude. Uma vez que seus fatores forem determinados, o expoente recuperador j
pode ser calculado a partir de φ(n) = ( p − 1)(q − 1) e k . Porém essa fatoração dependerá da
capacidade computacional e do tamanho de n , quanto maior mais difícil a fatoração.
Aplicação nos Calendários
Nosso calendário, o calendário Gregoriano, vem desde a segunda metade do século XVI.
1
O calendário anterior, introduzido por Júlio César, foi baseado em um ano de 365 de dias,
4
com um ano bissexto de 4 em 4 anos. Esta não foi uma medida precisa porque o ano solar é
de aproximadamente 365,2422 dias. Este pequeno erro fazia com que o calendário de César
pulasse um dia a cada 128 anos.
Por volta do século XVI, o erro acumulado fez com que o 1º dia da primavera caísse dia
11 de março em vez do dia correto, 21 de março. O papa Gregório XIII corrigiu essa
discrepância em um novo calendário, imposto nos principais países católicos da Europa. Foi
decretado que 10 dias seriam omitidos no ano de 1582, fazendo com que 15 de outubro
viesse logo depois de 4 de outubro daquele ano. Os anos bissextos seriam os anos divisíveis
por 4, exceto aqueles que fosse anos centenários. Anos centenários só seriam bissextos se
fossem divisíveis por 400.
Objetivo: Dado uma data após o ano de 1600 deve-se determinar a qual dia da semana esta
data corresponde usando Teoria dos Números.
Método: Como o dia adicionado no ano bissexto é 29 de fevereiro, vamos adotar como 1º de
março sendo o primeiro dia do ano e o último dia de fevereiro como sendo o último dia do
ano. De acordo com isso, no ano Y março e abril são os primeiro e segundo mês do ano,
respectivamente. Janeiro e fevereiro do ano Y+1 são contados como o 11º e o 12º mês do ano
Y. Outra conveniência é designar os dias da semana por:
Domingo
Segunda
Terça
Quarta
Quinta
Sexta
Sábado
0
1
2
3
4
5
6
O número de dias de um ano comum é 365 ≡ 1(mod 7) , em anos bissextos existem
366 ≡ 2(mod 7) dias. Por 28 de fevereiro ser o 365º dia do ano, e 365 ≡ 1(mod 7) , 28 de
fevereiro sempre cai no mesmo dia da semana que o anterior 1º de março do mesmo ano.
Logo, o próximo 1º de março é um dia da semana depois do 1º de março do ano anterior.
Mas se o próximo 1º de março é depois de 29 de fevereiro, o dia da semana correspondente
deve ser somado 2 módulo 7.
Seja D1600 , o dia da semana que representa o dia 1º de março do ano de 1600, então o 1º
de março dos anos 1601, 1602, 1603 é dado por D1600 + 1 , D1600 + 2 e D1600 + 3 ,
respectivamente.
Logo, o dia primeiro de março de um ano Y( DY ) é dado por:
D y ≡ D1600 + (Y − 1600) + L(mod 7)
90
FAMAT em Revista - Número 12 - Abril de 2009
Onde L é o número de dias de anos bissextos entre 1º de março de 1600 e 1º de março do ano
Y. O número de anos n no intervalo de 1600 < n ≤ Y que são divisíveis por 4 é dado por:
 Y − 1600   Y
 Y 
=  − 400 =   − 400


4
 4
 4
O número de anos centenários é dado por:
 Y − 1600   Y
  Y 
 100  = 100 − 16 = 100  − 16
Dentre esses o número de anos bissextos são:
 Y − 1600   Y
  Y 
 400  =  400 − 4 =  400  − 4
Logo, o valor de L é dado por:
 Y 
  Y 
  Y 
 Y   Y   Y 
L =    − 400  −  
− 16  +  
− 4  =   − 


+
 − 388
4
  100 
   400 
  4  100   400 
Considerando-se o fato de que D1600 (1º de março de 1600) caiu numa quarta-feira:
DY ≡ 3 + (Y − 1600) + L(mod 7)
Uma fórmula alternativa para L pode ser feita escrevendo Y como:
Y = 100c + y
0 ≤ y < 100
c: número de séculos e y denota o número de anos daquele século. Substituindo:
y 
y  c
y 

 y c
L = 25c +  − c +
+ +
− 388 = 24c +   +   − 388


4   100   4 400 

 4  4
Logo, a congruência DY aparece como:
 y c
DY ≡ 3 + (100c + y − 1600) + 24c +   +   − 388(mod 7)
 4 4
Que se reduz a:
c   y
DY ≡ 3 − 2c + y +   +   (mod 7)
4  4 
Referências Bibliográficas
-
Burton, M. David- Elementary Number Theory- Ed. McGraw Hill- 5ª edição-2004