Вход через социальные сети

  • 08.10.2017, 00:28
    0 up down
    Сообщение

    st256 в 07.10.2017, 20:52 написал(а): link
    Как можно одно натуральное число возвести в отрицательную степень и получить другое натуральное число?
    По модулю можно.

     

    Для данного g найти y, как решение уравнения g=y^\omega\;(mod \; p).

    Например 2^3=8, значит по модулю 5 будет 2^3=3\;(mod\;5). Значит 3^{-3}=2\;(mod\;5).

    (Можно попробовать все остатки от 0 до 4, возвести каждый в куб по модулю 5 и посмотреть при каком получим 3. Получим только для 2.)

    Сообщение было отредактировано zykov в 08.10.2017, 00:28.


  • 08.10.2017, 21:22
    0 up down
    Сообщение

    Спасибо, понял.

  • 15.10.2017, 21:58
    0 up down
    Сообщение

    Извиняюсь, здесь я Вас запутал. Вы спрашивали про возведение в отрицательную степень, хотя назвали тему "Дискретное логарифмирование". А я написал про дискретный корень.

     

    Дискретное логарифмирование: найти \omega для данных g и y из уравнения y=g^\omega (mod \;p).

    Дискретный корень y=g^{1/\omega} (mod \;p): найти y для данных g и \omega из уравнения g=y^{\omega} (mod \;p).

     

    Возведение в отрицательную степень проще всего.

    Если y=g^{-\omega} (mod \;p), то 1=y\cdot g^{\omega} (mod \;p).

    Т.е. можно сначала найти g^{\omega} (mod \;p), а потом обратную к этой величине. Или эквивалентно найти для g обратную g^{-1} (mod \;p) и возвести её в степень омега (g^{-1})^{\omega} (mod \;p).