ctf rsa已知n和phi

在CTF密码学挑战中，如果你遇到RSA公钥`n`（两个大素数`p`和`q`的乘积），以及私钥信息`c`（加密后的密文）的情况，并且你知道`p`和`q`非常接近（即它们之间的差值很小），这通常暗示着这两个素数是“伪随机”生成而非随机选择的，这种情况下可以尝试利用差分攻击来恢复原消息。 不过，直接从`n`、`c`和`p ≈ q`推导出原始明文并不是标准的RSA算法的安全漏洞，因为真正的RSA公钥生成应该是保证`p`和`q`之间的差异足够大，使得计算几乎不可能。 为了模拟这种情况并展示一个简化的示例，我们可以假设这里有一个简化版的伪随机`p`和`q`生成方法。以下是Python的一个简略版本，但这并不适用于实际的RSA攻击： ```python from sympy import factorint def is_close_to_pseudorandom(n): factors = factorint(n) p, q = factors.keys() return abs(p - q) <= 1 # 假设p和q相差不大于1 # 假设我们有一些已知的n和c n = ... # RSA模数 c = ... # 加密后的密文 if is_close_to_pseudorandom(n): # 这里只是一个演示，真实环境中需要更复杂的数学分析 # 我们可能会猜测p和q的形式，然后尝试一些候选解 p = n // (n - 1) # 假设q接近n - 1 q = n // p # 根据p求得q phi_n = (p - 1) * (q - 1) # 计算欧拉函数phi(n) # 使用中国剩余定理（Chinese Remainder Theorem, CRT） d = inverse_mod(c, phi_n) # 寻找模phi(n)的逆元作为d message = pow(c, d, n) # 解密密文 else: print("无法直接解密，p和q的差异过大") print(f"Decrypted message: {message}")

<think>嗯，我现在需要解决这个问题，题目是给定e、N、c，要求求出明文m。已知p和q的差的绝对值不超过2×10^5，而且N是两个质数p和q的乘积。我的任务是根据这些信息快速分解N，找到p和q，然后计算出私钥d，最后用d解密得到m。 首先，我得想到如何分解N。因为p和q的差很小，所以它们的平方根附近应该有一个接近的值。根据RSA的原理，N = p*q，且p和q都是质数。假设p和q相近，我们可以从sqrt(N)开始向两边搜索，找到这两个质数。 那具体怎么做呢？比如，先计算N的平方根，然后在这个值的附近寻找p和q。因为p和q的差很小，所以他们的平均值大约是sqrt(N)。假设p和q相差不大，比如在sqrt(N)附近的一个范围内，那么我们可以从sqrt(N)往两边找，直到找到满足条件的p，使得N能被p整除。这时候q就是N/p。 但是计算平方根的时候可能会有精度问题。例如，当N很大时，使用浮点数可能不够精确。这时候可以用二分法来找sqrt(N)的整数部分。或者，在C语言中用sqrt函数得到一个近似值，然后向下取整，再在这个值附近的一定范围内遍历可能的p。 比如，计算sqrt(N)，然后从sqrt(N) - 1e5开始，到sqrt(N) + 1e5结束，每次检查i是否是N的因数。因为题目中说|p - q| <= 2e5，所以p和q之间的距离不大，所以sqrt(N)附近的范围内应该有一个是p或者q。比如，假设sqrt(N)是中间点，那么p可能在sqrt(N) - 1e5到sqrt(N) + 1e5之间？ 或者，可以这样想，p和q的差是d= |p - q| ≤2e5。而N = p*q。假设p <= q，那么q = p + d。所以N = p*(p +d) = p² +d p。我们可以解这个方程，得到p的可能值。但这可能比较复杂，不如直接遍历sqrt(N)附近的数。 具体步骤可能是： 1. 计算sqrt_N = sqrt(N)，取整数部分。 2. 从sqrt_N开始，向上下检查附近的数i，看是否能被N整除。比如，从sqrt_N往左遍历到sqrt_N - 2e5，或者往右到sqrt_N + 2e5，直到找到i使得N%i ==0。 3. 找到其中一个因子p后，q=N/p。 4. 然后计算phi(N)=(p-1)*(q-1)。 5. 计算d为e的模逆元，即d ≡ e^{-1} mod phi(N)。 6. 最后，用快速幂计算m = c^d mod N。 那问题的关键在于如何快速找到p和q。因为N的范围是到1e18，所以sqrt(N)可以达到1e9，但遍历的范围是2e5，所以总共有约2e5次循环，这在时间上是可行的，因为每次循环只需要一次模运算，而模运算是O(1)的时间。 例如，样例输入中的N是293000179499792623，sqrt(N)大概是约sqrt(3e17)大约是5.4e8（具体数值可能需要计算）。假设sqrt(N)是1710000（比如），那么从该数附近遍历，直到找到一个能整除N的数。比如，假设正确的p是1710000附近的某个数，那么循环几次就能找到。 那么具体实现的时候，如何遍历呢？比如，我们可以从sqrt(N)开始，往小的方向遍历，直到sqrt(N) - 2e5，或者在sqrt(N)附近的一个足够大的范围内遍历。或者，考虑到p和q的差不超过2e5，那么最大的可能，其中一个因数应该在sqrt(N)的附近，所以我们可以从sqrt_N开始，往两边逐个测试，直到找到因数。 举个例子，假设N=293000179499792623，那么计算sqrt(N)的值。比如用计算器计算，或者用C代码中的sqrt函数。然后，比如，假设sqrt_N是约541000000左右？可能这个数值不准确，但代码中可以用循环来找到正确的因数。 那具体代码步骤： 1. 输入e、N、c。 2. 找到p和q，其中p <= q，并且q - p <= 2e5。 3. 计算phi = (p-1)*(q-1)。 4. 计算d = mod_inverse(e, phi)。 5. 计算m = qmi(c, d, N)。 6. 输出m。 关键点在于如何高效找到p和q。这里，遍历从sqrt(N)开始，向下找，直到找到一个i，使得N能被i整除。因为p和q的差很小，所以i应该在sqrt(N)附近。 例如，代码中可以这样实现： 从sqrt(N)开始，往小的方向遍历，每次减1，直到找到i，使得N%i ==0。或者，可能因为sqrt(N)的取整问题，需要同时检查i和i+1等。 比如： long long find_p(long long N) { long long sqrt_N = (long long)sqrt(N); // 因为sqrt可能有误差，所以需要检查附近的范围 for (long long i = sqrt_N; i >= sqrt_N - 2e5; --i) { if (N % i == 0) { return i; } } // 如果没找到，可能需要检查更大的范围或者另一方向？ // 根据题目条件，必定存在，所以可以不用处理 return -1; } 但是需要注意，当sqrt(N)的平方刚好等于N时，这时候i就是sqrt(N)，可能此时i就是p或者q。否则，比如当sqrt(N)是小数时，取整后的值可能比实际的sqrt(N)小或者大。比如，当N的平方根不是整数时，sqrt(N)取整后的值可能比实际的p或q小。所以可能需要检查sqrt(N)附近的数值。 或者，更高效的是，不管sqrt(N)的值，从sqrt_N开始向上下遍历，比如先向上，然后向下，或者只向下遍历一定范围。例如，因为p和q的差不超过2e5，所以它们的值应该分布在sqrt(N)附近，所以从sqrt_N开始，向下遍历到sqrt_N - 2e5即可找到其中一个因数。 比如，假设p和q的差是d，那么当p和q接近sqrt(N)时，sqrt(N) ≈ (p+q)/2。所以，如果d是小的，那么最大的可能是在sqrt(N)附近有一个因数。所以，遍历从sqrt(N)开始，向小的方向找，直到找到。 例如，在代码中，可以这样做： long long p = 0; long long sqrt_N = (long long)sqrt(N); for (long long i = sqrt_N; i >= 1; --i) { if (N % i == 0) { p = i; break; } } 但这样的话，如果p和q的差很大，那么可能需要很长时间。但根据题目条件，它们的差不超过2e5，所以sqrt(N)附近的i最多需要遍历2e5次，就可以找到p或者q。 所以，正确的做法是，从sqrt_N开始，向下遍历最多2e5次，就可以找到因数。例如： long long find_pq(long long N) { long long sqrt_N = (long long)sqrt(N); // 因为可能sqrt_N * sqrt_N < N，所以可能需要检查sqrt_N +1？ // 或者，遍历sqrt_N附近的范围，比如上下各1e5次？ // 题目中的条件是 |p - q| <= 2e5，所以p和q的差不大，所以sqrt_N应该接近p或q中的一个。 for (long long i = sqrt_N; i >= sqrt_N - 2e5; --i) { if (N % i == 0) { return i; } } // 如果没找到，可能需要检查更大的范围？ // 但是题目保证存在这样的p和q，所以这里应该不会走到 return -1; } 但是，例如，当sqrt(N)是某个小数时，i的初始值可能比实际的p或q小，导致向下遍历的时候可能错过正确的因数。例如，假设正确的p是sqrt_N + 100，而sqrt_N是整数，那么这时候i从sqrt_N开始向下遍历，可能找不到正确的因数。 这说明，这种方法可能存在错误。比如，当p和q的差很小，但都位于sqrt_N的附近，但sqrt_N的取整导致初始值不正确。 那这时候应该如何处理？ 或者，另一个方法是，遍历从sqrt_N - 1e5到sqrt_N +1e5的范围，检查每个i是否能整除N。因为p和q的差不超过2e5，所以其中一个因数必然在sqrt_N附近的这个范围内。 例如，假设正确的p是sqrt_N +k，其中k是某个较小的值，比如在±1e5范围内。这样，遍历这个范围就能找到因数。 所以，正确的代码应该是： 从sqrt_N -1e5到sqrt_N +1e5之间遍历每个i，检查是否能整除N。一旦找到，就可以得到p和q。 或者，为了优化，可以只遍历sqrt_N附近的可能范围。例如，如果p和q的差不超过2e5，那么它们的平均值是sqrt_N附近。所以，假设p是sqrt_N - t， q是 sqrt_N + t +d（其中d<=2e5），那么pq = N。但可能这样不太直观。 或者，更好的方法是，因为p和q的差不超过2e5，所以它们的乘积是N，所以其中较大的那个数最多是sqrt(N) +1e5，而较小的那个是sqrt(N) -1e5。例如，假设p < q，且q - p <=2e5，则p和 q必须位于sqrt(N)附近的范围内。例如，sqrt(N) -1e5 <= p <= sqrt(N) <= q <= sqrt(N)+1e5。或者类似的范围？ 或者，可以这样考虑，因为q = p + d，其中d <=2e5。所以，N = p*(p+d)。解这个方程的话，可以得到p的近似值。但可能比较复杂。 所以，回到遍历的思路，正确的做法是遍历sqrt_N附近的区域，比如从sqrt_N - 2e5到sqrt_N +2e5，检查每个数是否是N的因数。一旦找到i，则分解成功。 但这样的话，遍历的范围是4e5次，这在时间上是可行的吗？对于每个i来说，只需要进行一次取模运算，这在C语言中非常快，即使对于1e18的数来说，取模运算的时间也是可以接受的。所以遍历4e5次是完全可行的。 那代码的大致逻辑是： 输入e、N、c。 计算sqrt_N = sqrt(N)，转为long long类型。 然后从sqrt_N出发，向上下各扩展2e5的范围，寻找因数i。例如，循环i从sqrt_N -2e5到 sqrt_N +2e5，然后检查i是否能整除N。一旦找到i，那么另一个因数就是N/i。 但需要注意，sqrt_N可能并不是整数，所以当i超过sqrt_N时，i的平方可能超过N。例如，当i是sqrt_N +k，而k较大时，i可能超过sqrt(N)的真实值，导致i * (i -d)超过N。这可能不会发生，但遍历时只要找到i能整除N即可，不管i的大小。 或者，另一种方法是，从i=1到sqrt(N)遍历，但这样的话，当N很大时，时间会不够。但根据题目条件，p和q的差很小，所以应该集中在sqrt_N附近，所以遍历附近的区域是更高效的。 综上，正确的做法是： 遍历i从sqrt_N - 2e5到 sqrt_N +2e5的范围内的所有整数，检查是否能整除N。一旦找到，就分解成功。 例如，在C代码中： long long p = 0; long long q = 0; for (long long i = sqrt_N - 2e5; i <= sqrt_N + 2e5; ++i) { if (i <=0 ) continue; if (N % i == 0) { p = i; q = N / i; break; } } 这样就能找到p和q。但这里需要注意的是，i的范围必须大于0，否则会导致错误。 或者，更高效的是，从sqrt_N开始，向两边找，比如先找到最大的因数。例如，从sqrt_N开始，向下遍历，直到找到i能整除N。因为较大的因数可能离sqrt_N更近，所以这样可能更快找到。 比如，在代码中，可以这样： long long find_p(long long N) { long long sqrt_N = (long long)sqrt(N); for (long long i = sqrt_N; i >= sqrt_N - 2e5; --i) { if (i <=0) continue; if (N % i ==0) { return i; } } for (long long i = sqrt_N +1; i <= sqrt_N + 2e5; ++i) { if (N %i ==0) { return i; } } return -1; // 理论上不会发生 } 这样，先向下找，如果没找到，再向上找。这样可以优先找到较大的因数p，或者较小的因数q，取决于具体情况。 不过，不管如何，只要遍历的范围足够覆盖可能的因数，就可以正确找到p和q。 假设在样例输入中，N=293000179499792623。它的平方根大概是约 541,000,000的平方等于 541e6的平方是约 2.928e17，但可能计算更准确的值。例如，在样例输入中，p和q可能是 541,000,000附近的质数。或者，可能正确的p和q的差是小于等于2e5的。一旦找到其中一个因数，另一个因数就可以计算出来。 所以，在代码中，找到p之后，q=N/p。然后计算phi(N)=(p-1)*(q-1)。接下来计算d=mod_inverse(e, phi)。然后用快速幂计算c^d mod N得到m。 那现在，编写代码的思路已经明确。接下来需要考虑可能的错误点。 例如，sqrt(N)的计算是否正确？当N很大时，浮点数的精度是否足够？ 例如，当N接近1e18时，sqrt(N)的浮点计算可能会有精度误差。例如，当使用double类型的sqrt函数时，其有效位数大约为15~16位，而1e18有19位，所以这时候用sqrt函数得到的值可能不够精确，导致i的初始值错误。 例如，假设N是一个很大的数，其平方根是某个整数k，但是因为double的精度问题，导致k被计算为k-1或者k+1。这时，直接取整后的sqrt_N可能比实际的平方根小或者大。 这会导致后续遍历的范围不正确，从而无法找到正确的因数。 为了解决这个问题，应该使用更精确的方法计算sqrt(N)的整数部分。例如，使用二分法来找最大的i，使得i*i <=N。 这样，我们可以避免浮点数精度的问题。 例如，编写一个函数来计算sqrt(N)的整数部分： long long sqrt_int(long long N) { long long low = 0, high = 1e9 +1; // 因为N最大是1e18，所以sqrt是1e9左右 while (low <= high) { long long mid = (low + high) /2; if (mid * mid <= N) { low = mid +1; } else { high = mid -1; } } return high; } 这样，得到的high就是最大的整数，满足high^2 <=N。这样得到的sqrt_N更精确，不会有浮点数精度的问题。 所以，在代码中，应该用二分法来计算sqrt_N的值，而不是直接用sqrt函数。 例如，原来的sqrt_N计算方式可能有问题，比如： long long sqrt_N = (long long)sqrt(N); 当N很大时，sqrt的精度可能不够，导致得到的sqrt_N可能比实际的小或大。例如，假设N= (1e9 + 1)^2，这时候sqrt(N)会被计算为1e9，而正确的sqrt_N应该是1e9+1。这时候，用上述二分法得到的sqrt_N是正确的，而浮点数可能错误。 因此，正确的做法是使用二分法来找到sqrt_N的整数部分。 所以，代码中的sqrt_N计算应该改用二分法。这样，无论N多大，都能正确得到sqrt(N)的整数部分。 然后，遍历的范围是从sqrt_N - 2e5到 sqrt_N + 2e5吗？或者因为p和q的差不超过2e5，所以其中一个因数必然在sqrt_N附近，所以遍历这个范围就能找到。 例如，假设p和q的差是d，那么当p和q接近sqrt(N)时，最大的因数q是大约sqrt(N) + d/2，而较小的因数p是sqrt(N) -d/2。所以，当d<=2e5时，p和q分别位于sqrt_N的左右各约1e5的位置。因此，遍历的范围应该足够覆盖这个区域。 因此，在代码中，正确的做法是： 使用二分法找到sqrt_N的整数部分，然后从sqrt_N - 1e5开始，到sqrt_N +1e5结束，遍历每个i，检查是否是N的因数。或者，更准确地说，遍历i从sqrt_N - 2e5到 sqrt_N + 2e5，因为p和q的差可能达到2e5，所以其中一个因数可能离sqrt_N更远。 或者，假设p <= q，那么 q - p <=2e5，那么 q = p +d，其中d <=2e5。此时，N = p*(p +d). 所以，p的平方 +d*p =N. 这可以转化为p的方程，但解这个方程可能比较复杂，不如遍历更简单。 综上，正确的步骤是： 1. 用二分法找到sqrt_N的整数部分。 2. 遍历i从sqrt_N - 2e5到 sqrt_N +2e5，检查每个i是否能整除N。 3. 一旦找到i，p=i，q=N/i。 4. 计算phi=(p-1)*(q-1)。 5. 计算d=mod_inverse(e, phi)。 6. 计算m=qmi(c,d,N)。 7. 输出m. 这样，就能正确得到结果。 现在，需要考虑代码的具体实现。 例如，如何实现二分法求sqrt_N： long long sqrt_int(long long N) { long long low = 0, high = 1e9 + 1e5; // 因为sqrt(1e18)=1e9，所以适当增加high的上限 while (low <= high) { long long mid = (low + high) /2; // 计算mid*mid是否超过LLONG_MAX？对于N=1e18，mid最多是1e9，mid^2是1e18，对于long long来说可能刚好不溢出。 // 但此时如果N是1e18，则mid=1e9，mid*mid=1e18等于N。当mid超过一定值时，mid*mid可能溢出。 // 因此，应该用除法来比较。例如，如果 mid > N/mid，说明mid^2>N → high=mid-1. if (mid > N / mid) { // 防止溢出 high = mid -1; } else { low = mid +1; } } return high; } 这样，在计算mid是否超过sqrt(N)时，使用除法而不是乘法，可以避免溢出。 这样得到的sqrt_int函数更可靠。 接下来，遍历i的范围是sqrt_int(N) - 2e5到 sqrt_int(N) +2e5。对于每个i，如果i大于0且i <=N，并且N%i ==0，则得到p=i，q=N/i。 需要注意的是，当i超过N的平方根时，此时N/i会小于i，因此，当遍历到较大的i值时，得到的因数可能小于sqrt_N。但因为题目中给出的条件是p和q的差不超过2e5，所以在这种情况下，较大的因数可能离sqrt_N较近，所以遍历sqrt_N附近的较大范围即可。 例如，当p和q的差是2e5时，那么较大的因数q= p+2e5。那么，此时p ≈ sqrt(N) -1e5，而q ≈ sqrt(N)+1e5。所以，遍历的范围应该覆盖这两个值。 现在，编写完整的C代码： #include <stdio.h> #include <stdlib.h> long long sqrt_int(long long N) { if (N ==0) return 0; long long low = 1, high = N; while (low <= high) { long long mid = (low + high) /2; if (mid > N / mid) { high = mid -1; } else { low = mid +1; } } return high; } long long extended_gcd(long long a, long long b, long long *x, long long *y) { if (a == 0) { *x = 0; *y = 1; return b; } long long x1, y1, gcd = extended_gcd(b % a, a, &x1, &y1); *x = y1 - (b / a) * x1; *y = x1; return gcd; } long long mod_inverse(long long e, long long phi) { long long x, y, gcd = extended_gcd(e, phi, &x, &y); if (gcd != 1) return -1; x = (x % phi + phi) % phi; return x; } long long qmi(long long c, long long d, long long N) { long long res = 1 % N; while (d) { if (d & 1) res = (__int128)res * c % N; c = (__int128)c * c % N; d >>=1; } return res; } int main() { long long e, N, c; scanf("%lld %lld %lld", &e, &N, &c); long long sqrt_N = sqrt_int(N); long long p = -1; for (long long i = sqrt_N; i >= sqrt_N - 2e5 && i >=1; --i) { if (N % i ==0) { p = i; break; } } if (p == -1) { for (long long i = sqrt_N +1; i <= sqrt_N + 2e5; ++i) { if (N %i ==0) { p = i; break; } } } long long q = N / p; long long phi = (p-1)*(q-1); long long d = mod_inverse(e, phi); long long m = qmi(c, d, N); printf("%lld\n", m); return 0; } 这样，在遍历的时候，首先从sqrt_N向下找，直到sqrt_N -2e5或者直到找到因数。如果没找到，再在sqrt_N +1到sqrt_N+2e5范围内找。这样可以覆盖所有可能的因数，因为题目保证存在这样的p和q，所以一定能找到。 测试样例输入： 65537 293000179499792623 13189131411060906 输出的m是114514。 假设正确的p和q是sqrt_N附近的数。比如，假设sqrt_N是541000000左右的数，而p和q差不超过2e5。 可能的错误点： 1. 在计算sqrt_N时，用二分法是否正确？ 例如，当N是某个完全平方数时，sqrt_int函数返回正确的值。否则，返回的是最大的整数i，使得i² <=N。这可能比实际的平方根小。例如，如果N= (p)*(q)，其中p和q接近sqrt(N)，那么sqrt_N的整数值可能比p小，所以向下遍历的时候可能找不到p，需要向上遍历。 所以，在代码中，当在向下遍历的循环中没有找到因数时，需要继续向上遍历。例如，原代码中的循环： 首先，向下遍历从sqrt_N到 sqrt_N-2e5。如果没找到，则向上遍历从sqrt_N+1到sqrt_N+2e5。 这样，确保覆盖了可能的因数位置。 例如，在样例输入中，假设sqrt_N是541000000，而正确的p是541000000 -x，而q是541000000 +x，其中x的值较小。或者，可能p和q的其中一个位于sqrt_N附近，所以遍历能够找到。 综上，代码应该是正确的。 另一个可能的错误是，当p和q的差非常大，比如接近2e5时，可能遍历的范围不够。例如，假设p = sqrt_N -1e5， q = p +2e5。那么，sqrt_N是大约(p+q)/2。当p和q的差是2e5时，sqrt_N = (p + q)/2 = (p + p +2e5)/2 = p +1e5. 所以，p= sqrt_N -1e5， q = sqrt_N +1e5. 所以，在遍历sqrt_N -2e5到 sqrt_N +2e5的范围时，p位于sqrt_N -1e5，所以向下遍历时，可能i从sqrt_N开始，一直到sqrt_N -2e5，这时候i的范围包括sqrt_N -1e5吗？比如，sqrt_N -2e5可能小于 p。例如，假设sqrt_N是1e9，那么sqrt_N -2e5= 1e9 -200000= 999800000。而p是1e9 -1e5= 999900000。那么，在向下遍历时，i从1e9开始，直到999800000，那么i=999900000会被遍历到吗？ 是的，例如，当i从sqrt_N=1e9开始，逐步减到sqrt_N -2e5= 1e9 -200000=999800000。这时候，i=999900000是位于这个范围内的。所以，在遍历时会检查到i=999900000是否是因数。这样，就能找到正确的p。 所以，遍历的范围是足够的。 综上，该代码应该能够正确解决问题。</think>要解决这个问题，我们需要利用RSA密码系统的漏洞，即已知两个质数p和q的差较小（|p−q| ≤2×10^5），从而快速分解N=pq，恢复私钥并解密得到明文m。以下是详细步骤： ### 解决思路 1. **分解N**：由于p和q的差值较小，可以围绕N的平方根附近遍历寻找p和q。通过二分法精确计算N的平方根整数部分，并在其附近一定范围内遍历可能的因数。 2. **计算φ(N)**：得到p和q后，计算φ(N) = (p-1)(q-1)。 3. **计算私钥d**：利用扩展欧几里得算法求e关于φ(N)的模逆元d。 4. **解密c**：使用快速幂算法计算m = c^d mod N。 ### 解决代码 ```c #include <stdio.h> long long sqrt_int(long long N) { if (N == 0) return 0; long long low = 1, high = N; while (low <= high) { long long mid = (low + high) / 2; if (mid > N / mid) { high = mid - 1; } else { low = mid + 1; } } return high; } long long extended_gcd(long long a, long long b, long long *x, long long *y) { if (a == 0) { *x = 0; *y = 1; return b; } long long x1, y1, gcd = extended_gcd(b % a, a, &x1, &y1); *x = y1 - (b / a) * x1; *y = x1; return gcd; } long long mod_inverse(long long e, long long phi) { long long x, y, gcd = extended_gcd(e, phi, &x, &y); if (gcd != 1) return -1; x = (x % phi + phi) % phi; return x; } long long qmi(long long c, long long d, long long N) { long long res = 1 % N; while (d) { if (d & 1) res = (__int128)res * c % N; c = (__int128)c * c % N; d >>= 1; } return res; } int main() { long long e, N, c; scanf("%lld %lld %lld", &e, &N, &c); long long sqrt_N = sqrt_int(N); long long p = -1; // 向下搜索 for (long long i = sqrt_N; i >= sqrt_N - 2e5 && i >= 1; --i) { if (N % i == 0) { p = i; break; } } // 向上搜索 if (p == -1) { for (long long i = sqrt_N + 1; i <= sqrt_N + 2e5; ++i) { if (N % i == 0) { p = i; break; } } } long long q = N / p; long long phi = (p - 1) * (q - 1); long long d = mod_inverse(e, phi); long long m = qmi(c, d, N); printf("%lld\n", m); return 0; } ``` ### 代码解释 1. **sqrt_int函数**：使用二分法计算N的平方根整数部分，避免浮点精度问题。 2. **因数分解**：在sqrt(N)附近±2e5范围内遍历，寻找N的因数p和q。 3. **扩展欧几里得算法**：用于求模逆元，得到私钥d。 4. **快速幂算法**：高效计算大指数模运算，恢复明文m。 ###