RLM- Sucessão e Sequências

Respostas

LICEU - MATEMÁTICA - frente A - Equação e Inequações Modulares e frente B – Teorema de Pitágoras e teorema dos senos e cosenos

Segue o material da revisão da aula de 06/08.
frente A - Equação e Inequações Modulares
frente B – Teorema de Pitágoras e teorema dos senos e cosenos 
Link para Download: Aula1-3 bimestre

Revisão de Radiciação - Liceu

Segue o material da revisão.
Segue o link para download: MATERIAL DA AULA1

Revisão de Razões e Proporções e Geometria plana - Liceu

Segue o material da revisão.

Frente A - Razões e Proporções.

Frente B - Introdução a Geometria Plana.

Segue o link para download: MATERIAL DA AULA

Revisão de PA e PG - Liceu

Segue o material de PA e PG

Link: MATERIAL DA AULA

Algoritmos Matemáticos - Protocolo para a Distribuição de Chaves Secretas

Quando se adota o método de chaves secretas, é recomendável não utilizar por muito tempo a mesma. Quando ideal é a cada nova sessão uma nova chave seja estabelecida. Mas como estabelecer a chave ao início de cada sessão? Como evitar as escutas? Cifrar a mensagem? Com que chave? Aqui apresenta-se uma solução para ilustrar o conceito de funções unidirecionais.  A função a ser usada é a exponencial módulo de um número, isto é, dados os inteiros 'a', 'x' e 'n', seja ~x)=aAx mod n (n>O, x>=O). Assim, ftx) é o resto da divisão de aAx por n. O cálculo desta função é viável. O procedimento abaixo mostra uma maneira de calcular esta função :

Procedimento expomod (a,x,n,r:inteiro); {r possui o resultado da função}

declare y, c :  tipo inteiro

inicio

r:= l; 

y:=x; 

c:=a mod n; 

   

    enquanto y>O faça inicio

        se ímpar(y) então

            r=r*c mod n; 

            y=y div 2;             

            C=C 2 mod n;

       fim;

fim;

  Suponha que dois usuários A e B desejam manter uma conversa sigilosa através de chave secreta. As duas partes escolheram um número primo grande , p' da ordem de 10A 100, e já concordaram também em utilizar uma base , a'. Preferivelmente deve ser uma raiz primitiva de p, de modo que ffx)=aAx mod p é uma b~eção sobre o conjunto 1..p-l dos naturais x tais que l<=x<=p-l. Para iniciar o estabelecimento da chave, A gera ao acaso um expoente x no intervalo 1..p- l e B gera outro, y Usando expomod, A calcula ffx) e B ffy). Então A envia pela rede ffx) e B envia ffy). De posse de y e ffx), B calcula, usando

expomod :

K = [(ffx)]Ay mod p = (aAx mod p)Ay mod p = aA(xy) mod p = K.

Da mesma forma, A usa expomod e de posse de x e ffy) calcula:

k = [(ffy)]AX mod p = (aAy mod p)AX mod p = aA(xy) mod p - - K.

Assim A e B chegam a um número comum K, que será a chave de ciframento para as mensagens.

Suponha um espião bem informado que obtenha os valores de a e p e, através de escuta, os valores de f(f(x)) e de f(f(y)). Para determinar K, ele precisa determinar a função logaritmo módulo p, que é intratável. Mesmo A não é capaz de determinar o valor de y e B o valor de x. A função expomod é unidirecional sem segredo, permite a A e B trocarem uma chave secreta utilizando a própria rede. 

Algoritmos Matemáticos para calcular números primos - algoritmo AKS

O algoritmo AKS

No teste de Monte Carlo, se testarmos todas as possibilidades de r, poderemos afirmar se um número é primo. No entanto, isso é inviável para p grande. Logo, se fosse possível achar um sub-conjunto de valores para r quando aplicados ao teste nos fornecesse uma resposta certa, então teríamos um teste determinístico em P. É isso que faz o algoritmo AKS.

