Browse Prior Art Database

Implementation of Number Theoretic Transforms

IP.com Disclosure Number: IPCOM000089109D
Original Publication Date: 1977-Sep-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 2 page(s) / 18K

Publishing Venue

IBM

Related People

Nussbaumer, H: AUTHOR

Abstract

This is a method for implementing Number Theoretic Transforms (NTT) via table look-ups and indices in view of eliminating any multiplication operation normally required for the computation of NTTs.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 2

Implementation of Number Theoretic Transforms

This is a method for implementing Number Theoretic Transforms (NTT) via table look-ups and indices in view of eliminating any multiplication operation normally required for the computation of NTTs.

Let us consider an N-term NTT which is defined modulo prime Fermat number p, where p = 2/q/ 1 and q = 2/t/:

(Image Omitted)

In such a case, computing the transforms corresponds to converting the input sequence a(n) into the corresponding sequence u(n) via a table look-up procedure. The computation of the transform then reduces to replacing multiplications on a(n).W/nk/ by modulo 2/q/ additions on indices and summing modulo 2/q/ 1 the various terms g/(u(n)+vnk)/.

In addition, the number of table look-ups can be reduced and all operations performed on indices by using the following approach: assuming we want to perform the operation a(1).g/k(1)/ a(2)g/k(2)/ we have:

(Image Omitted)

If we have a table which for each index alpha gives the index beta corresponding to ((1 g/alpha/)), we can compute the operations of (5) with only four additions and one table look-up.

Moreover, if the multiplications are done by fixed coefficients, k(2)-k(1) can be precomputed and the number of additions reduced to three.

1

Page 2 of 2

2

[This page contains 1 picture or other non-text object]