前面我们已经学习过了高斯引理，那么二次互反律就呼之欲出了
我们先介绍一下什么是二次互反律
假设p，q是两个奇素数，二次互反律就是要研究p对q的勒让德符号和q对p的勒让德符号之间的关系
二次互反律给出了结论：
legendre(p,q)*legendre(q,p)=(-1)^((p-1)*(q-1)/4)
我们通过证明下式来证明二次互反律，它蕴含着二次互反律
T(p,q)+T(q,p)=(p-1)*(q-1)/4
怎么证明T函数具有这样一个奇妙性质呢？
不想写太多证明的东西，看几张图片直观感受一下你就明白了，其实这个公式不太难
这是最常见的利用填矩形的方式证明，直线上方点数就是T(p,q)，下方点数就是T(q,p)
图一：T(5,3)+T(3,5)=2*3
图二 T(11,7)+T(7,11)=3*5
图片是用java绘制的，代码分享给大家：
import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JFrame;
public class test{
static int width=800,height=800,r=4,d=80;
public static void paint_point(int x,int y,Graphics g) {
x=d+d*x;
y=height-d-d*y;
g.setColor(Color.black);
g.fillOval(x-r, y-r, r<<1, r<<1);
}
public static void paint_line(int fx,int fy,int sx,int sy,Graphics g) {
fx=d+d*fx;
fy=height-d-d*fy;
sx=d+d*sx;
sy=height-d-d*sy;
g.setColor(Color.BLACK);
g.drawLine(sx, sy, fx, fy);
}
public static void label_x(int p,int q,int i,Graphics g) {
String str="["+p+"*"+i+"/"+q+"]";
int x=d*i+60,y=height-d;
g.drawString(str, x, y);
}
public static void label_y(int p,int q,int i,Graphics g) {
String str="["+p+"*"+i+"/"+q+"]";
int x=d,y=height-i*d-d;
g.drawString(str, x, y);
}
public static void main(String[] args) {
JFrame jf=new JFrame() {
public void paint(Graphics g) {
g.setColor(Color.white);
g.fillRect(0, 0, width, height);
int p=13,q=11;//在这里修改你想要的值
for(int i=1;i<=p/2;i++) {
for(int j=1;j<=q/2;j++) {
paint_point(i,j,g);
}
}
for(int x=1;x<=p/2;x++) {
label_x(q, p, x, g);
}
for(int y=1;y<=q/2;y++) {
label_y(p, q, y, g);
}
paint_line(0, 0, p, q,g);
}
};
jf.setSize(width, height);
jf.setVisible(true);
jf.setDefaultCloseOperation(3);
}
}
话题收回来，我们知道了T(p,q)+T(q,p)=(p-1)*(q-1)/4
将两边作为-1的指数，就得到了二次互反律。
有了二次互反律，我们就可以高效解决判断二次剩余的问题了
下面我们给出算法：
求a对p的勒让德符号：
利用勒让德符号的周期性，先将a取模p
将a分解素因数，保留次数为奇数的素因素{a1,a2....an}
对2，利用高斯引理的推论直接计算，对其他奇素数，利用二次互反律计算
利用勒让德符号的可乘性，返回结果的积
此算法的瓶颈还是在于分解素因数，下面给出C++代码实现
#include<iostream>
using namespace std;
//用于分解素因子
struct breaker{
int num,cur=2;
breaker(int num){
this->num=num;
}
void next(int&res,int&pow){
pow=0;res=0;
while(num%cur==0){
res=cur;
pow++;num/=cur;
}
cur++;
}
//获取下一个奇数次素因子
int get(){
int res,pow;
next(res,pow);
while(pow%2==0&&num>1){
next(res,pow);
}
return res;
}
};
//计算a对p的勒让德符号，要求p是素数,a不是p的倍数
int legendre(int a,int p){
a%=p;
breaker bk(a);
int temp=bk.get();
int res=1;
if(temp==2){
//使用高斯引理推论计算
res*=((p*p-1)&8)?-1:1;
temp=bk.get();
}
while(temp){
//使用二次互反律计算
res*=legendre(p,temp)*(((p-1)&(temp-1)&2)?-1:1);
temp=bk.get();
}
return res;
}
int main(){
cout<<legendre(137,227);
}
希望对大家有帮助！
原文：https://www.cnblogs.com/qishihaohaoshuo/p/11934843.html