bmxskb 发表于 2015-5-26 15:37:08

2模p的阶

小白求助，希望大神帮帮忙啊！
P是一个比较大数，如何快速求的2模p的阶？

kastin 发表于 2015-5-26 16:56:46

你是指手动计算还是指计算机算法？

若是后者，只需计算出p的欧拉函数值，并找出该值的所有因子，并分别以之作为底数2的指数模p，若与1同余，则该指数就是2模p的乘法阶数。

为此，你需要实现三个算法，1.欧拉函数计算；2.因子分解；3.模幂运算。

方便的话自己用Mathematica调用函数就能瞬间得到结果。

bmxskb 发表于 2015-5-26 19:05:51

kastin 发表于 2015-5-26 16:56
你是指手动计算还是指计算机算法？

若是后者，只需计算出p的欧拉函数值，并找出该值的所有因子，并分别 ...

谢谢，如果p是两个大素数的乘积呢，有办法快速求得吗

kastin 发表于 2015-5-26 19:13:25

bmxskb 发表于 2015-5-26 19:05
谢谢，如果p是两个大素数的乘积呢，有办法快速求得吗

那更简单啊，只要你给出这两个素数，那么欧拉函数值有直接的简单公式，然后其因子分解就简单了，接着剩下只需要处理模幂运算即可，网上有高速算法。

bmxskb 发表于 2015-5-26 20:45:09

kastin 发表于 2015-5-26 19:13
那更简单啊，只要你给出这两个素数，那么欧拉函数值有直接的简单公式，然后其因子分解就简单了，接着剩下 ...

是我没说清楚，不好意思，主要是不知道这两个素数，因该怎么做啊？

bmxskb 发表于 2015-5-26 21:31:02

bmxskb 发表于 2015-5-26 20:45
是我没说清楚，不好意思，主要是不知道这两个素数，因该怎么做啊？

2的二进制比较特殊，是否能从这上面突破?

bmxskb 发表于 2015-5-26 21:32:13

kastin 发表于 2015-5-26 19:13
那更简单啊，只要你给出这两个素数，那么欧拉函数值有直接的简单公式，然后其因子分解就简单了，接着剩下 ...

2的二进制比较特殊，是否能从这上面突破?
页: [1]
查看完整版本: 2模p的阶