注册 登录
编程论坛 C++教室

求二次同余式:x 2≡a (mod p), p为素数

jeffzeng 发布于 2010-06-15 10:27, 535 次点击
写一个程序,各位大虾帮我改改我的程序
#include   <iostream>
#include <math.h>
using   namespace   std;

int   one(int   m)
{
  
if(   m%4   ==   1   ) return   1;
if(   m%4   ==   3   ) return   -1;

}

int   two(int   m)
{

if(   m%8   ==   1   ||   m%8   ==   7   ) return   1;

if(   m%8   ==   3   ||   m%8   ==   5   ) return   -1;

}


int   main()
{

int   m,   p,   q,   s,   t,     mul=1,i,n;

cout   <<   "请输入一个奇素数   p   和一个与它互素的正整数   m   :\n\n ";
cout    <<   "p   =   ";
cin     >>   p;   
cout   <<   "m   =   ";
cin     >>   m;
cout   <<   endl;

s=m;   t=p;

loop: if(   m> p   )
{
m%=p;

}

while(   m%2   ==   0   )
{
m/=2;
mul*=two(p);
}

if(   m   ==   -1   )
{
mul*=one(p);
goto   mark;
}

if(   m   ==   1   )
{
goto   mark;
}

q=p;   p=m;   m=q;

if(   (p-1)*(m-1)%8   )
{
mul*=-1;
}

goto   loop;

mark: cout   <<   "雅可比符号   ( ";
cout   <<   s   <<   "   /   "   <<   t;
cout   <<   "   )   的值为\t "   <<   mul   <<   endl   <<   endl;

if(mul==1)
{
cout   <<   "因此 "   <<   s   <<   "为模 "   <<   t   <<   "的二次剩余 "     <<   endl;
for(i=1;;i++){
n=sqrt(p*i+m);
if(n==(int)n)break;
}
cout<<n<<endl;

}

else   
{
cout   <<   "因此 "   <<   s   <<   "不是模 "   <<   t   <<   "的二次剩余 "     <<   endl;
}

return   0;

}

0 回复
1