1
Каков алгоритм, используемый GMP для инвертирования элемента в конечном поле?Какой алгоритм используется GMP для инверсии первичного поля (mpz_invert)?
A
ответ
4
Используется расширенный GCD, как реализован в mpz_gcdext: https://fossies.org/dox/gmp-6.1.0/mpz_2invert_8c_source.html.
См. Раздел 15.3.4 руководства по GMP: [https://gmplib.org/manual/Extended-GCD.html#Extended-GCD](https://gmplib.org/manual/Extended-GCD.html # Extended-GCD) – user448810
В частности, он вызывает 'mpz_gcdext' с аргументом NULL для одного из коэффициентов Bézout, поскольку он не требуется. '(g, z, NULL, x, модуль)'. Наименьший неотрицательный остаток (обратный) будет находиться в пределах: '+/- модуль ', если' (z <0) '. Это связано с тем, что gcdext возвращает одну из двух возможных «минимальных» пар коэффициентов. –