Расчет таблицы инверсий по модулю простого числа

Question

Я знаю, что расширенный евклидов алгоритм является идеальным способом для вычисления мультипликативной инверсии одного числа по модулю простого числа p.

Но что, если я хочу создать массив A, в котором A[x] имеет обратное значение x? Есть ли более быстрый способ вычисления такого массива, чем вычисление инверсии каждого элемента в отдельности?

Я интуитивно ожидаю, что есть ярлык, потому что у вас есть много идентичностей, таких как

A[x*y % p] = A[x]*A[y] % p

Однако я не могу придумать общую методологию для получения всего массива А.

Answer 1

Простой способ вдвое сократить вычисления - использовать

inverse(p - k) = p - inverse(k)

и заполнить только первую половину массива, используя расширенный евклидов алгоритм, а оставшуюся половину - симметрией.

Я не уверен, что следующее будет быстрее, оно потребует меньше вычислений, но будет иметь худшие шаблоны доступа к массиву, поэтому оно может быть медленнее:

int A[p] = {0};
A[1] = 1;
for(int k = 2; k < p; ++k) {
    if (A[k] == 0) {
        // haven't found the inverse yet
        inv = inverse(k,p); // extended Euclidean algorithm or Fermat's theorem
        int m = k, i = inv;
        while(m != 1) {
            A[m] = i;
            m = (m*k) % p;
            i = (i*inv) % p;
        }
    }
}

Каждый раз, когда вы сталкиваетесь со значением, обратное которому вы еще не знаете, вы итеративно вычисляете обратные значения для всей подгруппы, сгенерированной этим значением, используя только два модульных умножения на элемент (кроме начальной инверсии). Вы должны относительно скоро поразить генератор всей группы юнитов по модулю p,

Answer 2

Для простого числа элементы {1, 2, 3, ..., (p-1)} образуют циклическую группу. То есть существует число (на самом деле много) x такое, что {x^0, x^1, x^2, ..., x^(p-2)} является множеством. После того, как вы найдете обратное для x и назовете его y, вы можете получить соответствующие обратные значения, просто подняв y до соответствующей степени, y^k - обратное значение x^k. Как вы находите такой х? Выберите случайный элемент и возведите его в степень (p-1)/2. Это число будет либо 1, либо -1 (р-1). Если это -1, у вас есть генератор. Возведение элемента в степень должно быть сделано с помощью "возведения в степень путем возведения в квадрат".

Answer 3

Следующий код получен из определения функции мода:

https://stackru.com/images/e4db7aaf8ddec9e2a2bb56170fd f5448765156c1.png

public long[] InverseTable(long n, long p)
{
    long[] inverse = new long[n+1];
    inverse[1] = 1;
    for (long i = 2; i <= n; i++)
        inverse[i] = p - (inverse[p % i] * (p / i) % p);
    return inverse;
}