寒假有朋友打电话吐槽九省联考,看了眼数学卷子感觉非常刺激。刚开学没事干,试着做一下
\(19\). (\(17\) 分)
离散对数在密码学中有重要的应用。设 \(p\) 是素数,集合 \(X=\{1,2,\cdots,p-1\}\),若 \(u,v\in X,m\in\mathbb{N}\),记 \(u\otimes v\) 为 \(uv\) 除以 \(p\) 的余数,\(u^{m,\otimes}\) 为 \(u^{m}\) 除以 \(p\) 的余数;设 \(a\in X\),\(1,a,a^{2,\otimes},a^{3,\otimes},\cdots,a^{p-2,\otimes}\) 两两不同,若 \(a^{n,\otimes}=b(n\in\{1,2,\cdots,p-2\}\),则称 \(n\) 是以 \(a\) 为底 \(b\) 的离散对数,记为 \(n=\log(p)_{a}b\)
(2) 对 \(m_{1},m_{2}\in\{0,1,2,\cdots,p-2\}\),记 \(m_{1}\oplus m_{2}\) 为 \(m_{1}+m_{2}\) 除以 \(p-1\) 的余数。证明:\(\log(p)_{a}(b\otimes c)=\log(p)_{a}b\oplus\log(p)_{a}c\),其中 \(b,c\in X\)
(3) 已知 \(n=\log(p)_{a}b\),对 \(x\in X,k\in\{1,2,\cdots,p-2\}\),令 \(y_{1}=a^{k,\otimes},y_{2}=x\otimes b^{k,\otimes}\)。证明 \(x=y_{2}\otimes y_{1}^{n(p-2),\otimes}\)
只在 \(\mathbb{Z}\) 中讨论
\(x\) 除以 \(p\) 的余数记为 \(x\bmod p\)。\(x,y\) 除以 \(p\) 的余数相同记为 \(x\equiv y\pmod p\)
费马小定理:若 \(p\) 为素数,\(\gcd(a,p)=1\),则 \(a^{p-1}\equiv1\pmod p\)
证明:由 \(\forall i\in X,(ia\bmod p)\in X\) 且 \(i\ne j\Rightarrow ia\not\equiv ja\pmod p\) 得 \(X=\{ia\bmod p|i\in X\}\),则 \(\displaystyle\prod_{i\in X}i\equiv\prod_{i\in X}ia\pmod p\)。设 \(f=(p-1)!\),则有 \(f\equiv fa^{p-1}\pmod p\)。由 \(\gcd(f,p)=1\) 得 \(a^{p-1}\equiv1\pmod p\)
(2)
设 \(b=a^{m},c=a^{n}\)
只需证 \(b\otimes c=a^{m\oplus n,\otimes}\)
只需 \(a^{m+n}\equiv a^{(m+n)\bmod (p-1)}\pmod p\)
由费马小定理即证
(3)
\(y_{2}\times y_{1}^{n(p-2)}\equiv x\times a^{nk}\times a^{nk(p-2)}\equiv x\times(a^{nk})^{p-1}\equiv x\pmod p\)
(2) 的本质是 \(a^{n}\equiv a^{n\bmod(p-1)}\pmod p\),(3) 的本质是 \(a^{-1}\equiv a^{p-2}\pmod p\)。我是知道这两点编了个过程
对竞赛生来说纯送分,即使是我这种“号称学过”水平的退役 OIer 都会做
对高考生来说就很困难了。需要会 \(ax\equiv ay\pmod p,\gcd(a,p)=1\Rightarrow x\equiv y\pmod p\),注意到 \(a^{p-1}\) 的特殊性,借助 (1) 猜到费马小定理并证明。特别是放到卷子里,不知道前面做完能剩多少时间,至少我觉得不可做
不过我还是喜欢这种题,多学点科技总比在高考范围内硬卷好吧
标签:log,pmod,bmod,2024,cdots,九省,otimes,联考,equiv From: https://www.cnblogs.com/ft61/p/18021885