problem matematyczno informatyczny

[kwak2k]

Problem pewnie banalny. U mnie brak wiedzy bardziej specjalistycznej sie kłania
Mamy stałe a b i c , jak wyznaczyc wzór na najniższe o ile nie jedyne x

b jest nieparzyste.

\(\displaystyle{ a = ( x^{b} ) \ mod \ c}\)

[adek05]

\(\displaystyle{ a + cx = x^{b}\\
a = x^{b} - cx \\
a = x ( x^{b-1} -c)}\)
Dalej nie wiem, ale to mniej więcej tak będzie szło.

[xiikzodz]

To wcale nie jest latwe.
Problem nazywa sie logarytm dyskretny (na trudnosci jego rozwiazania opiera sie system RSA np.).

Mozna szukac np. metoda Silvera-Pohlinga-Hellmana.

Oczywiscie dla malego \(\displaystyle{ c}\) mozna po prostu przepadac metoda brute force korzystajac ewentualnie z metody iterowanego kwadratu.

[kwak2k]

xiikzodz, ja szukam x nie b
- b jest stałe i jest nieparzystą liczbą pierwszą
- c [niestety nie jest liczba 1 i jest cholernie dlugie ]

[xiikzodz]

Aaa, sorry.
W takim razie wystarczy wziac:
\(\displaystyle{ x=a^{-b\;\mathrm{mod}\;c}\;\mathrm{mod}\;c}\)
To znaczy w wykladniku kladziemy dodatnia reszte z dzielenia \(\displaystyle{ -b}\) przez \(\displaystyle{ c}\), czyli w przypadku \(\displaystyle{ b}\)

[kwak2k]

dzieki, zaraz przetestuje na miracl.