2007/08/22 by Elisa Gorla, Gorla, Elisa, Christoph Puttmann +3
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #cs.CC #cs.CR
paper · pdf · doi:10.48550/arxiv.0708.3014
11 pages, to appear in the proceedings of SAC2007
arxiv created 2007/08/22 · openalex publication_date 2007/08/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Efficient computation of the Tate pairing is an important part of pairing-based cryptography. Recently with the introduction of the Duursma-Lee method special attention has been given to the fields of characteristic 3. Especially multiplication in F36m, where m is prime, is an important operation in the above method. In this paper we propose a new method to reduce the number of F3m multiplications for multiplication in F36m from 18 in recent implementations to 15. The method is based on the fast Fourier tranmsform and explicit formulas are given. The execution times of our software implementations for F36m show the efficiency of our results.