BSGS

#include<bits/stdc++.h> using namespace std; #define int long long int a,b,mod; map<int,int> mp; int ksm(int x,int y,int mod){ int ans=1; while(y){ if ......

离散对数问题: 在循环群(循环群的定义见密码协议学习笔记(1.4):密码学的一些数学基础 - Isakovsky - 博客园 (cnblogs.com))$(\mathbb{G},\cdot)$上已知两个元素$g,h\in\mathbb{G}$,求式子$g^x=h$中$x$的值的问题,叫做离散对数问 ......

### 阶 由欧拉定理得 $a^{\varphi(m)}\equiv1\space(\text{mod}\space m),(a,m)=1$ . 故满足 $a^n\equiv1\space(\text{mod}\space m)$ 的最小 $n$ 存在，称为 $a$ 模 $m$ 的阶，记作 $\de ......

# 7.29 数论 WIP $a\equiv b\pmod p\Rightarrow \frac{a}{d}\equiv \frac{b}{d}\pmod{\frac{p}{d}},d=\gcd(a,b,p)$。 ## exGCD 1. 若 $(a,b)=1$，则 $0\leq xb\to a\bm ......

上一篇博客提到，BSGS算法是用来解决形如：$a^{x}\equiv b\pmod{p}$ 的高次同余方程。其中 $a\perp p$。 那如果 $a$ 与 $b$ 不互质，阁下又该如何应对呢？ exBSGS算法就是来解决形如：$a^{x}\equiv b\pmod{p}$ 的高次同余方程。其中 $ ......

今天刚学了个算法：BSGS算法（Baby-Step Giant-Step），即大步小步算法。常用于求解离散对数问题。 该算法可以在 $O(\sqrt p)$ 的时间内求解形如：$a^{x}\equiv b\pmod{p}$ 的高次同余方程。 **问题：** [P3846 [TJOI2007] 可爱的 ......

# (ex)BSGS/（扩展）大步小步算法 学习笔记 在即将暂时退役之际杀掉了[P4195](https://www.luogu.com.cn/problem/P4195)的毒瘤模板题，于是来写篇学习笔记。 谨此为我初中三年摆烂的OI生涯画上一个句号。（距离中考还有20天！） ## BSGS [li ......

## 取模 > 取模符号：$x \bmod y$，表示 $x$ 除以 $y$ 得到的余数。 例如， $$ 5 \bmod 3 = 2\\ 7 \bmod 4 = 3\\ 3 \bmod 3 = 0\\ $$ 设 $x$ 为被除数，$y$ 为除数，$z$ 为余数，则 $x = k \cdot y + ......

 ![](https://img2023.cnblogs.com/blog/3122215/20 ......

## 简介 大步小步(Baby Step Giant Step)算法，可以在 $O(\sqrt{p}\cdot f(p))$ 的时间复杂度内（$f(p)$ 为一个大小为 $p$ 的映射结构（如 map、hash table）进行单次读取 / 随机访问 的时间复杂度）内解下列关于 $x$ 的方程（离散 ......

距离上一篇已经四个月了，我来填坑了 上一篇：$浅谈同余2(扩展欧几里得，中国剩余定理，BSGS)$ (https://www.cnblogs.com/xyy-yyds/p/17418472.html) 0x50 扩展BSGS $O(\sqrt n)$ 【模板】扩展 BSGS/exBSGS 题目背景 ......

上一篇：$浅谈同余1(常用定理和乘法逆元)$ (https://www.cnblogs.com/xyy-yyds/p/17418458.html) 下一篇: $浅谈同余3(扩展中国剩余定理，扩展BSGS)$ (https://www.acwing.com/blog/content/34866/) 0 ......

解决高次同余问题。 $a^x\equiv b(\mod p)$，其中 $a$ 与 $p$ 同余。 这个形式与欧拉定理类似。 思想：meet in the middle（折半搜索）。 具体的，令 $x=A\times t-B$，且 $x$ 一定在 $[0,\phi(p))$ 的范围内。但是 $p$ 是 ......

在 $O(\sqrt{p})$ 的时间内求解 $$ a^x \equiv b \pmod p $$ 其中 $a\perp p$，方程的解 $x$ 满足 $0 \le x < p$。 ......