卡哈希

本文基于 NOI WC 2024 csy 专家进行的讲解。

什么？你还在为卡不掉选手的十模哈希而感到痛苦？

什么？你还在 CF hack 时看着对方的随机五十模数哈希而感到迷茫？

不要担心，现隆重向您推出——LLL 算法卡哈希！

在这之前，我们快速回顾一下几种简单的卡哈希方法。

OI 中常见的字符串哈希函数一般形如下式：

H(s)=\sum_{i=1}^{|s|}s_ib^i\bmod p

其中

0\le s_i<26\le b<p

，且

p

一般为质数。

多模哈希是选择多组

(b,p)

，将

H(s)

构成的有序对作为哈希结果。

单模哈希

相信这个东西的卡法已经为人熟知了，直接随机一堆字符串看看有没有相同即可，利用了生日悖论。

这个做法挂亿会机也能找到双模哈希的碰撞。

自然溢出哈希

p=2^{64}

，对

b

的奇偶性分类讨论：

$b$ 为偶数，那么有

b^{64}\equiv2^{64}\left(\dfrac b2\right)^{64}\equiv0\pmod{2^{64}}

所以只需要构造低

64

位相同的字符串即可。

$b$ 为奇数，我们考虑字符集为 $\{0,1\}$ 的字符串 $s$ ，定义其取反 $\bar s$ 为 $0$ 变为 $1$ ， $1$ 变为 $0$ 后得到的字符串。令 $s_1=[0],s_{i+1}=s_i+\bar{s_i}$ ，那么容易发现 $H(s_{12})=H_{\bar{s_{12}}}$ 。

多模哈希

众所周知，某些选手在不会写 SA 或者 Z-function 或者 Manacher 等等字符串算法时会选择二分哈希这种做法，对于写正解的选手非常不公平，在介绍如何针对这些选手之前，先对 Lenstra-Lenstra-Lovász Lattice Reduction 算法 进行介绍。

格与基

本文只关注欧几里得空间中由向量加法构成的格，所以我们给出格的定义：

格是欧几里得空间

\mathbb R^n

的一个离散加法子群，且其中的元素可由

n

个整系数的向量基线性组合生成。

换句话说，基就是

n

个整数向量

\vec{v_i}

，格就是所有的

\sum k_i\vec{v_i},k_i\in\mathbb Z

。

Gram-Schmidt 正交化

先定义正交基：

正交基 是一组基

\vec{v_i}

，满足：

\forall i\ne j,\vec{v_i}\cdot\vec{v_j}=0

Gram-Schmidt 正交化可以将一组基

\vec{v_i}

变为一组正交基

\vec{v_i}^\ast

。

Gram-Schmidt 正交化采用增量法构造，加入第一个向量时，直接令

\vec{v_1}^\ast=\vec{v_1}

即可。

加入第

n+1

个向量时，我们考虑计算

\vec{v_n}

对

\vec{v_i}^\ast,1\le i<n

的投影，从

\vec{v_n}

中减去投影，具体可以参考这个图：

然后我们就得到了这个公式：

\vec{v_n}=\vec{v_n}-\sum_{i=1}^{n-1}\frac{\vec{v_i}\cdot\vec{v_n}}{\vec{v_i}\cdot\vec{v_i}}\vec{v_i}

LLL 算法主体

LLL 算法有一个参数

\delta

，需要满足

\dfrac14<\delta<1

，一般取

\delta=\dfrac34

。

定义一组基

\vec{v_i}

的 LLL reduced 条件：

\textbf{Size Condition}:|\mu_{i,j}|=\frac{|\vec{v_i}\cdot\vec{v_j}^\ast|}{|\vec{v_j}^\ast|^2}\le\frac12,\text{ for all }1\le j<i\le n

