Более быстрый алгоритм поиска примитивных корней
Я пытаюсь найти простые корни с помощью этого алгоритма:
std::vector<unsigned long long> Keyexchange::primroot(unsigned long long val) {
std::vector<unsigned long long> res;
for (unsigned long long i = 2; i<val - 1; i++) {
unsigned long long start = 1;
bool flag = 1;
for (unsigned long long j = 0; j<val / 2; j++) {
start = (start * i) % val;
if (start % val == 1) {
flag = 0;
break;
}
}
if (flag) {
res.push_back(i);
}
}
return res;
}
Это прекрасно работает, но очень и очень медленно.
Я хочу вычислить примитивные корни больших чисел, такие как 1073741789. Было бы лучше, если бы была возможность установить диапазон, потому что я вычисляю весь набор прямо сейчас.
В общем, я ищу способ [фрагмент кода был бы хорош], чтобы сгенерировать около 100 000 самых больших примитивных корней из этого большого числа.
Я знаю, что это намного быстрее с φ-функцией Эйлера, но я понятия не имею, как ее реализовать.
Большое спасибо.
Решение
Во-первых, если вы выберете случайное целое число от 2 до p-1, тогда у него будет неплохой шанс стать примитивным корнем. Таким образом, вы выбираете случайное целое число (или вы начинаете с 2), проверяете его, и если оно терпит неудачу, вы выбираете следующее и т. Д.
Чтобы проверить, что x является примитивным корнем: это означает, что x ^ (p-1) = 1 (по модулю p), но не меньшая степень p равна. Возьмем, к примеру, p = 31, p-1 = 30 = 2 x 3 x 5. Если p не является примитивным корнем, то один из x ^ (30/2), x ^ (30/3) и x ^ (30 / 5) должно быть 1 (по модулю р).
Фактор p-1 в его простых множителях вычисляет x ^ ((p-1) / f) (по модулю p) для каждого простого фактора f, и x является примитивным корнем, если ни один из результатов не равен 1.
Конечно, x ^ y (по модулю p) необходимо вычислять с повторным возведением в квадрат / умножением. Например, чтобы вычислить x ^ 10, вы должны вычислить x ^ 2, x ^ 4, x ^ 5, x ^ 10 в этом порядке.
Как только вы нашли примитивный корень g, g ^ k будет примитивным корнем, если gcd (k, p-1) = 1. Но это будет редкая ситуация, когда вы заботитесь о более чем одном примитивном корне.
Другие решения
Если введенный номер полупервичных и у вас есть его (два) основных фактора, тогда вы можете использовать это:
vector<uint64> Roots(uint64 p,uint64 q)
{
vector<uint64> roots;
uint64 zstar = p*q;
for (uint64 y=1; y<zstar; y++)
{
if (GCD(zstar,y) == 1 && InQR(y,p,q))
{
uint64 yp = PowMod(y,(p+1)/4,p);
uint64 yq = PowMod(y,(q+1)/4,q);
uint64 r1 = Map(0+yp,0+yq,p,q);
uint64 r2 = Map(0+yp,q-yq,p,q);
uint64 r3 = Map(p-yp,0+yq,p,q);
uint64 r4 = Map(p-yp,q-yq,p,q);
roots.push_back(r1);
roots.push_back(r2);
roots.push_back(r3);
roots.push_back(r4);
}
}
return roots;
}
Вот вспомогательные функции:
uint64 GCD(uint64 a,uint64 b)
{
uint64 c = a%b;
if (c == 0)
return b;
return GCD(b,c);
}
uint64 PowMod(uint64 x,uint64 e,uint64 n)
{
uint64 y = 1;
while (e > 0)
{
if (e & 1)
y = (y*x)%n;
x = (x*x)%n;
e >>= 1;
}
return y;
}
bool InQR(uint64 y,uint64 p)
{
return PowMod(y,(p-1)/2,p) == 1;
}
bool InQR(uint64 y,uint64 p,uint64 q)
{
return InQR(y,p) && InQR(y,q);
}
uint64 Map(uint64 u,uint64 v,uint64 p,uint64 q)
{
uint64 a = q*Inverse(p,q);
uint64 b = p*Inverse(q,p);
return (u*a+v*b)%(p*q);
}
uint64 Inverse(uint64 n,uint64 a)
{
int64 x1 = 1;
int64 x2 = 0;
int64 y1 = 0;
int64 y2 = 1;
uint64 r1 = n;
uint64 r2 = a;
while (r2 != 0)
{
uint64 r3 = r1%r2;
uint64 q3 = r1/r2;
int64 x3 = x1-q3*x2;
int64 y3 = y1-q3*y2;
x1 = x2;
x2 = x3;
y1 = y2;
y2 = y3;
r1 = r2;
r2 = r3;
}
return (uint64)(y1>0? y1:y1+n);
}