计算勒让德符号（legendre symbol）代码实现（含运行结果） |
您所在的位置：网站首页 › 151实现函数 › 计算勒让德符号（legendre symbol）代码实现（含运行结果） |
计算勒让德符号（legendre symbol）代码实现（含运行结果）
|
勒让德符号，或二次特征，是一个由阿德里安-马里·勒让德在1798年尝试证明二次互反律时引入的函数。 勒让德符号定义如下：
即，如果(a|p) = 1，a便称为二次剩余(modp)；如果(a|p) = −1，则a称为二次非剩余(mod p)。通常把零视为一种特殊的情况。 legendre符号的计算公式如下：
legendre符号快速计算的参考算法如下：
以下是legendre符号计算的C语言代码实现： #include int ee(int &a){ int e=0; while(a%2==0){ a=a/2; e++; } return e; } int L_FAST(int a,int p) { int s; if(a==0){ return 0; }else if(a==1){ return 1; }else{ if(ee(a)%2==0){ s=1; }else{ if(p%8==1||p%8==7){ s=1; } if(p%8==3||p%8==5){ s=-1; } } if(p%4==3&&a%4==3){ s=-s; } int p1=p%a; if(a==1){ return s; }else{ return s*L_FAST(p1,a); } } } int main(){ int a,p,L; printf("请依次输入整数a，奇素数p>=3，且0 |
【本文地址】
今日新闻 |
推荐新闻 |