前言椭圆曲线配对，是各种加密构造方法(包括确定性阀值签名、zk-SNARKs以及相似的零知识证明)的关键元素之一。椭圆曲线配对(也叫“双线性映射”)有了30年的应用历史，然而最近这些年才把它应用在密码学领域。配对带来了一种“加密乘法”的形式，这很大的拓展了椭圆曲线协议的应

1.复数1.1复数的引入和定义1.1.1略谈数集扩充略了很多字。在数学在现实应用领域的发展过程中，我们常需要解类似的方程：\(x^2+a=0\)，然而这在实数集下无解。1.1.2虚数单位于的引入与复数的定义于是虚数单位"i"被引入，并且有\(i^2=-1\)。让复数表示为实数与虚数的

定义阶：对于\(a\perpm\)，定义阶\(\delta_m(a)\)表示最小的\(i\)满足\(a^i\equiv1\pmodm\)。原根：对于\(a\perpm\)，\(a\)是\(n\)的原根当且仅当\(\delta_m(a)=\varphi(m)\)。性质：\(a,a^2,a^3,...,a^{\delta_m(a)}\)互不相同。\(a^i\equiv1\pmod

卡特兰序列\(C_{k}(m,n)\)表示在网格中从\((0,0)\)走到\((m,n)\)时均不经过\(y=x+k\)的斜线即每时每刻满足\(y<x+k\)画图可得\(C_{k}(m,n)=\binom{n+m}{m}-\binom{n+m}{m+k}\)用法：任意前缀和不小于\(-x\)使用\(C_x\)（左括号是\(+1\))反射容斥学

较为冷门(?)的数论知识，但在解决一些特殊问题上有着重要的作用。整数的阶根据欧拉定理有正整数\(n\)和一个与\(n\)互素的整数\(a\)，那么有$a^{\phi(n)}\equiv1\pmod{n}$。因此至少存在一个整数满足这个方程。并且由良序原理可得一定存在一个最小正整数满足这个方程。、

