Praticando a Aritmética   Lacerda [www.souexatas.blogspot.com.br] [materialcursoseconcursos.blogspot.com.br]
649 pág.

Praticando a Aritmética Lacerda [www.souexatas.blogspot.com.br] [materialcursoseconcursos.blogspot.com.br]


DisciplinaEstatística I20.436 materiais107.007 seguidores
Pré-visualização50 páginas
para quebra´-los. A histo´ria e´ marcada por co´digos que de-
cidiram o resultado de batalhas, como na 2a Guerra Mundial, com os alema\u2dces
\u201cMain\u201d
2006/12/15
page 168
168 [CAP. 4: TEORIA DOS NU´MEROS PRIMOS EM N
utilizando a ma´quina ENIGMA, na guerra entre a Pe´rsia e Gre´cia (narrada por
Hero´doto), provocando a morte de reis e rainhas (Maria, rainha da Esco´cia,
1586). Para quebrar um co´digo eficiente e´ preciso deter conhecimento em di-
versas a´reas, como tecnologia, matema´tica, religia\u2dco, teoria qua\u2c6ntica e outras,
ou seja ser multidisciplinar.
Na tentativa de se desenvolver co´digos eficientes o homem fez va´rias tenta-
tivas como por exemplo a esteganografia, que consistia em ocultar a mensagem.
Uma maneira muito usada era a de esconder uma mensagem dentro de um ovo
cozido fazendo uma tinta com uma onc¸a de alume e um quart ilha de vinagre
enta\u2dco escrevendo na casca do ovo. A soluc¸a\u2dco penetra na casca porosa e deixa a
mensagem sobre a clara endurecida do ovo. E´ claro que tal procedimento era
vulnera´vel, pois bastava o acesso a` mensagem para se conhecer o seu conteu´do.
Portanto houve a evoluc¸a\u2dco da criptografia (KRIPTOS - OCULTO), onde o seu
objetivo na\u2dco e´ ocultar a existe\u2c6ncia da mensagem, mas esconder o seu signifi-
cado. A vantagem da criptografia e´ que se o inimigo descobrir a mensagem, o
mesmo ainda tera´ que decodifica´-la.
O me´todo mais conhecido de criptografia e´ o RSA, inventado por R.L.Rivest,
A.Shamir e L. Adleman, que trabalhavam no M.I.T em 1978. Este me´todo faz
parte de muitos outros co´digos de chave pu´blica (os co´digos modernos sa\u2dco todos
de chave pu´blica, criados para fins comerciais e na\u2dco de espionagem). O fato de
que a chave e´ pu´blica na\u2dco significa que o me´todo e´ fraco, uma vez que nesses
tipos de co´digos saber codificar na\u2dco implica em saber decodificar.
O Algoritmo RSA e´ fundamentado nos seguintes princ´\u131pios:
1o ) Selecione dois nu´meros primos (p e q), preferencialmente grandes;
2o ) Calcule n e z, sabendo que n = p × q e z = (p \u2212 1)× (q\u2212 1);
3o ) Escolha d, supondo d e z primos entre si;
4o ) Determine e tal que, e× d \u2261 1(mod. z)
I) Criptografando uma mensagem M.
Fac¸a C \u2261Md(mod. n)
II) Descriptografando a mensagem M.
Fac¸a M \u2261 Cd(mod. n)
Conclusa\u2dco: Para criptografarmos e´ necessa´rio que saibamos os nu´meros e e n,
e para descriptografarmos e´ necessa´rio sabermos d e n.
\u201cMain\u201d
2006/12/15
page 169
[SEC. 4.26: EXERC´ICIOS RESOLVIDOS 169
Obs.:
1a ) e e n fazem parte da \u201cchave pu´blica\u201d;
2a ) d e n fazem parte da \u201cchave privada\u201d.
A grande dificuldade para obtermos d, a partir de e e n, esta´ na fatorac¸a\u2dco
de nu´meros grandes. Supondo o tempo me´dio por instruc¸a\u2dco de 1 microsse-
gundo, um computador levaria 4 bilho\u2dces de anos para fatorar um nu´mero de
200 algarismos; 1025 anos para fatorar um nu´mero de 500 algarismos. Mesmo
levando 1 nanosegundo (realidade atual), levaria muito tempo para fatorar.
Ex:. Seja criptografar a letra S (cod 19).
Resoluc¸a\u2dco:
1o ) Admitamos dois primos pequenos: p = 3 e q = 11;
2o ) n = 3× 11 = 33;
3o ) z = (3\u2212 1)× (11\u2212 1) = 20;
4o ) Seja d = 7, um dos nu´meros primos entre si com 20;
5o ) Como 7× e \u2261 1(mod. 20)
6o ) Criptografando: C \u2261 193(mod. 33)
7o ) Descriptografando: M \u2261 287(mod. 33) \u2261 19(mod. 33)
Neste exemplo foi fa´cil fatorar n = 33 e obter p, q e z. Conhecendo-se z,
obtemos d usando o algoritmo de Euclides.
4.26 Exerc´\u131cios Resolvidos
1) Sendo N =
2x × 3× 52
2
,
a) determinar x de modo que N possua 30 divisores.
A expressa\u2dco acima pode ser escrita da forma:
N = 2x\u22121 × 31 × 52
De acordo com os dados, temos:
QD(N) = 30, da´\u131,
(x\u2212 1+ 1)× (1+ 1)× (2+ 1) = 30
6x = 30 \u2234 x = 5
\u201cMain\u201d
2006/12/15
page 170
170 [CAP. 4: TEORIA DOS NU´MEROS PRIMOS EM N
b) determinar N
Se x = 5, enta\u2dco, N = 25\u22121×31×52 ou N = 24×31×52 \u21d2 N = 16×3×25
N = 1.200
c) determinar a quantidade de divisores pares de N.
QDp(N) = 4× (1+ 1)× (2+ 1) = 4× 2× 3 \u2234 QDp(N) = 24
d) determinar a quantidade de divisores \u131´mpares (QDi(N)) de N.
QDi(N) = (1+ 1)× (2+ 1) = 2× 3 \u2234 QDi(N) = 6
e) determinar a quantidade de divisores na\u2dco primos de N.
Na decomposic¸a\u2dco de N, ou seja, N = 24 × 31 × 52, ve\u2c6-se que existem 3
fatores primos na base, sa\u2dco eles: 2, 3 e 5. Subtraindo do total de divisores
(30) esses tre\u2c6s fatores, temos que a quantidade de divisores na\u2dco primos de N e´
30\u2212 3 = 27.
f) determinar a quantidade de divisores mu´ltiplos de 2.
N = 24 × 31 × 52
QD(2\u2d9) = 4+ 4× 1+ 4× 2+ 4× 1× 2 \u2234 QD(2\u2d9) = 24
Obs.: Esse resultado tambe´m pode ser obtido do seguinte modo:
24 × 31 × 52
2
= 23×31×52 \u21d2 QD(2\u2d9) = (3+1)×(1+1)×(2+1) \u2234 QD(2\u2d9) = 24
g) determinar a quantidade de divisores mu´ltiplos de 3.
1o modo:
QD(3\u2d9) = 1+ 1× 4+ 1× 2+ 1× 4× 2 \u2234 QD(3\u2d9) = 15
2o modo:
QD(3\u2d9) =
24 × 31 × 52
3
= 24 × 52
QD(3\u2d9) = (4 + 1)× (2+ 1) = 15
h) determinar a quantidade de divisores mu´ltiplos de 10.
QD(1\u2d90) =
24×31×52
10 = 2
3 × 31 × 51
QD(1\u2d90) = (3+ 1)× (1+ 1)× (1+ 1) \u2234 QD(1\u2d90) = 16
\u201cMain\u201d
2006/12/15
page 171
[SEC. 4.26: EXERC´ICIOS RESOLVIDOS 171
2) Determinar o nu´mero de divisores de N = 125 × 457.
125 × 457 = (22 × 31)5 × (32 × 51)7 = 210 × 35 × 314 × 57 = 210 × 319 × 57
QD(N) = (10+ 1)× (19+ 1)× (7+ 1) = 11× 20× 8
QD(N) = 1.760
3) Determinar todos os divisores \u201cinteiros\u201dde 12.
Em ordem crescente temos, mentalmente:
{\u221212,\u22126,\u22124,\u22123,\u22122,\u22121,+1,+2,+3,+4,+6,+12}
No´tula: Observando esse exemplo, pode-se concluir que, para determinarmos
o nu´mero de divisores inteiros, basta multiplicarmos o nu´mero de divisores por
2.
4) Determinar o nu´mero de divisores inteiros de 120.
Como 120 = 23 × 31 × 51 enta\u2dco, o nu´mero de divisores inteiros de 120 e´
igual a 2× (3+ 1)× (1+ 1)× (1+ 1) = 32
5) Determinar o menor nu´mero natural com 10 divisores.
Dois sa\u2dco os fatores no sistema decimal que, multiplicados, geram o produto
igual a 10.
Sa\u2dco eles:
1× 10 e 2× 5
1o ) 1× 10 = (v+ 1)(w+ 1)\u21d2
\uf8f1\uf8f2\uf8f31 = v+ 1 \u2234 v = 010 = w+ 1 \u2234 w = 9
2o ) 2× 5 = (x + 1)(y+ 1)\u21d2
\uf8f1\uf8f2\uf8f32 = x+ 1 \u2234 x = 15 = y+ 1 \u2234 y = 4
Como estamos a determinar o menor nu´mero, esses pares de valores devera\u2dco
ser substitu´\u131dos nos expoentes dos dois menores nu´meros primos, ou seja, o 2
e o 3. Assim sendo, teremos:
N1 = 2
9 × 30 \u21d2 N1 = 512× 1 \u2234 N1 = 512
N2 = 2
4 × 31 \u21d2 N1 = 16× 3 \u2234 N2 = 48
Conclusa\u2dco: O menor nu´mero e´ o 48.
\u201cMain\u201d
2006/12/15
page 172
172 [CAP. 4: TEORIA DOS NU´MEROS PRIMOS EM N
6) Calcular o nu´mero de primos entre si com:
a) 23, menores que 23;
b) 30, menores que 30;
c) 81, menores que 81;
d) 360, menores que 360;
a) N = 23
\u3d5(23) = 23\u2212 1
\u3d5(23) = 22
b) N = 30
30 = 2× 3× 5
\u3d5(30) = (2 \u2212 1)× (3\u2212 1) × (5\u2212 1)
\u3d5(30) = 8
c) N = 81
N = 34
\u3d5(81) = 34\u22121 × (3\u2212 1) = 33 × 2
\u3d5(81) = 54
d) N = 360
360 = 23 × 32 × 5
\u3d5(360) = 23\u22121 × 32\u22121 × 51\u22121 × (2\u2212 1)× (3\u2212 1)× (5\u2212 1)
\u3d5(360) = 96
7) Determinar o nu´mero de vezes que o fator primo 3 aparece na decomposic¸a\u2dco,
em fatores primos, do produto dos trezentos primeiros nu´meros naturais, a
partir de 1.
Resoluc¸a\u2dco:
Seja 1× 2× 3× · · ·× 298× 299× 300, a multiplicac¸a\u2dco que gera tal produto.
Como nos mu´ltiplos de 3 o fator (3), e´ claro, aparece em sua decomposic¸a\u2dco,
apenas ira\u2dco nos interessar os fatores que contenham esses mu´ltiplos, ou seja:
3× 6× 9× · · · × 297× 300\ufe38 \ufe37\ufe37 \ufe38
100 fatores
Decompondo-se, convenientemente, os fatores anteriormente \u201csubchavea-
dos\u201d, teremos:
\u201cMain\u201d
2006/12/15
page 173
[SEC. 4.26: EXERC´ICIOS RESOLVIDOS 173
3× 1× 3× 2× 3× · · · × 3× 99× 3× 100\ufe38 \ufe37\ufe37 \ufe38
200 fatores
Ve\u2c6-se que de 3× 1 ate´ 3× 100 o fator 3 aparece 100 vezes, logo a expressa\u2dco
anterior pode, tambe´m, ser escrita da forma:
3100 × 1× 2× 3 · · · × 100\ufe38 \ufe37\ufe37 \ufe38
100 fatores
Daqui por diante, raciocinaremos de modo ana´logo ao que ja´ foi feito ante-
riormente. Assim sendo, a expressa\u2dco anterior ficara´:
3100 × 3× 6× 9× · · · × 99\ufe38 \ufe37\ufe37 \ufe38