软件构造博客3

#include
#include
#include
#include
using namespace std;

// 生成伪素数
const int MAX_ROW = 50;
size_t Pseudoprime()
{
    bool ifprime = false;
    size_t a = 0;
    int arr[MAX_ROW];   //数组arr为{3，4，5，6...52}
    for (int i = 0; i < MAX_ROW; ++i)
    {
        arr[i] = i + 3;
    }
    srand((unsigned)time(NULL));
    while (!ifprime)
    {
        srand((unsigned)time(0));
        ifprime = true;
        a = (rand() % 10000) * 2 + 3; //生成一个范围在3到20003里的奇数
        for (int j = 0; j < MAX_ROW; ++j)
        {
            if (a % arr[j] == 0)
            {
                ifprime = false;
                break;
            }
        }
    }
    return a;
}

size_t  repeatMod(size_t base, size_t n, size_t mod)//模重复平方算法求(b^n)%m
{
    size_t a = 1;
    while (n)
    {
        if (n & 1)
        {
            a = (a * base) % mod;
        }
        base = (base * base) % mod;
        n = n >> 1;
    }
    return a;
}
unsigned int ProduceRandomOdd() {
    //UINT无符号整形，各伪随机数放在RandomArray数组中 
    time_t t;//c++时间类型 
    unsigned int RandomNumber;//记录随机数 
    do {

        srand((unsigned)time(NULL));//srand(seed)用于给rand()函数设定种子,此处用系统时间
        //生成 
        RandomNumber = ((rand() << 17) | (rand() << 3) | (rand())) % 100000;
        //cout<     } while (RandomNumber % 2 == 0 || RandomNumber < 10000);
    //返回   
    return RandomNumber;
}
//Miller-Rabin素数检测
bool rabinmiller(size_t n, size_t k)
{

    int s = 0;
    int temp = n - 1;
    while ((temp & 0x1) == 0 && temp)
    {
        temp = temp >> 1;
        s++;
    }   //将n-1表示为(2^s)*t
    size_t t = temp;

    while (k--)  //判断k轮误判概率不大于(1/4)^k
    {
        srand((unsigned)time(0));
        size_t b = rand() % (n - 2) + 2; //生成一个b(2≤a ≤n-2)

        size_t y = repeatMod(b, t, n);
        if (y == 1 || y == (n - 1))
            return true;
        for (int j = 1; j <= (s - 1) && y != (n - 1); ++j)
        {
            y = repeatMod(y, 2, n);
            if (y == 1)
                return false;
        }
        if (y != (n - 1))
            return false;
    }
    return true;
}
//简单的素数检测方法
bool isprime(size_t n)
{
    if (n == 2)
        return true;
    for (int i = 2; i <= (int)sqrt((float)n); ++i)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
//拓展欧几里得算法
long long ExtendedEuclidean(long long e, long long f)
{
    long long phi = f, mod = f;
    for (long long i = 2; i <= f / i; i++)
        if (f % i == 0)
        {
            phi = phi / i * (i - 1);
            while (f % i == 0)
                f /= i;
        }
    if (f > 1)
        phi = phi / f * (f - 1);
    phi--;
    long long res = 1, t = e;
    while (phi)
    {
        if (phi & 1)
            res = (res * t) % mod;
        t = (t * t) % mod, phi >>= 1;
    }
    return res;
}
bool isrp(int a, int b)
{
    if (a == 1 || b == 1)     // 两个正整数中，只有其中一个数值为1，两个正整数为互质数
        return true;
    while (1)
    {          // 求出两个正整数的最大公约数
        int t = a % b;
        if (t == 0)
        {
            break;
        }
        else
        {
            a = b;
            b = t;
        }
    }
    if (b > 1)    return false;// 如果最大公约数大于1，表示两个正整数不互质
    else return true;    // 如果最大公约数等于1,表示两个正整数互质
}
//在2到f-1范围内取一个与f互质的数e
long long generate(long long f) {
    long long e = (rand() % (f - 2)) + 2;
    while (!isrp(e,f))
    {
        e = (rand() % (f - 2)) + 2;
    }
    return e;
}

int main()
{
     long long p;
     long long q;
     long long f;
     long long n;
     long long e;
     long long d;
    do {
        p = Pseudoprime();
    } while (p < 1000 || rabinmiller(p, 20) == false);
    do {
        q = Pseudoprime();
    } while (q < 1000 ||  q == p || rabinmiller(q, 20) == false);
    f = (p - 1) * (q - 1);
    n = p * q;
    e = generate(f); //在2到f-1范围内取一个与f互质的数e
    d = ExtendedEuclidean(e, f);
    cout << "p = " << p << endl;
    cout << "q = " << q << endl;
    cout << "f = (p - 1) * (q - 1) = " << f << endl;
    cout << "n = p * q = " << n << endl;
    cout << "e = " << e << endl;
    cout << "d = " << d << endl;
    cout << "(e * d) % f = " << (e * d) % f << endl;
    string code = "abcdefghijklmnopqrstuvwxyz";
    long long temp[26]{};
    int i = 0;
    cout << "Source: " << endl << code << endl;
    for (const auto& item : code) {
        cout << hex << int(item) << "t";
    }
    cout << endl;
    cout << "Encode:" << endl;
    for (const auto& item : code) {
        temp[i++] = repeatMod((int)item, e, n);
        cout << hex << temp[i-1] << "t";
    }
    cout << endl  <<"Decode:" << endl;
    i = 0;
    for (const auto& item : code) {
        cout << hex << repeatMod(temp[i++],d,n) << "t";
    }
    cout << endl;
    cout << "Decryption:" << endl;
    i = 0;
    for (const auto& item : code) {
        cout << (char)repeatMod(temp[i++], d, n);
    }
    cout << endl;
    getchar();
    return 0;
}