Автори пропонують ряд методів збільшення продуктивності алгоритму мультиплікативного інвертування у двійковому полі на основі розширеного алгоритму Евкліда. Перший метод ґрунтується на специфіці самого розширеного алгоритму Евкліда: інваріантний поліном або залишається без змін, або обмінюється вмістом з інваріантним поліномом u, це дозволяє уникнути необхідності обчислення ступеня полінома. Наступний метод заснований на методі "наступного підходящого індексу" при обчисленні ступеня полінома: враховуючи той факт, що в процесі роботи розширеного алгоритму Евкліда, ступінь інваріантного полінома зменшується хоча б на 1, то при подальшому обчисленні ступеня полінома можна враховувати поточне значення ступеня. Запропоновані методи дозволяють збільшити продуктивність програмної реалізації інвертування для 32-х розрядних платформ на 15-20%.
Авторы предлагают ряд методов к увеличению производительности алгоритма мультипликативного инвертирования в двоичном поле на основе расширенного алгоритма Эвклида (РАЭ). Первый метод основывается на специфике самого РАЭ: инвариантный полином , либо остается без изменений, либо обменивается содержимым с инвариантным полиномом u, это позволяет избежать необходимости вычисления степени полинома . Второй метод основан на поиске "следующего подходящего индекса" при вычислении степени полинома, т.к.степень инвариантного полинома уменьшается хотя бы на 1, то при дальнейшем вычисление степени полинома, можно учитывать текущее значение. Основываясь на втором методе, при модификации инвариантов, авторы предлагают использовать в вычислениях лишь значимые слагаемые, учитывая текущие степени пар полиномов и . Предложенные методы позволяют увеличить производительность программной реализации инвертирования, для 32-х разрядных платформ, на 15-20%.
Authors propose several methods for increasing performance of multiplicative inversion algorithm in binary fields based on Extended Euclidean Algorithm. First method is based on Extended Euclidean Algorithm specific: either invariant polynomial is a same or swaps with invariant polynomial u. Thus, it does not necessary to compute degree of polynomial . Next method is based on "next fit element" in polynomial degree computation: on each iteration of Extended Euclidean Algorithm execution, degree of invariant polynomial decreases at list one. On next iteration Extended Euclidean Algorithm degree searches from where it left off the previous time. Proposed methods allow to increase performance of software implementation of inversion in binary field for 32-bit architectures on 15-20%.
