雅可比法.cpp

新手上路 用雅可比符号来计算勒让德符号的值 用于判断与素数p互素的正整数n是否是mod p 的二次剩余

#include <iostream>
using namespace std;


int neg_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, d, mul=1;
		
		cout << "请输入一个素数 p 和一个与它互素的正整数 m :\n\n";
		cout << "m = ";
		cin  >> m; 
		cout << "p = ";
		cin  >> p;
		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*=neg_one(p);
			goto mark;
		}

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

		q=p;p=m;m=q;
		
		if( (p-1)*(m-1)%8 != 0 )
		{
			mul*=-1;
		}
	
		goto loop;

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

}