0

I'm trying to do modular exponentiation with numbers larger than the size of uint16_t. Therefore, 65536 is the maximum value that can be represented in the data type. To express larger numbers, I'm using a pointer array and using 65536 as the base. Addition, subtraction, and multiplication are all implemented, so I'm able to use these in the function for modular exponentiation, I just have no clue how to approach this specific function.

I'm aware x * y (mod z) = x mod z * y mod z, and I know the function would have to be incremental, but I don't know how to handle the large base 65536 numbers and I don't know how to do anything that wouldn't take too long to run.

None of the other solutions on this site, or the internet, are for input values larger than the size of the data type, and as such are comletely pointless to me. I need to be able to do the calculations on an array of values that represent one large int of base 65536.

I am looking for code-based answers, not theory as I understand the theory behind modular exponentiation, I just don't see how to implement it at all.

timothybarker
  • 1
  • 1
  • Use strings instead of int to represent your numbers. So you can do operations with *potentially infinite* size (as long as you have memory available) – Cid Oct 24 '20 at 09:53
  • 1
    Suggestion: https://en.wikipedia.org/wiki/Modular_exponentiation – pmg Oct 24 '20 at 09:54
  • @Cid: “Strings” are not an answer to this. Arrays of `uint16_t` are [strings](https://en.wikipedia.org/wiki/String_(computer_science)) in the theoretical sense, and they are the same here in practice: You have a sequence of digits, whether the digits are base 10 or base 65536, and you need to construct arbitrary-precision integer arithmetic from them. With either base, the principles are the same: Do arithmetic on individual digits, propagating carries, borrows, remainders, or whatever from position to position. – Eric Postpischil Oct 24 '20 at 10:59
  • … in grade school. The work is simply done with some other base instead of base 10. That may be base 65536, or it might be base 256, depending on what elementary operations are readily available to you. After you study the other question’s answers, you might ask a more specific question, such as how you implement a 16-bit by16-bit multiplication that produces a 32-bit product if all you have is multiplications that produce a 16-bit product, or 32-by-32 to 64 given only 32-by-32 to 32, or whatever situation you have. Or you could ask specific questions about division or about… – Eric Postpischil Oct 24 '20 at 11:06
  • … implementing the exponentiation in an efficient way. But simply asking how to implement all of the arithmetic involved is too broad. – Eric Postpischil Oct 24 '20 at 11:06
  • Hmm, it looks like a moderator deleted the first of a set of three comments (my first comment above, to Cid, is not part of that set), leaving the following two orphaned. – Eric Postpischil Oct 25 '20 at 13:49

0 Answers0