Дискретний логарифм: відмінності між версіями

''Дискретний логарифм'' — це просто обернена операція. Наприклад, візьмемо рівняння 3^''k'' ≡ 13 (mod 17) for ''k''. Як показано вище ''k''=4 є розв'язком. Через те що 3¹⁶ ≡ 1 (mod 17), також випливає, що якщо ''n'' ціле, тоді 3^{4+16 ''n''} ≡ 13 × 1^''n'' ≡ 13 (mod 17). Звідси, рівняння має нескінченно багато розв'язків у вигляді 4 + 16''n''. Більше того, тому що 16 є найменшим додатнім цілим ''m'', що задовільняє 3^''m'' ≡ 1 (mod 17), тобто 16 — це [[показник числа за модулем|показник]] 3 в ('''Z'''₁₇)^×, це єдині розв'язки. Тотожно, Розв'язок можна виразити як ''k'' ≡ 4 (mod 16).

 

Нехай в деякій скінченній мультиплікативній [[абелева група|абелевій]] групі <math>G</math> задане рівняння

 

 

Найчастіше розглядається випадок, коли <math>G=\langle g\rangle</math>, тобто [[циклічна група|циклічна]], породжена елементом <math>g</math>. В такому разі рівняння завжди має розв'язок. У випадку довільної групи питання розв'язності задачі дискретного логарифмування вимагає окремого розгляду.

 

== Примітки ==