1

So of course I know there are simple solutions to this such as using the GMP library or numerous other arbitrary-precision libraries. This is for class work so I am not allowed to take any of these routes. After we build up all our operations we are leading up to be able to do a RSA encryption scheme.

I am using vectors to store n-bit numbers represented in binary. I have conversions to decimal later but I must operate on the binary and only convert for display.

I have successfully implemented addition, subtraction, and multiplication. I am stuck on division and modular operations... specifically modular exponentiation. I understand the algorithms at least at a basic level but cant seem to translate it into code that will work on arbitrary length numbers. I cant seem to find any examples of this type of work done in c++ without external libraries.

Some specific questions:

is there a better way to do modulus on a n-bit number besides just calling the division function I am writing and using the remainder returned?

I really would love to see some good c++ examples as I cant follow the GMP source code well at all.

Any good resources to study or some help would be greatly appreciated. Thanks

4

1 回答 1

1

您可以使用除法来伪造模数运算。您的模数运算相当于：

v = n - (n / m) * m

其中 n 是除数，m 是模数，v 是输出值（所有任意精度数）

如果你被困在除法上，你可以像手动执行长除法一样实现它。（你应该在中学通过乘法和减法学会如何做到这一点。将过程转换为基数 2 很容易。如果你遇到困难，请在纸上做一些。如果你想要一个更有效的算法，你可能可以通过在谷歌上搜索“任意精度除法算法”之类的东西来找到一个）

一旦你有了模数，你就可以用重复平方计算模幂。观察我们计算一些大整数 X 的 67 次方，mod N：

v1  = X mod N         // X^1 mod N
v2  = v1  * v1  mod N // X^2 mod N
v4  = v2  * v2  mod N // X^4 mod N
v8  = v4  * v4  mod N
v16 = v8  * v8  mod N
v32 = v16 * v16 mod N
v64 = v32 * v32 mod N // X^64 mod N

v66 = v64 * v2  mod N // X^66 mod N
v67 = v66 * v1  mod N // X^67 mod N

从数学上讲，您可以看到为什么这是有道理的。该算法是计算模幂的常用算法，并且在时间和空间上运行，与指数的大小成对数，与底数的大小成对数（即，即使对于巨大的数字，它也很快）

PS 确保你告诉你的教授他不让你使用外部库是愚蠢的。程序员可以学习的最重要的事情之一是何时变得懒惰（即何时找到并使用库来做某事，而不是自制自己的解决方案）

于 2012-09-26T19:31:40.843 回答