##
## Algoritmos de Criptoanalise do metodo RSA
##

## Metodo da "forca bruta" -  ou seja, vai-se tentar a divisao sucessiva
## por todos os numeros primos ate ao maior inteiro contido em raiz 
## quadrada de n.  
##
## -> n, o inteiro a factorizar 
## <- resp, o primeiro factor primo encontrado
function resp=Divisoes(n)
  ## calculo do limite
  limite=floor(sqrt(n));
  ## vector com todo os primos ate ao limite
  c=crivoEratostenes(limite);
  ## numero de primos obtidos
  nprimos=columns(c);
  i=0;
  ## assume-se que nao existe nenhum factor primo
  resp=0;
  ## ciclo de teste, desde o primeiro ate ao penultimo primo
  do
    i=i+1;
    if(mod(n,c(i))==0)
      resp=c(i);
    endif
  until (i>=nprimos || mod(n,c(i))==0)
  ## teste para o ultimo primo
  if (i>=nprimos && mod(n,c(nprimos))==0)
    resp=c(nprimos);
  endif
endfunction


## Utilizacao da formula 6k+1 e 6k-1 para determinar
## numeros primos. Como esta formula gera tambem numeros
## alguns dos casos nao representam tentativas reais. Vai-se 
## testar ate ao maior inteiro contido em raiz quadrada
## de n.
## 
## -> n
## <- resp, o primeiro factor primo
function resp=Divisoes1(n)
  limite=floor(sqrt(n));
  resp=0;
  ## testa para 2 e para 3
  if (mod(n,2)==0) resp=2; endif
  if (mod(n,3)==0) resp=3; endif
  ## de 6*1-1=5 ate ao limite
  p=5;
  while (p<=limite && resp==0)
    ## testa 6k-1 e 6k-1+2=6k+1
    if (mod(n,p)==0) resp=p; endif
    if (mod(n,p+2)==0) resp=p+2; endif
    p=p+6;
  endwhile
endfunction

## Metodo de Euclides 
## Utilizacao do Algoritmo de Euclides para a determinacao
## do mdc entre dois numeros para obter um factor primo de n
## Multiplicam-se todos os primos de 2 ate ao maior inteiro 
## contido em raiz quadrada de n, de seguida determina-se o
## mdc entre esse produto e n, o resultado e o primeiro factor
## primo de n.
## Para obstar às dificuldades de representar o numero obtido da 
## multiplicacao divide-se essa tarefa em partes.
##
## -> n
## <- resp, o primeiro factor primo
function resp=Euclides(n)
  ## calculo do limite 
  limite=floor(sqrt(n)); 
  ## vector com todo os primos ate ao limite
  c=crivoEratostenes(limite);
  ## numero de primos obtidos
  nprimos=columns(c);
  ## inicializacao das variaveis que controlam a construcao dos
  ## conjuntos auxiliares (de 10 em 10)
  passo=10;k=1;i=1;si=passo;
  ## inicializa o vector dos produtos so com 1s (elemento neutro
  ## da multiplicacao)
  prods=ones(1,limite);
  ## calculo dos produtorios (guardados no vector "prods")
  while (i<=nprimos)
    if (c(i)>si)
      si=si+passo;
      k=k+1;
    endif
    prods(k)=prods(k)*c(i);
    i=i+1;
  endwhile
  m=1;i=1;
  ## calculo do mdc entre os produtorios e n
  while (i<=k && m==1) 
    m=mdc(prods(i),n);
    if (m!=1)
      resp=m;
    endif
    i=i+1;
  endwhile	
endfunction

## Metodo de Fermat - consiste em encontrar dois inteiros a e b
## que permitam representar n como a diferenca de dois quadrados
## n=a^2-b^2 o que significa n=(a-b)(a+b), ou seja temos de imediato
## os factores primos que pretendiamos
## 
## -> n
## <- resp=[a,b] 
function resp=Fermat(n)
  ## comeca-se por tomar a = (maior inteiro contido em raiz 
  ## quadrada de n) + 1
  a=floor(sqrt(n))+1;
  ## se a e um quadrado entao a resposta e [a,a]
  if (issqr(n))
    resp=[a,a];
  else # senao
    do    
      b=a^2-n;
      ## se b=raiz quadrada(a^2-n) e um inteiro entao a resposta
      ## e [a,b]
      if (issqr(b))
        resp=[a,sqrt(b)];
      endif
      ## senao incrementa-se a de uma unidade e recomeca-se
      a=a+1;
    until (issqr(b)) # ate que b seja um inteiro
  endif
endfunction

## Crivo de Eratostenes - constroi o vector com todos 
## os numeros primos menores ou iguais a n.
##
## -> n
## <- primos, vector de numeros primos menores que n
function primos=crivoEratostenes(n)
  ## comeca por construir um vector de 2 a n
  crivo=2:n;
  k=n-1;
  prox=1;
  nprimos=0;
  ## vai fazer n-1 vezes o seguinte
  while (prox<n-2)
    ## determina o primeiro elemento do
    ## vector, esse e primo
    while ((prox<=n-1) && (crivo(prox)==0))
      prox=prox+1;
    endwhile
    ## coloca-o no vector de primos
    if (prox<=n-1)
      nprimos=nprimos+1;
      primos(nprimos)=crivo(prox);
    endif
    aux=prox;
    ## vai retirar (coloca igual a zero) esse
    ## numero assim como todos os seus
    ## multiplos (os quais nao sao primos).
    while (aux<=n) 
      crivo(aux)=0;
      aux=aux+primos(nprimos);
    endwhile
  endwhile
endfunction


## Algoritmo de Euclides para a determinacao do mdc 
## (Donald Knuth. The Art of Computer Programming, Volume 2)
## Dados dois numeros naturais a e b, e assumindo que a e maior ou 
## igual que b, verifica-se se b e zero. Se sim, a e' o mdc., senao
## repete-se o processo usando b e o resto da divisao inteira de
## a por b.
##
##
## -> a,b, com a>=b
## <- e,  o maximo divisor comum entre m e n
function e= mdc(a,b)
  
  resto(1)=mod(a,b);
  resto(2)=mod(b,resto(1));
  
  prox=2;
  while ( resto(prox) != 0)
    prox= prox + 1;
    resto(prox)= mod(resto(prox-2),resto(prox-1));
  endwhile
  e=resto(prox-1);
endfunction


## Algoritmo de Euclides para a determinacao do mdc 
##
## implementacao de acordo com a versao original de Euclides, 
## baseia-se nas seguintes propriedades do mdc
##
## mdc(a,b) = a,          se a=b
##            mdc(a,b-a), se a<b
##            mdc(a-b,b), se a>b
##
## -> a,b
## <- res=mdc(a,b)
function res=mdcEuclides(a,b)
  while (a != b)
    if a > b
      a=a-b;
    else
      b=b-a;
    endif
  endwhile
  resp=a;
endfunction

## Funcao auxiliar para verificar se um dado x e' (ou nao) um quadrado
## perfeito.
function y=issqr(x)
  y=floor(sqrt(x))^2==x;
endfunction