|
Что такое примитивный элемент поля ℤp? задан 23 Ноя '14 1:59 
Тимур 1 |
|
Это такой элемент поля, степенью которого являются все ненулевые элементы. Его ещё называют первообразным корнем по модулю $%p$% -- это то же самое. Например, при $%p=7$% можно рассмотреть степени двойки: 1, 2, 4, ... , и дальше остатки начинают периодически повторяться. Значит, 2 не годится в качестве такого элемента. А если взять степени тройки (их остатки от деления на 7), то получатся числа 1, 3, 2, 6, 4, 5. Это все ненулевые остатки. Значит, 3 будет первообразным корнем по модулю 7. В теории чисел доказывается теорема, из которой следует, что первообразные корни по любому (нечётному) простому модулю существуют; известно также их количество. Однако для данного $%p$% требуется какой-то перебор, позволяющий находить такой элемент. Сразу обычно бывает не ясно, что подойдёт. Какой-то простой закономерности на этот счёт не имеется. Фактически, нужно уметь решать такую достаточно общую задачу: дано простое число $%p$% и некоторое целое $%a$%, не делящееся на $%p$%. И надо научиться выяснять (желательно как можно более быстрым способом), будет ли $%a$% первообразным корнем. Если научиться это делать, то далее просто перебираем значения для $%a$%, беря числа 2, -2, 3, -3 и так далее. Какое-то из них достаточно быстро подойдёт, но какое именно -- это сказать по внешнему виду числа $%p$% достаточно непросто. Если нужно, я могу описать на каком-нибудь типовом примере способ проверки. отвечен 23 Ноя '14 2:26 
falcao Уже многое понятно.
(23 Ноя '14 2:49)
Тимур 1
@Тимур_77: обычно следят за остатками от деления на $%p$%, поэтому все они меньше $%p$%. Сами степени могут быть очень большими, и за ними следить трудно. То утверждение, о котором Вы спросили, неверно. Момент, когда одна степень меньше $%p$%, а следующая больше, бывает всегда, но из этого ничего не следует.
(23 Ноя '14 3:08)
falcao
Значит, чтобы утверждать, что число $%a$% - первообразный корень, необходимо пройтись по его степеням ($%a^x \mod p$%) пока не будут получены все числа меньшие $%p$%? И если да, то верно ли, что если получился повтор, то число $%a$% точно не первообразный корень?
(23 Ноя '14 3:14)
Тимур 1
@Тимур_77: да, нужно пройтись по всем степеням, выясняя, какой при этом получается минимальный период. Если он равен $%p-1$%, то все ненулевые остатки появятся. Если же повтор числа произойдёт раньше времени, то период будет меньше $%p-1$%, и тогда число не будет первообразным корнем. Для малых значений $%p$% лучше всё в таком виде и делать, а для значений чуть побольше есть убыстренные способы.
(23 Ноя '14 3:21)
falcao
Огромное спасибо, очень помогло.
(24 Ноя '14 22:11)
Тимур 1
|