Implementação do "problema de logaritmos discretos" em C/C++

[scherzo 0]

Olá, sou novo por aqui :natalbiggrin:

 

e estou com dificuldades para solucionar um problema: o conhecido problema dos logaritmos discretos resume-se a encontrar x dados A, B e N na equação:

 

B = A ^ x (mod N)

Tenho uma implementção em C utilizando a biblioteca MIRACL (_http://indigo.ie/~mscott/) para a solução deste problema, porém o que eu quero, na verdade, é: dado os valores de B, N e x, encontrar A de forma que satisfaça a equação acima.

 

Peço a ajuda de alguém para mostrar-me opções para a solução deste problema ou mesmo um "source code".

 

Grato desde já,

 

scherzo

[Palc 0]

beleza Scherzo,

 

Cara não sou expert nisso, é só uma idéia ok.

No 1o. caso: dados A, B e N e calcular x que satisfaça B = resto da div inteira de (A^x) por N , correto ?

a ) sempre B < N, pois numa divisão o resto ( B ) sempre é menor q o divisor ( N )

b ) A, B, N e x sempre inteiros

c ) vamos chamar de Q, também inteiro, o quociente da divisão (A^x) por N

Logo, Q . N + B = A^x pois o quociente ( Q ) vezes o divisor ( N ) mais o resto ( B ) é igual ao dividendo (A^x) -> básico da divisão lembra ?

 

Agora aplique logarítmo em ambos lados da equação: log ( Q . N + B ) = log ( A^x )

Aplique a propriedade dos log (q não lembro o nome) para tirar o x do expoente: log ( Q. N + B ) = x . log( A )

Isole o x da equação: x = log ( Q . N + B ) / log ( A )

A, B e N são dados porém Q não é, mas podemos chutar um valor para Q desde 0 até algum número e ir calculando x até chegarmos num x que seja inteiro, bem isso não interessa pois você já possui o algorítmo para este 1o. caso. http://forum.imasters.com.br/public/style_emoticons/default/joia.gif A idéia é q interessa e vai servir de base p/ o q você realmente precisa.

 

No 2. caso: dados x, B e N e calcular A que satisfaça B = ... (idem acima)

a ) , b ) e c ) ... (idem acima)

Logo, Q . N + B = A^x

 

Agora nem precisa usar logarítmo p/ isolar o A

A = ( Q . N + B ) ^ (1/x) que é a mesma coisa que A = raiz x de ( Q.N+B ) http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

 

B, N e x são dados porém Q não é, então chute valores para Q de 0 até um número e verifique se o resultado do A é inteiro. Qdo for páre pois achou o A que buscava.

 

Caso o processador não tenha raiz "n" mas só as 4 operações ( + - . / ), use o método de Newton para calcular a raiz. A idéia certamente é mais simples q no 1o. caso onde você teve que calcular o log :P

 

O método de Newton é iterativo porém muuuuito rápido, em poucas iterações (< 5) se chega num resultado, resumindo:

 

Imagine a função f(A), o método diz que os números que fazem essa função ser 0 (zero) convergem para um valor se fizermos:

Ai+1 = Ai - f(Ai)/f ' (Ai)

 

onde Ai+1 é o resultado da próxima iteração (i+1)

i é a iteração e vai de -1 até ... 5 por exemplo, pois em 5 ou 6 iterações se chega num resultado, se calcular a 7a. você vai ver q o resultado praticamente repete o da 6a. iteração

Ai é o resultado da iteração já calculada anteriormente

f(Ai) é o valor da função calculado para Ai

f ' (Ai) é o valor da derivada da função calculado para Ai

 

Se fizermos f(A) = A^x - ( Q.N+B ), a nossa equaçãozinha lá de cima, então f ' (A) = x.A^(x-1) sempre !

 

Quando tivermos fazendo as iterações,

f(Ai) = Ai^x - ( Q.N+B ) e

f ' (Ai) = x.Ai^(x-1)

Logo basta você fazer umas 5 ou 6 vezes o seguinte cálculo sempre aproveitando o resultado anterior:

Ai+1 = Ai - [ Ai^x - ( QN+B ) ] / [ x.Ai^(x-1) ] que ainda podemos simplificar e isolar alguns termos até obtermos,

 

Ai+1 = Ai . { 1 - (1/x) . [ 1 - ( QN+B ) / (Ai^x) ] } observe q podemos implementar facilmente só com as 4 operações http://forum.imasters.com.br/public/style_emoticons/default/joia.gif

 

A0 (chute inicial) pode ser 1 ou qq outro número

Repita esse cálculo para i=0 até 5 ou 6

 

