快速数论变换NTT学习笔记

2024-01-26 13:04

本文主要是介绍快速数论变换NTT学习笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是NTT?

数论变换(number-theoretic transform, NTT)是离散傅里叶变换(DFT)在数论基础上的实现。
NTT是一种计算卷积的快速算法,FFT也是其中一种。

但是FFT具有一些实现上的缺点,举例来说,向量必须乘上复数系数的矩阵进行处理,而且每个复数系数的实部和虚部是一个正弦及余弦函数,因此大部分的系数都是浮点数,也就是说,必须做浮点复数运算,计算量会比较大,并且浮点数运算产生的误差会比较大。

NTT解决的是多项式乘法带模数的情况,受到模数的限制,数也比较大。
在数学中,NTT 是关于任意环上的DFT。在有限域的情况下,通常称为数论变换,即NTT。

原根

FFT的实现是找单位圆上的 n n n个点 ω n 0 , ω n 1 , … , ω n n \omega_n^0, \omega_n^1, \dots, \omega_n^n ωn0,ωn1,,ωnn(称为单位根) ,然后对这些点进行FFT。因此,对于NTT,我们需要在取模域上找到和这个点等价的数。为了找到这 n n n个等价的数,我们要使用原根。

n n n为大于1的2的幂, p p p为质数且 n ∣ ( p − 1 ) n|(p-1) n(p1),即 n n n整除 p − 1 p-1 p1 ,则存在本原 n n n次方根。对于质数 p = q n + 1 p=qn+1 p=qn+1,(模 p p p意义下的)原根 g g g满足: g q n = 1 ( m o d p ) g^{qn}=1 (\mod p) gqn=1(modp),将 g n = g q ( m o d p ) = g p − 1 n ( m o d p ) g_n=g^q (\mod p)=g^{{p-1}\over n} (\mod p) gn=gq(modp)=gnp1(modp)看作 ω n \omega_n ωn的等价。

于是原根 g n g_n gn和单位根 ω n \omega_n ωn满足相似的性质!

原根和单位根的等价性

g n = g p − 1 n g_n=g^{{p-1}\over n} gn=gnp1

于是,
g n n = g n ⋅ p − 1 n = g p − 1 g_n^n=g^{n \cdot {p-1\over n}}=g^{p-1} gnn=gnnp1=gp1

g n n 2 = g p − 1 2 g_n^{n\over 2}=g^{p-1\over 2} gn2n=g2p1

g a n a k = g a k ( p − 1 ) a n = g k ( p − 1 ) n = g n k 【对应单位根消去引理】 g_{an}^{ak}=g^{\frac{ak(p-1)}{an}}=g^{\frac{k(p-1)}{n}}=g_n^k【对应单位根消去引理】 ganak=ganak(p1)=gnk(p1)=gnk【对应单位根消去引理】

可以得到:
g n n ≡ 1 ( m o d p ) 【对应单位根 ω n n ≡ 1 】 g_n^n \equiv 1 (\mod p) 【对应单位根\omega_n^n\equiv 1】 gnn1(modp)【对应单位根ωnn1

g n n 2 ≡ − 1 ( m o d p ) 【对应单位根 ω n n 2 ≡ − 1 】 g_n^{n\over 2} \equiv -1 (\mod p)【对应单位根\omega_n^{n\over 2}\equiv -1】 gn2n1(modp)【对应单位根ωn2n1

g n k + n 2 = g n k ⋅ g n n 2 = − g n k ( m o d p ) 【对应单位根折半引理】 g_n^{k+{n\over 2}}=g_n^{k}\cdot g_n^{n\over 2}=-g_n^{k} (\mod p)【对应单位根折半引理】 gnk+2n=gnkgn2n=gnk(modp)【对应单位根折半引理】

( g n k + n 2 ) 2 = g n 2 k + n = g n 2 k ⋅ g n n = g n 2 k ( m o d p ) (g_n^{k+{n\over 2}})^2=g_n^{2k+n}=g_n^{2k}\cdot g_n^n=g_n^{2k} (\mod p) (gnk+2n)2=gn2k+n=gn2kgnn=gn2k(modp)

我们发现单位根具有的性质原根都有,所以我们将 g n k g_n^k gnk g n k + n 2 g_n^{k+{n\over 2}} gnk+2n代入,本质上和将 ω n k \omega_n^k ωnk ω n k + n 2 \omega_n^{k+{n\over 2}} ωnk+2n代入并无二异!

在INTT中,乘单位根的共轭复数的操作也就会相应地变为乘原根在模意义下的逆元。

常见的模数和原根如下:
p = 1004535809 = 479 × 2 21 + 1 , g = 3 p = 998244353 = 7 × 17 × 2 23 + 1 , g = 3 p=1004535809=479\times 2^{21}+1, g=3 \\ p = 998244353=7\times 17\times2^{23}+1, g=3 p=1004535809=479×221+1,g=3p=998244353=7×17×223+1,g=3

快速数论变换(FNTT)

简而言之,FNTT是NTT增加分治操作之后的快速算法,也是FFT在数论基础上的实现。FNTT使用的分治办法,与FFT使用的分治办法完全一致。

DFT、FFT、NTT、FNTT的关系

  • 在 DFT与NTT的基础上,增加分治操作,得到FFT与FNTT。分治操作同FFT一致。
  • 在DFT与FFT的基础上,将复数加法与复数乘法替换为模 p p p意义下的加法和乘法,一般大小限制在0到 p − 1 p-1 p1之间;将本原单位根改为模 p p p意义下的相同阶数的本原单位根,阶数为2的幂,即可得到NTT与FNTT。

一大堆参考资料

  • 快速数论变换(NTT)超详解
  • OI Wiki 快速数论变换
  • 快速数论变换NTT
  • 快速傅立叶变换FFT学习笔记

这篇关于快速数论变换NTT学习笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/646885

相关文章

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

SpringBoot快速接入OpenAI大模型的方法(JDK8)

《SpringBoot快速接入OpenAI大模型的方法(JDK8)》本文介绍了如何使用AI4J快速接入OpenAI大模型,并展示了如何实现流式与非流式的输出,以及对函数调用的使用,AI4J支持JDK8... 目录使用AI4J快速接入OpenAI大模型介绍AI4J-github快速使用创建SpringBoot

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操