数论基础整除只在整数域上讨论。一般形式为\(a|b\)，叫做\(a\)能整除\(b\)。其性质在此不过多叙述。约数与整除相关。若\(a|b\)，则称\(b\)是\(a\)的倍数，\(a\)是\(b\)的约数。在具体问题中，如果没有特别说明，约数总是指正约数。最大公因数和最小公倍数即\((a,b

先直接从IMO2005预选赛C7开始看。问题：给定一个长度为\(n\)的序列\(a\)，保证\(n\mid(\suma_i)\)。证明存在两个排列\(\sigma\)与\(\tau\)，使得\(\sigma_i+\tau_i\equiva_i\pmodn\)。解：若存在一个序列\(a\)和其的一组解\((\sigma,\tau)\)，同时存在一个序列\(b

1阶1.1定义由欧拉定理可知，对于\(a\in\mathbb{Z},m\in\mathbb{N}^+\)，如果\(\gcd(a,m)=1\)，则\(a^{\varphi(m)}\equiv1\pmodm\)。因此满足同余式\(a^n\equiv1\pmodm\)的最小正整数\(n\)存在，这个\(n\)就被称为\(a\)模\(m\)的阶，记作\(\delta_m(a)\)。1.2性质

前置根据快速傅里叶变换，可以在\(\Theta(n\logn)\)的时间计算卷积。但是由于用到了复数及三角函数，具有精度误差，且不方便取模。于是考虑快速傅里叶变换在数论上的实现，避免了精度误差，支持了取模运算。引入概念原根：阶定义由欧拉定理可知，对\(a\in\mathbf{Z}，m\in\mathbf{N}^

学原根发现拔山盖世算法忘光了，干脆一块儿写了吧。\(BSGS\)算法\(BSGS\)算法，又名拔山盖世算法、北上广深算法。他解决的问题如下：求解最小的可行的\(k\)，满足\(a^k\equivb(\bmodp)\)，其中保证\(\gcd(a,p)=1\)。容易想到暴力枚举，时间复杂度\(O(p)\)，但是巨劣，考虑优化。

RSA加密是一种非对称加密，原理是：使⽤算法可以⽣成两把钥匙A和B使⽤A加密的信息，使⽤B可以解开使⽤B加密的信息，使⽤A可以解开⽇常使⽤中，我们把⼀把作为公钥公开发布。⼀把作为私钥，⾃⼰保留。这样，任何⼈都可以使⽤我们的公钥加密信息发给我们，我们则可以使⽤⾃⼰的私

可能是不知道什么学习笔记捏阶使得\(a^x\equiv1\pmodm\)的最小正整数\(x\)被称为\(a\)模\(m\)的阶，记作\(\delta_m(a)\)。由欧拉定理可知，\(a\perpm\)是\(\delta_m(a)\)存在的充要条件。证明充分性：若\(a\perpm\)，根据欧拉定理，\(x=\varphi(m)\)就是一个解，所以

CTF-CRYPTO椭圆加密4.BSGS(小步大步法)[HITCTF2021]task.py#EllipticCurve:y^2=x^3+7modNwhichissecp256k1N=2**256-2**32-2**9-2**8-2**7-2**6-2**4-1E=EllipticCurve(GF(N),[0,7])xG=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b1

数论四大定理：包括威尔逊定理、欧拉定理、孙子定理（中国剩余定理）、费马小定理同余同余：对于任意整数a，b，对指定的整数m(m>1)进行整除，若余数相同，则称a和b模m同余，记作\(a\equivb(mod\quadm)\)例如：\(3\equiv10(mod\quad7)\)通过整数m对任意整数进行分类，同余（模m）为一类，即剩余类

多项式全家桶多项式求逆给定多项式\(f(x)\)，求\(f^{-1}(x)\)。首先，易知\[[x^0]f^{-1}(x)=([x^0]f(x))^{-1}\]假设已经求出\(f(x)\)在模\(x^{\lceil\frac{n}2\rceil}\)意义下的逆元\(f_0^{-1}(x)\)。\[f(x)f_0^{-1}(x)\equiv0\pmod{x^{\lceil\frac{n}2\rceil}}\\f(x)

不难发现循环节长度为60，预处理前60项即可，下为证明。注意到\(F_{15}\equivF_0\,(mod\,10)\)，由斐波那契性质\(F_n=F_{n-1}+F_{n-2}\)。得到\(F_{16}=F_{15}+F_{14}，F_{17}=F_{16}+F_{15}，F_{18}=F_{17}+F_{16}\)\(F_{15}\equiv0\cdotF_{14}，F_{16}\equiv1\cdotF_{14}，F_{17

##二次剩余>这东西挺有意思的。###问题>给定$n,p$，求方程$x^2\equivN\bmodp$的解。>>保证$p$是奇素数。####1.判断一个$N$是否是二次剩余(方程解的个数)根据费马小定理，对于任意非$0$整数$x$都有$x^{p-1}\equiv1\bmodp$。则$x^{p-1}\equivx^{2{\fra

在HTML5中，<meta>标签的http-equiv属性用于提供与HTTP头部字段等效的名称/值对。这允许开发者在HTML文档中模拟一些HTTP响应头部的效果，尽管这些头部实际上并不是由服务器发送的。然而，需要注意的是，随着Web技术的发展，许多http-equiv指令已经过时或被更好的替代方案所取代，因

欧拉函数定义与\(m\)互素的剩余类的个数记为\(\varphi(m),\varphi(m)\)称之为欧拉函数关于欧拉函数的结论定理1:(欧拉定理)若\((k,m)=1,\)则:\(k^{\varphi(m)}\equiv1(\bmodm)\)$定理2:(费尔玛小定理)若\(p\)为素数,则对所有的整数\(a,a^{p}=a(\bmodm)\)$定

我们知道，扩展欧拉定理的内容如下：\[a^b\equiv\begin{cases}a^b&b<\varphi(m)\\a^{(b\bmod\varphi(m)+\varphi(m))}&b\ge\varphi(m)\end{cases}\pmodm\]但是又有多少人会它的证明呢？也许大佬们一看到就会证了，但是我刚刚才会，不得不说oi-wiki上的证明是真屎。首先第一种情况

更新日志2024/12/11：开工。概念同中国剩余定理，但模数两两不相同。求解。思路我们先考虑两个方程如何解决。\[\begin{cases}x\equivr_1\pmod{m_1}\\x\equivr_2\pmod{m_2}\end{cases}\\\Rightarrowx=m_1p+r_1=m_2q+r_2\\\Leftrightarrowm_1p-m_2q=r_2-r_1\]其中

更新日志2024/12/09：开工。概念就不写引入部分了，直接进入正题。中国剩余定理用来求解形如下式的方程的一组特解：\[\begin{cases}x\equivr_1\pmod{m_1}\\x\equivr_2\pmod{m_2}\\x\equivr_3\pmod{m_3}\\\dots\\x\equivr_n\pmod{m_n}\end{cases}\]其中\(m\)

多项式学习笔记目录多项式学习笔记多项式乘法逆多项式乘法逆给出\(F(x)\)，求\(G(x)\)使得\(F(x)G(x)\equiv1(\bmodx^n)\)。首先\(G_0(x)=\frac{1}{F_0(x)}\)，然后考虑倍增，用\(\bmodx^{\left\lceil\frac{n}{2}\right\rceil}\)的答案推\(\bmodx^n\)的答案：\[

更新日志2024/12/05：开工。2024/12/06：完工。公式对于一个质数\(p\)，其必然满足：\[\LARGE(p-1)!\equiv-1\pmodp\]那个\(!\)是阶乘不是\(\not\equiv\)证明首先同余式两边同时除以\(-1\)（必与\(p\)互质），得到：\[(p-2)!\equiv1\pmodp\]注：左侧去掉了\(p-1\)不难发现

更新日志2024/12/05：开工。公式若\(p\)为质数，则：\[\LARGEa^p\equiva\pmodp\]若同时满足\(\gcd(a,p)=1\)，则：\[\LARGEa^{p-1}\equiv1\pmodp\]证明欧拉定理快速证明我们先证明第二个形式：根据欧拉定理可得：\[a^{\varphi(p)}\equiv1\pmodp\\\because\varphi(p

\(\mathrm{RSA}\)公钥系统(二)\(\mathrm{RSA}\)密钥生成、加密和解密步骤BobAlice密钥生成选择私密的质数$p$和$q$选择加密指数$e$使得$\text{gcd}(e,(p-1)(q-1))=1$公布$N=pq$和$e$\(~\)加密\(~\)选择明文$m$使用Bob的公

\(\mathrm{RSA}\)公钥系统(一)定理1模\(pq\)情形的“欧拉”公式费马小定理在\(m=pq\)时的推广，这是在密码学应用中最重要的情况。设$p$和$q$是不同的素数，且设$g=\gcd(p-1,q-1)$。那么对于所有满足$\gcd(a,pq)=1$的$a$，有：\[a^{\frac{(p-1

感觉还是挺好玩的一个题目的。首先显然猜想如果\(inv\equiv\frac{n(n-1)}{2}\pmod2\)才有解。否则尝试构造。如果现在存在\(i\neqpos_i\)，我们可以操作这个数并且用完他的所有余额让他回到应该在的位置上。这个其实就是先操作\((i,j)\)（\(j\)余额没有用完）再操作\((i,a_i)

1.1.4逆元主要内容：扩欧求逆元，快速幂求逆元，线性（递归）求逆元，同余模公式（补充），反复平方法求幂（补充）一、逆元首先给出逆元的定义：$$\begin{aligned}假设a\cdotp&\equiv1\quad(mod\quadb)\\且(a,b)&=1\quad即\quada,b互素\\则称p为a的逆元&，记作p=a^{-1}\end{aligned}$

在Lagrange之前，不妨先看看CRT。CRT问题\[\begin{cases}x\equivr_1\pmod{m_1}\\x\equivr_2\pmod{m_2}\\\vdots\\x\equivr_n\pmod{m_n}\end{cases}\]其中\(m_{1\simn}\)两两互质。解法定义\(e_i\)为满足\(e_i\equiv1\pmod{m_i}\)且对于任