Fiz uns testes para alguns valores numa planilha eletrônica para conferir:

Sem usar o método de Newton (processador com cálculo de raiz "x")

Dados: x=3; B=2; N=3

Equação q deve ser satisfeita: 2 = resto da div inteira de (A^3) por 3

Calcule o A que satisfaça a equação acima.

Nossa equação inserindo o Q: Q.3+2 = A^3

Fazendo Q=0 nossa equação fica: 0+2=A^3 logo A=1,2599... não serve pq não é inteiro

Fazendo Q=1 nossa equação fica: 1.3+2=A^3 logo A=1,7099... não serve pq não é inteiro

Fazendo Q=2 nossa equação fica: 2.3+2=A^3 logo A=2 ... :P achou !

Conferindo: 2 = resto da div inteira de (2^3) por 3 ? Claro q sim, pois 8 dividido por 3 é 2 e sobram 2 http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

 

Usando o método de Newton (processador só com 4 op.)

Dados: x=3; B=2; N=3

Equação q deve ser satisfeita: 2 = resto da div inteira de (A^3) por 3

Calcule o A que satisfaça a equação acima.

Nossa equação inserindo o Q: Q.3+2 = A^3

Fazendo Q=0 nossa equação fica: 0+2=A^3, usando o mét. d Newton para calcular A,

A0=1 (chute inicial)

A1 = A0 . { 1 - (1/x) . [ 1 - ( QN+B ) / (Ai^x) ] }

A1 = 1 . { 1 - (1/3) . [ 1 - (0 +2) / (1^3) ] } = 1+1/3 = 1,333...

A2= 1,333 . { 1 - (1/3) . [ 1 - (0+2) / (1,333^3) ] } = 1,263...

A3 = 1,263 . { 1 - (1/3) . [ 1 - (0+2) / (1,263^3) ] } = 1,259...

A4 = 1,259 . { 1 - (1/3) . [ 1 - (0+2) / (1,259^3) ] } = 1,259...

A5 = 1,259 . { 1 - (1/3) . [ 1 - (0+2) / (1,259^3) ] } = 1,259... começou a repetir, convergiu porém o valor não é inteiro logo não serve :angry:

Fazendo Q=1 nossa equação fica: 3+2=A^3, usando o mét. d Newton para calcular A,

A0=1 (chute inicial)

A1 = A0 . { 1 - (1/x) . [ 1 - ( QN+B ) / (Ai^x) ] }

A1 = 1 . { 1 - (1/3) . [ 1 - ( 3 +2) / (1^3) ] } = 1+4/3 = 2,333...

A2= 2,333 . { 1 - (1/3) . [ 1 - (3+2) / (2,333^3) ] } = 1,861...

A3 = 1,861 . { 1 - (1/3) . [ 1 - (3+2) / (1,861^3) ] } = 1,722...

A4 = 1,722 . { 1 - (1/3) . [ 1 - (3+2) / (1,722^3) ] } = 1,710...

A5 = 1,710 . { 1 - (1/3) . [ 1 - (3+2) / (1,710^3) ] } = 1,710... começou a repetir, convergiu porém o valor não é inteiro logo não serve :angry:

Fazendo Q=2 nossa equação fica: 2.3+2=A^3, usando o mét. d Newton para calcular A,

A0=1 (chute inicial)

A1 = A0 . { 1 - (1/x) . [ 1 - ( QN+B ) / (Ai^x) ] }

A1 = 1 . { 1 - (1/3) . [ 1 - ( 6 +2) / (1^3) ] } = 1+7/3 = 3,333...

A2= 3,333 . { 1 - (1/3) . [ 1 - (6+2) / (3,333^3) ] } = 2,462...

A3 = 2,462 . { 1 - (1/3) . [ 1 - (6+2) / (2,462^3) ] } = 2,081...

A4 = 2,081 . { 1 - (1/3) . [ 1 - (6+2) / (2,081^3) ] } = 2,003...

A5 = 2,003 . { 1 - (1/3) . [ 1 - (6+2) / (2,003^3) ] } = 2,000...

A6 = 2,000 . { 1 - (1/3) . [ 1 - (6+2) / (2,000^3) ] } = 2,000... começou a repetir e o valor é inteiro logo serve http://forum.imasters.com.br/public/style_emoticons/default/joia.gif

 

Tenho certeza q se você entender bem a implementação do algorítmo q você já tem em C/C++ p/ o 1o. caso e misturar com o do 2o. caso vai conseguir montar um algorítmo mais rápido e eficiente q o q eu descreví ;)

 

Era isso.

 

{}

Palc