Calculate a*a mod n without overflow
biginteger, c++, modulo
Solution
If you can't use a big-integer library, and you don't have a native `uint128_t` (or similar), you'll need to do this manually.
One option is to express `a` as the sum of two 32-bit quantities, i.e. a = 232b + c, where b contains the 32 msbs, and c contains the 32 lsbs. Squaring is then a set of four cross-multiplications; each result is guaranteed to fit into a 64-bit type. You then do the modulo operation as you recombine the individual terms (carefully taking into account the shifts needed to realign everything).
Problem
I need to calculate `a*a` mod `n` but `a` is fairly large, resulting in overflow when I square it. Doing `((a % n)*(a % n)) % n` doesn't work because (n-1)2 can overflow. This is in C++ and I'm using `int64_t` Edit: Example value: a = 821037907258 and n = 800000000000, which overflows if you square it. I am using DevCPP and I've already tried getting big-integer libraries working to no avail. Edit 2: No, there's no pattern to these numbers.