Пусть i наименьшее число, что gi равно 1, тогда если i = p-1, то g первообразный иначе нет.
Очевидно, что gi*x равно 1 для целых x и только они (из-за наименьшести i). Тогда из того что мы проверили gp-1 = 1 следует что p-1=i*x, то есть i делит p-1, что тоже самое что «i равно p-1, или i делит хоть что-то из (p-1)/ki». Если i = p-1 — все отлично, иначе если i делит (p-1)/ki то g(p-1)/ki тоже будет равно 1, что мы собственно и проверяем.
> Как искать первообразный корень? Я использую полный перебор, начиная с 2 до p
Можно ускорить проверку числа на первообразность. Пусть p-1 = k1a1k2a2k3a3… — разложение на простые множители, тогда если g(p-1)/ki mod p не равно 1 для всех i, а gp-1 равно 1, то g — первообразный корень.
Всего таких k для каждого числа очень мало. Разложить все числа от 2 до p на простые множители можно тоже относительно быстро с помощью решета Эратосфена.
Таким образом можно перебрать за приемлемое время первообразный хоть для p порядка 109 :)
Машинка нашла баг в движке. Она на старте застревает, а потом подпрыгивает в небо на вот такое расстояние.
Пусть i наименьшее число, что gi равно 1, тогда если i = p-1, то g первообразный иначе нет.
Очевидно, что gi*x равно 1 для целых x и только они (из-за наименьшести i). Тогда из того что мы проверили gp-1 = 1 следует что p-1=i*x, то есть i делит p-1, что тоже самое что «i равно p-1, или i делит хоть что-то из (p-1)/ki». Если i = p-1 — все отлично, иначе если i делит (p-1)/ki то g(p-1)/ki тоже будет равно 1, что мы собственно и проверяем.
Можно ускорить проверку числа на первообразность. Пусть p-1 = k1a1k2a2k3a3… — разложение на простые множители, тогда если g(p-1)/ki mod p не равно 1 для всех i, а gp-1 равно 1, то g — первообразный корень.
Всего таких k для каждого числа очень мало. Разложить все числа от 2 до p на простые множители можно тоже относительно быстро с помощью решета Эратосфена.
Таким образом можно перебрать за приемлемое время первообразный хоть для p порядка 109 :)
Почти угадал :)