当前位置: 首页 > news >正文

求阶

阶:满足 \(x^{k}\equiv 1(\text{mod}\ p)\) 的最小 \(k\)
首先,若 \(x\not\perp p\),则无解。
\(f(k) = x^k\mod p\)
若有解,则由费马小定理知,\(k = p - 1\)\(f(x) = 1\) 的一个解。
令其最小解为 \(k_0\)
则,\(f\) 是周期函数且 \(k_0\) 是其最小正周期。
因为 \(f(k + k_0) = x^{k + k_0}\mod p = x^{k}\cdot x^{k_0}\mod p = x^k\mod p = f(k)\)
我们易得,\(k_0 \mid (p - 1)\)
因为假设 \(k_0\nmid(p - 1)\),令 \(p - 1 = k_0m + n,1\leq n\leq m - 1\)

\[1 = x^{p - 1}\mod p = x^{k_0m + n}\mod p = (x^{k_0})^m \cdot x^n = x^n\mod p \]

这与 \(k_0\) 是最小解矛盾。
所以成立。
因此,我们可以枚举 \(p - 1\) 的因数,来求阶。

http://www.hskmm.com/?act=detail&tid=25514

相关文章:

  • gin 框架 - 教程
  • 赛前训练 5 树形 dp
  • 递推求解逆元
  • 一些做题记录(2025 2-3)
  • 智慧决策的透明化路径:“空白金兰契”架构下的“悟空备案制”研究
  • 笔记:寻找适合自己的简历工具(YAMLResume)
  • 实用指南:Linux 权限管理入门:从基础到实践
  • vue插槽
  • Magnet Axiom 9.6 新增功能概览 - 数字取证与分析
  • Windows 11 24H2 中文版、英文版 (x64、ARM64) 下载 (2025 年 9 月发布)
  • Windows 11 25H2 正式版发布,新增功能简介
  • 无法定时发送
  • 计算能力的重要性:从内存配置到进程迁移的未来展望
  • MongoDB财报超预期,文档数据库技术解析
  • 深入解析:【RabbitMQ】- Channel和Delivery Tag机制
  • 2020CSPS T1 儒略日题解
  • 调用百度AI接口实现网络图片中的文字识别
  • 英语_阅读_ChatGPT_待读
  • 实用指南:React 组件异常捕获机制详解
  • win11 为什么我的程序断网就转入导后台进程
  • 深入解析:AI与区块链:数据确权与模型共享的未来
  • 10.6阅读笔记
  • hetao 国庆
  • 详细介绍:运维 pgsql 安装完后某次启动不了
  • visual studio
  • [MCP] StreamableHTTPServer
  • 牛客 周赛109 20250924
  • 罗技G102螺丝型号
  • 详细介绍:深入剖析C#构造函数执行:基类调用、初始化顺序与访问控制
  • 英语_阅读_Let your baby go_待读