\textbf{Lov\'asz Condition}:|\vec{v_i}|^2\ge\left(\delta-\mu_{i,i-1}^2\right)|\vec{v_{i-1}}|^2,\text{ for all }1<i\le n

\textbf{Lov\'asz Condition}

的一个等价表述为：

\textbf{Lov\'asz Condition}':\delta|\vec{v_i}|^2\le|\mu_{i,i+1}\vec{v_i}+\vec{v_{i+1}}|,\text{ for all }1\le i<n

其中

\vec{v_i}^\ast

为

\vec{v_i}

的 Gram-Schmidt 正交化基，还是增量法，对于

n=1

，我们什么也不用做就可以满足两个条件。

现在假设我们已经把

\vec{v_i},1\le i<k

变换成了 LLL reduced 的，我们加入了新向量

\vec{v_k}

，我们先求出这些向量的 Gram-Schmidt 正交化基

\vec{v_i}^\ast

，为了满足

\textbf{Size Condition}

，我们枚举

j

从

k-1

到

1

，执行：

\vec{v_k}\gets\vec{v_k}-\lfloor\mu_{k,j}\rceil\vec{v_j}

（

\lfloor x\rceil

表示

x

四舍五入。）检查一下

\textbf{Lov\'asz Condition}

是否成立，如果成立，我们直接令

k\gets k+1

，否则，我们交换

\vec{v_{k-1}}

与

\vec{v_k}

，并令

k\gets\max(k-1,2)

，与更前面的基进行比较。

这个算法的正确性证明和终止性证明和时间复杂度证明都比较复杂，所以就不写了（~~就是不会~~）。

LLL reduced 基有如下性质：

设

\vec{v_i}

是

n

维格

\mathcal L

的一组 LLL reduced 基，那么有：

|\vec{v_1}|\le\left(\frac2{\sqrt{4\delta-1}}\right)^{n-1}\lambda_1(\mathcal L)

其中

\lambda_1(\mathcal L)

为格

\mathcal L

中的最短向量长度，求解该向量被称为 SVP 问题（Shortest Vector Problem）。

证明可以归纳法，所以我们直接把

\delta

拉满（比如

0.99

）就能产生一组不错的基，这个算法的时间复杂度是

O(n^6\log^3B)

，其中

B

是

\max|\vec{v_i}|

，当然实际运用中严重跑不满。

这样 LLL 算法就找到了 SVP 问题的一个近似解。

CVP

格中的困难问题之一——Closest Vector Problem，寻找格

\mathcal L

中与向量

\vec t

最近的向量（虽然这和怎么卡哈希没有关系，还是讲一下吧）。

Babai's nearest plane algorithm：首先将

\mathcal L

跑一遍 LLL 得到 LLL reduced 基

\vec{v_i}

，置

\vec b=\vec t

，枚举

j

从

n

到

1

，令

\vec b=\vec b-\left\lceil\dfrac{\vec b\cdot\vec{b_j}}{\vec{b_j}\cdot\vec{b_j}}\right\rceil\vec{v_j}

，最后的

\vec b

就是一个比较好的解。

近似程度有多好呢？我们有这个算法求出的解至多是正确答案的

2^{n/2}

倍。

对 LLL 卡常

下面是 sagemath 中 LLL 算法的实现，假设我们需要对由

\vec{y_i}

生成的格进行 LLL 算法。

首先计算 Gram-Schmidt 正交化基

\vec{y_i}^\ast

和

\mu

矩阵，计算

\gamma_i=|\vec{x_i}|^2

，令

k=2

表示我们准备好添加

\vec{y_k}

进入 LLL reduced 基了。

首先定义 reduce(k, l) 过程：如果

|\mu_{k,l}|>\dfrac12

，令

\vec{y_k}\gets\vec{y_k}-\lfloor\mu_{k,l}\rceil\vec{y_l}

，然后对于所有

1\le j<l

，将

\mu_{k,j}

减去

\lfloor\mu_{k,l}\rceil\mu_{l,j}

。

最后令

\mu_{k,l}\gets\mu_{k,l}-\lfloor\mu_{k,l}\rceil

即可。

然后定义 exchange(k) 过程：交换

\vec{v_k},\vec{v_{k-1}}

，令

\nu=\mu_{k,k-1},\delta=\gamma_k+\nu^2\gamma_{k-1}

更新

\mu_{k,k-1}=\dfrac{\nu\gamma_{k-1}}\delta,\gamma_k=\dfrac{\gamma_k\gamma_{k-1}}\delta,\gamma_{k-1}=\delta

。

然后对于所有

1\le j<k-1

，交换

\mu_{k-1,j},\mu_{k,j}

，对于所有

k+1\le j\le n

，令

x_i=\mu_{i,k}

，并置

\mu_{i,k}=\mu_{i,k-1}-\nu\mu_{i,k},\mu_{i,k-1}=\mu_{k,k-1}\mu_{i,k}+x_i

。

等会补充证明。

然后令

k=2

，重复执行直到

k>n

：

reduce(k, k - 1)
如果 $\gamma_k\ge(\delta-\mu_{k,k-1}^2)\gamma_{k-1}$ ，倒序枚举 $l=k-1\to 1$ ，reduce(k, l)，将 $k$ 加 $1$ 。
否则，exchange(k) 并令 $k=\max(k-1,2)$ 。

卡掉哈希！

考虑将构造哈希碰撞转换为求解一个格的 SVP 问题。

首先看这个题：

PYTHON

h0 = 45740974929179720441799381904411404011270459520712533273451053262137196814399

# 2**168 + 355
g = 374144419156711147060143317175368453031918731002211L


def shitty_hash(msg):
    h = h0
    msg = map(ord, msg)
    for i in msg:
        h = (h + i) * g
        # This line is just to screw you up :))
        h = h & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

    return h - 0xe6168647f636

也就是

b=2^{168}+355,p=2^{256}

的

H

，你需要构造两个串满足其哈希相同。

不妨设我们构造的两个串为

s_i,t_i

，那么有：

\sum_{i=0}^{n-1}s_ib^{n-i}\equiv\sum_{i=0}^{n-1}t_ib^{n-i}\pmod p

\sum_{i=0}^{n-1}(s_i-t_i)b^{n-i}\equiv0\pmod p

\sum_{i=0}^{n-1}(s_i-t_i)b^{n-i}-kp=0

容易将问题转化为构造长

n

的整数序列

x_i=s_i-t_i

和整数

k

，满足

\sum x_ib^{n-i}-kp=0

，考虑构造这样的格：

\begin{bmatrix}1&0&0&\cdots&0&Kg^n\\0&1&0&\cdots&0&Kg^{n-1}\\0&0&1&\cdots&0&Kg^{n-2}\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&1&Kp\end{bmatrix}

其中

K

是一个大常数，比如

2^{200}

，然后跑 LLL 算法，求一个 SVP。

注意到我们的

K

非常大，所以求出的 SVP 如果在

K

这个维度不是

0

，那么一定非常长，所以这个维度一定是

0

，就满足了条件。

由于我不想下 sagemath，于是就有了下面的代码：

PYTHON

from sympy import *

mod = 2 ** 256
h0 = 45740974929179720441799381904411404011270459520712533273451053262137196814399
g = 374144419156711147060143317175368453031918731002211
K = 2 ** 200
N = 50
y = []
for i in range(N):
    y.append([])
    for j in range(N + 1):
        if i == j:
            y[i].append(Rational(1, 1))
        elif j == N:
            y[i].append(Rational(K * pow(g, N - i, mod), 1))
        else:
            y[i].append(Rational(0, 1))
def dot(x, y):
    n = len(x)
    ans = 0
    for i in range(n):
        ans += x[i] * y[i]
    return ans
delta = Rational(99, 100)
n, m = N, N + 1
y_star = [[y[0][i] for i in range(m)]]
mu = [[Rational(0, 1) for i in range(m)] for j in range(n)]
for i in range(1, n):
    print('Gram-Schmidt: i =', i)
    y_star.append([y[i][j] for j in range(m)])
    for j in range(i):
        mu[i][j] = dot(y_star[j], y_star[i]) / dot(y_star[j], y_star[j])
        for k in range(m):
            y_star[i][k] -= y_star[j][k] * mu[i][j]
gamma = [dot(y_star[i], y_star[i]) for i in range(n)]
def round(x):
    return (x + Rational(1, 2)).floor()
def reduce(k, l):
    if abs(mu[k][l]) > Rational(1, 2):
        for i in range(m):
            y[k][i] -= round(mu[k][l]) * y[l][i]
        for j in range(l):
            mu[k][j] -= round(mu[k][l]) * mu[l][j]
        mu[k][l] -= round(mu[k][l])
def exchange(k):
    y[k - 1], y[k] = y[k], y[k - 1]
    nu = mu[k][k - 1]
    delta = gamma[k] + nu * nu * gamma[k - 1]
    mu[k][k - 1] = nu * gamma[k - 1] / delta
    gamma[k] *= gamma[k - 1] / delta
    gamma[k - 1] = delta
    for j in range(k - 1):
        mu[k - 1][j], mu[k][j] = mu[k][j], mu[k - 1][j]
    for i in range(k + 1, n):
        xi = mu[i][k]
        mu[i][k] = mu[i][k - 1] - nu * mu[i][k]
        mu[i][k - 1] = mu[k][k - 1] * mu[i][k] + xi
k = 1
maxk = 1
while k < n:
    if maxk < k:
        maxk = k
        print('LLL: new k =', k)
    reduce(k, k - 1)
    if gamma[k] >= (delta - mu[k][k - 1] ** 2) * gamma[k - 1]:
        for l in range(k - 2, -1, -1):
            reduce(k, l)
        k = k + 1
    else:
        exchange(k)
        if k > 1:
            k = k - 1
def shitty_hash(msg):
    h = h0
    msg = map(ord, msg)
    for i in msg:
        h = (h + i) * g
        # This line is just to screw you up :))
        h = h & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

    return h - 0xe6168647f636
s1 = 'a' * n
s2 = ''
for i in range(n):
    s2 += chr(ord(s1[i]) + y[0][i])
print(y[0])
print(max(y[0]), min(y[0]), max(y[0]) - min(y[0]))
print(s1)
print(s2)
print(shitty_hash(s1))
print(shitty_hash(s2))
if shitty_hash(s1) == shitty_hash(s2):
    print('ok')
else:
    print('wa')

在一万两千多次迭代之后，LLL 算法给出的如下的

\vec{y_0}

：

[15, -14, 17, 14, 6, 0, 12, 21, 8, 29, 6, -4, -9, 10, -2, -12, -6, 0, -12, 13, -28, -28, -24, -3, 6, -5, -16, 15, 17, -14, 3, -2, -16, -25, 3, -21, -27, -9, 16, 5, -1, 0, -3, -4, -4, -19, 6, 8, 0, 0, 0]

并产生了两个串：

CPP

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
pSrogamvi~g]Xk_U[aUnEEI^g\QprSd_QHdLFXqf`a^]]Ngiaa

并其 hash 值都是

106025341237231370726407656306665079105509255639964756437758376184556498283725

。

Tree Attack

来源：On the mathematics behind rolling hashes and anti-hash tests。

有的时候，选手会对每个字符给定一个随机权值的方法来防止自己的哈希被 LLL 卡掉，这是非常不好的。

Tree Attack 尝试找到

\alpha_i\in\{-1,0,1\}

满足：

\sum_{i=0}^{n-1}(b^{n-i-1}\bmod p)\alpha_i=0

中的

s_i-t_i

将被限制于

\{-1,0,1\}

中，定义一个簇

C

是

\{0,1,\dots,n-1\}

的子集，定义簇的和为：

S(C)=\sum_{i\in C}\alpha_i(b^{n-i-1}\bmod p)

我们维护系数

\alpha_i

上的簇

C_1,C_2,\dots

，。

我们可以将两个簇

C_1,C_2

合并为一个满足

S(C_3)=|S(C_1)-S(C_2)|

的簇

C_3

：不妨设

S(C_1)>S(C_2)

，我们将

C_2

中的

\alpha_i

全部取反然后令

C_3=C_1\cup C_2

即可。

初始令

n=2^k

（

k

在下面会进行分析），我们令

\alpha_i=1

，并创建

n

个簇

C_i

，其中仅包含

\{i\}

。

在每一轮中，我们对所有簇

C

按照

S(C)

排序，然后合并相邻的簇，如果我们得到了一个

S(C)=0

的簇

C

，将不在

C

中的所有

\alpha_i

全部置为

0

，并返回这些

\alpha_i

。

k

的值应该取多少？我们可以合理地假设

b^{n-i-1}\bmod p

在

[0,p)

中均匀分布，那么在

i

轮之后，最大值应当除以大约

2^i

，所以

k

轮以后，最大值大约为

\dfrac p{2^{k(k-1)/2}}

，所以

k\approx\sqrt{2\log p}+1

是一个合理的选择。

Multi Tree Attack

在 Tree Attack 的基础上，将每个簇能得到的最小的

m

个值存储，显然可以在

O(m\log m)

时间内合并两个簇。

实战演练

叉掉 CF Submission 251754156，来自

\color{purple}\sf a\_little\_cute

在 CF Round 934 (Div. 1) 对 B 题的提交。

题意简述：

定义字符串 $t$ 是 $k$ -好的当且仅当存在一个非回文的长 $k$ 的 $t$ 的子串。

对于字符串 $t$ 定义 $f(t)$ 为所有满足 $t$ 是 $k$ -好的正整数 $k$ 之和。

给定长 $n$ 字符串 $s$ 与 $q$ 次询问 $l,r$ ，求 $f(s_{l\sim r})$ 的值。

$1\le n,q\le10^5$

题解：

如果串里全部都相同，那么答案为 $0$ 。如果所有奇数位置的字符和偶数位置的字符都相同，那么 $k$ 只能是偶数。

注意特判一下整个串是否是回文串即可。

重点来了，我们需要快速判断一个子串

s_{l\sim r}

是回文的。

这位选手采用了四模哈希与固定底数

31

，模数列表为

995662561,995662609,995662621,998244353

。

用上面的模板可以找到如下碰撞：

CPP

aaaaaaadaaaacacacacacbaadbcaccbaacecaaacadebabaaaa
aabbbaaabfbaaeabacadaaacaaafaaadbaaaaaeafaaabaaaaa

所以构造这组数据：

CPP

1
100 1
aaaaaaadaaaacacacacacbaadbcaccbaacecaaacadebabaaaaaaaaabaaafaeaaaaabdaaafaaacaaadacabaeaabfbaaabbbaa
1 100

即可叉掉此提交！

参考代码：

PYTHON

import fractions as f
K = 2 ** 50
N = 50
cnt = 4
mod_ = [995662561, 995662609, 995662621, 998244353]
base_ = [31, 31, 31, 31]
y = []
for i in range(N):
    y.append([])
    for j in range(N):
        if i == j:
            y[i].append(f.Fraction(1, 1))
        else:
            y[i].append(f.Fraction(0, 1))
    for j in range(cnt):
        y[i].append(f.Fraction(pow(base_[j], N - i, mod_[j]) * K, 1))
def dot(x, y):
    n = len(x)
    ans = 0
    for i in range(n):
        ans += x[i] * y[i]
    return ans
delta = f.Fraction(99, 100)
n, m = N, N + cnt
y_star = [[y[0][i] for i in range(m)]]
mu = [[f.Fraction(0, 1) for i in range(m)] for j in range(n)]
for i in range(1, n):
    print('Gram-Schmidt: i =', i)
    y_star.append([y[i][j] for j in range(m)])
    for j in range(i):
        mu[i][j] = dot(y_star[j], y_star[i]) / dot(y_star[j], y_star[j])
        for k in range(m):
            y_star[i][k] -= y_star[j][k] * mu[i][j]
gamma = [dot(y_star[i], y_star[i]) for i in range(n)]
def round(x):
    return (x + f.Fraction(1, 2)).__floor__()
def reduce(k, l):
    if abs(mu[k][l]) > f.Fraction(1, 2):
        for i in range(m):
            y[k][i] -= round(mu[k][l]) * y[l][i]
        for j in range(l):
            mu[k][j] -= round(mu[k][l]) * mu[l][j]
        mu[k][l] -= round(mu[k][l])
def exchange(k):
    y[k - 1], y[k] = y[k], y[k - 1]
    nu = mu[k][k - 1]
    delta = gamma[k] + nu * nu * gamma[k - 1]
    mu[k][k - 1] = nu * gamma[k - 1] / delta
    gamma[k] *= gamma[k - 1] / delta
    gamma[k - 1] = delta
    for j in range(k - 1):
        mu[k - 1][j], mu[k][j] = mu[k][j], mu[k - 1][j]
    for i in range(k + 1, n):
        xi = mu[i][k]
        mu[i][k] = mu[i][k - 1] - nu * mu[i][k]
        mu[i][k - 1] = mu[k][k - 1] * mu[i][k] + xi
k = 1
maxk = 1
while k < n:
    if maxk < k:
        maxk = k
        print('LLL: new k =', k)
    reduce(k, k - 1)
    if gamma[k] >= (delta - mu[k][k - 1] ** 2) * gamma[k - 1]:
        for l in range(k - 2, -1, -1):
            reduce(k, l)
        k = k + 1
    else:
        exchange(k)
        if k > 1:
            k = k - 1
print(y[0])
s1 = s2 = ''
for i in range(n):
    now = int(y[0][i])
    if now <= 0:
        s1 += 'a'
        s2 += chr(ord('a') - now)
    else:
        s1 += chr(ord('a') + now)
        s2 += 'a'
print(s1)
print(s2)
def calc_hash(s, b, m):
    ans = 0
    for i in range(len(s)):
        ans = (ans + (ord(s[i]) - ord('a')) * pow(b, N - i, m)) % m
    return ans
for i in range(cnt):
    print(calc_hash(s1, base_[i], mod_[i]), calc_hash(s2, base_[i], mod_[i]))

构造非回文的“回文”串

叉掉 CF Submission 251715199，来自

\color{red}\sf Crystally

在 CF Round 934 (Div. 1) 对 B 题的提交。

这要求我们构造一个串

s

满足

H(s)=H(r(s))

，

r(s)

表示

s

逆序得到的字符串，不妨设

s

长度为

2n

，那么：

\sum_{i=1}^{2n}s_ib^{i-1}\equiv \sum_{i=1}^{2n}s_{2n-i+1}b^{i-1}\pmod p

\sum_{i=1}^{2n}(s_i-s_{2n-i+1})b^{i-1}\equiv0\pmod p

我们设

x_i=s_i-s_{2n-i+1}

，则对于

i+j=2n+1

，有

x_i=-x_j

，所以我们只需要

x_{1\sim n}

。

那么我们有：

\sum_{i=1}^nx_ib^{i-1}-\sum_{i=1}^nx_ib^{2n-i+1}\equiv0\pmod p

\sum_{i=1}^nx_i(b^{i-1}-b^{2n-i+1})\equiv0\pmod p

参考代码：

PYTHON

import fractions as f
K = 2 ** 200
N = 50
cnt = 1
mod_ = [2305843009213693951]
base_ = [1145141919]
y = []
for i in range(N):
    y.append([])
    for j in range(N):
        if i == j:
            y[i].append(f.Fraction(1, 1))
        else:
            y[i].append(f.Fraction(0, 1))
    for j in range(cnt):
        #y[i].append(f.Fraction(pow(base_[j], N - i, mod_[j]) * K, 1))
        y[i].append(f.Fraction((pow(base_[j], 2 * N - i - 1, mod_[j]) - pow(base_[j], i, mod_[j])) % mod_[j] * K, 1))
def dot(x, y):
    n = len(x)
    ans = 0
    for i in range(n):
        ans += x[i] * y[i]
    return ans
delta = f.Fraction(99, 100)
n, m = N, N + cnt
y_star = [[y[0][i] for i in range(m)]]
mu = [[f.Fraction(0, 1) for i in range(m)] for j in range(n)]
for i in range(1, n):
    print('Gram-Schmidt: i =', i)
    y_star.append([y[i][j] for j in range(m)])
    for j in range(i):
        mu[i][j] = dot(y_star[j], y_star[i]) / dot(y_star[j], y_star[j])
        for k in range(m):
            y_star[i][k] -= y_star[j][k] * mu[i][j]
gamma = [dot(y_star[i], y_star[i]) for i in range(n)]
def round(x):
    return (x + f.Fraction(1, 2)).__floor__()
def reduce(k, l):
    if abs(mu[k][l]) > f.Fraction(1, 2):
        for i in range(m):
            y[k][i] -= round(mu[k][l]) * y[l][i]
        for j in range(l):
            mu[k][j] -= round(mu[k][l]) * mu[l][j]
        mu[k][l] -= round(mu[k][l])
def exchange(k):
    y[k - 1], y[k] = y[k], y[k - 1]
    nu = mu[k][k - 1]
    delta = gamma[k] + nu * nu * gamma[k - 1]
    mu[k][k - 1] = nu * gamma[k - 1] / delta
    gamma[k] *= gamma[k - 1] / delta
    gamma[k - 1] = delta
    for j in range(k - 1):
        mu[k - 1][j], mu[k][j] = mu[k][j], mu[k - 1][j]
    for i in range(k + 1, n):
        xi = mu[i][k]
        mu[i][k] = mu[i][k - 1] - nu * mu[i][k]
        mu[i][k - 1] = mu[k][k - 1] * mu[i][k] + xi
k = 1
maxk = 1
while k < n:
    if maxk < k:
        maxk = k
        print('LLL: new k =', k)
    reduce(k, k - 1)
    if gamma[k] >= (delta - mu[k][k - 1] ** 2) * gamma[k - 1]:
        for l in range(k - 2, -1, -1):
            reduce(k, l)
        k = k + 1
    else:
        exchange(k)
        if k > 1:
            k = k - 1
print(y[0])
s1 = s2 = ''
for i in range(n):
    now = int(y[0][i])
    if now <= 0:
        s1 += 'a'
        s2 += chr(ord('a') - now)
    else:
        s1 += chr(ord('a') + now)
        s2 += 'a'
print(s1)
print(s2)
print(s1 + s2[::-1])
def calc_hash(s, b, m):
    ans = 0
    for i in range(len(s)):
        ans = (ans + (ord(s[i]) - ord('a')) * pow(b, i, m)) % m
    return ans
s = s1 + s2[::-1]
#for i in range(cnt):
#    print(calc_hash(s1, base_[i], mod_[i]), calc_hash(s2, base_[i], mod_[i]))
for i in range(cnt):
    print(calc_hash(s, base_[i], mod_[i]), calc_hash(s[::-1], base_[i], mod_[i]))

文章操作

单模哈希

自然溢出哈希

多模哈希

格与基

Gram-Schmidt 正交化

LLL 算法主体

CVP

对 LLL 卡常

卡掉哈希！

Tree Attack

Multi Tree Attack

实战演练

构造非回文的“回文”串

相关推荐

评论

卡哈希