在10^30的空间内搜索ID。

问题描述 投票:0回答:1

我在一个10^30的数字空间内分布了5000万个ID。id是随机分布的,找不到序列或逆向函数。例如,最小值和最大值是。

  • 25083112306903763728975529743
  • 29353757632236106718171971627

两个连续的id的距离顺序至少为10^19。比如说

  • 28249462572807242052513352500
  • 28249462537043093417625790615

这个分布对蛮力攻击来说是很稳固的,因为要找到1个连续到另一个,至少需要10^19次搜索(对时间有个概念,1000次搜索需要1秒,那么它将花费10^16秒...)。

在这个空间里还有其他的搜索算法,可以用更少的时间,让我的ids分布不那么扎实?

algorithm search binary-search-tree brute-force
1个回答
0
投票

如果你的5000万真的是随机分布在10^30的空间内,你除了蛮力之外,什么都做不好。

这意味着你只能按照随机的顺序迭代你的10^30的值,平均来说,你要测试的是 10^30 / (5 10^7) = 2.10^22 来找到一个。

当然,存在一种算法,可以在第一次尝试时就找到所有的算法,但如果你不先知道id,偶然发现的可能性极小。

© www.soinside.com 2019 - 2024. All rights reserved.