Input: Integer n > 1

1. if (n = ab with b > 1) then output COMPOSITE;

2. r := 2;

3. while (r < n) {

4. if (gcd(n,r) is not 1) then output COMPOSITE;

5. if (r is prime greater than 2) then {

6. let q be the largest factor of r-1;

7. if (q > 4sqrt(r)log n) and not(n(r-1)/q 1 (mod r)) then

8. break;

9. r := r + 1;

10. }

11. for a := 1 to 2sqrt(r)log n {

12. if not( (x-a)n (xn-a) (mod xr-1,n) ) then output COMPOSITE;

13. }

14. output PRIME;

As linhas de 1 a 10 funcionam como um filtro para descartar muitos valores que não influem na decisão de primalidade, dados certos princípios algébrico já conhecido.

Na primeira linha, é necessário aplicar um algoritmo que detecte potências perfeitas em tempo polinomial.

A linha 4, verifica se o máximo divisor comum de dois inteiros n e r é diferente de 1.

Note que se n for primo, mdc(n, r) = 1 para qualquer r < n. Já na linha 5, é preciso determinar se o número r é primo por força bruta (todos os valores até sua raiz quadrada), pois se for usado algum algoritmo probabilístico (comum nas linguagens matemáticas como Maple e Matlab), então estaremos tornando o AKS também probabilístico.

A linha 6 determina o maior fator primo de r-1 (q) sendo r primo.

Na linha 12, vemos a aplicação do Pequeno Teorema de Fermat. Considere C(n, p) = n! / p!(n-p)!, n primo diferente de 2 e a co-primo de n. Então, temos que:

(x-a)n = - C(n,0)x0an + C(n,1)x1an-1 + ... - C(n,n-1)xn-1a1 + C(n,n)xna0 =

= -an + C(n,1)x1an-1 + ... - C(n,n-1)xn-1a1 + xn

Como C(n, i) 0 (mod n) (divisível por n) para i [1, n-1], temos em módulo n que:

(x - a)n -an + xn (xn - an) (xn - a) (mod n)

Já se n for composto, então ele terá um fator primo q. Considere qk a maior potência de q que divide n (n = rqk). Então, temos que o binômio de xi quando i = qk:

C(n, i) = n!/i!(n-i)! = (qkr)!/qk!(qkr-qk)! =

= (qkr)(qkr-1)!/(qk)(qk-1)!(qkr-qk)! = (r)(qkr-1)!/(qk-1)!(qkn-1)!

E este binômio não é divisível por n=rqk (igual a zero módulo n) e, por isso, n é composto. Isto é facilmente verificável dividindo-se os binômios de uma linha n do Triângulo de Pascal por n e constatando que todos são divisíveis se e somente se n é primo.

0: 1

1: 1 1

2: 1 2 1

3: 1 3 3 1

4: 1 4 6 4 1

5: 1 5 10 10 5 1

6: 1 6 15 20 15 6 1

7: 1 7 21 35 35 21 7 1

8: 1 8 28 56 70 56 28 8 1

9: 1 9 36 84 126 126 84 36 9 1

10:1 10 45 120 210 252 210 120 45 10 1

Os binômios da linha n são divisíveis por n quando este é primo.

O problema desta abordagem é que quando n for muito grande, calcular todos os n-1 binômios o pior caso, C(n, n-1)0 (mod n) será muito custoso. Alterando a congruência para módulo xr-1, implicitamente, faz-se o teste apenas para os r últimos termos de (x - a)n, ou seja, i [n-r, n-1].

No entanto, agora, alguns compostos n podem equivocadamente satisfazer a congruência da linha 12 para alguns valores de (a, r) e, por isso, são testados separadamente na linha 2.

O algoritmo primeiro escolhe um r primo para obter q, o maior fator primo de r-1, tal que este r delimita um intervalo onde certamente haverá um fator primo de n se este for composto.

Em seguida, o algoritmo testa a congruência para a [1, 2r1/2log(n)], uma quantidade de testes realizáveis em tempo polinomial no pior caso. Este é justamente o avanço feito por este algoritmo.

Algoritmos Matemáticos para calcular números primos - Teste de primitividade de Miller-Rabin

Teste de primitividade de Miller-Rabin

O teste Miller-Rabin (por Gary Miller e Michael O. Rabin) é um teste probabilístico da primitividade de um dado número n. Se um número n não passar pelo teste, n com certeza é um número composto (ou seja, não-primo). Se o número passar no teste, ele é primo, com uma probabilidade , sendo que denomina o conjunto de todos números primos. A margem de erro pode ser diminuída aleatoriamente, aplicando-se o teste várias vezes ao mesmo número n.

O teste é parecido com o o teste Solovay-Strassen, portanto sua margem de erro é bem menor.

A importância desse algoritmo se deve à criptografia asimétrica, onde a necessidade de uma grande quantidade de números primos grandes é vital para a segurânça dos algoritmos. Tais números são tão grandes que testes não probabilisticos como o da simples divisão por números primos menores que o número gerado ou o tabelamento de todos os números primos são impraticáveis.

É importante dizer que o teste Miller-Rabin, ou Rabin-Miller como as vezes também é chamado, não dá indícios sobre a fatorização no número n. Devido suas caraterísticas, esse teste é o mais utilizado para o teste da primitividade.

Funcionamento

Seja n um número primo e a um número inteiro escolhido aleatoriamente, tal que 1 < a < p. Seja , s é o maior expoente, tal que .

Seja d = (n − 1) / 2^s. Por definição de s, d é, necessariamente ímpar.

Teorema: Se n é um número primo e a não tiver um divisor em comum com p, então ou, existe um , tal que Um número a que não satisfaz o teorema acima é denominado de testemunha contra a primitividade de n.

Algoritmos Matemáticos para calcular números primos -GIMPS

(Great Internet Mersenne Prime Search) ou GIMPS é o grupo de busca de números primos de Mersenne. Este grupo de pesquisa busca grandes números primos, utilizando para isso a fórmula matemática de Mersenne. O Gimps utiliza um software instalado em microcomputadores onde através de uma computação em cluster (Sistema de processamento distribuído) divide o processo entre todos os computadores que tenham o software instalado. O usuários utilizam ou Prime95 ou MPrime. Mersenne investigou um tipo particular de número: 2p − 1 em que P é um número primo.

Maiores Números Primos de Mersenne.

Atualmente o maior número primo conhecido é um primo de Mersenne, com 9.808.358 [1] algarismos.

Ranking dos Maiores Números Primos

rank	prime	digits	who	when	reference
1	232582657-1	9808358	G9	2006	Mersenne 44??
2	230402457-1	9152052	G9	2005	Mersenne 43??
3	225964951-1	7816230	G8	2005	Mersenne 42??
4	224036583-1	7235733	G7	2004	Mersenne 41??
5	220996011-1	6320430	G6	2003	Mersenne 40??
6	213466917-1	4053946	G5	2001	Mersenne 39?
7	27653.29167433+1	2759677	SB8	2005	Mersenne 38?

Algoritmos Matemáticos para calcular números primos -Números de Mersenne

Algoritmo para testar a primalidade de números de Mersenne

Os números da forma Mⁿ = 2ⁿ-1 com n um número primo são chamados de números de Mersenne, a sua consideração deriva do estudo de números perfeitos (um número perfeito, é um número cujo resultado da soma dos seus divisores naturais é ele mesmo; por exemplo o número 6 tem como divisores 1,  2,  3 e 1+2+3=6, 28 tem como divisores 1, 2, 4, 7, 14 e 1+2+4+7+14=28) efectuado por Marin Mersenne.

Algoritmo:

Mⁿ =2ⁿ + 1 é um número primo se e só se Mⁿ divide Sn-2, com (Sk)k1, uma sucessão definida recursivamente por : 

S0= 4, Sk+1=Sk² -2. 

Algoritmos Matemáticos para calcular números primos - Teorema de Green-Tao

Na matemática, o teorema de Green-Tao, demonstrado por Ben Green e Terence Tao em 2004, afirma que a seqüência de números primos contém progressões aritméticas arbitrariamente longas. Em outras palavras, para cada número natural k, existe uma progressão aritmética formarda de k números primos.Generalizações

Em 2006, Tao e Tamar Ziegler generalizaram o resultado de forma a ser válido para progressões polinomiais. Mas precisamente, dado k polinômios de coeficientes inteiros, tais que , existem infinitos pares de inteiros números primos.

Construções

Dado que estes teoremas são de existência pura, eles não trazem qualquer informação sobre como encontrar tais sequências. Em 18 de janeiro de 2007, Aroslaw Wroblewski encontrou a primeira seqüência aritmética de primos com 24 termos:

468395662504823 + 205619 × 23# × n, for n = 0 to 23 (23# = 223092870).

Algoritmos Matemáticos para calcular números primos - Algoritmo de Pepin

Algoritmo de Pepin para testar a primalidade dos números de Fermat

Como os números de Fermat (Fⁿ  = 2^{2^n} +1) crescem muito rapidamente em função de n, torna-se muito laborioso testar a sua primalidade. No entanto, Pepin obteve em 1877 um algoritmo para testar a primalidade de números de Fermat.

Algoritmo de Pepin:

Seja Fⁿ  = 2^{2^n} +1, com n³2, e k³2. Então as seguintes condições são equivalentes: 

1. Fⁿ é um número primo e (k/ Fⁿ) = -1; 

2.  k^{(Fn -1)/2} -1 (mód.  Fⁿ ).

Este algoritmo é praticamente uma aplicação da fórmula de Euler para os factores de Fⁿ (Euler demonstrou que todos os factores de Fⁿ , com n³2, são da forma k x 2ⁿ⁺²+1 e através do qual descobriu que 641 divide F⁵ : F⁵ = 641 x 6 700 417) . No entanto se Fⁿ é composto, este não nos indica qualquer factor deste.

Algoritmos Matemáticos para calcular números primos - Algoritmo de Brillhart, Lehmer & Selfridge

Em 1927, Lehmer tornou o algoritmo de Lucas datado de 1891 mais prático, mas este foi ainda tornado mais flexivel por Brillhart, Lehmer & Selfridge em 1975: Seja N>1. Assuma-se que para cada factor primo q de N-1 existe um inteiro a = a(q)>1 tal que: 1. a^N-1 | | 1 (mód. N). 

        2. a^(N-1)/q | | 1 (mód.N).

Então N é um número primo.

Defeitos do algoritmo: mais uma vez, é necessário conhecer os factores primos de N-1, mas poucas congruências têm de satisfeitas.

Algoritmos Matemáticos para calcular números primos - Algoritmo de Lucas

Estes algoritmos são baseados no Pequeno Teorema de Fermat (para distinguir do  denominado Grande Teorema de Fermat).Que diz que: 
Seja n um número primo então para qualquer número inteiro a,
 tem-se que : a^p  | |a (mód. p)

Algoritmo de Lucas de 1876:

Seja N>1. Assuma-se que existe um inteiro a>1 tal que:

1. a^{N-1| |}1 (mód. N),
2. a^m | |1 (mód. N), para m =1,2, ..., N - 2.

Então N é um número primo.

Defeitos do algoritmo: pode parecer perfeito, mas requer N-2 sucessivas multiplicações por a, e a busca dos resíduos do módulo N : Demasiadas operações.

Algoritmo de Lucas de 1891:

Seja N>1. Assuma-se que existe um inteiro a>1 tal que:

1. a^N-1 | |1 (mód. N).
2. a^m | |1 (mód. N) para cada m<N, tal que m seja divisor de N-1.

Então N é um número primo.

Defeitos apresentados por este algoritmo: requer o conhecimento prévio de todos os factores de N-1, embora seja fácil de aplicar quando N é da forma N= 2ⁿ + 1 ou quando N=3.2ⁿ  + 1.

Algoritmos Matemáticos para calcular números primos - Crivo Erastotenes

Erastotenes (no século III a.C.) teve a brilhante ideia de organizar estas maravilhosas computações, na forma de um bem conhecido crivo. Tal crivo, serve para determinar todos os números primos, assim como as factorizações dos números compostos, até um dado número N. Vamos ilustrar para N= 101.

Método da Substituição – O código de César

Suetônio, escritor romano que viveu no início da era cristã (69 d.C.), em seu livro “Vida dos Césares”, escreveu a biografia dos imperadores romanos de Júlio César a Domiciano. Na publicação, o autor conta que Júlio César (100 – 44 a.C.) usava na sua correspondência militar uma chave de substituição muito simples, na qual cada letra da mensagem original era substituída pela letra que a seguia em três posições no alfabeto. A letra A era substituída pela D, a B pela E, e assim sucessivamente.
(Fonte: Http://www.numaboa.com.br/criptologia/cifras/transposicao/scytale.php)

Artifícios de trocar (transpor) as letras de posição no ato de encriptar as mensagens, como o exemplo ilustrado pelo Scytale, deram o nome de “Transposição” ao método criptográfico.

Veja o exemplo na Figura 3.

Olhe, em detalhes, o método criptográfico de Substituição que Júlio César usava para enviar mensagens a seus generais.
Na Figura 3, na primeira linha estão representadas as letras em ordem Alfabética.
Na segunda linha, a seqüência alfabética começa com a letra D, a terceira letra depois da letra A. Esta é a chave. Em seguida, acrescentamse as outras letras, terminando a segunda linha com as letras que foram esquecidas.
Outro exemplo é a mensagem “encontro confirmado sexta-feira”, encriptada com a chave de Júlio César, que ficaria assim:
“HQFRQWURFRQILUPDGRVHAWDIHLUD”.
Em homenagem ao imperador romano, chamamos de código de César qualquer cifra em que cada letra da mensagem original seja substituída por outra deslocada em um número fixo de posições, não necessariamente três.
Com um alfabeto de 26 letras, são possíveis 25 códigos distintos de César.
O número de casas deslocadas é a chave do código e a chave original de César tem o número 3.
(Fonte: UFF/Exercito brasileiro)

Exercício em chave 3
Yrfhhrfdud
Decifre?
Mande a resposta?

História da Criptografia Clássica: Método da Transposição – O Scytale

        A cidade-estado grega de Esparta, por volta do século V a.C., era uma sociedade na qual a democracia não era uma prática. A retórica e a cultura, tão bem cultuadas na vizinha cidade-estado de Atenas, passavam longe das preocupações de Esparta. Dominados por uma rígida cultura da guerra, os espartanos tinham grande preocupação com a segurança das comunicações militares. Isto impulsionou várias formas de codificar mensagens, sendo o “Scytale espartano” ou “Bastão de Licurgo” o exemplo mais notável desta época. Veja a Figura 1:

     Para que o interceptador tenha sucesso não basta apenas acessar a mensagem, é preciso descobrir o algoritmo e a chave.

      A técnica do Scytale foi descrita por Plutarco, ensaísta e biógrafo grego, em 90 d.C., no livro “Vidas de Homens Ilustres”. Era um bastão de madeira ao redor do qual enrolava-se firmemente, em forma de espiral, uma tira, de couro ou papiro, longa e estreita. O remetente escrevia a mensagem de modo vertical, em colunas, ao longo do bastão e depois desenrolava a tira, que se convertia em uma sequência de letras sem sentido. O mensageiro usava a tira como cinto, com as letras voltadas para dentro. O destinatário, ao receber o “cinto”, enrolava-o em seu bastão, cujo diâmetro e comprimento eram iguais ao do bastão do remetente. Desta forma, podia ler a mensagem.

Fonte:  UFF/Exercito Brasileiro.