Relatório Discretos 2018 2

Prévia do material em texto

Universidade Federal de 
Pernambuco 
DEPARTAMENTO DE ELETRÔNICA E SISTEMAS – DES
 
Sistemas Discretos
Projeto 1
Grupo: 
Matheus Batista de Araújo
João Victor Belo
Matheus José Araújo Oliveira
Sumário 
 Introdução ................................................ 2
 Fundamentação teórica............................ 3
 Metodologia ............................................. 4
4. Análise ...................................................... 5
5. Conclusão ................................................. 
6. Apêndice.....................................................
7. Anexo..........................................................
1. Introdução
O presente trabalho visa se aprofundar sobre os assuntos da primeira unidade da disciplina e algumas de suas aplicações, em específico, para este projeto, sobre a estruturação e funcionamento do protocolo de comunicação para se jogar “cara-ou-coroa” à distância.
	O protocolo foi criado em 1981, por Blum, e visava como já sugere o nome, permitir que duas pessoas pudessem jogar “cara-ou-coroa” à distância, impedindo trapaças durante jogo.	
2 
2. Fundamentação Teórica
	Para a realização deste projeto, foi necessário cumprirmos algumas tarefas básicas para a implementação do Protocolo de comunicação usado no “cara-ou-coroa” à distância, era necessário que gerássemos números primos e encontrássemos suas raízes primitivas.
	Primeiramente, a fim de facilitar as explicações a seguir, consideremos “A” como o número que estamos usando como exemplo para nossa análise. 
Podemos definir um número primo como “Um número que é divisível por apenas 4 números (o resto da divisão de A por estes números será 0).
 Divisores de A = {1, -1, A, -A}
Agora, nos direcionando ao conceito de raiz primitiva, temos que A é uma raiz primitiva se “a ordem de A módulo n = phi(n)”.
Ord(A) mod n = φ (n)
	Para entendermos a condicional acima, temos de explicar o que é ordem e o que é a função phi de n (função Totiente).
	A função Totiente, retorna o quantidade de números relativamente primos a n, menores que n. Ou seja, vamos assumir que n = 8, os números menores que 8 que são relativamente primos à 8 são {1,3,5,7}, logo phi(8) = 4.
	Dois números são relativamente primos se o MDC entre A e B é igual a 1, (A,B) = 1. 
	Por definição, phi(A) = A-1 se A é um número primo, pois o único número que dividirá A será o próprio A.
	
Com relação à ordem de um número, podemos defini-la da seguinte forma: 
 Sendo A e n, números inteiros, onde n é positivo e A é relativamente primo à n, definimos que a Ord(a) mod n é o menor inteiro positivo T, que cumpre 	.
		
	Para gerarmos um número primo, foi necessário utilizar de técnicas como o Teorema de Fermat, um teste de composição, para testar se o número que estávamos analisando era composto, caso o mesmo não fosse havia uma maior chance de que ele fosse um número primo.
	Se , então A é um número composto
	Caso contrário, não podemos afirmar nada, porém a chance de A ser primo é maior.
	Outra alternativa para adquirirmos números primos é através do Teste de Miller Rabin, onde utilizaríamos o número A (número que estamos analisando) para encontrar as soluções de uma equação diofantica, dessa forma saberemos que A é primo se as únicas soluções encontradas forem 1 e -1.
				 
Se A é primo, X só pode assumir os valores de 1 e -1. 
3 
Metodologia
Soluções teóricas e exemplos
Aqui estarão as soluções teóricas solicitadas nas atividades do projeto, as demais soluções de atividades estão nas seções de anexo e apêndice (já estão embutidas no código). 
Atividade A 
	Item 4 – 
Atividade B
	Item 2 – A operação de multiplicação com BIG NUMBERS pode ser feita da mesma forma que multiplicação de números binários, vamos supor que temos 2 BIG NUMBERS, N1 e N2, onde o tamanho de N1 é n e o tamanho de N2 é (2048 – n) , logo se fizermos a multiplicação de N1 por N2, ambos vetores binários completamente preenchidos por 1 ( maior valor possível para cada um, o que também gerará o maior vetor resultado possível para o tamanho solicitado de 2048 bits), temos que :
	
	 11111..1 <- N1
 x 1111..1 <- N2
	 111.......1
 + 11111........1 <- o tamanho do deslocamento das casas será de n-1.
