搜索结果
查询Tags标签： varphi，共有 28条记录-
P4139 上帝与集合的正确用法
求 \[2^{2^{2^{2^{2^{...}}}}}mod\,p \]\[p\leq 10^7 \] 显然硬干是不行的，那么考虑别的思路。设 \(f(p)\) 为原式模 \(p\) 的解，那么 \(f(p)=2^{f(\varphi(p))+\varphi(x)}\) ,递归可以求出上一项的值即可，边界是 \(\varphi(p)=1\) 时 \(f(p)=0\) ，需要预处理出 \(\v…
2022/8/30 23:24:12 人评论 次浏览 -
筛法求欧拉函数之和
题目描述 求\(1\sim n\)每个数欧拉函数之和 想法如果\(i\)是质数 \(\varphi (i) = i - 1\)质数\(i\)只有\(1\)和\(i\)两个因数，\(i\)不和\(i\)本身互质，因数只有一个\(1\)，所以互质的数就有\(i-1\)个如果\(i\)不是质数\(i \% j = 0\) \(j\)是质数 则\(j\)即\(i\)的一个…
2022/7/24 6:24:07 人评论 次浏览 -
P4240 毒瘤之神的考验
Description \(\mathcal{P}\text{ortal.}\) Solution 首先想到要把 \(\varphi(ij)\) 拆开，这里有个公式 \[\varphi(ij)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} \]考虑证明，有 \[\begin{aligned} \varphi(i)\varphi(j) &= i\prod\limits_{p|i,p…
2022/7/5 23:21:25 人评论 次浏览 -
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 人评论 次浏览 -
P3747 [六省联考 2017] 相逢是问候
Problem: 题目描述Informatik verbindet dich und mich. 信息将你我连结。B 君希望以维护一个长度为 \(n\) 的数组，这个数组的下标为从 \(1\) 到 \(n\) 的正整数。 一共有 \(m\) 个操作，可以分为两种：0 l r 表示将第 \(l\) 个到第 \(r\) 个数（ \(a_l,a_{l+1} ...a_r\)…
2022/6/3 23:23:19 人评论 次浏览 -
复杂度分析
复杂度分析 前言 \(O(x)\) 表示 \(x\) 的严格上界，\(\Omega(x)\) 表示 \(x\) 的严格下界，\(\Theta(x)\) 表示 \(x\) 的严格界（即严格上下界同阶）。 让人遗憾的是，人们在OI往往滥用了它们，严格来说，除了 \(O(1)\) 和 \(\Theta(1)\) 可以无歧义的混用，其他地方都应该…
2022/4/22 23:45:33 人评论 次浏览 -
【学习笔记】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 人评论 次浏览 -
经典同态加密算法（加法与乘法）
加法同态 - Paillier算法Pailier算法是法国密码学家Paillier于1999年欧密会上发表，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法。 数学知识 1、Carmichael函数，当a与n互素时，aλ(n)a^{λ(n)}aλ(n) = 1 mod n 卡迈克尔函数定义：当 n 为 1、2…
2022/1/14 12:03:53 人评论 次浏览 -
经典同态加密算法（加法与乘法）
加法同态 - Paillier算法Pailier算法是法国密码学家Paillier于1999年欧密会上发表，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法。 数学知识 1、Carmichael函数，当a与n互素时，aλ(n)a^{λ(n)}aλ(n) = 1 mod n 卡迈克尔函数定义：当 n 为 1、2…
2022/1/14 12:03:53 人评论 次浏览 -
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
算法竞赛进阶指南--打卡--数学知识篇--0x30 ①：可见的点（欧拉函数，暴力）在一个平面直角坐标系的第一象限内，如果一个点$ (x,y)$ 与原点 \((0,0)\)的连线中没有通过其他任何点，则称该点在原点处是可见的。 例如，点 \((4,2)\) 就是不可见的，因为它与原点的连线会通过…
2022/1/7 9:03:39 人评论 次浏览 -
# 算法竞赛进阶指南--打卡--数学知识篇--0x30
算法竞赛进阶指南--打卡--数学知识篇--0x30 ①：可见的点（欧拉函数，暴力）在一个平面直角坐标系的第一象限内，如果一个点$ (x,y)$ 与原点 \((0,0)\)的连线中没有通过其他任何点，则称该点在原点处是可见的。 例如，点 \((4,2)\) 就是不可见的，因为它与原点的连线会通过…
2022/1/7 9:03:39 人评论 次浏览 -
RAS加密算法
信息的加密与去密 信息加密的简单模型如图所示：就是先对数字信息\(x\)做一个变换\(E\)，将变换后的信息\(y=E(x)\)发出，接收方收到信息\(y\)后，进行一个相反的变换\(D\)(也就是\(E\)的逆运算)，恢复成数字信息\(x=D(y)\)，从而识别原始信息。 通常把数字信息\(x\)叫做明…
2022/1/4 1:07:22 人评论 次浏览 -
RAS加密算法
信息的加密与去密 信息加密的简单模型如图所示：就是先对数字信息\(x\)做一个变换\(E\)，将变换后的信息\(y=E(x)\)发出，接收方收到信息\(y\)后，进行一个相反的变换\(D\)(也就是\(E\)的逆运算)，恢复成数字信息\(x=D(y)\)，从而识别原始信息。 通常把数字信息\(x\)叫做明…
2022/1/4 1:07:22 人评论 次浏览
