2模p的阶

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

小白求助，希望大神帮帮忙啊！
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的二进制比较特殊，是否能从这上面突破?

账号		自动登录	找回密码
密码			欢迎注册

[求助] 2模p的阶

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

点评

点评

浏览过的版块