Logaritmo discreto

[Stradh]

Ripropongo anche in questo forum un problema che, sotto altro nick, ho proposto e risolto nel forum di Matematicamente, ma vorrei avere anche un vostro parere a riguardo:

Sia $ a,b,c $ interi vogliamo sapere se esiste e come calcolare $ x $ sempre intero tale che:

$ a^x=b(c) $

[Alex90]

Ora non vorrei essere banale ma non è semplicemente il logaritmo in base a di b(c)?

$ $ x= \log_a b(c) $

Se vuoi che sia intero occorre che $ $b(c) $ sia una potenza di $ a $

[Stradh]

Il punto è che il numero deve essere intero! La mia notazione $ a^x=b(c) $ è relativa a $ a^x=b mod c $

[Stradh]

In particolare provare a verificare:

$ 5^x=8(11) $
non ha soluzioni.

ed invece:

$ 5^x=3(11) $
ha soluzioni per:
$ x=2(10) $

[Algebert]

$ a^x=b(c) $

Ah ma quindi tu intendi:

$ $a^x \equiv b \pmod c$ $

Giusto ?


P.S:
impara il LaTeX e mettilo da ParTeX !

[Stradh]

Sìsì

La notazione per il modulo è oramai un poco tanto in me radicata...

[fph]

Uhm... se non sbaglio è un problema piuttosto "grosso" di crittografia -- non esistono algoritmi efficienti, e se ce ne fossero farebbero saltare parecchi algoritmi di crittografia largamente diffusi. Quindi chi ha una soluzione più veloce di quelle su http://en.wikipedia.org/wiki/Discrete_logarithm è destinato a diventare molto ricco o molto famoso.

(parlo degli aspetti algoritmici -- la parte di "quando esiste la soluzione e quante ce ne sono", in astratto o per numeri piccoli, è fattibilissima)

[Stradh]

Ma nessuno ancora mi ha provato a spiegare l'esistenza della soluzione...