2

I want to multiply two integers modulo another (prime) integer (approximately 50 bit in length) in C.

uint64_t x = ...;
uint64_t y = ...;
uint64_t q = ...;
uint64_t z = (x*y) % q;

This would produce a 64 bit integer smaller than q but unfortunately x%q * y%q is way too large for a 64 bit type. So it overflows before I can calculate the remainder.

I thought about some workarounds:

  • using gcc's __uint128_t would violate the C standard and wouldn't work with other compilers
  • cast variables to double or long double but the result wouldn't be correct due to floating point inaccuracy
  • using a multiple precision library like GMP would work but that introduces a new project dependency and maybe comes with some overhead
  • writing an own multiplication function for that purpose, but as far as I know I would need assembly, so portability is gone

Are there other options or what would you recommend?

EDIT: I forgot to mention, that a self written solution is only worth doing if it is efficient. For example doing dozens of inefficient % operations would be bad.

firefexx
  • 616
  • 6
  • 16
  • 2
    Try [this](http://stackoverflow.com/questions/2566010/fastest-way-to-calculate-a-128-bit-integer-modulo-a-64-bit-integer?rq=1). You can do 128 bit multiplication easily then use the above 128-by-64 bit modulus – phuclv Apr 25 '14 at 14:55

1 Answers1

2

Of course you don't need assembly to implement arbitrary-precision multiplication yourself.

There are plenty of well-known algorithms for this, and (by definition) they will be possible to implement in C.

See Wikipedia for a lot more information. In my experience, getting code like that right can be a bit tricky, so perhaps your time is better spent by adding the dependency.

unwind
  • 378,987
  • 63
  • 458
  • 590