International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Direct Division in Factor Rings

Authors:
Patrick Fitzpatrick
Christopher Wolf
Download:
URL: http://eprint.iacr.org/2004/353
Search ePrint
Search Google
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
}