From 841a9d82c595b276fcf721dd38e54f3139b499fc Mon Sep 17 00:00:00 2001 From: Tianyi Qiu Date: Thu, 19 Nov 2020 20:20:24 +0800 Subject: [PATCH] minor fi --- docs/misc/rand-technique.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/misc/rand-technique.md b/docs/misc/rand-technique.md index 4df898ac..7f952199 100644 --- a/docs/misc/rand-technique.md +++ b/docs/misc/rand-technique.md @@ -258,7 +258,7 @@ $$ - 观察：对于任意的 $A\neq B; A,B\leq N$ 和随机选取的质数 $Q\leq Q_{max}$ ， $\mathrm{Pr}[A\equiv B(\bmod Q)]=O\big(\dfrac{\log N \log Q_{max}}{Q_{max}}\big)$ - 理由：使 $A\equiv B$ 成立的 $Q$ 一定满足 $Q|(A-B)$ ，这样的 $Q$ 至多有 $d(A-B)\leq \log_2 N$ 个；而由质数定理， $Q_{max}$ 以内不同的质数又有 $\Theta(\dfrac {Q_{max}}{\log Q_{max}})$ 个。将两者相除即可。 -- 在上述观察中取 $A,B$ 满足 $A\neq B$ 为某一特定项在 $P_0,P_1$ 中的系数（也就等于该项对应的串在 $G_0,G_1$ 中的出现次数），则易见 $A,B\leq (m_1+m_2)^{L}$ ，得到 $\mathrm{Pr}[A\equiv B(\bmod Q)]=O\big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\big)$ ，所以取 $Q_{max}\approx 10^{12}$ 就绰绰有余。如果机器无法支持这么大的整数运算，可以用双哈希代替。 +- 在上述观察中取 $A,B$ （满足 $A\neq B$ ）为某一特定项在 $P_0,P_1$ 中的系数（也就等于该项对应的串在 $G_0,G_1$ 中的出现次数），则易见 $A,B\leq (m_1+m_2)^{L}$ ，得到 $\mathrm{Pr}[A\equiv B(\bmod Q)]=O\big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\big)$ ，所以取 $Q_{max}\approx 10^{12}$ 就绰绰有余。如果机器无法支持这么大的整数运算，可以用双哈希代替。 分析后者发生的概率： -- 2.11.0