# Number Theoretic Transform (NTT) I

Start with RSA
Method for modular reductions

[toc]

## - Montgomery:
Hensel remainder and quotient
from A mod N $\to$ $A/R$ mod N
R is $2^k$, $k$ is a known value

gcd(N,R)=1

$\exists N', R'$ s.t. $NN' - RR' = -1$
hence $NN' \equiv -1 (mod\ R)$

let $l = AN' mod\ R$
p.s. we don't actually calculate this way,
we probably transform into "$(A\ mod\ R)N'\ mod\ R$"

$l*N \equiv AN'N \equiv -A(mod\ R)$

$A + lN = 0\ (mod\ R)$
R | (A+l*N) (以2進為表示的時候 末幾位都為0 所以R才能被整除)

$A+lN \equiv A(R^{-1}\ mod\ N)(mod \ N) \equiv A/R\ mod\ N$

- mod N
p.s. 區分清楚 x, y, X, Y

define $f(x) = X = xR\ mod\ N$
define $f(y) = Y = yR\ mod\ N$

$f: x \to xR\ mod\ N$ is 對射(bijection)
$f(x+y) \equiv f(x)+f(y)\ mod\ N$
$f(xy) \equiv xyR (mod\ N) = (xR)*(yR)R^{-1} (mod\ N)$
And this is Montgomery Reduction of $f(x)\ f(y)$

p.s. $X = xR$ and $Y = yR$

assumption: commutative and inverse exist
(Which we already know that $Z$ has the above mentioned properties)

how to do "f":
$R^3 mod\ N$ (Using Montgomery Reduction)
and then take $R^3 mod\ N$ back to "f"

- Hensel Reduction

$N\ mod\ 2 = 1$
$x_0 = 1$
$x_{n+1} = 2x_n + x_n^2N$
while we know that $x_0N \equiv -1 (mod\ 2)$

* All of the above are unsigned numbers

$0 < (A+l*N)/R < 2N$
Then Montgomery Reduction could also be written in the form of $(A-ln) = (A-ANN') = 0\ mod\ R$:

\
Since the value is between 0 and 2N, so when do this calculation on computer, we simply subtract it with N
- case 1: result > 0 take this
- case 2: result < 0 take the un-sub(original) value

## - In PQC
- value are signed
- many small integers

$(A-ln) = (A-ANN') = 0\ mod\ R$

A - l*N 童餘 0 mod R
AB 計算中
in MK(AB') we can speed up by using the following method.
$N' = N^{-1}\ mod\ R \equiv \frac{AB' - (AB''\ mod\ R)N}{R\ mod\ N}$

2高 1低 （計算的數值）

## - Barrett Reduction

* low multiply
$AB\ mod\ R$
* high multiply
$\lfloor \frac{AB}{R} \rfloor$
* high multiplication with rounding
$\lfloor \frac{AB}{R} \rceil$

$A\ mod\ N = A - \lfloor \frac{A}{N} \rfloor N$
$A\ mod\ \pm N = A - \lfloor \frac{A}{N} \rceil N$

p.s.
$\lfloor \frac{A}{N} \rfloor \approx \lfloor A \lfloor \frac{R}{N} \rfloor /R \rfloor$
while $\lfloor \frac{A}{N} \rfloor$ is already calculated

* Bound of Approximating Quotients
p.s. $R = 2^k$
$A\ge A_N = \lceil \lceil (N-R / \lceil R/N\rceil)^{-1} \rceil R \lceil R/N \rceil \rceil$

* Example:
For $N = 4591, k = 32, A = 2161$
$A_N = 9921150(<M^2)$

When it is out of bounds, needs to adjust usually by $\pm M$

* Error of Approximation Quotients
$Error = A\ mod\ N - BAR_N(A) = N(\lceil A\lceil R/N\rfloor /R \rfloor - \lceil A/N \rfloor)$

2低 1高 (高要四捨五入)

* Accuracy for Rounding Barret multiplication
max: $\epsilon := |\lfloor BR/M \rceil - BR/M| \le 2^{-h}$
for both signed and unsigned numbers 會有誤差
5
## - Signed Plantard

In breif, a number of length 2N multiply by a number of length N -> Then take the middle N bit.