11111111...........1 <- o tamanho do vetor resultante será no máximo 2048 (o tamanho será o 
 tamanho de N1 + tamanho de N2) .
	Item 3 – Assim como a operação de multiplicação, a operção de adição de BIG NUMBERS também pode ser feita como operação de números binários, vamos supor que temos 2 BIG NUMBERS, N1 e N2, ambos de mesmo tamanho n e preenchidos completamente por 1 (maior valor possível para N1 e N2), desta forma, se fizermos a soma de N1 e N2 teremos:
	 11111......1 <- N1
	+11111......1 <- N2
	111111......1 <- o vetor resultante possuirá tamanho (n+1) pois haverá um carry out
			 devido à soma do ultimo bit (bit mais a esquerda) dos vetores. 
Atividade D
	Item 2 – Utilizando o código criado no item 1, pudemos constatar que os números (, são números primos, enquanto o número ( é composto.
4 
4. Análise
5
	5.Conclusão
13 
6. Apêndice
Atividade 1
#codificando o texto
Def cod(texto):
texto_l = list(texto)
 i = codig = 0
 r = len(texto_l)
 n = a = texto_l
 for i in range(0,r):
 a[i] = ord(texto_l[i])
if a[i] == 32:
 a[i] = 123
 n[i] = a[i]%27
codig = codig + n[i]*27**i
 i = i+1
return codig
texto = input('digite o texto:')
print(cod(texto))
------------------------------------------------
#decodificando o texto
Def des(codig):
 i = 0
texto_d = ""
while codig != 0:
 a = codig % 27
codig = codig//27
if 15 < a < 27:
 a = a + 81
elif 0 <= a < 15:
 a = a + 108
elif a == 15:
 a = 32
 a = chr(a)
texto_d = texto_d[:i] + a
 i = i+1
return texto_d
codig = int(input('digite o codigo: '))
print(des(codig))
Atividade 2
#a estrutura BIG NUMBER ja existe no ambiente de desenvolvimento python, constituindo o BIG NUMBER de uma string de inteiros.
#retornando o tamanho de um big number em bits
def tamanho(numero):
count = 0
while count<= 2048:
if 2**count>numero:
return count
 break
else:
count+=1
if count>2048:
print('O tamanho do número inserido ultrapassa 2048 bits')
#soma de dois big numbers de acordo com o limite imposto
Def adicao(numero1, numero2):
if tamanho(numero1) != None:
if tamanho(numero2) != None:
if tamanho(numero1)==2048 & tamanho(numero2)==2048:
print('O valor da soma ultrapassa 2048 bits')
else:
 resultado = numero1 + numero2
return resultado
#multiplicacao de dois big numbers
Def multB(numero1, numero2):
if tamanho(numero1) != None:
if tamanho(numero2) != None:
if tamanho(numero1)+tamanho(numero2) <= 2048:
 resultado = numero1 * numero2
return resultado
else: print('O valor da multiplicacao ultrapassa 2048 bits')
#divisao de dois big numbers
Def divisao(numero1, numero2):
if tamanho(numero1) != None:
if tamanho(numero2) != None:
 resultado = numero1 // numero2
return resultado
#reducao a modulo de big numbers
Def mod(numero1, modulo):
if tamanho(numero1) != None:
if tamanho(modulo) != None:
 resultado = numero1 % modulo
return resultado
#provando que se tamanho(numero1) + tamanho(numero2) <= 2048, tamanho(numero1*numero2) <= 2048
''' assim como numa multiplicação binaria (assumindo que usamos ate o maior valor possível, ou seja: [1...1] ) se multiplicarmos um vetor binário N1 de tamanho N por um vetor binário N2 detamanho (2048-N), o resultado será um vetorde no máximo tamanho 2048 '''
#provando que a soma de dois big numbers de tamanho N, resultara num big number de tamanho N ou N+1
''' assim como a soma de dois números binários, assumindo dois vetores de mesmo tamanho N, [1...1],a soma resultara num vetor de tamanho N+1, pois o bit mais significativo poderá ter um carry out,gerando mais 1 bit para o vetor '''
Atividade 3
import atividade2
importmath
tamanho = atividade2.tamanho
adicao = atividade2.adicao
multB = atividade2.multB
divisao = atividade2.divisao
mod = atividade2.mod
mdc = math.gcd
defaddmod(a,b,n):
 resultado = mod(adicao(mod(a,n),mod(b,n)),n)
return resultado
#adicao de 'a' e 'b' modulo 'n' tem q ser bignumber
defmulmod(a,b,n):
 resultado = mod(multB(mod(a,n),mod(b,n)),n)
return resultado
#multiplicaçao de 'a' e 'b' modulo 'n' tem q ser bignumber
defexpmod(a,b,n): 
 i = 0
 lista = []
whileb != 0:
 c = b % 2
 b = b//2
if c == 1:
 d = mod(a,n)
 for k in range(i):
 d = mulmod(d,d,n)
lista.append(d)
 i+=1
whilelen(lista) > 1:
lista[-2] = mulmod(lista[-2],lista[-1],n)
lista.pop()
 resultado = lista[0]
return resultado
#'a' modulo 'n' elevado a segunda potencia tem q ser bignumber
definvmod(a,n):
ifmdc(a,n) == 1:
 for i in range(n):
 b = mulmod(a,i,n)
if b == 1:
return i
 break
else:
print('O número', a, 'não possui inversa módulo', n)
#sendo 'a' e 'n' bignumbers, nao há restriçoes de tamanho
Atividade 4
import atividade3
expmod = atividade3.expmod
def testePrimo(n):
 k = 1
 c = n-1
 t = 0
while c % 2 == 0:
 c = c // 2
 t+=1
 for a in range(2,n):
 r = expmod(a,c,n)
 for i in range(t):
rAnt = r
 r = expmod(r,2,n)
if r == 1 andrAnt != 1 andrAnt != n-1:
print('O número é composto')
 k = 0
 break
else:
ifr != 1:
print('O número é composto')
 k = 0
if k == 0:
 break
else:
 p = (1 - (0.25)**(n-1))*100
print(n, 'tem uma probabilidade de', p, '% de ser primo')
7. Anexo
 
Cara ou coroa a distância
#para o jogador A...
from random import randint
def gerador_primo(d):
 while d == 1:
 a = randint(1000,10000)
 b = 4*a - 1
 d = teste_primo(b)
 return b
def teste_primo(b):
 c = 2
 while c < b:
 if b % c == 0:
 d = 1
 break
 elif b % c != 0:
 d = 0
 c += 1
 return d
def gerador_n():
 p = gerador_primo(1)
 q = gerador_primo(1)
 n = p * q
 return n, p, q
def calculo_raizes(p, q, n, a):
 a = int(a)
 v = (int(p) + 1) / 4
 z = (int(q) + 1) / 4
 x1 = (a ** v) % n
 x2 = (a ** z) % n
 y1 = 0
 y2 = 0
 while (q*y1 - 1) % p != 0:
 y1 += 1
 while (p*y2 - 1) % q != 0:
 y2 += 1
 x01 = (x1*q*y1 + x2*p*y2) % n
 x02 = (x1*q*y1 - x2*p*y2) % n
 x03 = (-x1*q*y1 + x2*p*y2) % n
 x04 = (-x1*q*y1 - x2*p*y2) % n
 return x01, x02, x03, x04
print('gerando p e q automaticos...')
a = gerador_n()
print('p = ', a[1])
print('q = ', a[2])
print('n = ', a[0])
print('\nenvie o n para o jogador b...')
a1 = input('digite o valor de a recebido do jogador b: ')
print('calculando raizes...')
r = calculo_raizes(a[1], a[2], a[0], a1)
print('raizes possiveis: ', r)
print('escolha uma das 4 raizez anteriores e envie para o jogador b...')
#para o jogador b...
def teste_primo(b):
 c = 2
 while c < b:
 if b % c == 0:
 d = 1
 break
 elif b % c != 0:
 d = 0
 c += 1
 return d
def teste_n(n):
 d = teste_primo(n)
 if d == 1:
 k = 0
 elif d == 0:
 if n % 2 == 0:
 k = 0
 elif n % 2 != 0:
 k = 1
 if k == 0:
 print('n nao valido!')
 elif k == 1:
 print('n valido!')
 return k
def achar_a(x, n):
 if (x**2) < n:
 a = (x**2) + n
 elif (x**2) > n:
 a = (x**2) % n
 return a
 
n = input('digite o valor de n passado pelo jogador a: ')
print('testando n...')
k = teste_n(n)
if k == 1:
 x = input('escolha um numero entre 0 e n:')
 a = achar_a(x, n)
 print('envie o valor de a para o jogador a...')
 r = input('entre com a raiz escolhida pelo jogador a: ')
 if r == x || r == -x:
 print('voce perdeu')
 elif r != x && r != -x:
 print('voce ganhou')
else :
 print('n invalido!!')