[Dr.Lib]Note:Math – Extend Baby Step Giant Step

这种数学题都是转AC大神的……以及Seter

http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4

http://seter.is-programmer.com/posts/32188.html

Baby Step Giant Step

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{P}\]

求解x,我们可以做一个等价

\[x = i\ast m + j  ( 0 \leq i,j< m) ,m = \lceil \sqrt{C} \rceil\]

而这么分解的目的无非是为了转化为:

\[(A^{i})^{m} * A^{j} = B \mod C\]

之后做少许暴力的工作就可以解决问题:
(1) for i = 0 -> m, 插入\( Hash (A^i \mod C, i) \)

(2) 枚举 i ,对于每一个枚举到的i,令  \( {A}' = (A^m)^i \mod C\)
我们有\[A' * A^j = B \mod C\]

显然\(A'B,C\),均已知,而由于C为素数,那么(AA,C)无条件为1

令\(p=(A^M)^i \mod C,x=A^j \mod C\)则\(p*x=B\mod C\)。

我们从0开始枚举i直到i*M超过C-1,则相当于知道了p,要求x。

由于 (A',C)=1 ,于是对于这个模方程解的个数唯一(可以利用扩展欧几里得或 欧拉定理来求解)

那么对于得到的唯一解x,在Hash表中寻找(x,j),如果找到,则返回  \(i*m+j>0\) 。

如果需要得到 x > 0的解,那么只需要在上面的步骤中判断 当 \(i*m+j>0\) 的时候才返回。

扩展Baby Step Giant Step

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{N^*}\]

当C不是素数的时候能否直接套用呢?当然不可以……最直接的问题就是,不一定存在逆元!

考虑一个\(G'\)同时是ABC的因数,令\(B'=\frac{B}{G'},C'=\frac{C}{G'}\),则当x不等于0时,

\(\frac{A}{G'}*A^(x-1)=B'\mod  C'\)。

这样多弄几次,C的因数就越来越少,直到(A,C)=1。

那么如何选取\(G'\)呢?AC大神告诉你:不断取\(G'=gcd(A,C')\),直到\(G'\)=1。如果任意一个\(G'\)不是\(B'\)的因数则一定无解。

假设取了r次\(G'\),然后所有\(G'\)的积是G,则问题变为\(\frac{A^r}{G}*A^{x-r}=B'\mod C'\),令\(D=\frac{A^r}{G}\)(一定是整数),则由于此时\((A,C')=1\),所以\((D,C')=1\)。

那么上面算法中只要变成求\(D\)对于\(C'\)的逆元就可以了,返回的答案还要加上r。

还有一点小问题,就是这样得出的答案是大于等于r的。但是即使每次\(G'=2\),r最大也只有\(log_{2}C\),那么这些再暴力求解就可以了。

CC BY-SA 4.0 [Dr.Lib]Note:Math – Extend Baby Step Giant Step by Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.