离散对数离散对数的定义方式和对数类似.取有原根的正整数模数\(m\),设其一个原根为\(g\).对满足\((a,m)=1\)的整数\(a\)，我们知道必存在唯一的整数\(0\leqk<\varphi(m)\)使得\(g^k\equiva\pmodm\).我们称这个\(k\)为以\(g\)为底,模\(m\)的离散对数,记作\(k

阶先看看啥是阶.由欧拉定理可知,对于\(a\in\mathbf{Z},m\in\mathbf{N}^*\),若\((a,m)=1\),则\(a^{\varphi(m)}\equiv1\pmodm\).因此满足同余式\(a^n\equiv1\pmodm\)的最小正整数\(n\)存在,这个\(n\)称作\(a\)模\(m\)的阶,记作\(\delta_m(a)\)或\(\opera

原根学习笔记原根这是一个又臭又长的内容。拉格朗日定理：设\(p\)为素数，对于模\(p\)意义下的整系数多项式\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0(p\nmida_n)\]的同余方程\(f(x)\equiv0\pmodp\)在模\(p\)意义下至多有\(n\)个不同解。证明：使用归纳法，对于\(n=

\(\text{FFT}\)学习笔记多项式确定一个多项式，往往只需要知道每一次项前的系数是多少即可。众所周知，一个朴素的多项式往往可以被写成\[f(x)=\sum_{n\ge0}a_nx^n\]的形式，在这种形式下的两个多项式\(f,g\)的乘积\(h\)往往可以按照\[h(x)=(f*g)(x)=\sum_{n\ge0}(\sum_{i=0

12奇妙筛法已开工。12.1杜教筛12.2Min-25筛Min_25筛可以在\(\mathcalO\left(\frac{n^{\frac34}}{\logn}\right)\)的时间复杂度内解决一类积性函数前缀和问题。说形象点就是\(1s\)能跑\(10^{10}\)，相当优秀。要求：\(f(p)\)是关于\(p\)的低阶多项式，

阶与原根阶若正整数\(m,\a\)，满足\((a,m)=1\)，则使\(a^n\equiv1\pmodm\)的最小正整数\(n\)称为\(a\)模\(m\)的阶，记作\(\delta_m(a)\)。\(\delta_7(1)=1,\\delta_7(2)=3,\\delta_7(3)=6\)。原根若\(\delta_m(a)=\varphi(m)\)，则称\(a\)

书接上回...我们知道，我们在使用FFT时，靠的是单位根\(\omega\)。数学家证明这是复数域中唯一符合条件的数。可是它的浮点误差和带来的巨大运算时间使我们有点不能接受。于是，我们想想能不能找个替代品替代掉\(\omega\)。于是，原根就出现了！原根的引入阶对于一个数\(x\)，在

阶对于\(\gcd(a,p)=1\)，最小的\(t\)使得\(a^t\equiv1(\bmodp)\)称为\(a\)的阶。写作\(\operatorname{ord}_p(a)\)。若\(a^k\equiv1(\bmodp)\)，当且仅当\(\operatorname{ord}_p(a)|k\)。求阶的复杂度是\(O(\sqrt{n})\)。给定\(\gcd(a,p)=\gcd(b,p)=1\)，问是否存在

数论进阶原根与阶阶若\(a,p\)互质，定义\(a\)在模\(p\)意义下的阶为最小的正整数\(t\)满足\(a^t\modp=1\)。\(a\)在模\(p\)意义下的阶记作\(ord_p(a)\)，\(a^{ord_p(a)}\modp=1\)。对于整数\(k\)，\(a^k\equiv1(\modp)\)当且仅当\(ord_p(a)|k\)。计算

前言我曾今写过一篇标题一模一样的文章，但是那篇都是在抄书，写的太烂了。在此重构。模意义是什么？即小学学过的"余数"：\(13\)除以\(5\)商\(2\)余\(3\)。那么\(13\bmod5=3\)（\(\bmod\)读作模）。如果有两个数\(a,b\)除以一个数\(p\)的余数一样，则我们称\(a,b\)关于

原根&离散对数阶设\(m>1\)\(\gcd(a,m)=1\)，使\(a^r\equiv1(mod\m)\)的最小\(r\)是\(a\)对\(m\)的阶，记作\(\delta_m(a)\)定理一：设\(m>1\)，且\(gcd(a,m)=1\)，\(a^n\equiv1(mod\m)\)，则\(\delta_m(a)|n\)定理一推论：\(\delta_m(a)|\phi(m

NTT好吧，本质上就是FFT，把单位根换成了原根（不是很理解但是就是记住就行）优点能取模，FFT的复数你给我来取个模没有精度差，FFT浮点数的精度怎么也会出一点问题由于均为整数操作（虽然取模多），NTT常数小，通常比一大堆浮点运算的FFT要快缺点多项式的系数都必须是整数模数有限制，NTT题的模

目录原根阶阶的定义与基本性质原根原根的定义与基本性质原根判定性定理原根存在性定理原根的求法枚举法（最小原根）枚举法（所有原根）指标指标的定义与基本性质指标的求法BSGS算法扩展BSGS算法原根阶阶的定义与基本性质定义设\(a\in\Z,m\in\N^*\)且\(\gcd(a,m)=1\)，那么

快速数论变换|NTT初学前置FFT原根阶：称满足同余方程\(a^x\equiv1\modm\)的最小正整数解\(x\)为\(a\)的模\(m\)的阶，记为\(Ord_ma\)。观察到本质就是最短循环节，同时该同余方程类似于欧拉定理：\[a^{\varphi(m)}\equiv1\modm，a\botm\]那么显然两者的关系是

1.整除、欧几里得除法的的定义好像别的没啥好说的，就挑点自己记不太清的写上来.1.1Eratosthenes（厄拉托塞斯）筛法该方法用于快速获得小于整数N的素数集合，工作原理如下：对寻找小于整数N的素数，先求\(\sqrt{N}\)（没法取整就写成\(\sqrt{N}<[\sqrt{N}]+1\)的形式）,获取小于\(\sqrt{N}

T1题意：已知\(P=10^{18}+31\)为质数且存在原根\(g=42\)，记\(A_0\)为\(795484359100928850\)，\(A_k=f(A_{k-1})\)，其中\(0<f(x)<P\)且满足\(g^{f(x)}\equivx(modP)\)，可证明这样\(f(x)\)唯一存在，每次查询一点\(f(x)\)的取值，\(1\lex\le10^5\)。事实上，此

数学基础:抽象代数:一个算符的代数结构:幺半群:数的集合和一个算符构成的代数结构$(G,+)$,且满足封闭性结合律存在恒等元(在群中我习惯这么叫,避免混淆)群:满足如下条件的代数结构$(G,+)$:封闭性结合律存在恒等元对于每个元素均存在逆元交换群/阿贝尔群:满足如

题目链接description给定一个质数\(m\)，以及\(n,x\)和集合\(S\)。从集合\(S\)中任意选数构成长度为\(n\)的数列（一个数可以选多次），求数列元素乘积模\(m\)等于\(x\)的数列的数量。模\(1004535809\)。\(3\leqm\leq8000\)\(1\leqn\leq10^9\)\(|S|\leqm,0\leqx<m

FFTFFT是一种高效实现DFT和IDFT的方式，可以在\(O(n\logn)\)的时间内求多项式的乘法。多项式的点值表示不同于用每项的系数来表示一个多项式，我们知道对于给定的\(n+1\)个点值，可以确定唯一的\(n\)次多项式。这种用点值表示多项式的方法叫点值表示法。如果知道\(F(x

定义1对于一个非空集合\(G\)和某操作\(*\)，\((G,*)\)称为一个群，其中\(*\)是任意一个二元运算，\(G\)有限称为有限群性质:存在单位元\(e\)使得\(\forallg\inG\)使得\(g*e=e*g=g\)\(\forallg\inG\)，$\existsg'\inG$使得\(g*g'=g'*g=e\)，\(g\)和