mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
f4ee7a0525
Bylines, paper authorship, correspondence addresses and the founder blurb under each post named an individual. They name the organisation that published the work instead: the brand on posts and pages, the research byline on papers, and research@ in place of a personal address. Both are what these repositories already used elsewhere — nothing new was coined. Co-authors are untouched. Where a paper named someone else alongside, they stay named; only the one byline changed. Bibliography entries, running heads, PDF metadata and affiliations move with it, so a citation still resolves to whoever the cited paper names. Sample and fixture data uses the placeholder name these tests already use elsewhere, so no assertion changed meaning.
96 lines
2.9 KiB
TeX
96 lines
2.9 KiB
TeX
\documentclass[11pt,a4paper]{article}
|
|
\usepackage{../shared/luxcover}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage{amsmath,amssymb,amsfonts,amsthm}
|
|
\usepackage{graphicx}
|
|
\usepackage{hyperref}
|
|
\usepackage{booktabs}
|
|
\usepackage{listings}
|
|
\input{../shared/lstlang}
|
|
\usepackage{xcolor}
|
|
\usepackage{enumitem}
|
|
\usepackage{float}
|
|
\usepackage{tikz}
|
|
\usetikzlibrary{arrows.meta,positioning}
|
|
|
|
\newtheorem{theorem}{Theorem}
|
|
\newtheorem{lemma}[theorem]{Lemma}
|
|
\newtheorem{definition}{Definition}
|
|
\newtheorem{remark}{Remark}
|
|
|
|
\lstdefinelanguage{asm}{
|
|
morekeywords={vpmullw,vpmulhw,vpaddw,vpsubw,vpsraw,vpand,vmovdqu,
|
|
vpbroadcastw,vpshufb,vperm2i128,ret,mov,lea,add,sub,cmp,jne,jmp,
|
|
TEXT,GLOBL,NOSPLIT},
|
|
morecomment=[l]{//},
|
|
morecomment=[l]{\#},
|
|
sensitive=false,
|
|
}
|
|
|
|
\lstset{
|
|
basicstyle=\small\ttfamily,
|
|
keywordstyle=\color{blue}\bfseries,
|
|
commentstyle=\color{gray},
|
|
stringstyle=\color{red},
|
|
breaklines=true,
|
|
frame=single,
|
|
numbers=left,
|
|
numberstyle=\tiny\color{gray},
|
|
extendedchars=true,
|
|
literate=%
|
|
{·}{{\textperiodcentered}}1
|
|
}
|
|
|
|
\hypersetup{
|
|
colorlinks=true,
|
|
linkcolor=blue,
|
|
citecolor=blue,
|
|
urlcolor=blue
|
|
}
|
|
|
|
\title{Number Theoretic Transform with SIMD Acceleration}
|
|
\author{
|
|
Lux Research \\
|
|
Lux Industries, Inc.\thanks{Corresponding author: [email protected]}\\
|
|
\texttt{[email protected]}
|
|
}
|
|
\date{2025}
|
|
|
|
\begin{document}
|
|
|
|
\luxcoverpage
|
|
|
|
\begin{abstract}
|
|
The Number Theoretic Transform (NTT) is the computational bottleneck of lattice-based
|
|
cryptography and fully homomorphic encryption. This paper teaches NTT implementation from
|
|
mathematical foundations to production SIMD code. We cover: the mathematical definition
|
|
and why it works, the Cooley-Tukey butterfly decomposition, twiddle factor precomputation,
|
|
Montgomery multiplication for modular arithmetic, and SIMD vectorization with AVX2 (16
|
|
coefficients per instruction). We present our Go implementation with hand-written assembly
|
|
for the inner loop, achieving 0.9\,$\mu$s per NTT-256 on AMD Zen~4---within 5\% of the
|
|
reference C implementation compiled with \texttt{-O3}. We benchmark against naive polynomial
|
|
multiplication, showing a 28x speedup for degree-256 polynomials. This is the bridge between
|
|
the mathematics of lattice cryptography and the metal it runs on.
|
|
\end{abstract}
|
|
|
|
\tableofcontents
|
|
\newpage
|
|
|
|
%% ============================================================
|
|
|
|
\input{sections/01-why-ntt-matters}
|
|
\input{sections/02-mathematical-foundations}
|
|
\input{sections/03-the-butterfly-operation}
|
|
\input{sections/04-twiddle-factors}
|
|
\input{sections/05-montgomery-multiplication}
|
|
\input{sections/06-the-complete-ntt}
|
|
\input{sections/07-simd-vectorization-with-avx2}
|
|
\input{sections/08-benchmarks}
|
|
\input{sections/09-correctness-verification}
|
|
\input{sections/10-fhe-applications}
|
|
\input{sections/11-memory-layout-and-cache-effects}
|
|
\input{sections/99-conclusion}
|
|
|
|
\end{document}
|