Welcome to the resource topic for 2003/264
Title:
Inversion of Several Field Elements: A New Parallel Algorithm
Authors: Pradeep Kumar Mishra, Palash Sarkar
Abstract:In many crypographic hardware or software packages, a considerable part is devoted to finite field arithmetic. The finite field arithmetic is a very costly operation in comparison to other finite field operations. Taming the complexity of this operation has been a major challenge for researchers and implementers. One approach for the purpose is accumulate all the elements to be inverted and to compute several inversions simultaneously at the cost of one inversion and some multiplictions. One such algorithm is known as Montgomery’s trick. However Montgomery’s trick does not allow much parallelism. In~\cite{SMB03} an algorithm for computation of inverses of several field elements simultaneously in parallel has been proposed. The algorithm allows ample scope for parallelism and performes well if there is no restriction on the number of processors used. In the current work, we present an algorithm, which is same in complexity as Montgomery’s trick but suitable for a parallel implementation. In parallel implementation, it computes inverse of n elements in 2\log n parallel rounds. It performs better than both the previous algorithms under the circumstances where the restricted number of multipliers is used.
ePrint: https://eprint.iacr.org/2003/264
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .