2^x mod 11=9，x咋计算，除了穷举法，有没有啥快捷的方法
这不是离散对数么？用shor算法吧。
■网友
根据小学时候的奥数经验，这个应该是循环的吧，余数1,2,4,8,5,10,9,7,3,6,1,2,4,8.....
■网友
#include \u0026lt;stdio.h\u0026gt;
#include \u0026lt;math.h\u0026gt;
bool a;
int p,len;
void prime()
{
int i,j,k;
for(i=0;i\u0026lt;150;i++)
for(k=2*i+3,j=k*i+k+i;j\u0026lt;30000;j+=k)
a=1;
p=2;
len=1;
for(i=0;i\u0026lt;30000;i++)
if(!a)
p=(i\u0026lt;\u0026lt;1)+3;
}
int phi(int n)
{
int d,i,ans;
d=(int)sqrt(n);
ans=n;
for(i=0;i\u0026lt;len\u0026amp;\u0026amp;p\u0026lt;=d;i++)
if(n%p==0)
{
ans=ans/p*(p-1);
while(!(n%p))
{
n/=p;
}
}
if(n!=1)
ans=ans/n*(n-1);
return ans;
}
int mod(int x,int n,int p)
{
int ans=1;
while(n)
{
if(n\u0026amp;1)ans=(ans*(x%p))%p;
x=((x%p)*(x%p))%p;
n\u0026gt;\u0026gt;=1;
}
return ans;
}
int main()
{
prime();
int n = 11,i,x,t,temp;
x=phi(11);
\tt=x;
for(i=0;i\u0026lt;len\u0026amp;\u0026amp;p\u0026lt;t;i++)
{
【2^x mod 11=9，x咋计算，除了穷举法，有没有啥快捷的方法】 if(x%p==0)
{
temp=mod(2,x,11);
while(temp==9\u0026amp;\u0026amp;x%p==0)
{
x/=p;
temp=mod(2,x,11);
}
if(temp!=9)x*=p;
}
}
printf("2^%d mod %d = 9\",x,n);
return 0;
}
■网友
离散对数，我只会Baby step giant step。
推荐阅读
- 有啥方法，网站，项目可以自己练习计算广告学
- 汽车知识|试驾了一周的全新蔚来ES8，我卖掉了我的Model X
- 盖世汽车资讯|前十月全球电动车销量榜：特斯拉Model 3遭遇劲敌
- 大部分黑客或安全研究员读的是啥「大学专业 」
- 在哈尔滨工业大学计算机系就读是啥样的体验
- 计算机技术与科学专业怎样利用高中毕业的暑假
- 非计算机专业想要利用课余时间深入自学C++，想要找到比较体面的工作大概需要啥水平
- 特斯拉|五十步笑百步！特斯拉量产新电池，25万买的model3也将挨割
- 「巧克力中富含黄烷醇，能够增强脑部活动能力；因此人均巧克力消费量越高的国家，按人口平均计算的诺贝尔奖得主人数就越多。」这种说法科学么
- 有点计算机基础的人想尽快找份编程的工作。哪种编程的工作最好找还需要学些啥