1
Welcher Algorithmus verwendet GMP, um ein Element in einem endlichen Feld zu invertieren?Welcher Algorithmus wird von GMP für Primfeldinversion (mpz_invert) verwendet?
A
Antwort
4
Es verwendet erweiterte GCD wie in mpz_gcdext implementiert: https://fossies.org/dox/gmp-6.1.0/mpz_2invert_8c_source.html.
Siehe Abschnitt 15.3.4 des GMP-Handbuchs: [https://gmplib.org/manual/Extended-GCD.html#Extended-GCD](https://gmplib.org/manual/Extended-GCD.html # Extended-GCD) – user448810
Insbesondere ruft es 'mpz_gcdext' mit einem NULL-Argument für einen der Bézout-Koeffizienten auf - da es nicht benötigt wird. '(g, z, NULL, x, Modul)'. Der kleinste nicht-negative Rest (der umgekehrte) liegt innerhalb von: "+/- Modul" wenn "(z <0)". Dies liegt daran, dass gcdext eines von zwei möglichen "minimalen" Koeffizientenpaaren zurückgibt. –