问题标签 [rabin]

我正在寻找 Java 中 Rabin 哈希函数的实现，任何人都可以推荐一个快速库吗？

更新：我刚刚在这里测试了库。

在我的 2GHz 处理器上散列 1mm 随机 URL 大约需要 2200 毫秒。

这当然足以满足我的需求，但是当我得到一个 monent 并在此处发布结果时，我将测试另一个库。

是否有任何使用 .NET 的 rabin 指纹实现？

因此，我正在尝试查找有关 Michael Rabin 算法的详细信息，该算法在 O(n) 时间内给定一组 2D 点找到最近邻。出于某种原因，谷歌搜索完全让我失望。我找到的最好的（也是唯一的）描述在这里：http ://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/ 。

如果有人对此有所了解，或者知道在哪里可以找到有关该主题的书籍或论文（最好是在线的！），我非常感谢您参与进来。

几周前我在一次演示中看到了它，试图实现它，但失败了，然后就忘记了。但现在我想知道它是如何工作的 =)

这是一种有效传输/存储数据的方式。它适用于任何语言。这就是（我认为）它的作用：

您有 1 个非常大的文件（例如网站的整个 javascript 集合）。

1. 将其拆分为 48 字节的块
2. 散列每个 48 字节的块（例如 MD5）
3. 在以 0x00 结尾的哈希上拆分块列表
4. 大块（>= 1 个哈希）现在应该是不同的大小。有的很大，有的很小。
5. 在这些哈希之间粘贴块（再次：实际数据的大小非常不同）
6. 散列这些块
7. 现在你有一个代表大文件当前版本的哈希列表

这个想法是，当大文件中的一段代码发生变化时，只有 1 或 2 个哈希值发生变化。使用新文件，您执行上述所有步骤，并且只上传/下载实际更改的部分（块，可通过其哈希识别）。根据更改的代码量以及围绕该代码的块的大小，您永远不需要下载超过 4 个块。（而不是整个文件。）然后通信的另一端将用新块替换原始块（相同算法，相同功能）。

听起来有点熟？他们提到了一个名字，但在上面找不到任何东西。当我尝试构建它时，它只是没有用，因为如果你不完全更改 48 字节 [1]，那么更改 [2] 之后的所有哈希都是不同的......

如果有人知道这个名字：太好了。如果有人也可以解释一下：完美！

更新
我找到了它所在的演示文稿。它在新产品“Silo”中被提及（并被使用） ： http ://research.microsoft.com/apps/pubs/default.aspx?id=131524相关：http： //channel9.msdn.com/Events/MIX/MIX11/RES04（所以它实际上是微软的研究！很好！）

从第一个链接：

启用 Silo 的页面将此本地存储用作 LBFS 样式的块存储。

在第二个链接（视频）中，好东西从6:30. 现在我已经看过两次了...我仍然不明白 =)

关键字是Delta encoding和Rabin fingerprints。

下面包含一个非常快速和优雅的 Rabin 指纹的 Java 实现 https://github.com/themadcreator/rabinfingerprint

然而，可用于优化实现的最大多项式是 54 位。

我想减少出错的概率。

Rabin [1] 提出了两种降低错误概率的方法： • 通过增加 k 的值来降低错误输出的概率。这将需要更大的字长。• 概率也可以通过使用相同k 次的两个不同的不可约多项式P1(t) 和P2(t) 来降低。然后通过交织步骤运行该算法两次，一次使用 P1(t)，另一次使用 P2(t)。由于错误概率是独立的......（来自 CMPUT690 Term Project）

如果我运行该算法两次，如何在不破坏目标的情况下组合 2 个指纹以降低出错概率？

• 只需添加或倍增 2 个指纹？
• 使用第一次运行的输出作为第二次运行的基本指纹？

我不清楚什么是“交错步骤”。我需要将指纹保存为 64 位长的数字。

谢谢。

我在 Scala 程序中使用 Madcreator 的 Rabinfingerprint java 库，https://github.com/themadcreator/rabinfingerprint。

使用命令行我生成一个不可约的 53 度多项式：

然后指纹文件：

我遇到的问题是在给定相同输入的情况下使用代码产生相同的输出。

这是我的代码：

据我了解，这个测试应该能够处理非常大的数字，但我的脚本卡在 50034901 之类的数字上。我假设我在某处犯了错误/效率严重低下 - 因为我的脚本仍然适用于较小的数字.

我想将此代码实现到另一个程序中，但是当出现“空格”时出现消息问题，当 p = 167 和 q = 151 时出现另一个素数。它的行为如何？

代码：

我正在尝试在 Python 上实现 Miller-Rabin 算法。
我已经按照教科书的伪代码所说的那样进行编码，但是由于某种原因，它没有像我预期的那样工作。
具体来说，函数“test”在进行 Fermat 测试时有时会返回“true”。

我为此苦苦挣扎了几个小时，仍然找不到代码的哪一部分是问题所在。如果您有任何建议，请告诉我。PS exp (a,b,c) 返回 a^b mod c。

我试图了解是否可以使用 Rabin 密码系统而不是使用 RSA 来实现环签名（签名和验证）功能。

此处显示了一个作为环签名函数的 Python 实现的示例，但可以看出，它是通过 RSA 实现的。因为我不知道环签名如何工作的细节，所以我需要知道它在技术上或数学上是否可行。如果是这样，互联网上是否有任何示例可供我查看并尝试推进它以实现更具体的实施。

任何想法或贡献表示赞赏。