x偶数可以是负数吗时，指数为偶数，但没表标明加不加括号，乘出来是正负？急，
点击联系发帖人
时间：2018-04-09 13:04
上课时没注意老师讲有理数的乘方，计算惠计算，就是分不出得数是负是正，有什么好的方法_百度知道
上课时没注意老师讲有理数的乘方，计算惠计算，就是分不出得数是负是正，有什么好的方法
我有更好的答案
当底数为负数时，奇数个负数相乘的积是负数，偶数个负数相乘的积是正数，即负数的奇数次幂是负数，负数的偶数次幂是正数。比如：（-2）^3=(-2)x(-2)x(-2)= -8
采纳率：59%
来自团队：
负数的偶次方是正数，奇次方是负数。正数的任何次方都是正数。0的任何次方都是0
指数为负数，得数的正负与底数相同。指数为正数，且为偶数时，得数为正；若为奇数，得数正负与底数相同。
为您推荐：
其他类似问题
有理数的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。RSA加密算法 C++实现 - Silenceneo - 博客园
Talk is cheap. Show me the code.
&&& 上信息安全课，老师布置了几个大作业，其中一个为RSA加密算法的实现，不能用Java写。出于兴趣，决定尝试。完成之后，为了便于查找，于是写下这篇文章，以备后续查看。也供大家一起学习，一起进步。
1、预备知识
1.1 快速幂算法
&&& 顾名思义，快速幂就是快速算底数的$n$次幂。其时间复杂度为${\rm{O(log n)}}$，与朴素的$O\left( n \right)$相比，效率有了极大的提高。具体可以参考百度百科：。
1.2 扩展欧几里得算法
&&& 扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式
\[ax{\rm{ }} + {\rm{ }}by{\rm{ }} = {\rm{ }}gcd\left( {a,b} \right).\]
&&& 如果$a$是负数，可以把问题转化成
&&& $\left| a \right|\left( { - x} \right){\rm{ }} + {\rm{ }}by{\rm{ }} = {\rm{ }}gcd\left( {\left| a \right|,b} \right)$（$\left| a \right|$为a的绝对值），然后令$x\prime {\rm{ }} = {\rm{ }}\left( { - x} \right)$。具体可以参考维基百科：。
1.3 米勒-拉宾素性检验算法
&&& 要测试${\rm{N}}$是否为素数，首先将${\rm{N - 1}}$分解为${2^s}d$。在每次测试开始时，先随机选一个介于 [ 1 , N - 1 ] {\displaystyle [1,N-1]} $[1,N - 1]$的整数$a$，之后如果对所有的$r \in [0,s - 1]$，若${a^d}\bmod N \ne 1$且 a 2 r d mod N ≠ - 1 {\displaystyle a^{2^{r}d}\mod N\neq -1} ${a^{{2^r}d}}\bmod N \ne& - 1$，则$N$是合数。否则，$N$有$3/4$的概率为素数。
&&& 构成该算法的思想是，如果${a^d} \ne 1\left( {{\rm{mod n}}} \right)$以及$n = 1{\rm{ }} + {\rm{ }}{2^s}d$是素数，则值序列
\[{a^d}mod n,{a^{2d}}mod n,{a^{4d}}mod n, \ldots ,{a^{{2^s}d}}mod n\]
&&& 将以$1$结束，而且在头一个$1$的前边的值将是$n-1$(当$p$是素数时，对于${y^2} \equiv 1\left( {mod p} \right)$，仅有的解是$y \equiv& \pm 1\left( {mod p} \right)$，因为$\left( {y + 1} \right)\left( {y - 1} \right)$必须是$p$的倍数)。注意，如果在该序列中出现了$n-1$，则该序列中的下一个值一定是$1$,因为${\left( {n-1} \right)^2} \equiv {n^2}-2n + 1 \equiv 1\left( {mod n} \right)$。具体可以参考维基百科：。
1.4 RSA加密算法
1.4.1 公钥与私钥的产生
&&& 假设Alice想要通过一个不可靠的媒体接收Bob的一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥：
&&& 1、随意选择两个大的质数$p$和$q$，$p$不等于$q$，计算$N = pq$。
&&& 2、根据欧拉函数，求得$r = \varphi (N) = \varphi (p)\varphi (q) = (p - 1)(q - 1)$。
&&& 3、选择一个小于$r$的整数$e$，使$e$与$r$互质。并求得$e$关于$r$的模反元素，命名为$d$(求$d$令$ed \equiv 1(\bmod \;r)$）。(模反元素存在，当且仅当$e$与$r$互质）
&&& 4、将$p$和$q$的记录销毁。
&&& $\left( {N,e} \right)$是公钥，$\left( {N,d} \right)$是私钥。Alice将她的公钥$\left( {N,e} \right)$传给Bob，而将她的私钥$\left( {N,d} \right)$藏起来。
&&& 假设Bob想给Alice送一个消息$m$，他知道Alice产生的$N$和$e$。他使用起先与Alice约好的格式将$m$转换为一个小于$N$，且与$N$互质的整数$n$，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为$n$。用下面这个公式他可以将$n$加密为$c$：
\[{n^e} \equiv c({\rm{mod\;}}N)\]
&&& 计算$c$并不复杂。Bob算出$c$后就可以将它传递给Alice。
&&& Alice得到Bob的消息$c$后就可以利用她的密钥$d$来解码。她可以用以下这个公式来将$c$转换为$n$：
\[{c^d} \equiv n({\rm{mod\;}}N)\]
&&& 得到$n$后，她可以将原来的信息$m$重新复原。
&&& 解码的原理是
\[{c^d} \equiv {n^{ed}}({\rm{mod}}\:N)\]
&&& 已知$ed \equiv 1(\bmod \;r)$，即$ed = 1 + h\varphi (N)$。由欧拉定理得：
\[{n^{ed}} = {n^{1 + h\varphi (N)}} = n{\left( {{n^{\varphi (N)}}} \right)^h} \equiv n{(1)^h}(\bmod \;N) \equiv n(\bmod \;N)\]
&&& RSA也可用作数字签名。具体可以参考维基百科：。
2、模块设计
2.1 BigInteger类
&&& 因为该加密算法涉及的数可能很大，而C++中并没有像Java一样，内置大整数类BigInteger，故需自己实现，我的实现大概是模仿Java的BigInteger设计的。
&&& 该模块包含两个文件：BigInteger.h和BigInteger.cpp。代码如下所示。
&&& BigInteger.h代码如下。
: BigInteger.h
: -22.11.39
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #ifndef __BIGINTEGER_H__
10 #define __BIGINTEGER_H__
12 #include &string&
13 #include &vector&
14 #include &ostream&
15 class BigInteger {
16 public:
typedef long long long_t;
typedef unsigned base_t;
BigInteger(): is_negative(false) { data.push_back(<span style="color: #); }// 默认为0
BigInteger(const BigInteger &);
// 利用给定的大整数初始化
BigInteger(const std::string &);// 利用给定的十六进制字符串初始化
BigInteger(const long_t &);
// 利用给定的long_t类型数据初始化
~BigInteger() {}
BigInteger add(const BigInteger &);
// 大整数加法
BigInteger subtract(const BigInteger &);// 大整数减法
BigInteger multiply(const BigInteger &) const;// 大整数乘法
BigInteger divide(const BigInteger &);
// 大整数整除
BigInteger remainder(const BigInteger &);
// 大整数取余
BigInteger mod(const BigInteger &);
// 大整数取模
BigInteger divideAndRemainder(const BigInteger &, BigInteger &);// 大整数整除和取余
BigInteger pow(const BigInteger &);
// 大整数幂乘
BigInteger modPow(const BigInteger &, const BigInteger &) const;// 大整数幂模运算
BigInteger modInverse(const BigInteger &);// 用扩展欧几里得算法求乘法逆元
BigInteger shiftLeft(const unsigned);
// 移位运算,左移
BigInteger shiftRight(const unsigned);
// 移位运算,右移
int compareTo(const BigInteger &) const;// 比较运算
bool equals(const BigInteger &) const;// 判断是否等于给定数
static BigInteger valueOf(const long_t &);// 将给定数转换为大整数并返回
std::string toString() const;
// 将大整数转换为十六进制字符串
BigInteger abs() const;
// 求大整数的绝对值
44 protected:
// 以下运算符重载函数主要用于像基本类型一样使用大整数类型
friend BigInteger operator + (const BigInteger &, const BigInteger &);
friend BigInteger operator - (const BigInteger &, const BigInteger &);
friend BigInteger operator * (const BigInteger &, const BigInteger &);
friend BigInteger operator / (const BigInteger &, const BigInteger &);
friend BigInteger operator % (const BigInteger &, const BigInteger &);
friend bool operator & (const BigInteger &, const BigInteger &);
friend bool operator & (const BigInteger &, const BigInteger &);
friend bool operator == (const BigInteger &, const BigInteger &);
friend bool operator &= (const BigInteger &, const BigInteger &);
friend bool operator &= (const BigInteger &, const BigInteger &);
friend bool operator != (const BigInteger &, const BigInteger &);
// 重载版本,使其能用于long_t类型
friend BigInteger operator + (const BigInteger &, const long_t &);
friend BigInteger operator - (const BigInteger &, const long_t &);
friend BigInteger operator * (const BigInteger &, const long_t &);
friend BigInteger operator / (const BigInteger &, const long_t &);
friend BigInteger operator % (const BigInteger &, const long_t &);
friend bool operator & (const BigInteger &, const long_t &);
friend bool operator & (const BigInteger &, const long_t &);
friend bool operator == (const BigInteger &, const long_t &);
friend bool operator &= (const BigInteger &, const long_t &);
friend bool operator &= (const BigInteger &, const long_t &);
friend bool operator != (const BigInteger &, const long_t &);
friend std::ostream & operator && (std::ostream &, const BigInteger &);
BigInteger operator = (const std::string & str) { return (*this) = BigInteger(str); }
BigInteger operator = (const long_t & num) { return (*this) = BigInteger(num); }
74 private:
BigInteger trim();
// 去掉高位无用的0
int hexToNum(char);
// 十六进制字符转换为十进制数
77 public:
static const int base_bit = <span style="color: #;
// 2^5=32,大整数每位存储的二进制位数
static const int base_char = <span style="color: #;
// 组成大整数的一位需要的十六进制位数
static const int base_int = <span style="color: #;
// 大整数一位对应的二进制位数
static const int base_num = <span style="color: #xffffffff;// 截取低位的辅助
static const int base_temp = <span style="color: #x1f;
// 截取模32的余数的辅助
static const BigInteger ZERO;
// 大整数常量0
static const BigInteger ONE;
// 大整数常量1
static const BigInteger TWO;
// 大整数常量2
static const BigInteger TEN;
// 大整数常量10
87 private:
bool is_// 是否为负数
std::vector&base_t&// 按位数据存储,高位在后
class bit {
// 便于大整数运算的二进制处理类
bit(const BigInteger &);// 根据大整数初始化
size_t size() { return }
// 返回大整数对应的二进制位数
bool at(size_t);
// 返回第i位二进制是否为1
std::vector&base_t& bit_
// 二进制数据存储,每一个元素对应32位二进制
// 二进制的总位数
<span style="color: #0
friend class RSA;
// RSA为其友元类
<span style="color: #1 };
<span style="color: #2
<span style="color: #3 #endif // __BIGINTEGER_H__
&&& BigInteger.cpp代码如下。
: BigInteger.cpp
: -22.16.42
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &algorithm&
10 #include &cassert&
11 #include &cctype&
12 #include "BigInteger.h"
14 // 以下表示为静态常量赋值
15 const BigInteger BigInteger::ZERO = BigInteger(<span style="color: #);
16 const BigInteger BigInteger::ONE = BigInteger(<span style="color: #);
17 const BigInteger BigInteger::TWO = BigInteger(<span style="color: #);
18 const BigInteger BigInteger::TEN = BigInteger(<span style="color: #);
* 函数功能:根据给定的大整数构造一个新的大整数
* 参数含义:val代表给定的大整数
24 BigInteger::BigInteger(const BigInteger & val) {
* 函数功能:根据给定的十六进制字符串数据构造一个大整数
* 参数含义:str代表给定的数据
32 BigInteger::BigInteger(const std::string & str): is_negative(false) {
std::string t(str);
if (t.size() && t.at(<span style="color: #)=='-') {
if (t.size() & <span style="color: #)
is_negative = true;
t = t.substr(<span style="color: #);
int cnt = (<span style="color: #-(t.size()%<span style="color: #))%<span style="color: #;// 数的长度不是8的倍数,补足0
std::string
for (int i=<span style="color: #; i& ++i)
temp.push_back('<span style="color: #');
t = temp+t;
for (size_t i=<span style="color: #; i&t.size(); i+=base_char) {
base_t sum = <span style="color: #;
for (int j=<span style="color: #; j&base_ ++j) {
// 8位十六进制组成大整数的一位
char ch = t[i+j];
int num = hexToNum(ch);
sum = ((sum&&<span style="color: #) | (num));
data.push_back(sum);
reverse(data.begin(), data.end());// 高位在后
*this = trim();// 去除高位的0
* 函数功能:根据给定的long_t类型数据构造一个大整数
* 参数含义:num代表给定的数据
64 BigInteger::BigInteger(const long_t & num): is_negative(false) {
long_t t =
if (t & <span style="color: #) {
is_negative = true;
base_t temp = (t&base_num);
// 每次截取低32位
data.push_back(temp);
t &&= base_
} while (t);
* 函数功能:大整数加法运算
* 参数含义:val代表加数
81 BigInteger BigInteger::add(const BigInteger & val) {
BigInteger ans(*this);
if (ans.is_negative == val.is_negative) {// 同号
int len = val.data.size()-ans.data.size();
while ((len--) & <span style="color: #)
// 被加数位数少,高位补0
ans.data.push_back(<span style="color: #);
int carry = <span style="color: #;
for (size_t i=<span style="color: #; i&val.data.size(); ++i) {
base_t temp = ans.data[i];
ans.data[i] += val.data[i]+
// 无符号数相加,超出取其余数
// 进位:一种是有无进位都超出,一种是有进位才超出(比如十进制相加,9+9+1,得9,9+0+0,得9)
carry = (temp&ans.data[i] ? <span style="color: # : (temp&(temp+val.data[i]) ? <span style="color: # : <span style="color: #));
for (size_t i=val.data.size(); i&ans.data.size() && carry!=<span style="color: #; ++i) {// 还有进位
base_t temp = ans.data[i];
ans.data[i] +=
<span style="color: #0
carry = temp & ans.data[i];
<span style="color: #1
<span style="color: #2
<span style="color: #3
if (carry)
// 还有进位
<span style="color: #4
ans.data.push_back(carry);
<span style="color: #5
<span style="color: #6
<span style="color: #7
BigInteger a = abs();
<span style="color: #8
BigInteger b = val.abs();
<span style="color: #9
int flag = a.compareTo(b);
<span style="color: #0
// 绝对值相等,则结果为0,否则用绝对值大的减去小的,符号随绝对值大的
<span style="color: #1
if (flag == -<span style="color: #) {
<span style="color: #2
ans = b.subtract(a);
<span style="color: #3
ans.is_negative = val.is_
<span style="color: #4
<span style="color: #5
else if (flag == <span style="color: #)
<span style="color: #6
ans = ZERO;
<span style="color: #7
<span style="color: #8
ans = a.subtract(b);
<span style="color: #9
ans.is_negative = is_
<span style="color: #0
<span style="color: #1
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:大整数减法运算
<span style="color: #7
* 参数含义:val代表减数
<span style="color: #8
<span style="color: #9 BigInteger BigInteger::subtract(const BigInteger & val) {
<span style="color: #0
BigInteger ans(*this);
<span style="color: #1
BigInteger a = abs();
<span style="color: #2
BigInteger b = val.abs();
<span style="color: #3
if (ans.is_negative == val.is_negative) {// 同号
<span style="color: #4
int flag = a.compareTo(b);
<span style="color: #5
if (flag == <span style="color: #) {// a的绝对值大于b的绝对值,直接减
<span style="color: #6
int borrow = <span style="color: #;
<span style="color: #7
// 大数减小数
<span style="color: #8
for (size_t i=<span style="color: #; i&val.data.size(); ++i) {
<span style="color: #9
base_t temp = ans.data[i];
<span style="color: #0
ans.data[i] -= val.data[i]+
<span style="color: #1
// 借位:一种是有无借位都超出,另一种是有借位才超出(比如十进制相减,9-0-0,得9,9-9-1,得9)
<span style="color: #2
borrow = temp&ans.data[i] ? <span style="color: # : (temp-borrow&val.data[i] ? <span style="color: # : <span style="color: #);
<span style="color: #3
<span style="color: #4
for (size_t i=val.data.size(); i&ans.data.size() && borrow!=<span style="color: #; ++i) {// 还有借位
<span style="color: #5
base_t temp = ans.data[i];
<span style="color: #6
ans.data[i] -=
<span style="color: #7
borrow = temp & (base_t)
<span style="color: #8
<span style="color: #9
ans = ans.trim();// 去掉高位多余的0
<span style="color: #0
<span style="color: #1
else if (flag == <span style="color: #)
<span style="color: #2
ans = ZERO;
<span style="color: #3
else {// a的绝对值小于b的绝对值
<span style="color: #4
ans = b.subtract(a);
<span style="color: #5
ans.is_negative = !is_
<span style="color: #6
<span style="color: #7
<span style="color: #8
<span style="color: #9
ans = a.add(b);
// 转换为加法
<span style="color: #0
ans.is_negative = is_
<span style="color: #1
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:大整数乘法运算
<span style="color: #7
* 参数含义:val代表乘数
<span style="color: #8
<span style="color: #9 BigInteger BigInteger::multiply(const BigInteger & val) const {
<span style="color: #0
if (equals(ZERO) || val.equals(ZERO))
<span style="color: #1
return ZERO;
<span style="color: #2
// 将位数少的作为乘数
<span style="color: #3
const BigInteger & big = data.size()&val.data.size() ? (*this) :
<span style="color: #4
const BigInteger & small = (&big)==(this) ? val : (*this);
<span style="color: #5
<span style="color: #6
<span style="color: #7
bit t(small);
// 转换为二进制进行运算
<span style="color: #8
<span style="color: #9
for (int i=t.size()-<span style="color: #; i&=<span style="color: #; --i)
<span style="color: #0
if (t.at(i)) {
<span style="color: #1
BigInteger temp(big);
<span style="color: #2
temp.is_negative = false;
<span style="color: #3
temp = temp.shiftLeft(i);
// 移位对齐
<span style="color: #4
ans = ans.add(temp);
<span style="color: #5
<span style="color: #6
ans.is_negative = !(is_negative == val.is_negative);
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:大整数整除运算
<span style="color: #2
* 参数含义:val代表除数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::divide(const BigInteger & val) {
<span style="color: #5
<span style="color: #6
BigInteger ans = divideAndRemainder(val, temp);
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:大整数取余运算
<span style="color: #2
* 参数含义:val代表除数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::remainder(const BigInteger & val) {
<span style="color: #5
<span style="color: #6
divideAndRemainder(val, ans);
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:大整数取模运算(不同于取余,该函数总是返回正余数)
<span style="color: #2
* 参数含义:m代表模数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::mod(const BigInteger & m) {
<span style="color: #5
BigInteger ans = remainder(m);
<span style="color: #6
if (ans.is_negative)
<span style="color: #7
ans = ans.add(m);
<span style="color: #8
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 /**
<span style="color: #2
* 函数功能:大整数整除运算和取余运算,整除结果直接返回,取余结果由m传回
<span style="color: #3
* 参数含义:val表示除数,m表示取余结果
<span style="color: #4
<span style="color: #5 BigInteger BigInteger::divideAndRemainder(const BigInteger & val, BigInteger & m) {
<span style="color: #6
assert(!val.equals(ZERO));
<span style="color: #7
BigInteger a = abs();
<span style="color: #8
BigInteger b = val.abs();
<span style="color: #9
int flag = a.compareTo(b);
<span style="color: #0
if (flag == <span style="color: #)// 绝对值相等
<span style="color: #1
return (is_negative==val.is_negative) ? BigInteger(<span style="color: #) : BigInteger(-<span style="color: #);
<span style="color: #2
if (flag == -<span style="color: #) {
<span style="color: #3
m = *this;
<span style="color: #4
return ZERO;
<span style="color: #5
<span style="color: #6
<span style="color: #7
<span style="color: #8
bit bit_b(b);
<span style="color: #9
// 位数对齐
<span style="color: #0
while (true) {// a的绝对值大于b的绝对值
<span style="color: #1
bit bit_a(a);
<span style="color: #2
int len = bit_a.size()-bit_b.size();
<span style="color: #3
<span style="color: #4
// 找到移位
<span style="color: #5
while (len &= <span style="color: #) {
<span style="color: #6
temp = b.shiftLeft(len);
<span style="color: #7
if (temp.compareTo(a) != <span style="color: #)// 找到最大的左移位数使得当前的a大于等于b
<span style="color: #8
<span style="color: #9
<span style="color: #0
<span style="color: #1
if (len & <span style="color: #)
// 当前的a小于b了
<span style="color: #2
<span style="color: #3
base_t num = <span style="color: #;
<span style="color: #4
while (temp.compareTo(a) != <span style="color: #) {
<span style="color: #5
a = a.subtract(temp);
<span style="color: #6
// 统计当前的a最多大于等于几个移位后的b
<span style="color: #7
<span style="color: #8
temp = BigInteger(num);
<span style="color: #9
<span style="color: #0
temp = temp.shiftLeft(len);// 移位后表明当前的a是b的几倍
<span style="color: #1
ans = ans.add(temp);
<span style="color: #2
<span style="color: #3
ans.is_negative = !(is_negative==val.is_negative);
<span style="color: #4
m.data = a.
<span style="color: #5
m.is_negative = is_
<span style="color: #6
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:大整数幂乘运算
<span style="color: #1
* 参数含义:exponent代表指数
<span style="color: #2
<span style="color: #3 BigInteger BigInteger::pow(const BigInteger & exponent) {
<span style="color: #4
BigInteger ans(<span style="color: #);
<span style="color: #5
bit t(exponent);
// 转化为二进制,快速求幂
<span style="color: #6
for (int i=t.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #7
ans = ans.multiply(ans);
<span style="color: #8
if (t.at(i))
<span style="color: #9
ans = multiply(ans);// 从高位开始,位权累加效应
<span style="color: #0
<span style="color: #1
<span style="color: #2 }
<span style="color: #3
<span style="color: #4 /**
<span style="color: #5
* 函数功能:大整数模幂运算
<span style="color: #6
* 参数含义:exponent代表指数,m代表模数
<span style="color: #7
<span style="color: #8 BigInteger BigInteger::modPow(const BigInteger & exponent, const BigInteger & m) const {
<span style="color: #9
assert(!m.equals(ZERO));
<span style="color: #0
BigInteger ans(<span style="color: #);
<span style="color: #1
bit t(exponent);
<span style="color: #2
for (int i=t.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #3
ans = ans.multiply(ans).mod(m);
<span style="color: #4
if (t.at(i))
<span style="color: #5
ans = multiply(ans).mod(m);
<span style="color: #6
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:扩展欧几里得算法求乘法逆元
<span style="color: #2
* 参数含义:m代表求逆元时的模数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::modInverse(const BigInteger & m) {
<span style="color: #5
assert(!is_negative);
// 当前大整数为正数
<span style="color: #6
assert(!m.is_negative);
// m为正数
<span style="color: #7
if (equals(ZERO) || m.equals(ZERO))
<span style="color: #8
return ZERO;
// 有一个数为0,就不存在乘法逆元
<span style="color: #9
BigInteger a[<span style="color: #], b[<span style="color: #], t[<span style="color: #];
<span style="color: #0
// 以下进行初等变换
<span style="color: #1
a[<span style="color: #] = <span style="color: #; a[<span style="color: #] = <span style="color: #; a[<span style="color: #] = *this;
<span style="color: #2
b[<span style="color: #] = <span style="color: #; b[<span style="color: #] = <span style="color: #; b[<span style="color: #] =
<span style="color: #3
<span style="color: #4
for (t[<span style="color: #]=a[<span style="color: #].mod(b[<span style="color: #]); !t[<span style="color: #].equals(ZERO); t[<span style="color: #]=a[<span style="color: #].mod(b[<span style="color: #])) {
<span style="color: #5
BigInteger temp = a[<span style="color: #].divide(b[<span style="color: #]);
<span style="color: #6
for (int i=<span style="color: #; i&<span style="color: #; ++i) {
<span style="color: #7
t[i] = a[i].subtract(temp.multiply(b[i]));// 不超过一次a[2]-temp*b[2]就变为大数减小数
<span style="color: #8
a[i] = b[i];
<span style="color: #9
b[i] = t[i];
<span style="color: #0
<span style="color: #1
<span style="color: #2
if (b[<span style="color: #].equals(ONE)) {// 最大公约数为1,存在乘法逆元
<span style="color: #3
if (b[<span style="color: #].is_negative)// 逆元为负数
<span style="color: #4
b[<span style="color: #] = b[<span style="color: #].add(m);// 变为正数,使其在m的剩余集中
<span style="color: #5
return b[<span style="color: #];
<span style="color: #6
<span style="color: #7
return ZERO;// 最大公约数不为1,无乘法逆元
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:移位运算,左移
<span style="color: #2
* 参数含义:len代表移位的位数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::shiftLeft(const unsigned len) {
<span style="color: #5
int index = len&&base_
// 大整数每一位需要移动多少位
<span style="color: #6
int shift = len&base_
// 还剩下多少位
<span style="color: #7
BigInteger ans(*this);
<span style="color: #8
<span style="color: #9
int inc = (shift==<span style="color: #) ? index : index+<span style="color: #;// 有多余的位要多开大整数的一位
<span style="color: #0
for (int i=<span style="color: #; i& ++i)
<span style="color: #1
ans.data.push_back(<span style="color: #);
// 高位补0
<span style="color: #2
<span style="color: #3
if (index) {
<span style="color: #4
inc = (shift==<span style="color: #) ? <span style="color: # : <span style="color: #;// 有多余的位要预留一位
<span style="color: #5
for (int i=ans.data.size()- i&= --i)
<span style="color: #6
ans.data[i] = ans.data[i-index];
<span style="color: #7
for (int i=<span style="color: #; i& ++i)
<span style="color: #8
ans.data[i] = <span style="color: #;
<span style="color: #9
<span style="color: #0
if (shift) {
<span style="color: #1
base_t t = base_
<span style="color: #2
t &&= base_int-
// 用于截取高位
<span style="color: #3
<span style="color: #4
base_t temp = <span style="color: #;
<span style="color: #5
for (size_t i=<span style="color: #; i&ans.data.size(); ++i) {
<span style="color: #6
base_t tmp = ans.data[i];
<span style="color: #7
ans.data[i] = (tmp&&shift) |// 左移后加上大整数低位的高位
<span style="color: #8
temp = (tmp&t)&&(base_int-shift);// 获取该大整数位的高位
<span style="color: #9
<span style="color: #0
<span style="color: #1
ans = ans.trim();
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:移位运算,右移
<span style="color: #7
* 参数含义:len代表移位的位数
<span style="color: #8
<span style="color: #9 BigInteger BigInteger::shiftRight(const unsigned len) {
<span style="color: #0
bit val(*this);
<span style="color: #1
if (len &= val.size())// 当前大整数位数小于等于移位位数,返回0
<span style="color: #2
return ZERO;
<span style="color: #3
int index = len&&base_// 大整数每一位需要移动多少位
<span style="color: #4
int shift = len&base_// 还剩下多少位
<span style="color: #5
BigInteger ans(*this);
<span style="color: #6
<span style="color: #7
if (index) {
<span style="color: #8
for (int i=<span style="color: #; i& ++i)
<span style="color: #9
ans.data[i] = ans.data[i+index];
<span style="color: #0
for (int i=<span style="color: #; i& ++i)
<span style="color: #1
ans.data.pop_back();
// 高位删除
<span style="color: #2
<span style="color: #3
if (shift) {
<span style="color: #4
base_t t = base_
<span style="color: #5
t &&= base_int-
// 用于截取低位
<span style="color: #6
<span style="color: #7
base_t temp = <span style="color: #;
<span style="color: #8
for (int i=ans.data.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #9
base_t tmp = ans.data[i];
<span style="color: #0
ans.data[i] = (tmp&&shift) |// 右移后加上大整数高位的低位
<span style="color: #1
temp = (tmp&t)&&(base_int-shift);// 获取该大整数位的低位
<span style="color: #2
<span style="color: #3
<span style="color: #4
ans = ans.trim();
<span style="color: #5
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 /**
<span style="color: #9
* 函数功能:大整数比较函数,-1表示本大整数要小,0表示相等,1表示本大整数要大
<span style="color: #0
* 参数含义:val代表要与之比较的大整数
<span style="color: #1
<span style="color: #2 int BigInteger::compareTo(const BigInteger & val) const {
<span style="color: #3
if (is_negative != val.is_negative) {// 符号不同,负数必小
<span style="color: #4
if (is_negative == true)
<span style="color: #5
return -<span style="color: #;
<span style="color: #6
return <span style="color: #;
<span style="color: #7
<span style="color: #8
int flag = <span style="color: #;
<span style="color: #9
if (data.size() & val.data.size())// 位数较小
<span style="color: #0
flag = -<span style="color: #;
<span style="color: #1
else if (data.size() & val.data.size())// 位数较大
<span style="color: #2
flag = <span style="color: #;
<span style="color: #3
// 位数相等,从高位开始一一比较
<span style="color: #4
for (std::vector&base_t&::const_reverse_iterator it=data.rbegin(), ite=val.data.rbegin(); it!=data.rend(); ++it, ++ite)
<span style="color: #5
if ((*it) != (*ite)) {
<span style="color: #6
flag = (*it)&(*ite) ? -<span style="color: # : <span style="color: #;
// 高位小,则小
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0
if (is_negative)
// 如为负数,小的反而大
<span style="color: #1
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:大整数是否相等函数
<span style="color: #7
* 参数含义:val表示要与之比较的大整数
<span style="color: #8
<span style="color: #9 bool BigInteger::equals(const BigInteger & val) const {
<span style="color: #0
return (is_negative==val.is_negative) && (data==val.data);// 符号和数据都要相等
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:将一个long_t类型的数据转换为大整数并返回
<span style="color: #5
* 参数含义:num表示给定的数
<span style="color: #6
<span style="color: #7 BigInteger BigInteger::valueOf(const long_t & num) {
<span style="color: #8
return BigInteger(num);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 /**
<span style="color: #2
* 函数功能:将大整数转换为十六进制字符串并返回
<span style="color: #3
<span style="color: #4 std::string BigInteger::toString() const {
<span style="color: #5
std::string
<span style="color: #6
base_t t = base_
<span style="color: #7
t &&= base_int-<span style="color: #;
// 用于截取高4位
<span style="color: #8
for (int i=data.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #9
base_t temp = data[i];
<span style="color: #0
for (int j=<span style="color: #; j&base_ ++j) {
<span style="color: #1
base_t num = t&// 每次截取高4位
<span style="color: #2
num &&= base_int-<span style="color: #;
// 将高4位移到低4位
<span style="color: #3
temp &&= <span style="color: #;
<span style="color: #4
if (num & <span style="color: #)
<span style="color: #5
ans.push_back((char)('<span style="color: #'+num));
<span style="color: #6
<span style="color: #7
ans.push_back((char)('A'+num-<span style="color: #));
<span style="color: #8
<span style="color: #9
<span style="color: #0
while (ans.size()&<span style="color: # && ans.at(<span style="color: #)=='<span style="color: #')// 去掉高位无用的0
<span style="color: #1
ans = ans.substr(<span style="color: #);
<span style="color: #2
if (ans.empty())
// 空串说明为0
<span style="color: #3
ans.push_back('<span style="color: #');
<span style="color: #4
if (is_negative)
// 为负数加上负号
<span style="color: #5
ans = "-"+
<span style="color: #6
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:返回大整数的绝对值
<span style="color: #1
<span style="color: #2 BigInteger BigInteger::abs() const {
<span style="color: #3
<span style="color: #4
ans.data =// 只复制数据,符号默认为正
<span style="color: #5
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 // 以下运算符重载函数主要是为了使得能使用
<span style="color: #9 // 大整数类型像使用基本类型一样,不一一介绍
<span style="color: #0 BigInteger operator + (const BigInteger & a, const BigInteger & b) {
<span style="color: #1
BigInteger t(a);
<span style="color: #2
return t.add(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 BigInteger operator - (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
BigInteger t(a);
<span style="color: #7
return t.subtract(b);
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 BigInteger operator * (const BigInteger & a, const BigInteger & b) {
<span style="color: #1
BigInteger t(a);
<span style="color: #2
return t.multiply(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 BigInteger operator / (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
BigInteger t(a);
<span style="color: #7
return t.divide(b);
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 BigInteger operator % (const BigInteger & a, const BigInteger & b) {
<span style="color: #1
BigInteger t(a);
<span style="color: #2
return t.remainder(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 bool operator & (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
return a.compareTo(b) == -<span style="color: #;
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 bool operator & (const BigInteger & a, const BigInteger & b) {
<span style="color: #0
return b &
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 bool operator == (const BigInteger & a, const BigInteger & b) {
<span style="color: #4
return a.equals(b);
<span style="color: #5 }
<span style="color: #6
<span style="color: #7 bool operator &= (const BigInteger & a, const BigInteger & b) {
<span style="color: #8
return !(a & b);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 bool operator &= (const BigInteger & a, const BigInteger & b) {
<span style="color: #2
return !(a & b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 bool operator != (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
return !(a == b);
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 BigInteger operator + (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #0
return a+BigInteger(b);
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 BigInteger operator - (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #4
return a-BigInteger(b);
<span style="color: #5 }
<span style="color: #6
<span style="color: #7 BigInteger operator * (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #8
return a*BigInteger(b);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 BigInteger operator / (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #2
return a/BigInteger(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 BigInteger operator % (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #6
return a%BigInteger(b);
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 bool operator & (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #0
return a & BigInteger(b);
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 bool operator & (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #4
return a & BigInteger(b);
<span style="color: #5 }
<span style="color: #6
<span style="color: #7 bool operator == (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #8
return a == BigInteger(b);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 bool operator &= (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #2
return a &= BigInteger(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 bool operator &= (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #6
return a &= BigInteger(b);
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 bool operator != (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #0
return a != BigInteger(b);
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 std::ostream & operator && (std::ostream & out, const BigInteger & val) {
<span style="color: #4
out && val.toString();
<span style="color: #5
return out;
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 /**
<span style="color: #9
* 函数功能:创建该大整数的一个副本,去除掉高位无用的0后并返回
<span style="color: #0
<span style="color: #1 BigInteger BigInteger::trim() {
<span style="color: #2
size_t cnt = <span style="color: #;
<span style="color: #3
// 检查高位为0的元素的数量
<span style="color: #4
for (std::vector&base_t&::const_reverse_iterator it=data.rbegin(); it!=data.rend(); ++it) {
<span style="color: #5
if ((*it) == <span style="color: #)
<span style="color: #6
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0
if (cnt == data.size())
// 只有零的情况保留
<span style="color: #1
<span style="color: #2
BigInteger ans(*this);
<span style="color: #3
for (size_t i=<span style="color: #; i& ++i)
<span style="color: #4
ans.data.pop_back();
<span style="color: #5
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 /**
<span style="color: #9
* 函数功能:根据给定的字符确定它所对应的十进制数
<span style="color: #0
* 参数含义:ch代表给定的字符
<span style="color: #1
<span style="color: #2 int BigInteger::hexToNum(char ch) {
<span style="color: #3
int ans = <span style="color: #;
<span style="color: #4
if (isdigit(ch))
<span style="color: #5
ans = ch-'<span style="color: #';
<span style="color: #6
else if (islower(ch))
<span style="color: #7
ans = ch-'a'+<span style="color: #;
<span style="color: #8
<span style="color: #9
ans = ch-'A'+<span style="color: #;
<span style="color: #0
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:根据给定的大整数初始化
<span style="color: #5
* 参数含义:val代表给定的大整数
<span style="color: #6
<span style="color: #7 BigInteger::bit::bit(const BigInteger & val) {
<span style="color: #8
bit_vector = val.
<span style="color: #9
base_t temp = bit_vector[bit_vector.size()-<span style="color: #];// 大整数最高位
<span style="color: #0
length = bit_vector.size()&&base_
// 大整数一位占二进制32位
<span style="color: #1
base_t t = <span style="color: #&&(base_int-<span style="color: #);
// 用于截取一个数的二进制最高位
<span style="color: #2
<span style="color: #3
if (temp == <span style="color: #)
// 大整数最高位为0,减去32
<span style="color: #4
length -= base_
<span style="color: #5
<span style="color: #6
while (!(temp & t)) {// 从高位开始检测大整数的二进制位,为0长度减一
<span style="color: #7
<span style="color: #8
t &&= <span style="color: #;
// 右移一位表示检测下一位
<span style="color: #9
<span style="color: #0
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:检测大整数的第id位二进制位是否为1
<span style="color: #5
* 参数含义:id代表第id位
<span style="color: #6
<span style="color: #7 bool BigInteger::bit::at(size_t id) {
<span style="color: #8
size_t index = id&&base_// 确定其在大整数第几位
<span style="color: #9
size_t shift = id&base_// 确定其在大整数那一位的二进制第几位
<span style="color: #0
base_t t = bit_vector[index];
<span style="color: #1
return (t & (<span style="color: #&&shift));
<span style="color: #2 }
&&& 该类主要实现RSA相关功能，例如加密和解密等。
&&& 该模块也有两个文件：RSA.h和RSA.cpp。代码如下所示。
&&& RSA.h代码如下。
: -22.25.57
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #ifndef __RSA_H__
<span style="color: # #define __RSA_H__
<span style="color: #
<span style="color: # #include &ostream&
<span style="color: # #include "BigInteger.h"
<span style="color: # class RSA {
<span style="color: # public:
<span style="color: #
<span style="color: #
RSA(const unsigned len) { init(len); }
// 利用len初始化对象
<span style="color: #
<span style="color: #
<span style="color: #
void init(const unsigned);// 初始化,产生公私钥对
<span style="color: #
<span style="color: #
BigInteger encryptByPublic(const BigInteger &);
// 公钥加密
<span style="color: #
BigInteger decryptByPrivate(const BigInteger &);// 私钥解密
<span style="color: #
<span style="color: #
// 以下主要用于数字签名
<span style="color: #
BigInteger encryptByPrivate(const BigInteger &);// 私钥加密
<span style="color: #
BigInteger decryptByPublic(const BigInteger &);
// 公钥解密
<span style="color: # protected:
<span style="color: #
friend std::ostream & operator && (std::ostream &, const RSA &);// 输出相关数据
<span style="color: # private:
<span style="color: #
BigInteger createOddNum(unsigned);// 生成一个大奇数,参数为其长度
<span style="color: #
bool isPrime(const BigInteger &, const unsigned);// 判断是否为素数
<span style="color: #
BigInteger createRandomSmaller(const BigInteger &);// 随机创建一个更小的数
<span style="color: #
BigInteger createPrime(unsigned, const unsigned);// 生成一个大素数,参数为其长度
<span style="color: #
void createExponent(const BigInteger &);// 根据提供的欧拉数生成公钥、私钥指数
<span style="color: # public:
<span style="color: #
BigInteger n,// 公钥
<span style="color: # private:
<span style="color: #
BigI// 私钥
<span style="color: #
BigInteger p,// 大素数p和q
<span style="color: #
BigI// n的欧拉函数
<span style="color: # };
<span style="color: #
<span style="color: # #endif // __RSA_H__
&&& RSA.cpp代码如下。
: -22.27.51
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &cassert&
10 #include &sstream&
11 #include &ctime&
12 #include "RSA.h"
* 函数功能:初始化RSA对象的相关信息
* 参数含义:len表示大素数的二进制位数
18 void RSA::init(const unsigned len) {
srand((unsigned)time(NULL));
// 产生大素数p和q
p = createPrime(len, <span style="color: #);// 出错概率为(1/4)^15
q = createPrime(len, <span style="color: #);
// 计算出n
// 计算出n的欧拉函数
eul = (p-<span style="color: #)*(q-<span style="color: #);
// 设置加解密指数e和d
createExponent(eul);
* 函数功能:使用公钥进行加密
* 参数含义:m表示要加密的明文
35 BigInteger RSA::encryptByPublic(const BigInteger & m) {
return m.modPow(e, n);
* 函数功能:使用私钥进行解密
* 参数含义:c表示要解密的密文
43 BigInteger RSA::decryptByPrivate(const BigInteger & c) {
return c.modPow(d, n);
* 函数功能:使用私钥进行加密
* 参数含义:m表示要加密的明文
51 BigInteger RSA::encryptByPrivate(const BigInteger & m) {
return decryptByPrivate(m);
* 函数功能:使用公钥进行解密
* 参数含义:c表示要解密的密文
59 BigInteger RSA::decryptByPublic(const BigInteger & c) {
return encryptByPublic(c);
* 函数功能:输出RSA相关数据
* 参数含义:out表示输出流,rsa表示要输出的RSA对象
67 std::ostream & operator && (std::ostream & out, const RSA & rsa) {
out && "n: " && rsa.n && "\n";
out && "p: " && rsa.p && "\n";
out && "q: " && rsa.q && "\n";
out && "e: " && rsa.e && "\n";
out && "d: " && rsa.d;
return out;
* 函数功能:生成一个长度为len的奇数
* 参数含义:len代表奇数的二进制长度
80 BigInteger RSA::createOddNum(unsigned len) {
static const char hex_table[] = {'<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #',
'<span style="color: #', '<span style="color: #', 'A', 'B', 'C', 'D', 'E', 'F'};
len &&= <span style="color: #;
// 十六进制数据,每位占4位二进制
if (len) {
for (size_t i=<span style="color: #; i&len-<span style="color: #; ++i)
oss && hex_table[rand()%<span style="color: #];
oss && hex_table[<span style="color: #];// 最后一位为奇数
return BigInteger(oss.str());
return BigInteger("F");
* 函数功能:判断一个数是否为素数,采用米勒拉宾大素数检测算法,失误率为(1/4)^k
* 参数含义:num代表要判定的数,k代表测试次数
98 bool RSA::isPrime(const BigInteger & num, const unsigned k) {
assert(num != BigInteger::ZERO);// 测试num是否为0
<span style="color: #0
if (num == BigInteger::ONE)
<span style="color: #1
return false;
// 1不是素数
<span style="color: #2
if (num == BigInteger::TWO)
<span style="color: #3
return true;
// 2是素数
<span style="color: #4
<span style="color: #5
BigInteger t = num-<span style="color: #;
<span style="color: #6
BigInteger::bit b(t);// 二进制数
<span style="color: #7
if (b.at(<span style="color: #) == <span style="color: #)
// 减一之后为奇数,原数为偶数
<span style="color: #8
return false;
<span style="color: #9
// num-1 = 2^s*d
<span style="color: #0
size_t s = <span style="color: #;
// 统计二进制末尾有几个0
<span style="color: #1
BigInteger d(t);
<span style="color: #2
for (size_t i=<span style="color: #; i&b.size(); ++i) {
<span style="color: #3
if (!b.at(i)) {
<span style="color: #4
<span style="color: #5
d = d.shiftRight(<span style="color: #);// 计算出d
<span style="color: #6
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0
<span style="color: #1
for (size_t i=<span style="color: #; i&k; ++i) {// 测试k次
<span style="color: #2
BigInteger a = createRandomSmaller(num);// 生成一个介于[1,num-1]之间的随机数a
<span style="color: #3
BigInteger x = a.modPow(d, num);
<span style="color: #4
if (x == BigInteger::ONE)// 可能为素数
<span style="color: #5
<span style="color: #6
bool ok = true;
<span style="color: #7
// 测试所有0&=j&s,a^(2^j*d) mod num != -1
<span style="color: #8
for (size_t j=<span style="color: #; j&s && ++j) {
<span style="color: #9
if (x == t)
<span style="color: #0
ok = false;
// 有一个相等,可能为素数
<span style="color: #1
x = x.multiply(x).mod(num);
<span style="color: #2
<span style="color: #3
// 确实都不等,一定为合数
<span style="color: #4
return false;
<span style="color: #5
<span style="color: #6
return true;
// 通过所有测试,可能为素数
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:随机生成一个比val小的数
<span style="color: #1
* 参数含义:val代表比较的那个数
<span style="color: #2
<span style="color: #3 BigInteger RSA::createRandomSmaller(const BigInteger & val) {
<span style="color: #4
BigInteger::base_t t = <span style="color: #;
<span style="color: #5
<span style="color: #6
t = rand();
<span style="color: #7
} while (t == <span style="color: #);// 随机生成非0数
<span style="color: #8
<span style="color: #9
BigInteger mod(t);
<span style="color: #0
BigInteger ans = mod%
// 比val要小
<span style="color: #1
if (ans == BigInteger::ZERO)// 必须非零
<span style="color: #2
ans = val-BigInteger::ONE;
<span style="color: #3
<span style="color: #4 }
<span style="color: #5
<span style="color: #6 /**
<span style="color: #7
* 函数功能:生成一个二进制长度为len的大素数
<span style="color: #8
* 参数含义:len代表大素数的长度,k代表素数检测的次数
<span style="color: #9
<span style="color: #0 BigInteger RSA::createPrime(unsigned len, const unsigned k) {
<span style="color: #1
assert(k & <span style="color: #);
<span style="color: #2
BigInteger ans = createOddNum(len);// 先生成一个奇数
<span style="color: #3
while (!isPrime(ans, k)) {// 素性检测
<span style="color: #4
ans = ans.add(BigInteger::TWO);// 下一个奇数
<span style="color: #5
<span style="color: #6
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:根据提供的欧拉数生成公钥、私钥指数
<span style="color: #1
* 参数含义:eul表示提供的欧拉数
<span style="color: #2
<span style="color: #3 void RSA::createExponent(const BigInteger & eul) {
<span style="color: #4
e = <span style="color: #537;
<span style="color: #5
d = e.modInverse(eul);
<span style="color: #6 }
2.3 EncryptDecrypt类
&&& 该类主要用于封装加解密的一些操作，比如判断数据是否合法，输入输出加解密信息等。
&&& 该模块同样有两个文件：EncryptDecrypt.h和EncryptDecrypt.cpp。代码如下所示。
&&& EncryptDecrypt.h代码如下。
: EncryptDecrypt.h
: -22.29.58
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #ifndef __ENCRYPTDECRYPT_H__
<span style="color: # #define __ENCRYPTDECRYPT_H__
<span style="color: #
<span style="color: # #include &string&
<span style="color: # #include "RSA.h"
<span style="color: # class EncryptDecrypt {
<span style="color: # public:
<span style="color: #
EncryptDecrypt() {}
<span style="color: #
~EncryptDecrypt() {}
<span style="color: #
<span style="color: #
void menu();
// 菜单显示
<span style="color: #
bool encrypt();
<span style="color: #
bool decrypt();
<span style="color: #
void print();
// 打印RSA相关信息
<span style="color: #
void reset();
// 重置RSA相关信息
<span style="color: # protected:
<span style="color: #
void load(int);
// 根据给定位数加载RSA对象
<span style="color: #
bool islegal(const std::string &);// 判断输入字符串是否合法
<span style="color: # private:
<span style="color: #
<span style="color: # };
<span style="color: #
<span style="color: # #endif // __ENCRYPTDECRYPT_H__
&&& EncryptDecrypt.cpp代码如下。
: EncryptDecrypt.cpp
: -22.32.18
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &iostream&
10 #include &ctime&
11 #include "EncryptDecrypt.h"
* 函数功能:菜单显示
16 void EncryptDecrypt::menu() {
std::cout && "**********Welcome to use RSA encoder**********" && std::
std::cout && "
e: encrypt 加密
" && std::
std::cout && "
d: decrypt 解密
" && std::
std::cout && "
" && std::
std::cout && "
" && std::
std::cout && "
" && std::
std::cout && "input your choice:" && std::
* 函数功能:加密运算
29 bool EncryptDecrypt::encrypt() {
std::string
std::cout && "输入16进制数据:" && std::
std::cout && "&";
std::cin &&// 输入明文
if (!std::cin || !islegal(str))
return false;
BigInteger m(str);
clock_t start = clock();
BigInteger c = rsa.encryptByPublic(m);
clock_t finish = clock();
std::cout && std::fixed;
std::cout.precision(<span style="color: #);
std::cout && "用时: " && (double)(finish-start)/CLOCKS_PER_SEC && "s." && std::
std::cout && "明文: " && m && std::
std::cout && "密文: " && c && std::
return true;
* 函数功能:解密运算
52 bool EncryptDecrypt::decrypt() {
std::string
std::cout && "输入16进制数据:" && std::
std::cout && "&";
std::cin &&// 输入密文
if (!std::cin || !islegal(str))
return false;
BigInteger c(str);
clock_t start = clock();
BigInteger m = rsa.decryptByPrivate(c);
clock_t finish = clock();
std::cout && std::fixed;
std::cout.precision(<span style="color: #);
std::cout && "用时: " && (double)(finish-start)/CLOCKS_PER_SEC && "s." && std::
std::cout && "密文: " && c && std::
std::cout && "明文: " && m && std::
return true;
* 函数功能:输出RSA相关信息
75 void EncryptDecrypt::print() {
std::cout && rsa && std::
* 函数功能:重置RSA相关信息
82 void EncryptDecrypt::reset() {
std::cout && "输入密钥长度: ";
std::cin &&
load(len&&<span style="color: #);
* 函数功能:根据给定位数len加载rsa
92 void EncryptDecrypt::load(int len) {
std::cout && "初始化..." && std::
clock_t start = clock();
rsa.init(len);
clock_t finish = clock();
std::cout && "初始化完成." && std::
std::cout && std::fixed;
std::cout.precision(<span style="color: #);
<span style="color: #0
std::cout && "用时: " && (double)(finish-start)/CLOCKS_PER_SEC && "s." && std::
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:判断输入字符串str是否合法
<span style="color: #5
* 参数含义:str代表输入的字符串
<span style="color: #6
<span style="color: #7 bool EncryptDecrypt::islegal(const std::string & str) {
<span style="color: #8
for (std::string::const_iterator it=str.begin(); it!=str.end(); ++it) {
<span style="color: #9
if (!isalnum(*it))
// 不是字母或者数字
<span style="color: #0
return false;
<span style="color: #1
if (isalpha(*it)) {
<span style="color: #2
char ch = tolower(*it);
<span style="color: #3
if (ch & 'f')
// 超过十六进制字符'f'
<span style="color: #4
return false;
<span style="color: #5
<span style="color: #6
<span style="color: #7
return true;
<span style="color: #8 }
2.4 主文件
&&& 该模块就只有一个文件：Main.cpp。主要用于使各个模块结合起来，执行相应操作。
&&& Main.cpp代码如下。
: Main.cpp
: -22.19.24
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &iostream&
<span style="color: # #include "EncryptDecrypt.h"
<span style="color: #
<span style="color: # int main() {
<span style="color: #
EncryptDecrypt encrypt_
<span style="color: #
encrypt_decrypt.reset();// 设置密钥长度
<span style="color: #
<span style="color: #
<span style="color: #
std::string
<span style="color: #
bool ok = true;
<span style="color: #
<span style="color: #
<span style="color: #
encrypt_decrypt.menu();// 菜单显示
<span style="color: #
std::cout && "&";
<span style="color: #
std::cin &&
<span style="color: #
if (str.empty()) {
<span style="color: #
std::cout && "输入错误!请重新输入!" && std::
<span style="color: #
<span style="color: #
<span style="color: #
ch = str.at(<span style="color: #);
<span style="color: #
switch(ch) {
<span style="color: #
<span style="color: #
<span style="color: #
if (!encrypt_decrypt.encrypt())
<span style="color: #
std::cout && "加密失败,请重试!" && std::
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
if (!encrypt_decrypt.decrypt())
<span style="color: #
std::cout && "解密失败,请重试!" && std::
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encrypt_decrypt.print();// 打印相关信息
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encrypt_decrypt.reset();// 重新设置密钥长度
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
ok = false;
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
} while (ok);
<span style="color: #
return <span style="color: #;
<span style="color: # }
&&& 至此，RSA加密算法已经介绍完毕了，如有任何错误，欢迎指出，不胜感激。
RSA加密算法 Java版本
&&& 附上Java版本的RSA加密算法，仅供参考。
&&& RSA.java代码如下。
1 import java.math.BigI
2 import java.util.R
4 public class RSA {
public BigInteger n,// 公钥
private BigI// 私钥
private BigInteger p,
private BigI// n的欧拉函数
<span style="color: #
<span style="color: #
* 函数功能:初始化RSA对象的相关信息
<span style="color: #
* 参数含义:len表示大素数的二进制位数
<span style="color: #
<span style="color: #
public void init(int len) {
<span style="color: #
Random random = new Random();
<span style="color: #
// 产生大素数p和q
<span style="color: #
p = BigInteger.probablePrime(len, random);
<span style="color: #
q = BigInteger.probablePrime(len, random);
<span style="color: #
// 计算出n
<span style="color: #
n = p.multiply(q);
<span style="color: #
// 计算出n的欧拉函数
<span style="color: #
eul = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
<span style="color: #
// 设置加解密指数e和d
<span style="color: #
createExponent(eul);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:使用公钥进行加密
<span style="color: #
* 参数含义:m表示要加密的明文
<span style="color: #
<span style="color: #
public BigInteger encryptByPublic(BigInteger m) {
<span style="color: #
return m.modPow(e, n);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:使用私钥进行解密
<span style="color: #
* 参数含义:c表示要解密的密文
<span style="color: #
<span style="color: #
public BigInteger decryptByPrivate(BigInteger c) {
<span style="color: #
return c.modPow(d, n);
<span style="color: #
<span style="color: #
<span style="color: #
// 以下主要用于数字签名
<span style="color: #
<span style="color: #
* 函数功能:使用私钥进行加密
<span style="color: #
* 参数含义:m表示要加密的明文
<span style="color: #
<span style="color: #
public BigInteger encryptByPrivate(BigInteger m) {
<span style="color: #
return decryptByPrivate(m);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:使用公钥进行解密
<span style="color: #
* 参数含义:c表示要解密的密文
<span style="color: #
<span style="color: #
public BigInteger decryptByPublic(BigInteger c) {
<span style="color: #
return encryptByPublic(c);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:从一个欧拉数中生成公钥、私钥指数
<span style="color: #
* 参数含义:eul表示提供的欧拉数
<span style="color: #
<span style="color: #
private void createExponent(BigInteger eul) {
<span style="color: #
// TODO Auto-generated method stub
<span style="color: #
e = new BigInteger("65537");
<span style="color: #
d = e.modInverse(eul);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:输出RSA相关数据
<span style="color: #
<span style="color: #
public void print() {
<span style="color: #
System.out.println("n: " + n);
<span style="color: #
System.out.println("p: " + p);
<span style="color: #
System.out.println("q: " + q);
<span style="color: #
System.out.println("e: " + e);
<span style="color: #
System.out.println("d: " + d);
<span style="color: #
<span style="color: # }
&&& EncryptDecrypt.java代码如下。
1 import java.math.BigI
2 import java.util.S
4 public class EncryptDecrypt {
private RSA rsa = new RSA();
public Scanner in = new Scanner(System.in);
* 函数功能:菜单显示
public void menu() {
System.out.println("**********Welcome to use RSA encoder**********");
System.out.println("
e: encrypt 加密
System.out.println("
d: decrypt 解密
System.out.println("
System.out.println("
System.out.println("
System.out.println("input your choice:");
* 函数功能:加密运算
public boolean encrypt() {
System.out.println("输入10进制数据:");
System.out.print("&");
String str = in.next();
if (str==null || str.isEmpty() || !islegal(str))
return false;
BigInteger m = new BigInteger(str);
long start = System.currentTimeMillis();
BigInteger c = rsa.encryptByPublic(m);
long finish = System.currentTimeMillis();
System.out.println("用时:" + (finish-start) + "ms.");
System.out.println("明文: " + m);
System.out.println("密文: " + c);
return true;
* 函数功能:解密运算
public boolean decrypt() {
System.out.println("输入10进制数据:");
System.out.print("&");
String str = in.next();
if (str==null || str.isEmpty() || !islegal(str))
return false;
BigInteger c = new BigInteger(str);
long start = System.currentTimeMillis();
BigInteger m = rsa.decryptByPrivate(c);
long finish = System.currentTimeMillis();
System.out.println("用时:" + (finish-start) + "ms.");
System.out.println("密文: " + c);
System.out.println("明文: " + m);
return true;
* 函数功能:输出RSA相关信息
public void print() {
rsa.print();
* 函数功能:重置RSA相关信息
public void reset() {
System.out.print("输入密钥长度: ");
int len = in.nextInt();
load(len&&1);
* 函数功能:根据给定位数len加载rsa
private void load(int len) {
// TODO Auto-generated method stub
System.out.println("初始化...");
long start = System.currentTimeMillis();
rsa.init(len);
long finish = System.currentTimeMillis();
System.out.println("初始化完成.");
System.out.println("用时:" + (finish-start) + "ms.");
* 函数功能:判断输入字符串str是否合法
* 参数含义:str代表输入的字符串
private boolean islegal(String str) {
// TODO Auto-generated method stub
for (int i = 0; i & str.length(); i++) {
char ch = str.charAt(i);
if (!Character.isDigit(ch)) {
return false;
<span style="color: #0
return true;
<span style="color: #1
<span style="color: #2 }
&&& Main.java代码如下。
1 public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
EncryptDecrypt encryptDecrypt = new EncryptDecrypt();
encryptDecrypt.reset();
encryptDecrypt.menu();
<span style="color: #
System.out.print("&");
<span style="color: #
String str = encryptDecrypt.in.next();
<span style="color: #
if (str==null || str.isEmpty()) {
<span style="color: #
System.out.println("输入错误,请重新输入!");
<span style="color: #
<span style="color: #
<span style="color: #
char ch = str.charAt(0);
<span style="color: #
switch(ch) {
<span style="color: #
<span style="color: #
<span style="color: #
if (!encryptDecrypt.encrypt()) {
<span style="color: #
System.out.println("加密失败,请重试!");
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
if (!encryptDecrypt.decrypt()) {
<span style="color: #
System.out.println("解密失败,请重试!");
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encryptDecrypt.print();
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encryptDecrypt.reset();
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encryptDecrypt.in.close();
<span style="color: #
System.exit(0);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
} while (true);
<span style="color: #
<span style="color: #
<span style="color: # }}
上课时没注意老师讲有理数的乘方，计算惠计算，就是分不出得数是负是正，有什么好的方法
我有更好的答案
当底数为负数时，奇数个负数相乘的积是负数，偶数个负数相乘的积是正数，即负数的奇数次幂是负数，负数的偶数次幂是正数。比如：（-2）^3=(-2)x(-2)x(-2)= -8
采纳率：59%
来自团队：
负数的偶次方是正数，奇次方是负数。正数的任何次方都是正数。0的任何次方都是0
指数为负数，得数的正负与底数相同。指数为正数，且为偶数时，得数为正；若为奇数，得数正负与底数相同。
为您推荐：
其他类似问题
有理数的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。RSA加密算法 C++实现 - Silenceneo - 博客园
Talk is cheap. Show me the code.
&&& 上信息安全课，老师布置了几个大作业，其中一个为RSA加密算法的实现，不能用Java写。出于兴趣，决定尝试。完成之后，为了便于查找，于是写下这篇文章，以备后续查看。也供大家一起学习，一起进步。
1、预备知识
1.1 快速幂算法
&&& 顾名思义，快速幂就是快速算底数的$n$次幂。其时间复杂度为${\rm{O(log n)}}$，与朴素的$O\left( n \right)$相比，效率有了极大的提高。具体可以参考百度百科：。
1.2 扩展欧几里得算法
&&& 扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式
\[ax{\rm{ }} + {\rm{ }}by{\rm{ }} = {\rm{ }}gcd\left( {a,b} \right).\]
&&& 如果$a$是负数，可以把问题转化成
&&& $\left| a \right|\left( { - x} \right){\rm{ }} + {\rm{ }}by{\rm{ }} = {\rm{ }}gcd\left( {\left| a \right|,b} \right)$（$\left| a \right|$为a的绝对值），然后令$x\prime {\rm{ }} = {\rm{ }}\left( { - x} \right)$。具体可以参考维基百科：。
1.3 米勒-拉宾素性检验算法
&&& 要测试${\rm{N}}$是否为素数，首先将${\rm{N - 1}}$分解为${2^s}d$。在每次测试开始时，先随机选一个介于 [ 1 , N - 1 ] {\displaystyle [1,N-1]} $[1,N - 1]$的整数$a$，之后如果对所有的$r \in [0,s - 1]$，若${a^d}\bmod N \ne 1$且 a 2 r d mod N ≠ - 1 {\displaystyle a^{2^{r}d}\mod N\neq -1} ${a^{{2^r}d}}\bmod N \ne& - 1$，则$N$是合数。否则，$N$有$3/4$的概率为素数。
&&& 构成该算法的思想是，如果${a^d} \ne 1\left( {{\rm{mod n}}} \right)$以及$n = 1{\rm{ }} + {\rm{ }}{2^s}d$是素数，则值序列
\[{a^d}mod n,{a^{2d}}mod n,{a^{4d}}mod n, \ldots ,{a^{{2^s}d}}mod n\]
&&& 将以$1$结束，而且在头一个$1$的前边的值将是$n-1$(当$p$是素数时，对于${y^2} \equiv 1\left( {mod p} \right)$，仅有的解是$y \equiv& \pm 1\left( {mod p} \right)$，因为$\left( {y + 1} \right)\left( {y - 1} \right)$必须是$p$的倍数)。注意，如果在该序列中出现了$n-1$，则该序列中的下一个值一定是$1$,因为${\left( {n-1} \right)^2} \equiv {n^2}-2n + 1 \equiv 1\left( {mod n} \right)$。具体可以参考维基百科：。
1.4 RSA加密算法
1.4.1 公钥与私钥的产生
&&& 假设Alice想要通过一个不可靠的媒体接收Bob的一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥：
&&& 1、随意选择两个大的质数$p$和$q$，$p$不等于$q$，计算$N = pq$。
&&& 2、根据欧拉函数，求得$r = \varphi (N) = \varphi (p)\varphi (q) = (p - 1)(q - 1)$。
&&& 3、选择一个小于$r$的整数$e$，使$e$与$r$互质。并求得$e$关于$r$的模反元素，命名为$d$(求$d$令$ed \equiv 1(\bmod \;r)$）。(模反元素存在，当且仅当$e$与$r$互质）
&&& 4、将$p$和$q$的记录销毁。
&&& $\left( {N,e} \right)$是公钥，$\left( {N,d} \right)$是私钥。Alice将她的公钥$\left( {N,e} \right)$传给Bob，而将她的私钥$\left( {N,d} \right)$藏起来。
&&& 假设Bob想给Alice送一个消息$m$，他知道Alice产生的$N$和$e$。他使用起先与Alice约好的格式将$m$转换为一个小于$N$，且与$N$互质的整数$n$，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为$n$。用下面这个公式他可以将$n$加密为$c$：
\[{n^e} \equiv c({\rm{mod\;}}N)\]
&&& 计算$c$并不复杂。Bob算出$c$后就可以将它传递给Alice。
&&& Alice得到Bob的消息$c$后就可以利用她的密钥$d$来解码。她可以用以下这个公式来将$c$转换为$n$：
\[{c^d} \equiv n({\rm{mod\;}}N)\]
&&& 得到$n$后，她可以将原来的信息$m$重新复原。
&&& 解码的原理是
\[{c^d} \equiv {n^{ed}}({\rm{mod}}\:N)\]
&&& 已知$ed \equiv 1(\bmod \;r)$，即$ed = 1 + h\varphi (N)$。由欧拉定理得：
\[{n^{ed}} = {n^{1 + h\varphi (N)}} = n{\left( {{n^{\varphi (N)}}} \right)^h} \equiv n{(1)^h}(\bmod \;N) \equiv n(\bmod \;N)\]
&&& RSA也可用作数字签名。具体可以参考维基百科：。
2、模块设计
2.1 BigInteger类
&&& 因为该加密算法涉及的数可能很大，而C++中并没有像Java一样，内置大整数类BigInteger，故需自己实现，我的实现大概是模仿Java的BigInteger设计的。
&&& 该模块包含两个文件：BigInteger.h和BigInteger.cpp。代码如下所示。
&&& BigInteger.h代码如下。
: BigInteger.h
: -22.11.39
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #ifndef __BIGINTEGER_H__
10 #define __BIGINTEGER_H__
12 #include &string&
13 #include &vector&
14 #include &ostream&
15 class BigInteger {
16 public:
typedef long long long_t;
typedef unsigned base_t;
BigInteger(): is_negative(false) { data.push_back(<span style="color: #); }// 默认为0
BigInteger(const BigInteger &);
// 利用给定的大整数初始化
BigInteger(const std::string &);// 利用给定的十六进制字符串初始化
BigInteger(const long_t &);
// 利用给定的long_t类型数据初始化
~BigInteger() {}
BigInteger add(const BigInteger &);
// 大整数加法
BigInteger subtract(const BigInteger &);// 大整数减法
BigInteger multiply(const BigInteger &) const;// 大整数乘法
BigInteger divide(const BigInteger &);
// 大整数整除
BigInteger remainder(const BigInteger &);
// 大整数取余
BigInteger mod(const BigInteger &);
// 大整数取模
BigInteger divideAndRemainder(const BigInteger &, BigInteger &);// 大整数整除和取余
BigInteger pow(const BigInteger &);
// 大整数幂乘
BigInteger modPow(const BigInteger &, const BigInteger &) const;// 大整数幂模运算
BigInteger modInverse(const BigInteger &);// 用扩展欧几里得算法求乘法逆元
BigInteger shiftLeft(const unsigned);
// 移位运算,左移
BigInteger shiftRight(const unsigned);
// 移位运算,右移
int compareTo(const BigInteger &) const;// 比较运算
bool equals(const BigInteger &) const;// 判断是否等于给定数
static BigInteger valueOf(const long_t &);// 将给定数转换为大整数并返回
std::string toString() const;
// 将大整数转换为十六进制字符串
BigInteger abs() const;
// 求大整数的绝对值
44 protected:
// 以下运算符重载函数主要用于像基本类型一样使用大整数类型
friend BigInteger operator + (const BigInteger &, const BigInteger &);
friend BigInteger operator - (const BigInteger &, const BigInteger &);
friend BigInteger operator * (const BigInteger &, const BigInteger &);
friend BigInteger operator / (const BigInteger &, const BigInteger &);
friend BigInteger operator % (const BigInteger &, const BigInteger &);
friend bool operator & (const BigInteger &, const BigInteger &);
friend bool operator & (const BigInteger &, const BigInteger &);
friend bool operator == (const BigInteger &, const BigInteger &);
friend bool operator &= (const BigInteger &, const BigInteger &);
friend bool operator &= (const BigInteger &, const BigInteger &);
friend bool operator != (const BigInteger &, const BigInteger &);
// 重载版本,使其能用于long_t类型
friend BigInteger operator + (const BigInteger &, const long_t &);
friend BigInteger operator - (const BigInteger &, const long_t &);
friend BigInteger operator * (const BigInteger &, const long_t &);
friend BigInteger operator / (const BigInteger &, const long_t &);
friend BigInteger operator % (const BigInteger &, const long_t &);
friend bool operator & (const BigInteger &, const long_t &);
friend bool operator & (const BigInteger &, const long_t &);
friend bool operator == (const BigInteger &, const long_t &);
friend bool operator &= (const BigInteger &, const long_t &);
friend bool operator &= (const BigInteger &, const long_t &);
friend bool operator != (const BigInteger &, const long_t &);
friend std::ostream & operator && (std::ostream &, const BigInteger &);
BigInteger operator = (const std::string & str) { return (*this) = BigInteger(str); }
BigInteger operator = (const long_t & num) { return (*this) = BigInteger(num); }
74 private:
BigInteger trim();
// 去掉高位无用的0
int hexToNum(char);
// 十六进制字符转换为十进制数
77 public:
static const int base_bit = <span style="color: #;
// 2^5=32,大整数每位存储的二进制位数
static const int base_char = <span style="color: #;
// 组成大整数的一位需要的十六进制位数
static const int base_int = <span style="color: #;
// 大整数一位对应的二进制位数
static const int base_num = <span style="color: #xffffffff;// 截取低位的辅助
static const int base_temp = <span style="color: #x1f;
// 截取模32的余数的辅助
static const BigInteger ZERO;
// 大整数常量0
static const BigInteger ONE;
// 大整数常量1
static const BigInteger TWO;
// 大整数常量2
static const BigInteger TEN;
// 大整数常量10
87 private:
bool is_// 是否为负数
std::vector&base_t&// 按位数据存储,高位在后
class bit {
// 便于大整数运算的二进制处理类
bit(const BigInteger &);// 根据大整数初始化
size_t size() { return }
// 返回大整数对应的二进制位数
bool at(size_t);
// 返回第i位二进制是否为1
std::vector&base_t& bit_
// 二进制数据存储,每一个元素对应32位二进制
// 二进制的总位数
<span style="color: #0
friend class RSA;
// RSA为其友元类
<span style="color: #1 };
<span style="color: #2
<span style="color: #3 #endif // __BIGINTEGER_H__
&&& BigInteger.cpp代码如下。
: BigInteger.cpp
: -22.16.42
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &algorithm&
10 #include &cassert&
11 #include &cctype&
12 #include "BigInteger.h"
14 // 以下表示为静态常量赋值
15 const BigInteger BigInteger::ZERO = BigInteger(<span style="color: #);
16 const BigInteger BigInteger::ONE = BigInteger(<span style="color: #);
17 const BigInteger BigInteger::TWO = BigInteger(<span style="color: #);
18 const BigInteger BigInteger::TEN = BigInteger(<span style="color: #);
* 函数功能:根据给定的大整数构造一个新的大整数
* 参数含义:val代表给定的大整数
24 BigInteger::BigInteger(const BigInteger & val) {
* 函数功能:根据给定的十六进制字符串数据构造一个大整数
* 参数含义:str代表给定的数据
32 BigInteger::BigInteger(const std::string & str): is_negative(false) {
std::string t(str);
if (t.size() && t.at(<span style="color: #)=='-') {
if (t.size() & <span style="color: #)
is_negative = true;
t = t.substr(<span style="color: #);
int cnt = (<span style="color: #-(t.size()%<span style="color: #))%<span style="color: #;// 数的长度不是8的倍数,补足0
std::string
for (int i=<span style="color: #; i& ++i)
temp.push_back('<span style="color: #');
t = temp+t;
for (size_t i=<span style="color: #; i&t.size(); i+=base_char) {
base_t sum = <span style="color: #;
for (int j=<span style="color: #; j&base_ ++j) {
// 8位十六进制组成大整数的一位
char ch = t[i+j];
int num = hexToNum(ch);
sum = ((sum&&<span style="color: #) | (num));
data.push_back(sum);
reverse(data.begin(), data.end());// 高位在后
*this = trim();// 去除高位的0
* 函数功能:根据给定的long_t类型数据构造一个大整数
* 参数含义:num代表给定的数据
64 BigInteger::BigInteger(const long_t & num): is_negative(false) {
long_t t =
if (t & <span style="color: #) {
is_negative = true;
base_t temp = (t&base_num);
// 每次截取低32位
data.push_back(temp);
t &&= base_
} while (t);
* 函数功能:大整数加法运算
* 参数含义:val代表加数
81 BigInteger BigInteger::add(const BigInteger & val) {
BigInteger ans(*this);
if (ans.is_negative == val.is_negative) {// 同号
int len = val.data.size()-ans.data.size();
while ((len--) & <span style="color: #)
// 被加数位数少,高位补0
ans.data.push_back(<span style="color: #);
int carry = <span style="color: #;
for (size_t i=<span style="color: #; i&val.data.size(); ++i) {
base_t temp = ans.data[i];
ans.data[i] += val.data[i]+
// 无符号数相加,超出取其余数
// 进位:一种是有无进位都超出,一种是有进位才超出(比如十进制相加,9+9+1,得9,9+0+0,得9)
carry = (temp&ans.data[i] ? <span style="color: # : (temp&(temp+val.data[i]) ? <span style="color: # : <span style="color: #));
for (size_t i=val.data.size(); i&ans.data.size() && carry!=<span style="color: #; ++i) {// 还有进位
base_t temp = ans.data[i];
ans.data[i] +=
<span style="color: #0
carry = temp & ans.data[i];
<span style="color: #1
<span style="color: #2
<span style="color: #3
if (carry)
// 还有进位
<span style="color: #4
ans.data.push_back(carry);
<span style="color: #5
<span style="color: #6
<span style="color: #7
BigInteger a = abs();
<span style="color: #8
BigInteger b = val.abs();
<span style="color: #9
int flag = a.compareTo(b);
<span style="color: #0
// 绝对值相等,则结果为0,否则用绝对值大的减去小的,符号随绝对值大的
<span style="color: #1
if (flag == -<span style="color: #) {
<span style="color: #2
ans = b.subtract(a);
<span style="color: #3
ans.is_negative = val.is_
<span style="color: #4
<span style="color: #5
else if (flag == <span style="color: #)
<span style="color: #6
ans = ZERO;
<span style="color: #7
<span style="color: #8
ans = a.subtract(b);
<span style="color: #9
ans.is_negative = is_
<span style="color: #0
<span style="color: #1
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:大整数减法运算
<span style="color: #7
* 参数含义:val代表减数
<span style="color: #8
<span style="color: #9 BigInteger BigInteger::subtract(const BigInteger & val) {
<span style="color: #0
BigInteger ans(*this);
<span style="color: #1
BigInteger a = abs();
<span style="color: #2
BigInteger b = val.abs();
<span style="color: #3
if (ans.is_negative == val.is_negative) {// 同号
<span style="color: #4
int flag = a.compareTo(b);
<span style="color: #5
if (flag == <span style="color: #) {// a的绝对值大于b的绝对值,直接减
<span style="color: #6
int borrow = <span style="color: #;
<span style="color: #7
// 大数减小数
<span style="color: #8
for (size_t i=<span style="color: #; i&val.data.size(); ++i) {
<span style="color: #9
base_t temp = ans.data[i];
<span style="color: #0
ans.data[i] -= val.data[i]+
<span style="color: #1
// 借位:一种是有无借位都超出,另一种是有借位才超出(比如十进制相减,9-0-0,得9,9-9-1,得9)
<span style="color: #2
borrow = temp&ans.data[i] ? <span style="color: # : (temp-borrow&val.data[i] ? <span style="color: # : <span style="color: #);
<span style="color: #3
<span style="color: #4
for (size_t i=val.data.size(); i&ans.data.size() && borrow!=<span style="color: #; ++i) {// 还有借位
<span style="color: #5
base_t temp = ans.data[i];
<span style="color: #6
ans.data[i] -=
<span style="color: #7
borrow = temp & (base_t)
<span style="color: #8
<span style="color: #9
ans = ans.trim();// 去掉高位多余的0
<span style="color: #0
<span style="color: #1
else if (flag == <span style="color: #)
<span style="color: #2
ans = ZERO;
<span style="color: #3
else {// a的绝对值小于b的绝对值
<span style="color: #4
ans = b.subtract(a);
<span style="color: #5
ans.is_negative = !is_
<span style="color: #6
<span style="color: #7
<span style="color: #8
<span style="color: #9
ans = a.add(b);
// 转换为加法
<span style="color: #0
ans.is_negative = is_
<span style="color: #1
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:大整数乘法运算
<span style="color: #7
* 参数含义:val代表乘数
<span style="color: #8
<span style="color: #9 BigInteger BigInteger::multiply(const BigInteger & val) const {
<span style="color: #0
if (equals(ZERO) || val.equals(ZERO))
<span style="color: #1
return ZERO;
<span style="color: #2
// 将位数少的作为乘数
<span style="color: #3
const BigInteger & big = data.size()&val.data.size() ? (*this) :
<span style="color: #4
const BigInteger & small = (&big)==(this) ? val : (*this);
<span style="color: #5
<span style="color: #6
<span style="color: #7
bit t(small);
// 转换为二进制进行运算
<span style="color: #8
<span style="color: #9
for (int i=t.size()-<span style="color: #; i&=<span style="color: #; --i)
<span style="color: #0
if (t.at(i)) {
<span style="color: #1
BigInteger temp(big);
<span style="color: #2
temp.is_negative = false;
<span style="color: #3
temp = temp.shiftLeft(i);
// 移位对齐
<span style="color: #4
ans = ans.add(temp);
<span style="color: #5
<span style="color: #6
ans.is_negative = !(is_negative == val.is_negative);
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:大整数整除运算
<span style="color: #2
* 参数含义:val代表除数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::divide(const BigInteger & val) {
<span style="color: #5
<span style="color: #6
BigInteger ans = divideAndRemainder(val, temp);
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:大整数取余运算
<span style="color: #2
* 参数含义:val代表除数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::remainder(const BigInteger & val) {
<span style="color: #5
<span style="color: #6
divideAndRemainder(val, ans);
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:大整数取模运算(不同于取余,该函数总是返回正余数)
<span style="color: #2
* 参数含义:m代表模数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::mod(const BigInteger & m) {
<span style="color: #5
BigInteger ans = remainder(m);
<span style="color: #6
if (ans.is_negative)
<span style="color: #7
ans = ans.add(m);
<span style="color: #8
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 /**
<span style="color: #2
* 函数功能:大整数整除运算和取余运算,整除结果直接返回,取余结果由m传回
<span style="color: #3
* 参数含义:val表示除数,m表示取余结果
<span style="color: #4
<span style="color: #5 BigInteger BigInteger::divideAndRemainder(const BigInteger & val, BigInteger & m) {
<span style="color: #6
assert(!val.equals(ZERO));
<span style="color: #7
BigInteger a = abs();
<span style="color: #8
BigInteger b = val.abs();
<span style="color: #9
int flag = a.compareTo(b);
<span style="color: #0
if (flag == <span style="color: #)// 绝对值相等
<span style="color: #1
return (is_negative==val.is_negative) ? BigInteger(<span style="color: #) : BigInteger(-<span style="color: #);
<span style="color: #2
if (flag == -<span style="color: #) {
<span style="color: #3
m = *this;
<span style="color: #4
return ZERO;
<span style="color: #5
<span style="color: #6
<span style="color: #7
<span style="color: #8
bit bit_b(b);
<span style="color: #9
// 位数对齐
<span style="color: #0
while (true) {// a的绝对值大于b的绝对值
<span style="color: #1
bit bit_a(a);
<span style="color: #2
int len = bit_a.size()-bit_b.size();
<span style="color: #3
<span style="color: #4
// 找到移位
<span style="color: #5
while (len &= <span style="color: #) {
<span style="color: #6
temp = b.shiftLeft(len);
<span style="color: #7
if (temp.compareTo(a) != <span style="color: #)// 找到最大的左移位数使得当前的a大于等于b
<span style="color: #8
<span style="color: #9
<span style="color: #0
<span style="color: #1
if (len & <span style="color: #)
// 当前的a小于b了
<span style="color: #2
<span style="color: #3
base_t num = <span style="color: #;
<span style="color: #4
while (temp.compareTo(a) != <span style="color: #) {
<span style="color: #5
a = a.subtract(temp);
<span style="color: #6
// 统计当前的a最多大于等于几个移位后的b
<span style="color: #7
<span style="color: #8
temp = BigInteger(num);
<span style="color: #9
<span style="color: #0
temp = temp.shiftLeft(len);// 移位后表明当前的a是b的几倍
<span style="color: #1
ans = ans.add(temp);
<span style="color: #2
<span style="color: #3
ans.is_negative = !(is_negative==val.is_negative);
<span style="color: #4
m.data = a.
<span style="color: #5
m.is_negative = is_
<span style="color: #6
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:大整数幂乘运算
<span style="color: #1
* 参数含义:exponent代表指数
<span style="color: #2
<span style="color: #3 BigInteger BigInteger::pow(const BigInteger & exponent) {
<span style="color: #4
BigInteger ans(<span style="color: #);
<span style="color: #5
bit t(exponent);
// 转化为二进制,快速求幂
<span style="color: #6
for (int i=t.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #7
ans = ans.multiply(ans);
<span style="color: #8
if (t.at(i))
<span style="color: #9
ans = multiply(ans);// 从高位开始,位权累加效应
<span style="color: #0
<span style="color: #1
<span style="color: #2 }
<span style="color: #3
<span style="color: #4 /**
<span style="color: #5
* 函数功能:大整数模幂运算
<span style="color: #6
* 参数含义:exponent代表指数,m代表模数
<span style="color: #7
<span style="color: #8 BigInteger BigInteger::modPow(const BigInteger & exponent, const BigInteger & m) const {
<span style="color: #9
assert(!m.equals(ZERO));
<span style="color: #0
BigInteger ans(<span style="color: #);
<span style="color: #1
bit t(exponent);
<span style="color: #2
for (int i=t.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #3
ans = ans.multiply(ans).mod(m);
<span style="color: #4
if (t.at(i))
<span style="color: #5
ans = multiply(ans).mod(m);
<span style="color: #6
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:扩展欧几里得算法求乘法逆元
<span style="color: #2
* 参数含义:m代表求逆元时的模数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::modInverse(const BigInteger & m) {
<span style="color: #5
assert(!is_negative);
// 当前大整数为正数
<span style="color: #6
assert(!m.is_negative);
// m为正数
<span style="color: #7
if (equals(ZERO) || m.equals(ZERO))
<span style="color: #8
return ZERO;
// 有一个数为0,就不存在乘法逆元
<span style="color: #9
BigInteger a[<span style="color: #], b[<span style="color: #], t[<span style="color: #];
<span style="color: #0
// 以下进行初等变换
<span style="color: #1
a[<span style="color: #] = <span style="color: #; a[<span style="color: #] = <span style="color: #; a[<span style="color: #] = *this;
<span style="color: #2
b[<span style="color: #] = <span style="color: #; b[<span style="color: #] = <span style="color: #; b[<span style="color: #] =
<span style="color: #3
<span style="color: #4
for (t[<span style="color: #]=a[<span style="color: #].mod(b[<span style="color: #]); !t[<span style="color: #].equals(ZERO); t[<span style="color: #]=a[<span style="color: #].mod(b[<span style="color: #])) {
<span style="color: #5
BigInteger temp = a[<span style="color: #].divide(b[<span style="color: #]);
<span style="color: #6
for (int i=<span style="color: #; i&<span style="color: #; ++i) {
<span style="color: #7
t[i] = a[i].subtract(temp.multiply(b[i]));// 不超过一次a[2]-temp*b[2]就变为大数减小数
<span style="color: #8
a[i] = b[i];
<span style="color: #9
b[i] = t[i];
<span style="color: #0
<span style="color: #1
<span style="color: #2
if (b[<span style="color: #].equals(ONE)) {// 最大公约数为1,存在乘法逆元
<span style="color: #3
if (b[<span style="color: #].is_negative)// 逆元为负数
<span style="color: #4
b[<span style="color: #] = b[<span style="color: #].add(m);// 变为正数,使其在m的剩余集中
<span style="color: #5
return b[<span style="color: #];
<span style="color: #6
<span style="color: #7
return ZERO;// 最大公约数不为1,无乘法逆元
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 /**
<span style="color: #1
* 函数功能:移位运算,左移
<span style="color: #2
* 参数含义:len代表移位的位数
<span style="color: #3
<span style="color: #4 BigInteger BigInteger::shiftLeft(const unsigned len) {
<span style="color: #5
int index = len&&base_
// 大整数每一位需要移动多少位
<span style="color: #6
int shift = len&base_
// 还剩下多少位
<span style="color: #7
BigInteger ans(*this);
<span style="color: #8
<span style="color: #9
int inc = (shift==<span style="color: #) ? index : index+<span style="color: #;// 有多余的位要多开大整数的一位
<span style="color: #0
for (int i=<span style="color: #; i& ++i)
<span style="color: #1
ans.data.push_back(<span style="color: #);
// 高位补0
<span style="color: #2
<span style="color: #3
if (index) {
<span style="color: #4
inc = (shift==<span style="color: #) ? <span style="color: # : <span style="color: #;// 有多余的位要预留一位
<span style="color: #5
for (int i=ans.data.size()- i&= --i)
<span style="color: #6
ans.data[i] = ans.data[i-index];
<span style="color: #7
for (int i=<span style="color: #; i& ++i)
<span style="color: #8
ans.data[i] = <span style="color: #;
<span style="color: #9
<span style="color: #0
if (shift) {
<span style="color: #1
base_t t = base_
<span style="color: #2
t &&= base_int-
// 用于截取高位
<span style="color: #3
<span style="color: #4
base_t temp = <span style="color: #;
<span style="color: #5
for (size_t i=<span style="color: #; i&ans.data.size(); ++i) {
<span style="color: #6
base_t tmp = ans.data[i];
<span style="color: #7
ans.data[i] = (tmp&&shift) |// 左移后加上大整数低位的高位
<span style="color: #8
temp = (tmp&t)&&(base_int-shift);// 获取该大整数位的高位
<span style="color: #9
<span style="color: #0
<span style="color: #1
ans = ans.trim();
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:移位运算,右移
<span style="color: #7
* 参数含义:len代表移位的位数
<span style="color: #8
<span style="color: #9 BigInteger BigInteger::shiftRight(const unsigned len) {
<span style="color: #0
bit val(*this);
<span style="color: #1
if (len &= val.size())// 当前大整数位数小于等于移位位数,返回0
<span style="color: #2
return ZERO;
<span style="color: #3
int index = len&&base_// 大整数每一位需要移动多少位
<span style="color: #4
int shift = len&base_// 还剩下多少位
<span style="color: #5
BigInteger ans(*this);
<span style="color: #6
<span style="color: #7
if (index) {
<span style="color: #8
for (int i=<span style="color: #; i& ++i)
<span style="color: #9
ans.data[i] = ans.data[i+index];
<span style="color: #0
for (int i=<span style="color: #; i& ++i)
<span style="color: #1
ans.data.pop_back();
// 高位删除
<span style="color: #2
<span style="color: #3
if (shift) {
<span style="color: #4
base_t t = base_
<span style="color: #5
t &&= base_int-
// 用于截取低位
<span style="color: #6
<span style="color: #7
base_t temp = <span style="color: #;
<span style="color: #8
for (int i=ans.data.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #9
base_t tmp = ans.data[i];
<span style="color: #0
ans.data[i] = (tmp&&shift) |// 右移后加上大整数高位的低位
<span style="color: #1
temp = (tmp&t)&&(base_int-shift);// 获取该大整数位的低位
<span style="color: #2
<span style="color: #3
<span style="color: #4
ans = ans.trim();
<span style="color: #5
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 /**
<span style="color: #9
* 函数功能:大整数比较函数,-1表示本大整数要小,0表示相等,1表示本大整数要大
<span style="color: #0
* 参数含义:val代表要与之比较的大整数
<span style="color: #1
<span style="color: #2 int BigInteger::compareTo(const BigInteger & val) const {
<span style="color: #3
if (is_negative != val.is_negative) {// 符号不同,负数必小
<span style="color: #4
if (is_negative == true)
<span style="color: #5
return -<span style="color: #;
<span style="color: #6
return <span style="color: #;
<span style="color: #7
<span style="color: #8
int flag = <span style="color: #;
<span style="color: #9
if (data.size() & val.data.size())// 位数较小
<span style="color: #0
flag = -<span style="color: #;
<span style="color: #1
else if (data.size() & val.data.size())// 位数较大
<span style="color: #2
flag = <span style="color: #;
<span style="color: #3
// 位数相等,从高位开始一一比较
<span style="color: #4
for (std::vector&base_t&::const_reverse_iterator it=data.rbegin(), ite=val.data.rbegin(); it!=data.rend(); ++it, ++ite)
<span style="color: #5
if ((*it) != (*ite)) {
<span style="color: #6
flag = (*it)&(*ite) ? -<span style="color: # : <span style="color: #;
// 高位小,则小
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0
if (is_negative)
// 如为负数,小的反而大
<span style="color: #1
<span style="color: #2
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 /**
<span style="color: #6
* 函数功能:大整数是否相等函数
<span style="color: #7
* 参数含义:val表示要与之比较的大整数
<span style="color: #8
<span style="color: #9 bool BigInteger::equals(const BigInteger & val) const {
<span style="color: #0
return (is_negative==val.is_negative) && (data==val.data);// 符号和数据都要相等
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:将一个long_t类型的数据转换为大整数并返回
<span style="color: #5
* 参数含义:num表示给定的数
<span style="color: #6
<span style="color: #7 BigInteger BigInteger::valueOf(const long_t & num) {
<span style="color: #8
return BigInteger(num);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 /**
<span style="color: #2
* 函数功能:将大整数转换为十六进制字符串并返回
<span style="color: #3
<span style="color: #4 std::string BigInteger::toString() const {
<span style="color: #5
std::string
<span style="color: #6
base_t t = base_
<span style="color: #7
t &&= base_int-<span style="color: #;
// 用于截取高4位
<span style="color: #8
for (int i=data.size()-<span style="color: #; i&=<span style="color: #; --i) {
<span style="color: #9
base_t temp = data[i];
<span style="color: #0
for (int j=<span style="color: #; j&base_ ++j) {
<span style="color: #1
base_t num = t&// 每次截取高4位
<span style="color: #2
num &&= base_int-<span style="color: #;
// 将高4位移到低4位
<span style="color: #3
temp &&= <span style="color: #;
<span style="color: #4
if (num & <span style="color: #)
<span style="color: #5
ans.push_back((char)('<span style="color: #'+num));
<span style="color: #6
<span style="color: #7
ans.push_back((char)('A'+num-<span style="color: #));
<span style="color: #8
<span style="color: #9
<span style="color: #0
while (ans.size()&<span style="color: # && ans.at(<span style="color: #)=='<span style="color: #')// 去掉高位无用的0
<span style="color: #1
ans = ans.substr(<span style="color: #);
<span style="color: #2
if (ans.empty())
// 空串说明为0
<span style="color: #3
ans.push_back('<span style="color: #');
<span style="color: #4
if (is_negative)
// 为负数加上负号
<span style="color: #5
ans = "-"+
<span style="color: #6
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:返回大整数的绝对值
<span style="color: #1
<span style="color: #2 BigInteger BigInteger::abs() const {
<span style="color: #3
<span style="color: #4
ans.data =// 只复制数据,符号默认为正
<span style="color: #5
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 // 以下运算符重载函数主要是为了使得能使用
<span style="color: #9 // 大整数类型像使用基本类型一样,不一一介绍
<span style="color: #0 BigInteger operator + (const BigInteger & a, const BigInteger & b) {
<span style="color: #1
BigInteger t(a);
<span style="color: #2
return t.add(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 BigInteger operator - (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
BigInteger t(a);
<span style="color: #7
return t.subtract(b);
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 BigInteger operator * (const BigInteger & a, const BigInteger & b) {
<span style="color: #1
BigInteger t(a);
<span style="color: #2
return t.multiply(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 BigInteger operator / (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
BigInteger t(a);
<span style="color: #7
return t.divide(b);
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 BigInteger operator % (const BigInteger & a, const BigInteger & b) {
<span style="color: #1
BigInteger t(a);
<span style="color: #2
return t.remainder(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 bool operator & (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
return a.compareTo(b) == -<span style="color: #;
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 bool operator & (const BigInteger & a, const BigInteger & b) {
<span style="color: #0
return b &
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 bool operator == (const BigInteger & a, const BigInteger & b) {
<span style="color: #4
return a.equals(b);
<span style="color: #5 }
<span style="color: #6
<span style="color: #7 bool operator &= (const BigInteger & a, const BigInteger & b) {
<span style="color: #8
return !(a & b);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 bool operator &= (const BigInteger & a, const BigInteger & b) {
<span style="color: #2
return !(a & b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 bool operator != (const BigInteger & a, const BigInteger & b) {
<span style="color: #6
return !(a == b);
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 BigInteger operator + (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #0
return a+BigInteger(b);
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 BigInteger operator - (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #4
return a-BigInteger(b);
<span style="color: #5 }
<span style="color: #6
<span style="color: #7 BigInteger operator * (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #8
return a*BigInteger(b);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 BigInteger operator / (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #2
return a/BigInteger(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 BigInteger operator % (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #6
return a%BigInteger(b);
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 bool operator & (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #0
return a & BigInteger(b);
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 bool operator & (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #4
return a & BigInteger(b);
<span style="color: #5 }
<span style="color: #6
<span style="color: #7 bool operator == (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #8
return a == BigInteger(b);
<span style="color: #9 }
<span style="color: #0
<span style="color: #1 bool operator &= (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #2
return a &= BigInteger(b);
<span style="color: #3 }
<span style="color: #4
<span style="color: #5 bool operator &= (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #6
return a &= BigInteger(b);
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 bool operator != (const BigInteger & a, const BigInteger::long_t & b) {
<span style="color: #0
return a != BigInteger(b);
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 std::ostream & operator && (std::ostream & out, const BigInteger & val) {
<span style="color: #4
out && val.toString();
<span style="color: #5
return out;
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 /**
<span style="color: #9
* 函数功能:创建该大整数的一个副本,去除掉高位无用的0后并返回
<span style="color: #0
<span style="color: #1 BigInteger BigInteger::trim() {
<span style="color: #2
size_t cnt = <span style="color: #;
<span style="color: #3
// 检查高位为0的元素的数量
<span style="color: #4
for (std::vector&base_t&::const_reverse_iterator it=data.rbegin(); it!=data.rend(); ++it) {
<span style="color: #5
if ((*it) == <span style="color: #)
<span style="color: #6
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0
if (cnt == data.size())
// 只有零的情况保留
<span style="color: #1
<span style="color: #2
BigInteger ans(*this);
<span style="color: #3
for (size_t i=<span style="color: #; i& ++i)
<span style="color: #4
ans.data.pop_back();
<span style="color: #5
<span style="color: #6 }
<span style="color: #7
<span style="color: #8 /**
<span style="color: #9
* 函数功能:根据给定的字符确定它所对应的十进制数
<span style="color: #0
* 参数含义:ch代表给定的字符
<span style="color: #1
<span style="color: #2 int BigInteger::hexToNum(char ch) {
<span style="color: #3
int ans = <span style="color: #;
<span style="color: #4
if (isdigit(ch))
<span style="color: #5
ans = ch-'<span style="color: #';
<span style="color: #6
else if (islower(ch))
<span style="color: #7
ans = ch-'a'+<span style="color: #;
<span style="color: #8
<span style="color: #9
ans = ch-'A'+<span style="color: #;
<span style="color: #0
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:根据给定的大整数初始化
<span style="color: #5
* 参数含义:val代表给定的大整数
<span style="color: #6
<span style="color: #7 BigInteger::bit::bit(const BigInteger & val) {
<span style="color: #8
bit_vector = val.
<span style="color: #9
base_t temp = bit_vector[bit_vector.size()-<span style="color: #];// 大整数最高位
<span style="color: #0
length = bit_vector.size()&&base_
// 大整数一位占二进制32位
<span style="color: #1
base_t t = <span style="color: #&&(base_int-<span style="color: #);
// 用于截取一个数的二进制最高位
<span style="color: #2
<span style="color: #3
if (temp == <span style="color: #)
// 大整数最高位为0,减去32
<span style="color: #4
length -= base_
<span style="color: #5
<span style="color: #6
while (!(temp & t)) {// 从高位开始检测大整数的二进制位,为0长度减一
<span style="color: #7
<span style="color: #8
t &&= <span style="color: #;
// 右移一位表示检测下一位
<span style="color: #9
<span style="color: #0
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:检测大整数的第id位二进制位是否为1
<span style="color: #5
* 参数含义:id代表第id位
<span style="color: #6
<span style="color: #7 bool BigInteger::bit::at(size_t id) {
<span style="color: #8
size_t index = id&&base_// 确定其在大整数第几位
<span style="color: #9
size_t shift = id&base_// 确定其在大整数那一位的二进制第几位
<span style="color: #0
base_t t = bit_vector[index];
<span style="color: #1
return (t & (<span style="color: #&&shift));
<span style="color: #2 }
&&& 该类主要实现RSA相关功能，例如加密和解密等。
&&& 该模块也有两个文件：RSA.h和RSA.cpp。代码如下所示。
&&& RSA.h代码如下。
: -22.25.57
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #ifndef __RSA_H__
<span style="color: # #define __RSA_H__
<span style="color: #
<span style="color: # #include &ostream&
<span style="color: # #include "BigInteger.h"
<span style="color: # class RSA {
<span style="color: # public:
<span style="color: #
<span style="color: #
RSA(const unsigned len) { init(len); }
// 利用len初始化对象
<span style="color: #
<span style="color: #
<span style="color: #
void init(const unsigned);// 初始化,产生公私钥对
<span style="color: #
<span style="color: #
BigInteger encryptByPublic(const BigInteger &);
// 公钥加密
<span style="color: #
BigInteger decryptByPrivate(const BigInteger &);// 私钥解密
<span style="color: #
<span style="color: #
// 以下主要用于数字签名
<span style="color: #
BigInteger encryptByPrivate(const BigInteger &);// 私钥加密
<span style="color: #
BigInteger decryptByPublic(const BigInteger &);
// 公钥解密
<span style="color: # protected:
<span style="color: #
friend std::ostream & operator && (std::ostream &, const RSA &);// 输出相关数据
<span style="color: # private:
<span style="color: #
BigInteger createOddNum(unsigned);// 生成一个大奇数,参数为其长度
<span style="color: #
bool isPrime(const BigInteger &, const unsigned);// 判断是否为素数
<span style="color: #
BigInteger createRandomSmaller(const BigInteger &);// 随机创建一个更小的数
<span style="color: #
BigInteger createPrime(unsigned, const unsigned);// 生成一个大素数,参数为其长度
<span style="color: #
void createExponent(const BigInteger &);// 根据提供的欧拉数生成公钥、私钥指数
<span style="color: # public:
<span style="color: #
BigInteger n,// 公钥
<span style="color: # private:
<span style="color: #
BigI// 私钥
<span style="color: #
BigInteger p,// 大素数p和q
<span style="color: #
BigI// n的欧拉函数
<span style="color: # };
<span style="color: #
<span style="color: # #endif // __RSA_H__
&&& RSA.cpp代码如下。
: -22.27.51
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &cassert&
10 #include &sstream&
11 #include &ctime&
12 #include "RSA.h"
* 函数功能:初始化RSA对象的相关信息
* 参数含义:len表示大素数的二进制位数
18 void RSA::init(const unsigned len) {
srand((unsigned)time(NULL));
// 产生大素数p和q
p = createPrime(len, <span style="color: #);// 出错概率为(1/4)^15
q = createPrime(len, <span style="color: #);
// 计算出n
// 计算出n的欧拉函数
eul = (p-<span style="color: #)*(q-<span style="color: #);
// 设置加解密指数e和d
createExponent(eul);
* 函数功能:使用公钥进行加密
* 参数含义:m表示要加密的明文
35 BigInteger RSA::encryptByPublic(const BigInteger & m) {
return m.modPow(e, n);
* 函数功能:使用私钥进行解密
* 参数含义:c表示要解密的密文
43 BigInteger RSA::decryptByPrivate(const BigInteger & c) {
return c.modPow(d, n);
* 函数功能:使用私钥进行加密
* 参数含义:m表示要加密的明文
51 BigInteger RSA::encryptByPrivate(const BigInteger & m) {
return decryptByPrivate(m);
* 函数功能:使用公钥进行解密
* 参数含义:c表示要解密的密文
59 BigInteger RSA::decryptByPublic(const BigInteger & c) {
return encryptByPublic(c);
* 函数功能:输出RSA相关数据
* 参数含义:out表示输出流,rsa表示要输出的RSA对象
67 std::ostream & operator && (std::ostream & out, const RSA & rsa) {
out && "n: " && rsa.n && "\n";
out && "p: " && rsa.p && "\n";
out && "q: " && rsa.q && "\n";
out && "e: " && rsa.e && "\n";
out && "d: " && rsa.d;
return out;
* 函数功能:生成一个长度为len的奇数
* 参数含义:len代表奇数的二进制长度
80 BigInteger RSA::createOddNum(unsigned len) {
static const char hex_table[] = {'<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #', '<span style="color: #',
'<span style="color: #', '<span style="color: #', 'A', 'B', 'C', 'D', 'E', 'F'};
len &&= <span style="color: #;
// 十六进制数据,每位占4位二进制
if (len) {
for (size_t i=<span style="color: #; i&len-<span style="color: #; ++i)
oss && hex_table[rand()%<span style="color: #];
oss && hex_table[<span style="color: #];// 最后一位为奇数
return BigInteger(oss.str());
return BigInteger("F");
* 函数功能:判断一个数是否为素数,采用米勒拉宾大素数检测算法,失误率为(1/4)^k
* 参数含义:num代表要判定的数,k代表测试次数
98 bool RSA::isPrime(const BigInteger & num, const unsigned k) {
assert(num != BigInteger::ZERO);// 测试num是否为0
<span style="color: #0
if (num == BigInteger::ONE)
<span style="color: #1
return false;
// 1不是素数
<span style="color: #2
if (num == BigInteger::TWO)
<span style="color: #3
return true;
// 2是素数
<span style="color: #4
<span style="color: #5
BigInteger t = num-<span style="color: #;
<span style="color: #6
BigInteger::bit b(t);// 二进制数
<span style="color: #7
if (b.at(<span style="color: #) == <span style="color: #)
// 减一之后为奇数,原数为偶数
<span style="color: #8
return false;
<span style="color: #9
// num-1 = 2^s*d
<span style="color: #0
size_t s = <span style="color: #;
// 统计二进制末尾有几个0
<span style="color: #1
BigInteger d(t);
<span style="color: #2
for (size_t i=<span style="color: #; i&b.size(); ++i) {
<span style="color: #3
if (!b.at(i)) {
<span style="color: #4
<span style="color: #5
d = d.shiftRight(<span style="color: #);// 计算出d
<span style="color: #6
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0
<span style="color: #1
for (size_t i=<span style="color: #; i&k; ++i) {// 测试k次
<span style="color: #2
BigInteger a = createRandomSmaller(num);// 生成一个介于[1,num-1]之间的随机数a
<span style="color: #3
BigInteger x = a.modPow(d, num);
<span style="color: #4
if (x == BigInteger::ONE)// 可能为素数
<span style="color: #5
<span style="color: #6
bool ok = true;
<span style="color: #7
// 测试所有0&=j&s,a^(2^j*d) mod num != -1
<span style="color: #8
for (size_t j=<span style="color: #; j&s && ++j) {
<span style="color: #9
if (x == t)
<span style="color: #0
ok = false;
// 有一个相等,可能为素数
<span style="color: #1
x = x.multiply(x).mod(num);
<span style="color: #2
<span style="color: #3
// 确实都不等,一定为合数
<span style="color: #4
return false;
<span style="color: #5
<span style="color: #6
return true;
// 通过所有测试,可能为素数
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:随机生成一个比val小的数
<span style="color: #1
* 参数含义:val代表比较的那个数
<span style="color: #2
<span style="color: #3 BigInteger RSA::createRandomSmaller(const BigInteger & val) {
<span style="color: #4
BigInteger::base_t t = <span style="color: #;
<span style="color: #5
<span style="color: #6
t = rand();
<span style="color: #7
} while (t == <span style="color: #);// 随机生成非0数
<span style="color: #8
<span style="color: #9
BigInteger mod(t);
<span style="color: #0
BigInteger ans = mod%
// 比val要小
<span style="color: #1
if (ans == BigInteger::ZERO)// 必须非零
<span style="color: #2
ans = val-BigInteger::ONE;
<span style="color: #3
<span style="color: #4 }
<span style="color: #5
<span style="color: #6 /**
<span style="color: #7
* 函数功能:生成一个二进制长度为len的大素数
<span style="color: #8
* 参数含义:len代表大素数的长度,k代表素数检测的次数
<span style="color: #9
<span style="color: #0 BigInteger RSA::createPrime(unsigned len, const unsigned k) {
<span style="color: #1
assert(k & <span style="color: #);
<span style="color: #2
BigInteger ans = createOddNum(len);// 先生成一个奇数
<span style="color: #3
while (!isPrime(ans, k)) {// 素性检测
<span style="color: #4
ans = ans.add(BigInteger::TWO);// 下一个奇数
<span style="color: #5
<span style="color: #6
<span style="color: #7 }
<span style="color: #8
<span style="color: #9 /**
<span style="color: #0
* 函数功能:根据提供的欧拉数生成公钥、私钥指数
<span style="color: #1
* 参数含义:eul表示提供的欧拉数
<span style="color: #2
<span style="color: #3 void RSA::createExponent(const BigInteger & eul) {
<span style="color: #4
e = <span style="color: #537;
<span style="color: #5
d = e.modInverse(eul);
<span style="color: #6 }
2.3 EncryptDecrypt类
&&& 该类主要用于封装加解密的一些操作，比如判断数据是否合法，输入输出加解密信息等。
&&& 该模块同样有两个文件：EncryptDecrypt.h和EncryptDecrypt.cpp。代码如下所示。
&&& EncryptDecrypt.h代码如下。
: EncryptDecrypt.h
: -22.29.58
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #ifndef __ENCRYPTDECRYPT_H__
<span style="color: # #define __ENCRYPTDECRYPT_H__
<span style="color: #
<span style="color: # #include &string&
<span style="color: # #include "RSA.h"
<span style="color: # class EncryptDecrypt {
<span style="color: # public:
<span style="color: #
EncryptDecrypt() {}
<span style="color: #
~EncryptDecrypt() {}
<span style="color: #
<span style="color: #
void menu();
// 菜单显示
<span style="color: #
bool encrypt();
<span style="color: #
bool decrypt();
<span style="color: #
void print();
// 打印RSA相关信息
<span style="color: #
void reset();
// 重置RSA相关信息
<span style="color: # protected:
<span style="color: #
void load(int);
// 根据给定位数加载RSA对象
<span style="color: #
bool islegal(const std::string &);// 判断输入字符串是否合法
<span style="color: # private:
<span style="color: #
<span style="color: # };
<span style="color: #
<span style="color: # #endif // __ENCRYPTDECRYPT_H__
&&& EncryptDecrypt.cpp代码如下。
: EncryptDecrypt.cpp
: -22.32.18
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &iostream&
10 #include &ctime&
11 #include "EncryptDecrypt.h"
* 函数功能:菜单显示
16 void EncryptDecrypt::menu() {
std::cout && "**********Welcome to use RSA encoder**********" && std::
std::cout && "
e: encrypt 加密
" && std::
std::cout && "
d: decrypt 解密
" && std::
std::cout && "
" && std::
std::cout && "
" && std::
std::cout && "
" && std::
std::cout && "input your choice:" && std::
* 函数功能:加密运算
29 bool EncryptDecrypt::encrypt() {
std::string
std::cout && "输入16进制数据:" && std::
std::cout && "&";
std::cin &&// 输入明文
if (!std::cin || !islegal(str))
return false;
BigInteger m(str);
clock_t start = clock();
BigInteger c = rsa.encryptByPublic(m);
clock_t finish = clock();
std::cout && std::fixed;
std::cout.precision(<span style="color: #);
std::cout && "用时: " && (double)(finish-start)/CLOCKS_PER_SEC && "s." && std::
std::cout && "明文: " && m && std::
std::cout && "密文: " && c && std::
return true;
* 函数功能:解密运算
52 bool EncryptDecrypt::decrypt() {
std::string
std::cout && "输入16进制数据:" && std::
std::cout && "&";
std::cin &&// 输入密文
if (!std::cin || !islegal(str))
return false;
BigInteger c(str);
clock_t start = clock();
BigInteger m = rsa.decryptByPrivate(c);
clock_t finish = clock();
std::cout && std::fixed;
std::cout.precision(<span style="color: #);
std::cout && "用时: " && (double)(finish-start)/CLOCKS_PER_SEC && "s." && std::
std::cout && "密文: " && c && std::
std::cout && "明文: " && m && std::
return true;
* 函数功能:输出RSA相关信息
75 void EncryptDecrypt::print() {
std::cout && rsa && std::
* 函数功能:重置RSA相关信息
82 void EncryptDecrypt::reset() {
std::cout && "输入密钥长度: ";
std::cin &&
load(len&&<span style="color: #);
* 函数功能:根据给定位数len加载rsa
92 void EncryptDecrypt::load(int len) {
std::cout && "初始化..." && std::
clock_t start = clock();
rsa.init(len);
clock_t finish = clock();
std::cout && "初始化完成." && std::
std::cout && std::fixed;
std::cout.precision(<span style="color: #);
<span style="color: #0
std::cout && "用时: " && (double)(finish-start)/CLOCKS_PER_SEC && "s." && std::
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 /**
<span style="color: #4
* 函数功能:判断输入字符串str是否合法
<span style="color: #5
* 参数含义:str代表输入的字符串
<span style="color: #6
<span style="color: #7 bool EncryptDecrypt::islegal(const std::string & str) {
<span style="color: #8
for (std::string::const_iterator it=str.begin(); it!=str.end(); ++it) {
<span style="color: #9
if (!isalnum(*it))
// 不是字母或者数字
<span style="color: #0
return false;
<span style="color: #1
if (isalpha(*it)) {
<span style="color: #2
char ch = tolower(*it);
<span style="color: #3
if (ch & 'f')
// 超过十六进制字符'f'
<span style="color: #4
return false;
<span style="color: #5
<span style="color: #6
<span style="color: #7
return true;
<span style="color: #8 }
2.4 主文件
&&& 该模块就只有一个文件：Main.cpp。主要用于使各个模块结合起来，执行相应操作。
&&& Main.cpp代码如下。
: Main.cpp
: -22.19.24
: Silenceneo (silenceneo_)
: http://www.cnblogs.com/Silenceneo-xw/
* @Version : 2.0
9 #include &iostream&
<span style="color: # #include "EncryptDecrypt.h"
<span style="color: #
<span style="color: # int main() {
<span style="color: #
EncryptDecrypt encrypt_
<span style="color: #
encrypt_decrypt.reset();// 设置密钥长度
<span style="color: #
<span style="color: #
<span style="color: #
std::string
<span style="color: #
bool ok = true;
<span style="color: #
<span style="color: #
<span style="color: #
encrypt_decrypt.menu();// 菜单显示
<span style="color: #
std::cout && "&";
<span style="color: #
std::cin &&
<span style="color: #
if (str.empty()) {
<span style="color: #
std::cout && "输入错误!请重新输入!" && std::
<span style="color: #
<span style="color: #
<span style="color: #
ch = str.at(<span style="color: #);
<span style="color: #
switch(ch) {
<span style="color: #
<span style="color: #
<span style="color: #
if (!encrypt_decrypt.encrypt())
<span style="color: #
std::cout && "加密失败,请重试!" && std::
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
if (!encrypt_decrypt.decrypt())
<span style="color: #
std::cout && "解密失败,请重试!" && std::
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encrypt_decrypt.print();// 打印相关信息
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encrypt_decrypt.reset();// 重新设置密钥长度
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
ok = false;
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
} while (ok);
<span style="color: #
return <span style="color: #;
<span style="color: # }
&&& 至此，RSA加密算法已经介绍完毕了，如有任何错误，欢迎指出，不胜感激。
RSA加密算法 Java版本
&&& 附上Java版本的RSA加密算法，仅供参考。
&&& RSA.java代码如下。
1 import java.math.BigI
2 import java.util.R
4 public class RSA {
public BigInteger n,// 公钥
private BigI// 私钥
private BigInteger p,
private BigI// n的欧拉函数
<span style="color: #
<span style="color: #
* 函数功能:初始化RSA对象的相关信息
<span style="color: #
* 参数含义:len表示大素数的二进制位数
<span style="color: #
<span style="color: #
public void init(int len) {
<span style="color: #
Random random = new Random();
<span style="color: #
// 产生大素数p和q
<span style="color: #
p = BigInteger.probablePrime(len, random);
<span style="color: #
q = BigInteger.probablePrime(len, random);
<span style="color: #
// 计算出n
<span style="color: #
n = p.multiply(q);
<span style="color: #
// 计算出n的欧拉函数
<span style="color: #
eul = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
<span style="color: #
// 设置加解密指数e和d
<span style="color: #
createExponent(eul);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:使用公钥进行加密
<span style="color: #
* 参数含义:m表示要加密的明文
<span style="color: #
<span style="color: #
public BigInteger encryptByPublic(BigInteger m) {
<span style="color: #
return m.modPow(e, n);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:使用私钥进行解密
<span style="color: #
* 参数含义:c表示要解密的密文
<span style="color: #
<span style="color: #
public BigInteger decryptByPrivate(BigInteger c) {
<span style="color: #
return c.modPow(d, n);
<span style="color: #
<span style="color: #
<span style="color: #
// 以下主要用于数字签名
<span style="color: #
<span style="color: #
* 函数功能:使用私钥进行加密
<span style="color: #
* 参数含义:m表示要加密的明文
<span style="color: #
<span style="color: #
public BigInteger encryptByPrivate(BigInteger m) {
<span style="color: #
return decryptByPrivate(m);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:使用公钥进行解密
<span style="color: #
* 参数含义:c表示要解密的密文
<span style="color: #
<span style="color: #
public BigInteger decryptByPublic(BigInteger c) {
<span style="color: #
return encryptByPublic(c);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:从一个欧拉数中生成公钥、私钥指数
<span style="color: #
* 参数含义:eul表示提供的欧拉数
<span style="color: #
<span style="color: #
private void createExponent(BigInteger eul) {
<span style="color: #
// TODO Auto-generated method stub
<span style="color: #
e = new BigInteger("65537");
<span style="color: #
d = e.modInverse(eul);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
* 函数功能:输出RSA相关数据
<span style="color: #
<span style="color: #
public void print() {
<span style="color: #
System.out.println("n: " + n);
<span style="color: #
System.out.println("p: " + p);
<span style="color: #
System.out.println("q: " + q);
<span style="color: #
System.out.println("e: " + e);
<span style="color: #
System.out.println("d: " + d);
<span style="color: #
<span style="color: # }
&&& EncryptDecrypt.java代码如下。
1 import java.math.BigI
2 import java.util.S
4 public class EncryptDecrypt {
private RSA rsa = new RSA();
public Scanner in = new Scanner(System.in);
* 函数功能:菜单显示
public void menu() {
System.out.println("**********Welcome to use RSA encoder**********");
System.out.println("
e: encrypt 加密
System.out.println("
d: decrypt 解密
System.out.println("
System.out.println("
System.out.println("
System.out.println("input your choice:");
* 函数功能:加密运算
public boolean encrypt() {
System.out.println("输入10进制数据:");
System.out.print("&");
String str = in.next();
if (str==null || str.isEmpty() || !islegal(str))
return false;
BigInteger m = new BigInteger(str);
long start = System.currentTimeMillis();
BigInteger c = rsa.encryptByPublic(m);
long finish = System.currentTimeMillis();
System.out.println("用时:" + (finish-start) + "ms.");
System.out.println("明文: " + m);
System.out.println("密文: " + c);
return true;
* 函数功能:解密运算
public boolean decrypt() {
System.out.println("输入10进制数据:");
System.out.print("&");
String str = in.next();
if (str==null || str.isEmpty() || !islegal(str))
return false;
BigInteger c = new BigInteger(str);
long start = System.currentTimeMillis();
BigInteger m = rsa.decryptByPrivate(c);
long finish = System.currentTimeMillis();
System.out.println("用时:" + (finish-start) + "ms.");
System.out.println("密文: " + c);
System.out.println("明文: " + m);
return true;
* 函数功能:输出RSA相关信息
public void print() {
rsa.print();
* 函数功能:重置RSA相关信息
public void reset() {
System.out.print("输入密钥长度: ");
int len = in.nextInt();
load(len&&1);
* 函数功能:根据给定位数len加载rsa
private void load(int len) {
// TODO Auto-generated method stub
System.out.println("初始化...");
long start = System.currentTimeMillis();
rsa.init(len);
long finish = System.currentTimeMillis();
System.out.println("初始化完成.");
System.out.println("用时:" + (finish-start) + "ms.");
* 函数功能:判断输入字符串str是否合法
* 参数含义:str代表输入的字符串
private boolean islegal(String str) {
// TODO Auto-generated method stub
for (int i = 0; i & str.length(); i++) {
char ch = str.charAt(i);
if (!Character.isDigit(ch)) {
return false;
<span style="color: #0
return true;
<span style="color: #1
<span style="color: #2 }
&&& Main.java代码如下。
1 public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
EncryptDecrypt encryptDecrypt = new EncryptDecrypt();
encryptDecrypt.reset();
encryptDecrypt.menu();
<span style="color: #
System.out.print("&");
<span style="color: #
String str = encryptDecrypt.in.next();
<span style="color: #
if (str==null || str.isEmpty()) {
<span style="color: #
System.out.println("输入错误,请重新输入!");
<span style="color: #
<span style="color: #
<span style="color: #
char ch = str.charAt(0);
<span style="color: #
switch(ch) {
<span style="color: #
<span style="color: #
<span style="color: #
if (!encryptDecrypt.encrypt()) {
<span style="color: #
System.out.println("加密失败,请重试!");
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
if (!encryptDecrypt.decrypt()) {
<span style="color: #
System.out.println("解密失败,请重试!");
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encryptDecrypt.print();
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encryptDecrypt.reset();
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
encryptDecrypt.in.close();
<span style="color: #
System.exit(0);
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
} while (true);
<span style="color: #
<span style="color: #
<span style="color: # }}
我要回帖
更多关于 负数奇数偶数 的文章
更多推荐
- ·江苏淮安清江中学初中部教师队伍情况好吗
- ·教资24年不允许非师范生考不当老师是不是只能退了休才能培养兴趣爱好了😭😭😭？
- ·新疆工业经济乌鲁木齐中专学校排名师资力量
- ·大专院校有二个毕业学校代码怎么填，填志愿时填那个？
- ·计算能手苏教版六年级上册97页的解方程的计算器要过程？
- ·卡西欧fx991cnx打心形怎么输入d2×6
- ·vivo手机进水声音变小后开机后扬声器就没声音了，差上充电器显示查耳机怎么办？
- ·已知x＞-1，求 1╱x+1+x 4 x的平方 2x的最小值值？
- ·81年6月16日的人日本北海道适合几月去干什么职业
- ·7岁一米25高,28公斤拉活鱼超重高速收费吗多少
- ·axb=50那么a+(b+20)
- ·comicshelff c用处
- ·am×nbn×m=em×m,求r(a),r(b)
- ·惧哉毫不畏惧的意思思
- ·与《红色夏茂》红色经典读后感1500字
- ·度秘怎么了。度秘是不是跟人类老师去学习了，在线是小度机器人
- ·一五分之七含有七的成语多少个几分之一
- ·除了搬山txt下载工这篇短文你有什么感受
- ·团员一对一扶贫帮扶方案帮扶活动的德育教育，怎么写？
- ·手机黑名单有什么影响响
- ·x偶数可以是负数吗时，指数为偶数，但没表标明加不加括号，乘出来是正负？急，
- ·谁知道7999和gb t 8239 2014谁接近8000
- ·请以感动为话题写一篇让我感动的作文写人的文章。不少于700字
- ·哆啦A梦中有一集大雄临死前是哪一集发射了三支宇宙寻宝火箭第三支火箭找到一个石器时代的星球在那个星球挖到了大量值钱
- ·已知等差数列 an（an）的第四项比第二项大6，第一项与第五项的积为-32，求此数列的前三项
- ·广东地区征信用户销户办理销户的渠道有哪些？
- ·火山小视频点赞评论视频怎么看不见评论
- ·国标电缆线直径线线直径
- ·统计学相关基础问题
- ·冷锻工序 英文的打头和打平用英文怎样表达
- ·有人会做这个做数学题的软件吗
- ·用移步换景写一篇游记 是一种怎样的手法？
- ·ABC的英文缩写 22个字组成一句话情商 谢谢各位大神
- ·做包皮手术后多久可以同房有什么好处
- ·请问这张4维肺部肿瘤看片子能看出出是女宝还是男宝吗？谢谢解答。
