Candidate: Khan Shagufta Shagufa
Title: On Large Polynomial Multiplication in Certain Rings
Date: March 12, 2018
Time: 2:30pm
Place: EIT 3141
Supervisor(s): Hasan, Anwarul M.
Abstract:
Multiplication of polynomials with large integer coefficients and very high degree is used in cryptography. Residue number system (RNS) helps distribute a very large integer over a set of smaller integers, which makes the computations faster. In this thesis, multiplication of polynomials in ring Zp/(xn + 1) where n is a power of two is analyzed using the Schoolbook method, Karatsuba algorithm, Toeplitz matrix vector product (TMVP) method and Number Theoretic Transform (NTT) method. All coefficients are residues of p which is a 30-bit integer that has been selected from the set of 30-bit moduli for RNS in NFLlib.
NTT has a computational complexity of O(n log n) and hence, it has the best performance among all these methods for the multiplication of large polynomials. NTT method limits applications in ring Zp/(xn + 1). This restricts size of the polynomials to only powers of two. We consider multiplication in other cyclotomic rings using TMVP method which has a subquadratic complexity of O(n log2 3 ). An attempt is made to improve the performance of TMVP method by designing a hybrid method that switches to schoolbook method when n reaches a certain low value. It is first implemented in Zp/(xn + 1) to improve the performance of TMVP for large polynomials. This method performs as good as NTT for polynomials of size 212. TMVP method is then exploited to design multipliers in other rings Zp / k where k is a cyclotomic trinomial. Similar hybrid designs are analyzed to improve performance in the trinomial rings. This allows a wider range of polynomials in terms of size to work with and helps avoid unnecessary use of larger key size that might slow down computations.