RSA算法实现与异常检测：欧拉数、密钥生成

"本文介绍了RSA算法的基本原理和C语言实现，并通过一个实际的程序运行示例展示了如何使用RSA算法进行加密和解密。" RSA是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年提出，故得名RSA。该算法基于数论中的大数因子分解难题，具有较高的安全性。在RSA中，有两个密钥：公钥和私钥。公钥用于加密，私钥用于解密，确保了信息的安全性。 在RSA算法中，首先需要选取两个大素数p和q，两者的乘积n=pq作为模数。接着，选取一个整数e，要求e与(p-1)(q-1)互素，即e和(p-1)(q-1)的最大公约数为1。然后通过欧几里得扩展算法计算出d，使得ed=1 mod (p-1)(q-1)，d就是私钥。公钥由e和n组成，私钥由d和n组成。 加密过程是将明文m通过公钥加密为密文c，计算公式为ci=mi^e mod n。解密时，使用私钥d，计算mi=ci^d mod n，可以还原出原始明文m。 在给出的C语言程序中，主要包含以下几个部分： 1. `candp`函数：实现了幂的取余运算，这是加密和解密过程中的关键步骤。 2. `fun`函数：用于判断两个数是否互素，如果返回0，则表示互素，否则不互素。 3. `main`函数：用户输入素数p和q，计算n和t，然后获取公钥e，如果e不符合要求（小于1、大于t或者与t不互素），则要求重新输入。接着计算私钥d，并提供选项让用户选择加密或解密操作。 程序示例中，当p=43, q=59时，n=43 * 59，t=(43-1)*(59-1)。若初次选取的e不合法（如e=15），程序会提示重新输入，直到找到一个与t互素的e（如e=13）。由于int型限制，n的最大值不能超过65536，因此该实现仅适用于学习和理解RSA算法的基本原理，实际应用中需要更大型的素数和更高级的实现方式来确保足够的安全性。