[科普中国]-循环节

如果无限小数的小数点后，从某一位起向右进行到某一位止的一节数字循环出现，首尾衔接，称这种小数为循环小数，这一节数字称为循环节。 把循环小数写成个别项与一个无穷等比数列的和的形式后可以化成一个分数。

研究背景

对一个大整数求倒数，用牛顿法可以快速达到很高的精度，但需要的空间很大。如果求一个10^300数量级的质数p的倒数，其循环节长度有可能达到p-1，没有一台计算机的内存能够储存整个循环节的数据。如果用普通的除法，只需储存余数，占用的内存不大，可却可能要计算p-1次，不可能算完。则只要有循环节的长度就可以，不用输出循环节的内容，这种方法解决了这个问题。

另外，这个问题的另一种描述是：给定大整数n（可能是质数也可能是合数,且不知道这个数的分解形式），求最小的k使10^k ≡1 (mod n),对a^k ≡1 (mod n)，若n与a互素,求分母n的欧拉函数值ψ(n).那么循环节长度k必是ψ(n)的约数；若n与a有公因子，显然无解。根据这个性质，对每个约数试验就可以了。

ψ(n)的求法：

设n=p1^c1*p2^c2*...*pk^ck（pi为素数），

那么ψ(n)=(p1-1)*p1^(c1-1)*(p2-1)*p2^(c2-1)*...*(pk-1)*pk^(ck-1)。

因此求ψ(n)与将n因数分解密切相关，如果n有300位的话，对300位数分解是困难的。当然,以上只是对a^k ≡1 (mod n)（a为与n互素的任意数）形式来讨论的。如果a=2，可能有更好的办法。

事实上提出这个问题的初衷，是发现大数分解问题可以转化为求一个大数的倒数的循环节的长度

给定n，在RSA加密中，n肯定是两个质数的积。设n=p*q，此时1/n的循环节的长度l|gcd(p-1,q-1)。

假定知道l的因数分解，l=l(1)^c(1）*l(2)^c(2)*...*l(k)^c(k)，则l有∏[c(i)+1]个约数，将这些约数分别加上1，如果某个约数y(j)加一后是质数，则y(j)+1有可能是n的约数。对所有