请教给定一个大整数(如10^300数量级),可否快速求其倒数的循环节长度
请问给定一个大整数(如10^300数量级),可否快速求其倒数的循环节长度?
对一个大整数求倒数,用牛顿法可以快速达到很高的精度,但需要的空间很大,如果求一个10^300数量级的质数p的倒数,其循环节长度有可能达到p-1,没有一台计算机的内存能够储存整个循环节的数据,如果用普通的除法,只需储存余数,占用的内存不大,可却可能要计算p-1次,不可能算完,请问有什么好的方法解决这个问题吗?只要有循环节的长度就可以,不用输出循环节的内容
这个问题的另一种描述:给定大整数n(可能是质数也可能是合数,且不知道这个数的分解形式),求最小的k使10^k ≡1 (mod n)
如果把10改成2,有什么好的算法吗?
期待高手赐教,不胜感激!
本人第一次提问,囊中羞涩只有100分,希望大家不要见怪.参与讨论者有分
------解决方案--------------------
如果n是难分解的大整数，那么a=2又能带来什么便利呢？
------解决方案--------------------
我的意思是：对于＂a为与n互素的任意数＂，我给的方法是通用的．但是，对于特殊的a，可能存在比＂通过求ψ(n)，逐个试验＂更好的算法．
对一个大整数求倒数,用牛顿法可以快速达到很高的精度,但需要的空间很大,如果求一个10^300数量级的质数p的倒数,其循环节长度有可能达到p-1,没有一台计算机的内存能够储存整个循环节的数据,如果用普通的除法,只需储存余数,占用的内存不大,可却可能要计算p-1次,不可能算完,请问有什么好的方法解决这个问题吗?只要有循环节的长度就可以,不用输出循环节的内容
这个问题的另一种描述:给定大整数n(可能是质数也可能是合数,且不知道这个数的分解形式),求最小的k使10^k ≡1 (mod n)
如果把10改成2,有什么好的算法吗?
期待高手赐教,不胜感激!
本人第一次提问,囊中羞涩只有100分,希望大家不要见怪.参与讨论者有分
------解决方案--------------------
如果n是难分解的大整数，那么a=2又能带来什么便利呢？
------解决方案--------------------
我的意思是：对于＂a为与n互素的任意数＂，我给的方法是通用的．但是，对于特殊的a，可能存在比＂通过求ψ(n)，逐个试验＂更好的算法．