MASH-2 hash function
-
21-06-2021 - |
Pergunta
We have taken the MASH-2 hash function in a college course, and in the exam we are confronted with questions to calculate something like this ((62500)^257)) mod (238194151) using only a scientific calculator. now i know some theories with a^b (mod n) but the problem i present above is even hard to calculate manually. i think it would take about 15 minutes to solve this. i would like to know if there is a faster way to do this. or even if there is some way to do it in binary (convert the number to binary and then do some manipulations). i need to able to do this by hand with a scientific calculator.
Solução
In this special case the prime factor decomposition of a = 62500 = 2² ⋅ 5⁶
is very simple.
You can use this to calculate (2²)²⁵⁷
and (5⁶)²⁵⁷
first and calculate then the product.
But the problem I see, is that for n = 238194151
my scientific calculator can not calculate n²
correctly. If your calculator can do this, it should be no problem.
Since gcd(a, b) = 1
you also could use CRT, but I'm not sure if you can find the prime factors n = 13 ⋅ 59 ⋅ 310553
with only a scientific calculator. If so, this will make it much easier. You just calculate a²⁵⁷ mod (13⋅59)
and a²⁵⁷ mod 310553
and put the results together with CRT.
You can also use only Exponentiation by squaring so you only have to calculate 8 squares.