Зависит от того представления элементов, которое Вы выбрали. Например, как известно, мультипликативная группа поля циклична, откуда следует, что любой элемент представляется в виде
или
. В таком виде элементы можно перемножать ну очень быстро и искать обратный элемент - тоже очень быстро. Но для сложения придется использовать функцию Якоби - тоже либо затабулировать, либо вычислять каждый раз.
Если представляете элементы в виде многочленов, то
- последнее можно вычислять двоичным возведением в степень. Можно, наверное, использовать и алгоритм Евклида для многочленов для поиска обратного элемента (для
для поиска обратных элементов используется именно он).
Вычислять их по каждый раз - слишком затратно
В
использование алгоритма Евклида как раз вообще не затратно.
Оба алгоритма быстрые - за
в поле
работают.
Наверняка у программистов уже есть какая-то практика при работе с конечными полями - надо искать инфу о ней. А я не знаю