扩展大步小步法解决离散对数问题

离散对数(Discrete Logarithm)问题是这样一个问题,它是要求解模方程

 a^x \equiv b \pmod m

这个问题是否存在多项式算法目前还是未知的,这篇文章先从 m 是质数开始介绍大步小步法(Baby Step Giant Step)来解决它,之后再将其应用到 m 是任意数的情况。这个算法可以在 \mathcal O(\sqrt m) 的时间内计算出最小的 x,或者说明不存在这样一个 x

题目链接:BZOJ-2480SPOJ-MODBZOJ-3239

(more…)

Read More

扩展欧几里得算法与中国剩余定理

在《孙子算经》中有这样一个问题:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

这个问题说的是,有一件物品,我们不知道它的数量。但是,如果三个三个数,最后会剩下两个;如果五个五个数,最后会剩下三个;如果七个七个数,最后会剩下两个。问这个东西的数量是多少?

实际上,这个问题在现在我们可以将其转化为一个同余方程组:

 \left\{ \begin{aligned} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{aligned} \right.

中国剩余定理告诉了我们像这样的同余方程组的解。这个定理又称为孙子定理,通常被简写成CRT(Chinese Remainder Theorem)。

这篇文章将会从欧几里得算法开始讲起,之后过渡到扩展欧几里得算法解线性方程,最后介绍中国生于定理。

(more…)

Read More

[数论]线性求所有逆元的方法

前几天在看 lucas 定理的时候发现要求 1,~2,\cdots,p-1\bmod p 的逆元,然后就看到了一个 \Theta(n) 的做法发现太神了,虽然想起来是挺简单的

这个做法实际上是这样的,首先 1^{-1} \equiv 1 \pmod p

然后我们设 p = k\cdot i + r,~r < i,~1 < i < p

再将这个式子放到\mod p 意义下就会得到

k\cdot i + r \equiv 0 \pmod p

两边同时乘上 i^{-1}\cdot r^{-1} 就会得到

 \begin{eqnarray*} k\cdot r^{-1} + i^{-1} &\equiv& 0 &\pmod p\\ i^{-1} &\equiv& -k\cdot r^{-1} &\pmod p\\ i^{-1} &\equiv& -\left\lfloor\frac{p}{i}\right\rfloor\cdot \left(p\bmod i\right)^{-1} &\pmod p\ \end{eqnarray*}

于是就可以从前面推出当前的逆元了,代码也就一行

Read More

[数论]Miller-Rabin素性测试

如果给出一个正奇数 n,要判断它是不是素数,有一个最简单暴力的方法,就是从 2 开始一直试到 \sqrt n,这样的话能保证结果绝对正确,但是,时间复杂度也就是 \Theta (\sqrt n),当 n 的规模到达 10^{30} 甚至更高的级别的时候,就不能在可以忍受的时间内看到结果了。尤其是构造 RSA 密码体制时所需要用到的,找一个极大的素数。

那么,有没有一个比较快的方法来判断一个数是不是素数呢?

(more…)

Read More