primedlg.cpp

在密码学中判断一个数是否为素数很重要 该算法判断一个数是否为素数 c语言实现

      return (int *)k;
    }

  k[1]= a_l;    
  while (k[1]%2==0)
    {
      k[1]=k[1]/2;
      ++k[0];
    }

  return (int *)k;
}

////////////////////////////////////////////////////////////////////////
//模指数运算
unsigned long int modExpFun(long bas, int e, long m)
{
	  long p, tmpbas;
      int k = 0x40000000;             /*k用做掩码e的每个二进制数字*/

      if (m==0)                     /* 模数为0*/
        {
          return -1;         
        }

      if (m==1)                     /*模数为1*/
        {
          return 0;
        }

      if (e == 0)                     /*指数为0*/
        {
          return 0;
        }

      if (bas==0)                     /*底为0*/
        {
          return 0;
        }

      p=bas%m;
      tmpbas=p;
      while ((e & k) == 0)               /*确定指数e的首位置*/
        {
          k >>= 1;
        }

      k >>= 1;

      while (k != 0)                        
        {
          p=(p*p)%m;                 
          if ((e & k) != 0)
            {
              p=(p*tmpbas)%m;               /*乘以底数模m约化*/
            }
          k >>= 1;                             /*k用做循环计算器*/
        }
      if(p<0)                                 //返回值<0
        return (int)(p+m);
      else
        return (int)p;                     /*返回结果*/
	
}

////////////////////////////////////////////////////////////////////////////////////
//除法筛函数
int sieve_l (unsigned long int a_l,int no_of_smallprimes)
{
  unsigned long int bv,rv;
  int i = 1;

  if (a_l%2==0)
    {
      if (a_l== 2)
        {
          return 1;
        }
      else
        {
          return 2;
        }
    }

  bv = 2;
  do
    {
      rv = 0;
      bv += smallprimes[i];
      rv=a_l%bv;
    }
  while (rv != 0 && ++i < no_of_smallprimes);

  if (0 == rv)
    {
      if (a_l == bv)
        {
          bv = 1;
        }
    }
  else
    {
      bv = 0;
    }

  return bv;
}

//////////////////////////////////////////////////////////////////////////////
//二进制位数统计函数
unsigned long int bitCount(unsigned long int n_l)
{
  unsigned int l;
  unsigned long int test;

  l = (unsigned int)n_l;
  while (n_l == 0 && l > 0)
    {
      --l;
    }

  if (l == 0)
    {
      return 0;
    }

  test = n_l;
  l <<= 4U;

  while ((test & 0x8000U) == 0)
    {
      test <<= 1;
      --l;
    }

  return l;
}
////////////////////////////////////////////////////////////////////////////////////	
//概率素性检测函数，错误概率小于2^-80
int prime_l (unsigned long int n_l, int no_of_smallprimes, int iterations)
 {
  unsigned long int k,d_l,x_l, q_l;
  unsigned long int i, j, p;
  int isprime;
  int *a_t;                 
  //ModExpC Mexp = new ModExpC();

  if (n_l==1)
    {
      return 0;
    }
    
  k = sieve_l (n_l, no_of_smallprimes);
  
  if (1 == k)
    {
      return 1;
    }

  if (1 < k)
    {
      return 0;
    }
  else
    {
      if (0 == iterations)
        {
          k = bitCount(n_l);
          if      (k <   73) iterations = 37;
          else if (k <  105) iterations = 32;
          else if (k <  137) iterations = 25;
          else if (k <  197) iterations = 19;
          else if (k <  220) iterations = 15;
          else if (k <  235) iterations = 13;
          else if (k <  252) iterations = 12;
          else if (k <  273) iterations = 11;
          else if (k <  300) iterations = 10;
          else if (k <  332) iterations =  9;
          else if (k <  375) iterations =  8;
          else if (k <  433) iterations =  7;
          else if (k <  514) iterations =  6;
          else if (k <  638) iterations =  5;
          else if (k <  847) iterations =  4;
          else if (k < 1275) iterations =  3;
          else if (k < 2861) iterations =  2;
          else iterations = 1;
        }

      d_l= n_l;
      d_l--;
      a_t = twofact_l (d_l);
      k=a_t[0];
      q_l= a_t[1];
 
      p = 0;                 //以2为底开始Miller-Rabin素性检测
      i = 0;
      isprime = 1;

      do
        {
          p += smallprimes[i++];
          x_l=modExpFun(p, q_l, n_l);              //模指数运算

          if (x_l!=1)
            {

              j = 0;

              while (x_l!=1 && x_l!= d_l && ++j < k)
                {
                  x_l= (x_l*x_l)% n_l;
                  
                }

              if (x_l!=d_l)
                {
                  isprime = 0;
                }
            }

        }
      while ((--iterations > 0) && isprime!=0);
      
      return isprime;
    }
}



void CPRIMEDlg::OnClean() 
{
	// TODO: Add your control notification handler code here
	SetDlgItemText(IDC_PRIME,NULL);
}

void CPRIMEDlg::OnExam() 
{
	// TODO: Add your control notification handler code here
	unsigned long int nn;
	nn=GetDlgItemInt(IDC_PRIME);
	if (prime_l(nn,6542,0)==0)
	{
		MessageBox("不是素数!");
	}
	else 
	{
		MessageBox("是素数!");
	}
	

}