MASH-2散列函数

我们已经在大学课程中使用了MASH-2散列函数，并且在考试中我们遇到了使用问题计算类似（（62500）^ 257））mod（238194151）的问题只有一个科学计算器。现在我知道有一些^ b（mod n）的理论，但我上面提出的问题甚至很难手动计算。我认为解决这个问题大约需要15分钟。我想知道是否有更快的方法来做到这一点。或者即使有一些方法可以在二进制文件中执行（将数字转换为二进制文件，然后执行一些操作）。我需要能够用科学计算器手动完成这项工作。MASH-2散列函数

来源

2012-07-19 Ibrahim Najjar

正如所写，这几乎不是一个问题，没有问号，也没有任何句子的构造直接指向它需要一个问号。除此之外，抛开我对这个问题在SO上的主题的怀疑（它强烈地怀疑数学）：如果学生显示已经应用了她已经应用的一些证据，则对研究协助的请求会得到更好的答案教和卡住了。你试过什么了？ – 2012-07-19 10:08:46

相信我，我已经尝试了一切。我的问题很明显：是否有办法以比欧拉理论更快的方式来计算^ b（mod n）。 – 2012-07-19 10:13:51

我不记得我的头顶，但我相信在数论中有一些定理可以极大地简化a和m相对于素数的问题。如果今晚我下班回家时仍然开着，我会尽力找到我的数字理论书籍。 – bigbenbt 2012-07-19 14:10:48

在这种特殊情况下，a = 62500 = 2² ⋅ 5⁶的素因子分解非常简单。
您可以先用这个来计算(2²)²⁵⁷和(5⁶)²⁵⁷然后计算出产品。
但我看到的问题是，对于n = 238194151我的科学计算器无法正确计算n²。如果你的计算器可以做到这一点，那应该没问题。

由于gcd(a, b) = 1您也可以使用CRT，但我不确定是否可以使用科学计算器找到主要因子n = 13 ⋅ 59 ⋅ 310553。如果是这样，这将使它更容易。你只需计算a²⁵⁷ mod (13⋅59)和a²⁵⁷ mod 310553并将结果与CRT结合在一起。

您也可以只使用Exponentiation by squaring，所以你只需要计算8个方格。

来源

2014-05-31 19:52:23 AbcAeffchen

我什至不记得我问过这个问题。无论如何，你的解释听起来很合理，所以我要给你正确的答案。谢谢。 – 2014-06-01 13:03:14

MASH-2散列函数

回答

相关问题