Elgamal 加密算法C或者C++代码

以下是Elgamal加密算法的C++代码实现：

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

using namespace std;

typedef struct {
    int p;  // 素数
    int g;  // 原根
    int x;  // 私钥
    int y;  // 公钥
} ElgamalKey;

// 欧几里得算法求最大公约数
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// 扩展欧几里得算法求逆元
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 快速幂算法
int qpow(int a, int b, int mod) {
    int res = 1 % mod;
    while (b) {
        if (b & 1)
            res = (long long) res * a % mod;
        a = (long long) a * a % mod;
        b >>= 1;
    }
    return res;
}

// 生成Elgamal密钥对
void generateElgamalKey(ElgamalKey &key) {
    srand(time(NULL));
    int prime[] = {11, 23, 47, 59, 83, 107, 131, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719,
                   839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1439, 1487, 1619, 1823, 1907, 2027, 2063, 2099,
                   2111, 2129, 2383, 2543, 2579, 2639, 2687, 2699, 2711, 2729, 2783, 2963, 2999, 3119, 3167, 3259,
                   3323, 3467, 3539, 3559, 3583, 3659, 3671, 3767, 3823, 3911, 3923, 4007, 4079, 4139, 4159, 4229,
                   4259, 4283, 4339, 4379, 4423, 4483, 4499, 4547, 4643, 4679, 4799, 4919, 4999, 5039, 5087, 5231,
                   5279, 5411, 5507, 5639, 5651, 5711, 5743, 5839, 5843, 5867, 5879, 5939, 6011, 6047, 6079, 6131,
                   6143, 6191, 6263, 6299, 6323, 6359, 6443, 6551, 6563, 6659, 6683, 6827, 6863, 6959, 6983, 7019,
                   7103, 7127, 7199, 7223, 7343, 7439, 7511, 7523, 7547, 7643, 7739, 7823, 7879, 7939, 8099, 8219,
                   8231, 8291, 8351, 8363, 8423, 8447, 8539, 8579, 8591, 8627, 8639, 8687, 8747, 8819, 8863, 8923,
                   9047, 9059, 9203, 9283, 9299, 9311, 9371, 9419, 9479, 9539, 9623, 9679, 9719, 9743, 9859, 9923,
                   10007, 10079, 10103, 10139, 10211, 10243, 10247, 10271, 10319, 10343, 10427, 10499, 10559, 10607,
                   10631, 10711, 10799, 10847, 10883, 10903, 10939, 11003, 11027, 11071, 11119, 11159, 11171, 11279,
                   11303, 11351, 11423, 11519, 11579, 11699, 11743, 11807, 11879, 11903, 11959, 12011, 12071, 12107,
                   12143, 12203, 12239, 12251, 12263, 12323, 12379, 12479, 12527, 12539, 12583, 12611, 12647, 12707,
                   12743, 12763, 12823, 12919, 12983, 13007, 13099, 13127, 13171, 13219, 13259, 13331, 13399, 13427,
                   13499, 13523, 13619, 13679, 13763, 13807, 13859, 13967, 14011, 14039, 14143, 14207, 14243, 14251,
                   14287, 14327, 14387, 14407, 14423, 14519, 14591, 14627, 14699, 14759, 14831, 14887, 14939, 14951,
                   14983, 15031, 15083, 15107, 15227, 15287, 15319, 15383, 15407, 15443, 15527, 15559, 15583, 15647,
                   15683, 15731, 15803, 15887, 15919, 16007, 16063, 16127, 16139, 16223, 16267, 16319, 16363, 16411,
                   16427, 16499, 16567, 16631, 16691, 16703, 16787, 16823, 16879, 16943, 17027, 17099, 17107, 17183,
                   17207, 17291, 17327, 17419, 17471, 17483, 17567, 17579, 17659, 17707, 17783, 17839, 17891, 17903,
                   17939, 18047, 18059, 18119, 18143, 18211, 18287, 18311, 18359, 18379, 18443, 18479, 18491, 18503,
                   18587, 18611, 18671, 18719, 18731, 18779, 18839, 18911, 18947, 19031, 19079, 19139, 19183, 19207,
                   19259, 19267, 19319, 19403, 19423, 19471, 19507, 19559, 19603, 19607, 19679, 19727, 19819, 19843,
                   19891, 19919, 19979, 20003, 20047, 20107, 20123, 20191, 20231, 20359, 20399, 20407, 20483, 20507,
                   20627, 20663, 20699, 20743, 20771, 20807, 20879, 20903, 21011, 21023, 21059, 21107, 21179, 21211,
                   21319, 21383, 21407, 21491, 21503, 21527, 21611, 21647, 21719, 21787, 21839, 21863, 21911, 21943,
                   22027, 22067, 22123, 22147, 22211, 22259, 22343, 22367, 22439, 22483, 22511, 22571, 22619, 22639,
                   22679, 22739, 22787, 22811, 22859, 22943, 23003, 23039, 23087, 23159, 23167, 23179, 23227, 23279,
                   23327, 23399, 23447, 23459, 23507, 23567, 23627, 23687, 23719, 23819, 23831, 23879, 23927, 23971,
                   24007, 24071, 24107, 24203, 24239, 24251, 24359, 24407, 24443, 24527, 24551, 24571, 24611, 24683,
                   24707, 24799, 24839, 24883, 24919, 24971, 25031, 25067, 25127, 25163, 25247, 25303, 25307, 25343,
                   25411, 25439, 25471, 25523, 25583, 25607, 25667, 25703, 25799, 25847, 25867, 25903, 25919, 25943,
                   25999, 26003, 26027, 26083, 26119, 26171, 26207, 26267, 26303, 26339, 26387, 26407, 26447, 26539,
                   26591, 26627, 26687, 26731, 26759, 26807, 26879, 26927, 26987, 27011, 27059, 27107, 27179, 27211,
                   27239, 27323, 27371, 27407, 27431, 27479, 27539, 27583, 27647, 27683, 27767, 27791, 27803, 27827,
                   27883, 27919, 27983, 28019, 28079, 28123, 28163, 28183, 28219, 28279, 28307, 28379, 28411, 28451,
                   28499, 28547, 28583, 28643, 28691, 28723, 28759, 28807, 28859, 28883, 28919, 29023, 29039, 29087,
                   29159, 29207, 29243, 29287, 29327, 29399, 29443, 29483, 29599, 29611, 29663, 29687, 29723, 29759,
                   29819, 29867, 29927, 29983, 30011, 30047, 30083, 30103, 30167, 30211, 30283, 30307, 30319, 30367,
                   30467, 30511, 30559, 30631, 30659, 30683, 30707, 30727, 30763, 30851, 30911, 30959, 31019, 31079,
                   31123, 31159, 31219, 31247, 31319, 31379, 31423, 31487, 31511, 31583, 31607, 31667, 31723, 31799,
                   31847, 31907, 31991, 32003, 32051, 32087, 32143, 32203, 32231, 32279, 32303, 32351, 32411, 32467,
                   32507, 32579, 32611, 32719, 32783, 32807, 32831, 32903, 32999, 33023, 33071, 33119, 33179, 33199,
                   33247, 33287, 33359, 33391, 33427, 33479, 33539, 33587, 33619, 33703, 33767, 33791, 33827, 33863,
                   33871, 33911, 33967, 34019, 34031, 34099, 34127, 34183, 34211, 34283, 34319, 34367, 34439, 34499,
                   34543, 34583, 34631, 34679, 34739, 34759, 34847, 34883, 34919, 34967, 35023, 35107, 35159, 35171,
                   35207, 35279, 35339, 35363, 35447, 35471, 35507, 35531, 35591, 35671, 35723, 35803, 35819, 35879,
                   35911, 35963, 36011, 36083, 36107, 36151, 36223, 36287, 36307, 36359, 36427, 36479, 36527, 36583,
                   36607, 36671, 36719, 36767, 36863, 36919, 36967, 37087, 37159, 37207, 37223, 37259, 37307, 37379,
                   37447, 37487, 37511, 37559, 37619, 37663, 37747, 37783, 37811, 37903, 37951, 37967, 38039, 38083,
                   38119, 38219, 38287, 38327, 38351, 38447, 38543, 38567, 38639, 38651, 38711, 38767, 38839, 38891,
                   38927, 39019, 39047, 39083, 39119, 39227, 39251, 39323, 39359, 39383, 39419, 39499, 39551, 39583,
                   39623, 39671, 39719, 39791, 39827, 39887, 39911, 39959, 40031, 40063, 40111, 40199, 40219, 40283,
                   40343, 40427, 40487, 40531, 40591, 40639, 40703, 40751, 40787, 40847, 40867, 40903, 40967, 41011,
                   41059, 41131, 41183, 41263, 41351, 41387, 41447, 41471, 41543, 41579, 41627, 41687, 41719, 41759,
                   41807, 41879, 41951, 42019, 42071, 42107, 42143, 42179, 42227, 42283, 42359, 42383, 42407, 42443,
                   42491, 42539, 42587, 42623, 42719, 42743, 42839, 42863, 42923, 42983, 43007, 43067, 43103, 43159,
                   43207, 43283, 43319, 43391, 43427, 43471, 43523, 43607, 43651, 43711, 43759, 43823, 43867, 43943,
                   43991, 44027, 44087, 44131, 44159, 44279, 44311, 44351, 44383, 44459, 44519, 44603, 44651, 44687,
                   44759, 44783, 44819, 44851, 44959, 45007, 45047, 45083, 45179, 45263, 45307, 45347, 45383, 45439,
                   45491, 45587, 45631, 45707, 45767, 45823, 45887, 45943, 46003, 46051, 46103, 46183, 46259, 46307,
                   46339, 46387, 46439, 46471, 46559, 46619, 46663, 46687, 46723, 46763, 46811, 46847, 46919, 469