写一段快速幂运算 用C++

C语言中可以使用快速幂算法实现快速幂运算。以下是一个快速幂函数的示例代码：

#include <stdio.h>

long long quick_pow(int a, int b) {
    long long result = 1;
    while (b > 0) {
        if (b & 1) {
            result = result * a;
        }
        b >>= 1;
        a = a * a;
    }
    return result;
}

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%lld\n", quick_pow(a, b));
    return 0;
}

该代码实现了快速幂算法，每次将幂次 b 除以 2，并将底数 a 乘以自身。该代码对于任意输入的 a 和 b，都能够计算出 a^b 的结果。

相关问题

给出可以人工输入变量的模幂运算的C++代码

以下是一个可以人工输入变量的模幂运算的C++代码示例：

#include<iostream>
using namespace std;

// 计算 x^y mod p 的值
long long power(long long x, long long y, long long p){
    long long res = 1;
    x %= p;
    while (y > 0){
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

int main(){
    long long x, y, p;
    cout << "请输入 x、y、p 的值：";
    cin >> x >> y >> p;

    cout << "x^y mod p = " << power(x, y, p) << endl;

    return 0;
}

这段代码中，我们定义了一个 `power` 函数来计算模幂运算的结果。其中，`x` 表示底数，`y` 表示指数，`p` 表示模数，函数返回 `x^y mod p` 的值。在 `main` 函数中，我们通过 `cin` 来读入用户输入的 `x`、`y`、`p` 的值，并输出计算结果。

用c++写一个DSA加密算法

DSA（Digital Signature Algorithm）是一种用于数字签名的加密算法，它基于离散对数问题和有限域上的算术运算。以下是用C++实现DSA算法的示例代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

// 求 a^b mod c 的值
int modpow(int a, int b, int c) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;
    }
    return res;
}

// 判断 n 是否为素数
bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

// 生成大素数
int gen_prime() {
    int p;
    do {
        p = rand() % 1000 + 1000; // 生成1000 ~ 1999之间的随机数
    } while (!is_prime(p));
    return p;
}

// 生成密钥对
void gen_key_pair(int &p, int &q, int &g, int &x, int &y) {
    // 生成两个大素数 p 和 q
    p = gen_prime();
    q = gen_prime();

    // 计算 g，满足 g^q mod p = 1
    for (g = 2; g < p; ++g) {
        if (modpow(g, q, p) == 1) {
            break;
        }
    }

    // 生成随机数 x，满足 0 < x < q
    x = rand() % q + 1;

    // 计算 y，满足 y = g^x mod p
    y = modpow(g, x, p);
}

// 生成签名
void gen_signature(int p, int q, int g, int x, int &r, int &s, int m) {
    // 随机选择 k，满足 0 < k < q
    int k = rand() % q + 1;

    // 计算 r，满足 r = (g^k mod p) mod q
    r = modpow(g, k, p) % q;

    // 计算 s，满足 s = (k^-1 * (m + x * r)) mod q
    int inv_k = modpow(k, q - 2, q);
    s = (inv_k * (m + x * r)) % q;
}

// 验证签名
bool verify_signature(int p, int q, int g, int y, int r, int s, int m) {
    if (r < 1 || r > q || s < 1 || s > q) {
        return false;
    }

    // 计算 w，满足 w = s^-1 mod q
    int w = modpow(s, q - 2, q);

    // 计算 u1，满足 u1 = (m * w) mod q
    int u1 = (m * w) % q;

    // 计算 u2，满足 u2 = (r * w) mod q
    int u2 = (r * w) % q;

    // 计算 v，满足 v = ((g^u1 * y^u2) mod p) mod q
    int v = ((modpow(g, u1, p) * modpow(y, u2, p)) % p) % q;

    return v == r;
}

int main() {
    srand(time(nullptr));

    int p, q, g, x, y;
    gen_key_pair(p, q, g, x, y);

    int m = 123456;
    int r, s;
    gen_signature(p, q, g, x, r, s, m);

    bool result = verify_signature(p, q, g, y, r, s, m);
    if (result) {
        cout << "Signature is valid." << endl;
    } else {
        cout << "Signature is invalid." << endl;
    }

    return 0;
}

这段代码实现了DSA算法的密钥对生成、签名和验证功能。其中，`modpow()`函数用于求幂取模，`is_prime()`函数用于判断一个数是否为素数，`gen_prime()`函数用于生成一个大素数，`gen_key_pair()`函数用于生成密钥对，`gen_signature()`函数用于生成签名，`verify_signature()`函数用于验证签名。