Logaritmo discreto

O problema do logaritmo discreto é encontrar o valor de x  dado a, b e n tal que

 $a^{x} = b (mod n)$

O algoritmo básico seria calcular todas as potências de  a,a^2,a^3,...,  até encontrar o valor b.

O algoritmo Shanks basea-se na reescrita de x como $x = im + j$, com $m = ceil (sqrt(n) )$ , $0<=i
$a^{im + j} = b$
$a^{im} a^{j} = b$
$a^{j}  = b(a^{-m})^{i}$

O algoritmo pré-computa $a^{j}$ para alguns valores de j. Para cada valor de i, ele testa se existe algum j que

$a^{j}        = b(a^{-m})^{i}$

Se sim, devolve o valor im+j
Se não, passa para o próximo valor de i

Pseudo-código

1. m ← Ceiling(√n)
2. para todo j onde 0 ≤ j < m:
   1. Compute α^j mod n and armazene o par (j, α^j) em uma tabela. 
3. Compute α^−m mod n
4. γ ← β. (set γ = β)
5. For i = 0 to (m − 1):
   1. verifique se existe γ como a segunda componente (α^j) de algum par na tabela.
   2. Se sim, devolva im + j.
   3. If não, γ ← γ • α^−m mod n

Código

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

int n,a,b,m;
int g;

typedef struct {
 int index;
 int value;
} table; 

//função que calcula o mdc estendido ax + by = mdc(a,b)
int mdc(int  a, int b, int *x, int *y);

//calcula o inverso multiplicativo modulo n
//a*x = 1 mod n
int inverso(int a, int n);

//algoritmo de exponeciacao rapida modular
int fastexp(int a,int b, int n);

//busca binaria do valor g no vetor giant de tamanho n
int busca_binaria(int g, int n, table giant[]);

//funcao usada no qsort
int compara(const void *a, const void *b);

int shanks(int a, int b, int n){
 
 int g,m,r;
 int i,j;
 

 m = (int)ceil( sqrt(n) );
 
 printf("valor de m: %d\n",m);
 
 table giant[m];
 
 a = a%n;
 b = b%n;
 
 giant[0].index = 0;
 giant[0].value = 1;
 
 //Passo de Gigante
 for(j=1;j<m;j++){
  giant[j].index = j;
  giant[j].value = (giant[j-1].value*a)%n;
 }
 
 qsort(giant, m , sizeof(table), compara );
 
 //Passo de Gigante
 printf("Passo gigante\n");
 for(j=0;j<m;j++){
   printf("%d %d\n",giant[j].index, giant[j].value);
 }
 
 r = fastexp(inverso(a,n),m,n);
 g = b;
 
 //Passo de Baby
 printf("Passo de bebe\n");
 for(i=0;i<m;i++){
  printf("g: %d\n",g);
  j = busca_binaria(g,m,giant);
  if( j!=-1 ){
    printf("j: %d\n", giant[j].index); 
    return i*m + giant[j].index;
  }else{
   g = (g*r)%n;
  }
 }    

}

int main(){
 
 int j;
 int r;
 
 scanf("%d %d %d",&a,&b,&n);

 printf("%d\n",shanks(a,b,n));
 
 return 0; 

}

int mdc(int  a, int b, int *x, int *y) {
  int xx, yy, d;
  if(b==0) {
    *x=1; *y=0;
    return a;
  }

  d = mdc(b, a%b, &xx, &yy);
  *x = yy;
  *y = xx - a/b*yy;
  return d;
}


int inverso(int a, int n){
  int x,y,d;
  d = mdc(a,n,&x,&y);
  if(x<0){
    x = x+n;
  }
  return x;
}

int fastexp(int a,int b, int n){

  long long int x;

  if(b==0) return 1;
  if(b==1) return a;

  if(b%2==0){
    x = fastexp(a,b/2,n)%n;
    return (x*x)%n;
  }else{
    return (a*fastexp(a,b-1,n))%n;
  }

}

int compara(const void *a, const void *b){
 return ((table*)a)-> value - ((table*)b)->value;
}

int busca_binaria(int g, int n, table giant[]){
 int i,f;
 int m;
 
 i = 0;
 f = n-1;

 while(i<=f){
  m = (i+f)/2;
  if(giant[m].value == g) return m;
  else if(giant[m].value > g){
   f = m-1;
  }else {
   i = m+1;
  }
 }
 
 return -1;
  
}

Saída

5 315 317

valor de m: 18

Passo gigante

0 1

1 5

2 25

8 81

9 88

6 92

10 123

3 125

7 143

17 154

13 159

14 161

15 171

16 221

12 222

5 272

11 298

4 308

Passo de bebe

i 0 g: 315

i 1 g: 303

i 2 g: 219

i 3 g: 265

i 4 g: 270

i 5 g: 305

i 6 g: 233

i 7 g: 46

i 8 g: 5

j: 1

145

Pressione qualquer tecla para continuar. . .

$log_{5} 315 = mi + j = 18(8) + 1 = 145 $

A complexidade deste algoritmo é O($\sqrt(n) lg \sqrt(n)$)

Calculadora de logaritmos discretos
http://www.numbertheory.org/php/discrete_log.html


Referências:
http://en.wikipedia.org/wiki/Baby-step_giant-step
http://pastebin.com/F8Nin82x
http://pt.scribd.com/doc/63892535/38/Algoritmos-para-PLD