quinta-feira, 15 de março de 2012

Aritmética do relógio

Você sabia que é possível desenvolver uma aritmética observando um relógio de parede. Essa aritmética é chamada de aritmética modular. A aritmética modular é utilizada em teoria dos números, teoria dos grupos, álgebra abstrata, criptografia, ciência da computação, música etc. 

Primeiro, vamos observar um relógio com o ponteiro das horas sobre o número 12.

Qual é a posição do ponteiro depois de 3 horas? Na aritmética usual, faríamos 12 + 3 = 15. Observe que depois do número 12, os números acabam e começam novamente no 1. Na aritmética do relógio é diferente, 12 + 3 = 3.
Imagine o ponteiro sobre o número 12 novamente, qual é a posição do ponteiro depois de 15 horas? Na aritmética usual, faríamos 12 + 15 = 27.  Na aritmética do relógio, 12 + 15 = 3 horas. Observe que o relógio dá uma volta completa e para sobre o número 3.
Imagine o ponteiro sobre o número 12 novamente, qual é a posição do ponteiro se voltarmos 9 horas? Observe que novamente, o ponteiro terminará sobre o número 3.
Observando a aritmética do relógio, o número 3 é equivalente ao número 15 . O conjunto de todos os números equivalentes ao número 3 é:
|3| = { 3 + 12k : k Z} = {...,-21,-9,3,15,27,...} (1)
Observe que esse conjunto é formado pelos números com o mesmo resto na divisão por 12. O conjunto descrito em (1) é o conjunto solução da seguinte equação modular:
x = 3 (mod 12) ou x mod 12 = 3

Seja a e b dois números inteiros, então a = b (mod 12) se somente se a-b é múltiplo de 12.

Aritmética modular
Essa aritmética continua valendo para um relógio com n horas com as seguintes propriedades:
1. (a+b) mod n = (a mod n + b mod n) mod n
2. (a-b) mod n = (a mod n - b mod n) mod n
3. (a*b) mod n = (a mod n * b mod n) mod n
4. (a/b) mod n = (a mod n * b-1 mod n) mod n

Aplicações
Divisibilidade
A sua tarefa é, dado um número positivo N com 1000 dígitos, determinar se ele é um múltiplo de onze.
#include <stdio.h>
#include <string.h>
int main(){
    char n[1001];
    int d;
    while(1){
    scanf("%s",n);    
    if(strcmp(n,"0")==0) break;
    //Algoritmo da divisao
    d = 0;
    for(int i=0;n[i]!='\0';i++){        
        d = d*10 + n[i]-'0';
        d = d %11;
    }
    if(d==0)
      printf("%s is a multiple of 11.\n",n);
    else
        printf("%s is not a multiple of 11.\n",n);
    }
    return 0;
} 
 
Critografia RSA

Passo 1: Escolha dois números primos grande p e q.
Passo 2:Calcule n = p*q 
Passo 3: Calcule = (p-1)(q-1) 
Passo 4: Publique a chave pública (e,n)
Passo 5: Guarde a chave privada (d,n)
Passo 6: Cifrar mensagem(a)
   C(a) = ae  mod n
Passo 7: Decifrar mensagem(m)
  D(a) = ad mod n
     
    Observe que tanto a operação de cifragem como a operação de
    decifragem utiliza a potenciação modular.
     Algoritmo 1 an mod m
int exp1(int a, int n , int m){
  int i,res;
  res = 1;
  for(i=1;i<=n;i++)
  res = res*a;
  return res%m;
} 

Desvantagens: facilidade na ocorrência do overflow. Podemos reduzir evitar a
ocorrência do overflow utilizando a propriedades da aritmética modular.
Algoritmo 2: an mod m
int exp2(int a, int n , int m){
  int i,res;
  res = 1;
  for(i=1;i<=n;i++)
  res = (res*a%m)%m;
  return res%m;
}
Desvantagens: número de multiplicações O(n)  
    Exponenciação Modular Rápida
    an  mod m =(a (n/2) mod m)2 mod m , n é par e n > 0
    an  mod m = a mod m* a(n-1) mod m , n é impar e n > 0
    amod m = 1          , caso contrário

    Algoritmo 3: an  mod m
  int fastexpmod (int a, int n, int m){
    if(n==0) return 1;
    else if(n%2==0){
    int x = fastexpmod(a,n/2,m);
    return (x*x)%m; 
    }else{
     return (a%m*fastexpmod(a,n-1,m))%m;
    }
  }
 
 

Nenhum comentário: