# Automorphism in NTT representation In the polynomial ring $R=\mathbb{Z}[X]/(X^n+1)$, the transformation $X\mapsto X^k$ for $k$ satisfying $\gcd(k,n)=1$ is an automorphism. The polynomial are considered in standard or CRT representation. The output is a permutation of the coefficients with possible change in sign. when $n$ is a power of 2, the set of all $ks has the [[Multiplicative group of integers modulo powers of 2|structure]] of cyclic subgroup of order $\phi(n)/2$ times cyclic subgroup of order of 2. The element $5$ is a generator of the large cyclic subgroup. This means that if we compute NTT(or FFT) with primitive roots of unity ordered in the first row $\zeta$, in the 2nd row $\zeta^5$ in the 3rd row $\zeta^{5^2}$ etc., the transformation by $X\mapsto X^{5^j}$ rotate the first $n/2$ elements inside themselves (i.e., the $n/2-1$ elements is shuffled to the firs place) and the rest $n/2$ elements inside themselves. See python implementation in `CKKS-RNS/src/ring.py: rotate5_left() and nega_to_nega5()` ## Created 2025-11-05 15:32