CryptoDB
Direct Division in Factor Rings
Authors: | |
---|---|
Download: | |
Abstract: | Conventional techniques for division in the polynomial factor ring $\Ftm$ or the integer ring $\Zzs$ use a combination of inversion and multiplication. We present a new algorithm that computes the division directly and therefore eliminates the multiplication step. The algorithm requires $2\,{\rm degree\/}{(m)}$ (resp. $2 \log_2 n$) steps, each of which uses only shift and multiply-subtract operations. |
BibTeX
@misc{eprint-2004-12316, title={Direct Division in Factor Rings}, booktitle={IACR Eprint archive}, keywords={implementation / Division, Extended Euclid, Elliptic Curves, Multivariate Quadratic, Public Key}, url={http://eprint.iacr.org/2004/353}, note={Electronic Letters 38 No. 21 (2002), pp 1253-1254 Christopher.Wolf@esat.kuleuven.ac.be 12770 received 13 Dec 2004, last revised 18 Dec 2004}, author={Patrick Fitzpatrick and Christopher Wolf}, year=2004 }