Cryptology ePrint Archive: Report 2004/353

Direct Division in Factor Rings

Patrick Fitzpatrick and Christopher Wolf

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.

Category / Keywords: implementation / Division, Extended Euclid, Elliptic Curves, Multivariate Quadratic, Public Key

Publication Info: Electronic Letters 38 No. 21 (2002), pp 1253-1254

Date: received 13 Dec 2004, last revised 18 Dec 2004

Contact author: Christopher Wolf at esat kuleuven ac be

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20041218:200417 (All versions of this report)

Short URL: ia.cr/2004/353

Discussion forum: Show discussion | Start new discussion