WeChall - PyHash

PyHash (Coding, Python) by gizmore 利用 CPython 大整数 hash 的同余性质绕过哈希检查

Challenge

def fly_away(num: int) -> bool:
    return hash(num) == 31337

要求找一个整数参数使函数返回 True。题面注明测试环境是 CPython 64-bit Python 3.10。

Solution

CPython 对小整数有优化：hash(n) == n。所以直接传 31337 的话，hash(31337) == 31337 确实成立——但题面暗示要更大的整数，而且必须用 int，不是 float。

关键是大整数的 hash 实现。CPython 用一个固定 modulus 做折叠：

import sys
P = sys.hash_info.modulus  # 64-bit CPython: 2**61 - 1 = 2305843009213693951

对一个任意大整数 x，hash(x) 近似等于 x % P（实际还有一步 murmur-style mixing，但对这个场景不重要）。因此构造一个与 31337 同余于 P 的大整数即可：

import sys
P = sys.hash_info.modulus
candidate = 31337 + P  # 2305843009213725288
print(hash(candidate))  # 31337

完整解法：

import sys

def fly_away(num: int) -> bool:
    return hash(num) == 31337

P = sys.hash_info.modulus          # 2**61 - 1
num = 31337 + P                    # 2305843009213725288
assert fly_away(num)               # True
print(num)                         # 提交这个数

这个解依赖 CPython 实现细节和 64-bit 平台。32-bit CPython 的 modulus 是 2**31 - 1，其他 Python implementation（PyPy, Jython）可能完全不同。在目标版本（CPython 3.10 64-bit）上验证通过。

如果 31337 + P 已被别人提交过，就试 31337 + k * P（k 为任意正整数）——所有同余值都有效。

2305843009213725288（或 31337 + k * 2305843009213693951）