谁有大整数相乘和模的原理（超过平台的整数），给我介绍下

最近想完成RSA加密，但是平台的整数实在是太小的，想要找大整数运算的办法，大家有什么办法，帮我介绍下原理就行了，代码我自己来就可以了，谢谢了

16 个解决方案

#1

用字符串表示数字了，你想表示多大就能表示多大，当然了运算就比较困难了，需要自己实现运算，例如加法还是比较简单的，你从另个字符串中提取数字，一个一个提取，从以后向前提取，然后一位一位的加，结果之后的结果的末尾保持到一个字符串的末尾，进位留下来和高位做加。以此类推。

#2

就是除法不好实现。我还没考虑清楚除法改怎么做。

#3

http://www.fjptsz.com/xxjs/xjw/rj/106.htm
这里有介绍

#4

当然，过过你不考虑效率的话，实现了乘法之后，可以用乘法和减法来实现除法。思路是，被除数从1开始乘，乘到不操作除数的那个最大值就是商了。这个方法就是太消耗时间了。呵呵

#5

不知道，你看懂了没有。

#6

现在我主要想实现的就是乘方还有算模,也正是你说的实现起来比较难啊,,看来兄弟好象也对大整形有所研究嘛,

#7

算 RSA 的话，基数用 2 的幂应该比较方便。
关键部分的乘方取模运算，可以参考“蒙哥马利幂模算法”。

至于除法我就不知道什么特别好的办法了，以前在一本书上看到过一个估值原理，楼主也可以参照 这里（不过这个上面的公式没有给出图片，囧）。

当然，如果只是要用就方便多了，可以用 GMP 这类成熟的运算库，也可以试试 HugeCalc 库：
http://gmplib.org/
http://www.emath.ac.cn/hugecalc/

#8

引用 6 楼 ilovejr 的回复:

现在我主要想实现的就是乘方还有算模,也正是你说的实现起来比较难啊,,看来兄弟好象也对大整形有所研究嘛,

研究就说不上了，只是以前粗略的想过一点。可能是我上面说的太不清楚了。你可以使用乘法和减法来实现取模的啊。就像我们小学时做除法笔算的时候，其实真正用的是乘法和减法。想一下，我们小学时如何做除法笔算的，我想着就是问题的答案。

#9

http://topic.csdn.net/u/20100122/23/e567edb8-0426-4249-89da-044755be2ec9.html

#10

http://topic.csdn.net/u/20100122/23/e567edb8-0426-4249-89da-044755be2ec9.html

#11

引用 8 楼 javajz 的回复:

引用 6 楼 ilovejr 的回复:
现在我主要想实现的就是乘方还有算模,也正是你说的实现起来比较难啊,,看来兄弟好象也对大整形有所研究嘛,

研究就说不上了，只是以前粗略的想过一点。可能是我上面说的太不清楚了。你可以使用乘法和减法来实现取模的啊。就像我们小学时做除法笔算的时候，其实真正用的是乘法和减法。想一下，我们小学时如何做除法笔算的，我想着就是问题的答案。

不过现在大数运算已经搞定了，就差加密和解密速度的问题了，就上面小哥所说用蒙哥马利算法，但是还不太懂，希望多多指教

#12

引用 7 楼 hpsmouse 的回复:

算 RSA 的话，基数用 2 的幂应该比较方便。
关键部分的乘方取模运算，可以参考“蒙哥马利幂模算法”。

至于除法我就不知道什么特别好的办法了，以前在一本书上看到过一个估值原理，楼主也可以参照这里（不过这个上面的公式没有给出图片，囧）。

当然，如果只是要用就方便多了，可以用 GMP 这类成熟的运算库，也可以试试 HugeCalc 库：
http://gmplib.org/
htt……

蒙哥马利是个不错的算法，提高了加密有解密的速度，但是不太看的懂，希望详细讲下，我想在javascript 下面实现加密，PHP在服务器进行解密

#13

参考小学三年级乘法和除法竖式。(^_^)

#14

大数就是用数组来实现，要考虑进位，和少位数

#15

引用 12 楼 ilovejr 的回复:

蒙哥马利是个不错的算法，提高了加密有解密的速度，但是不太看的懂，希望详细讲下，我想在javascript 下面实现加密，PHP在服务器进行解密

蒙哥马利算法基于多项式求值的快速算法，例如有 32 位二进制数 b，可以做变换：

其中每一位为 0 或 1。
把
c*d mod N = ((c mod N) * (d mod N)) mod N  （可以看作 mod 的分配律）
作用在上面最后一个表达式上，就可以通过线性次数的乘法运算求出 a^b mod N 的结果。

#16

加密和解密没有研究过啊。和Lz一起等高手。