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.

http://br.spoj.pl/problems/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

    a0  mod 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;

    }

  }