math - 查找任何互质数

Question

我正在尝试实现 RSA 的乐趣，但我被困在你必须找到 n 的共同素数的部分（即 pxq，其中 p 和 q 是两个大素数）。

有没有办法做到这一点？除了我不需要的数字的互质数之外，我似乎找不到任何东西。

Answer 1

任何两个均匀采样的整数互质的概率约为 60%。

您可以简单地在所需范围内选择一个随机整数，并使用原始数字测试其 GCD，如果它们不是互质的，则循环（重新采样）。

Answer 2

我们只关心残数模n，所以有n个。只有当它是p或q（或两者）的倍数时，残差才不是n的互质数。

p是 q 的倍数，其中q是p 的倍数，其中一个（零）是两者，所以有p + q –1 个残基不与n互质，所以随机残差的机会 (从均匀分布中选择）不是互质数正好是 1/ p +1/ q –1/( pq )。由于p和q在实际使用中（而不是课堂练习）很大，因此找到非互质数的机会很小。这也意味着你已经破解了这个n的加密，因为除零以外的任何非互质数都可以让您轻松找到p和q。（应用欧几里得算法找到最大公约数。它是p或q。）

顺便说一句，您应该期望这在您的一生中不会偶然发生，因此除了通过人为构造要测试的数字或使用非常p和q的小数（在这种情况下，测试是有缺陷的，因为它无法在此代码路径上执行大数的算术）。实际上甚至没有必要对此进行测试或包含处理这种情况的代码，因为与实际（巨大的） p和q出现这种情况相比，计算机更有可能崩溃。

Answer 3

#include <stdio.h>  
 int gcd(int a,int b)  
{  
  int temp;  
  while(b!=0)  
  {  
       temp=a;  
       a=b;  
       b=temp%b;  
  }  
  return a;  
   }  
   int main()  
    {  
  int n,i,d,count;  
  count=1;  
  scanf("%d",&n);  
  for(i=2;i<n;i++)  
  {  
       d=gcd(n,i);  
       if(d==1)  
            count+=1;  
  }  
  printf("%d\n",count);  
  return 0;  
        }