求一个数模逆元的c++代码
时间: 2023-12-03 18:45:53 浏览: 53
以下是求一个数的模逆元的C++代码:
```c++
#include <iostream>
using namespace std;
int modInverse(int a, int m) {
int m0 = m, t, q;
int x0 = 0, x1 = 1;
if (m == 1) return 0;
while (a > 1) {
q = a / m;
t = m;
m = a % m, a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
int main() {
int a = 5, m = 7;
cout << "The modulo inverse of " << a << " under " << m << " is " << modInverse(a, m) << endl;
return 0;
}
```
输出结果为:
```
The modulo inverse of 5 under 7 is 3
```
其中,`modInverse(a, m)` 函数用于计算 a 在模 m 意义下的逆元。
相关问题
用c++写一个用辗转相除法求任意数的模乘逆元的代码
以下是用辗转相除法求任意数的模乘逆元的C代码:
```
#include <stdio.h>
int extended_gcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int r = extended_gcd(b, a % b, y, x);
*y -= (a / b) * (*x);
return r;
}
int mod_inverse(int a, int m) {
int x, y;
int gcd = extended_gcd(a, m, &x, &y);
if (gcd != 1) {
printf("The inverse of %d does not exist modulo %d.\n", a, m);
return -1;
} else {
return (x % m + m) % m;
}
}
int main() {
int a, m;
printf("Enter a and m (separated by a space): ");
scanf("%d %d", &a, &m);
int inv = mod_inverse(a, m);
if (inv != -1) {
printf("The inverse of %d modulo %d is %d.\n", a, m, inv);
}
return 0;
}
```
该程序中的 `extended_gcd` 函数实现了扩展欧几里得算法,用于计算最大公约数和模乘逆元。 `mod_inverse` 函数则利用 `extended_gcd` 函数求出模乘逆元(如果存在)并返回。在主函数中,程序要求用户输入要求模乘逆元的数和模数,并输出计算结果。
在C++当中用代码实现仿射密码的加密和解密
下面是C语言实现仿射密码的加密和解密的代码:
```
#include <stdio.h>
#include <string.h>
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int modInverse(int a, int m) {
a = a % m;
for (int x = 1; x < m; x++) {
if ((a * x) % m == 1) {
return x;
}
}
return -1;
}
void affine_encrypt(char* plaintext, int a, int b, char* ciphertext) {
int len = strlen(plaintext);
for (int i = 0; i < len; i++) {
if (plaintext[i] >= 'a' && plaintext[i] <= 'z') {
ciphertext[i] = (char) (((a * (plaintext[i] - 'a') + b) % 26) + 'a');
} else if (plaintext[i] >= 'A' && plaintext[i] <= 'Z') {
ciphertext[i] = (char) (((a * (plaintext[i] - 'A') + b) % 26) + 'A');
} else {
ciphertext[i] = plaintext[i];
}
}
ciphertext[len] = '\0';
}
void affine_decrypt(char* ciphertext, int a, int b, char* plaintext) {
int len = strlen(ciphertext);
int a_inv = modInverse(a, 26);
for (int i = 0; i < len; i++) {
if (ciphertext[i] >= 'a' && ciphertext[i] <= 'z') {
plaintext[i] = (char) (((a_inv * ((ciphertext[i] - 'a' - b + 26) % 26)) % 26) + 'a');
} else if (ciphertext[i] >= 'A' && ciphertext[i] <= 'Z') {
plaintext[i] = (char) (((a_inv * ((ciphertext[i] - 'A' - b + 26) % 26)) % 26) + 'A');
} else {
plaintext[i] = ciphertext[i];
}
}
plaintext[len] = '\0';
}
int main() {
char plaintext[100], ciphertext[100], decryptedtext[100];
int a, b;
printf("Enter the plaintext: ");
scanf("%[^\n]s", plaintext);
printf("Enter the value of a (should be coprime with 26): ");
scanf("%d", &a);
printf("Enter the value of b: ");
scanf("%d", &b);
if (gcd(a, 26) != 1) {
printf("Invalid value of a. It should be coprime with 26.\n");
return 0;
}
affine_encrypt(plaintext, a, b, ciphertext);
printf("Encrypted text: %s\n", ciphertext);
affine_decrypt(ciphertext, a, b, decryptedtext);
printf("Decrypted text: %s\n", decryptedtext);
return 0;
}
```
在这个程序中,我们使用了两个函数affine_encrypt和affine_decrypt来分别实现仿射密码的加密和解密。这两个函数的参数分别是明文,a和b(这是仿射密码的两个参数),以及密文或解密后的明文。我们还使用了gcd函数来计算两个数的最大公约数,以及modInverse函数来计算a模26的逆元。在主函数中,我们先输入明文,a和b,然后进行加密和解密,并输出结果。注意,输入的明文应该只包含字母和空格,不应该包含标点符号或数字。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)