Существует ли метод нахождения полного генератора отличный от полного перебора? Никак не могу найти алгос, а ведь если даже решать сложную задачу дискретного логарифма, то надо бы знать хотябы основание логарифма, которым должен являться полный генератор! Пример, 3^18 = 1 mod 19, и не равно 1 при любой меньшей степени. Другой, 5^9 = 1 mod 19, поэтому 5 это дрянь, а 3 - генератор. Как отыскать генератор и гарантировать его свойства в большом поле, скажем 64 бит или даже криптографического размера 2048 бит, где полный перебор не возможен?
Нутром чую, Петька, а доказать не могу... Берем p-1, раскладываем на множители... Возводим пробное число a_ во всевозможные выборки множителей из разложения. Если единицы не возникает кроме как для p-1, то это генератор.
Если это так, то круто получается! Вместо 2^Nбит нужно перебрать только 2^Nмнож, в моем случае число множителей равно семь.
Еще более быстрый способ придумал! Если число является свидетелем простоты в тесте рабина миллера то оно будет полным генератором.
Не, с тестом рабина не работает, например 8^9 = -1 mod 19, но 8 это лишь генератор периода шесть. Остается только с разложением p-1 и взятием булиана по всем множителям.
Число g порождает группу ненулевых элементов по модулю простого числа p относительно умножения тогда и только тогда, когда g лежит в этой группе и для всех простых делителей q|p-1 число g^((p-1)/q) не сравнимо с 1 по модулю p. Для нахождения примитивных корней просто проверяют все значения g подряд, начиная с 2. В предположении расширенной гипотезы Римана это гарантированно приводит к результату за полиномиальное (по log p) время.
Мда, выходит что перебор по булеану множителей это явный оверкилл... Достаточно перебрать множители по штучно, причем кратность можно не учитывать. Генераторов должно быть дофига, их число равно функции эйлера от p-1
говоря о трудностях перебора, я имел в виду не столько перебор претендентов, сколько действия проводимые для проверки каждого из них. Слава Богу,оказалось достаточно просто N раз возвести в степень (p-1)/q[N]
