Baby_Step_Gaint_Step(BSGS) 算法
2022/7/21 1:23:35
本文主要是介绍Baby_Step_Gaint_Step(BSGS) 算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
\(BSGS\) 算法,又称 “北(\(B\))上(\(S\))广(\(G\))深(\(S\))” 算法,“拔山盖世”算法,可以在 \(O(\sqrt{n})\) 的复杂度内求解离散对数问题。
题目描述:
给定质数 \(p\) 和整数 \(a, n\),求最小的非负整数 \(m\) ,满足 \(a^m \equiv n(mod\ \ p)\) 。
算法分析:
最暴力的算法就是每句每一个 \(m \in [1, p]\) ,看一下有没有一个 \(m\) 满足。时间复杂度 \(O(p)\) 。
因此就需要使用 \(\texttt{BSGS}\) 算法来求解 。
\(\texttt{BSGS}\) 算法的流程如下:
- 将原式做如下操作:
-
易得 \(k \leq \sqrt{q}\),\(b \leq \sqrt{q}\)。
-
我们枚举每一个 \(k\) ,将 \(a ^ {k \left \lfloor\sqrt{p}\right\rfloor}\) 的值存到一个 \(hash\) 里面,然后在枚举 \(b\),判断 \(hash\) 中是否存在即可。
时间复杂度 \(O(\sqrt{q})\)。
这篇关于Baby_Step_Gaint_Step(BSGS) 算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01动态面包屑学习:新手入门教程
- 2024-11-01动态权限学习入门指南
- 2024-11-01动态主题处理学习:初学者指南
- 2024-10-3111 个全球最好的 AI 文本转语音工具分析(2024 年)
- 2024-10-30数据回测教程:初学者必备指南
- 2024-10-30自动交易学习:新手入门指南
- 2024-10-30基于卡尔曼滤波器的递归状态估计与ROS 2的应用讲解
- 2024-10-30?? pgai 向量化工具:用一条 SQL 命令在 PostgreSQL 自动生成 AI 嵌入向量
- 2024-10-30量化进阶实战:零基础到初级量化交易者的必修课
- 2024-10-30量化交易项目实战:初学者指南