Денис Мурзов
Денис Мурзов

Помогите пожалуйста решить задачу исполизуя метод "Шаг младенца-шаг великана"



Даны числа y, a и p. Вычислить значение дискретного логарифма log_a(y)mod p, используя Шаг младенца- шаг великана. p=107, a=88, y=47

НК
Никита Коршунов

Берем два целых числа m и k, таких что mk > p (как правило, m=k=|sqrt(p)|).
sqrt(p) = 10,344...
Поэтому m=k=10.

Затем вычисляются два ряда чисел:

y, y*a, y*a^2, … , y*a^(m-1) (mod p)
a^m, a^(2*m), a^(3*m), … , a^(k*m) (mod p)

47 mod 107 = 47
47*88 mod 107 = 70
47*88^2 mod 107 = 18
47*88^3 mod 107 = 18
47*88^4 mod 107 = 86
47*88^5 mod 107 = 78
47*88^6 mod 107 = 16
47*88^7 mod 107 = 17
47*88^8 mod 107 = 105
47*88^9 mod 107 = 38

88^10 mod 107 = 37
88^20 mod 107 = 85
88^30 mod 107 = 42
88^40 mod 107 = 56
88^50 mod 107 = 39
88^60 mod 107 = 52
88^70 mod 107 = 105
88^80 mod 107 = 33
88^90 mod 107 = 44
88^100 mod 107 = 23

Найдем такие i и j, для которых y*a^i=a^(j*m) . Тогда x=j*m-i.

47*88^8 mod 107 = 88^70 mod 107 = 105
i = 8, j = 7
x = 62

Проверка: a^x mod p = 88^62 mod 107 = 47 = y

log_a(y)mod p = 62

МЕ
Мишина Елена

Щаз как исполизую!!!

Похожие вопросы
помогите решить задачу линейного программирования графическим методом
Помогите пожалуйста решить задачу по С# пожалуйста пожалуйста пожалуйста
Помогите решить задачу методом подстановки
Помогите решить задачу по С++. Пожалуйста))
Помогите пожалуйста решить задачу по С#
Помогите пожалуйста решить задачу в с#
Помогите пожалуйста решить задачу по математическому методу оценке
Скажите пожалуйста можно ли решить данную задачу методом градиентного спуска с дроблением шага?
Помогите решить задачу по мат методам!!!
С++ помогите пожалуйста решить задачу