Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
685 views
in Technique[技术] by (71.8m points)

c++ - Calculate a*a mod n without overflow

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...