搜索结果
查询Tags标签： pmod，共有 21条记录-
Millar-Rabin 米勒罗宾算法小结 （内附费马小定理证明以及二次探测定理证明）
因为他我学了龟速乘 Millar-robin 米勒罗宾 这个小东西是用来素数判定的，且听我细细道来。 前置知识肥妈小定理 又名费马小定理 ： 当一个数 \(x\) 不是一个质数 \(p\) 的倍数时有： \[x^{p-1} \equiv 1 \pmod{p} \]证明： 对于一个序列 \[b = \left \{1,2,3....p-1\rig…
2022/9/2 1:25:35 人评论 次浏览 -
关于一加一碰手游戏的一点研究
首先介绍 “一加一碰手游戏”。 具体规则是这样的：游戏有两个玩家，每个玩家有两只手。初始所有手上的数字都为 \(1\)。两个玩家轮流行动，轮到一个玩家时他可以选择对方任意一只手上的数字，将自己任意一只手上的数字加上这个数后对 \(10\) 取余数。若有一只手上的数字为…
2022/8/29 23:25:46 人评论 次浏览 -
二次剩余与 Cipolla 算法
二次剩余 对于 \(P,n\)，若存在 \(x\)，满足： \[x^2≡n\pmod p \]则称 \(n\) 为模 \(P\) 意义下的二次剩余。 勒让德符号 定义如下： \[\left(\frac{n}{p}\right)= \begin{cases} 1,&n\text{ 在模 $p$ 意义下是二次剩余}\\ -1,&n\text{ 在模 $p$ 意义下是非二次剩…
2022/7/28 14:34:12 人评论 次浏览 -
快速幂求逆元
快速幂求逆元 给定 $ n $ 组 $ a_i, p_i $，其中 $ p_i $ 是质数，求 $ a_i $ 模 $ p_i $ 的乘法逆元，若逆元不存在则输出 impossible。 注意：请返回在 $ 0 \sim p-1 $ 之间的逆元。 乘法逆元的定义若整数 $ b，m $ 互质，并且对于任意的整数 $ a $，如果满足 $ b|a $，…
2022/7/24 6:23:50 人评论 次浏览 -
二次剩余 Cipolla 算法浅析
参考资料yyb blog Kewth blog求解 \[x^2=n \pmod p \]仅介绍模数 p 为奇素数的解法，也就是 Cipolla 算法。 判定是否存在二次剩余 设 \(n=g^a,x=g^b\)，由于原根环的长度为 \(p-1\) （是个偶数）， 列出方程 \(2b = a \pmod {p-1}\)，根据贝祖定理，当且仅当 \(\gcd(p-1,…
2022/7/6 1:21:02 人评论 次浏览 -
RSA
一、基本原理 公钥与私钥的产生随机选择两个不同大质数 \(p\) 和 \(q\)，计算 \(n=p\times q\)。 求得 \(\varphi ( n )\)。 选择 \(e < \varphi ( n )\)，使 $e \perp \varphi (n) $。并求得 \(e\) 在模 \(\varphi ( n )\) 下的逆元 \(d\)。 销毁 \(p\) 和 \(q\)。此时…
2022/6/24 23:24:40 人评论 次浏览 -
乘法逆元学习笔记
乘法逆元和求法 基本的数论知识，有必要补一发。 开始之前模运算：取余运算，比如 \(a \bmod b\) 就是 \(a\) 除以 \(b\) 得到的余数。性质：在加、减、乘、乘方的运算过程中，进行取余运算，不会对结果产生影响。优先级：取余运算的优先级和乘法、除法的优先级相同，高于…
2022/4/30 23:14:13 人评论 次浏览 -
【学习笔记】BSGS 算法
引入 BSGS（baby-step giant-step），即大步小步算法，常用于求解离散对数问题。该算法可以在 \(O(\sqrt p)\) 的时间复杂度内求解 \[a^x \equiv b \pmod p \]第一部分：\(a \perp p\) 我们将求解的答案 \(x\) 设为 \(km-c \ (c < m)\) 的形式，即 \[a^{km-c} \equiv b…
2022/3/5 22:15:11 人评论 次浏览 -
数论同余学习笔记 Part 2
逆元 准确地说，这里讲的是模意义下的乘法逆元。 定义：如果有同余方程 \(ax\equiv 1\pmod p\)，则 \(x\) 称为 \(a\bmod p\) 的逆元，记作 \(a^{-1}\)。 作用是抵消乘法，即 \(x\cdot a\cdot a^{-1}\equiv x\pmod p\) 进一步可以得到 \(\frac xa\equiv x\times a^{-1}\pm…
2022/2/8 23:51:17 人评论 次浏览 -
Tonelli-Shanks算法_python
Tonelli-Shanks算法_python 该算法应用于求二次剩余 也就是形如x2≡n(modp)x^2\equiv n\pmod px2≡n(modp)的同余式，已知n,pn,pn,p求xxx 判断二次（非）剩余 为了执行这个算法，需要知道如何判断二次（非）剩余 所谓二次（非）剩余也就是上面提到的同余式有无解的另…
2022/1/22 21:04:47 人评论 次浏览 -
RSA 加密算法
RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德李维斯特（Ron Rivest）、阿迪萨莫尔（Adi Shamir）和伦纳德阿德曼（Leonard Adleman）在1977年一起提出的[1] RSA 加密算法的可靠性源自于对于极大的整数做因数分解很难在有限的时…
2022/1/11 9:04:01 人评论 次浏览 -
RSA 加密算法
RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德李维斯特（Ron Rivest）、阿迪萨莫尔（Adi Shamir）和伦纳德阿德曼（Leonard Adleman）在1977年一起提出的[1] RSA 加密算法的可靠性源自于对于极大的整数做因数分解很难在有限的时…
2022/1/11 9:04:01 人评论 次浏览 -
《算法竞赛进阶指南》笔记
目录0x30 数学知识0x33 同余概念与定理例题The Luckiest Number扩展欧几里得算法$(exgcd)$定理及概念线性同余方程高次同余方程0x34 矩阵乘法0x35 高斯消元与线性空间高斯消元线性空间0x36 组合计数基本概念组合数的求法二项式定理多重集的排列数与组合数Lucas 定理Catala…
2021/11/15 22:12:21 人评论 次浏览 -
《算法竞赛进阶指南》笔记
目录0x30 数学知识0x33 同余概念与定理例题The Luckiest Number扩展欧几里得算法$(exgcd)$定理及概念线性同余方程高次同余方程0x34 矩阵乘法0x35 高斯消元与线性空间高斯消元线性空间0x36 组合计数基本概念组合数的求法二项式定理多重集的排列数与组合数Lucas 定理Catala…
2021/11/15 22:12:21 人评论 次浏览 -
[噼昂!]探监心得
Problem A. 货币兑换 / \(\mathcal{Money}\)最贪心的思路显然是每次取当前花费最小的一边，但是暴力做显然会超时。考虑我们这样选造成的后果 —— 两种数字花费的价格一定是差不多的，于是我们可以二分这个“差不多”的价格 \(mid\)，每次尽可能将两种货币能换的都换了，…
2021/11/8 23:14:48 人评论 次浏览
