math - 互いに素な数を見つける

Question

私は楽しみのために RSA を実装しようとしていますが、n と素数 (pxq、p と q は 2 つの大きな素数) を見つける必要がある部分に行き詰まっています。

これを行う方法はありますか？必要のない数の余素の数以外は何も見つからないようです。

Answer 1

一様にサンプリングされた任意の 2 つの整数が互いに素である確率は~60%です。

目的の範囲内でランダムな整数を選択し、その GCD を元の数値でテストし、それらが互いに素でない場合はループ (再サンプリング) することができます。

Answer 2

#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;  
        }