Legendre符号的用途

 

 

一、     二次剩余

勒让德符号的提出的意义是判断一个数是否是模n的二次剩余，所以研究勒让德符号之前应该了解一下二次剩余。

存在x使x的平方与a MOD (p)就称a为模p的二次剩余，其中p为素数，a>0且a<p。

通过勒让德符号和雅可比符号可以判定二次剩余是否存在。

二、     勒让德符号

勒让德符号可以计算当p为素数的情况的二次剩余判别问题，而雅可比符号判定条件为a为任意整数，p为任意奇数。

高斯推导出著名的二次互反律。

通过二次互反律解决了勒让德符号的计算问题，可以通过递归调用解决计算。

三、  计算：

(1)如果a=1，则L(a,p)=1;

(2)如果a为偶数，则L(a,p)= L(a/2,p)*(-1)(p2-1)/8;

(3)如果a为奇数，且不等于1，则L(a,p)=L(p mod a,a)*(-1)(a-1)*(p-1)/4.

 

 

int Legrend(int a, int p)

{if (a == 1)

              return1;

       if (p % a== 0)

              return0;

       if (a % 2== 0)

              returnLegrend(a / 2, p) * pow(-1, (pow(p, 2) - 1) / 8);

       returnLegrend(p%a, a)*pow(-1, (a - 1)*(p - 1) / 4);}

运行结果：

四、     用途：

（1）可以判别选取的数是否为模n的二次剩余。

（2）可以判断两个大数是否被整除，即判断勒让德符号是否为0。

（3）在Feige-Fiat-Shamir身份验证体制中，由仲裁人选取一个数v，令v为模n的一个二次剩余，所以通过勒让德符号的计算，可以快速计算出勒让德符号来判别v是否符合要求。