Mersenne Prime — M61 for Hashing

Revision en2, by -synx-, 2018-01-11 21:36:47

It is easy to calculate modulus using this prime (with bitwise operations, it is well known)!
My question is how can we efficiently calculate , where a and b can both have at most 61 bits.

UPD: Found a function here that multiplies 64 bit with 32 bit while maintaining modulo. Can it be extended for 64 bit multiplied with 64 bit efficiently?

Tags hash, mersenne, prime


  Rev. Lang. By When Δ Comment
en2 English -synx- 2018-01-11 21:36:47 256
en1 English -synx- 2018-01-11 18:40:56 306 Initial revision (published)