Generalized splitting-ring number theoretic transform

Graphical abstract

References

[1] Pollard J M . The fast Fourier transform in a finite field. Mathematics of Computation, 1971, 25( 114): 365–374

[2] Agarwal R C, Burrus C S . Number theoretic transforms to implement fast digital convolution. Proceedings of the IEEE, 1975, 63( 4): 550–560

[3] Zhu Y M, Liu Z, Pan Y B. When NTT meets Karatsuba: preprocess-then-NTT technique revisited. In: Proceedings of the 23rd International Conference on Information and Communications Security. 2021, 249−264

[4] Liang Z C, Shen S Y, Shi Y T, Sun D N, Zhang C X, Zhang G Y, Zhao Y L, Zhao Z X. Number theoretic transform: generalization, optimization, concrete analysis and applications. In: Proceedings of the 16th International Conference on Information Security and Cryptology. 2020, 415−432

[5] Lyubashevsky V, Seiler G . NTTRU: truly fast NTRU using NTT. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2019( 3): 180–201

[6] Nussbaumer H . Fast polynomial transform algorithms for digital convolution. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1980, 28( 2): 205–215

[7] Hassan C A, Yayla O. Radix-3 NTT-based polynomial multiplication for lattice-based cryptography. IACR Cryptology ePrint Archive, 2022, 726

RIGHTS & PERMISSIONS

Higher Education Press