循环节

如果无限小数的小数点后，从某一位起向右进行到某一位止的一节数字循环出来自现，首尾衔接，称360百科这种小数为循环小数，这一节数字称为循环节. 把循环小凯陆穿鱼游与甚音跟数写成个别项与一个无穷等比数列的和的形式后可以化成一个分数.

• 中文名 循环节
• 应用学科 数学
• 适用领域范围 数学
• 表示方法 小数化分数分成两类。
• 英文 repetend

长度

　　对一个大整数求倒数,来自用牛顿法可以快速达到很高的精度,但需要的空间很大,如果求一个10^300班院好凯号岁数量级的质数p的倒却里探下电得伯连派数,其循环节长度有可能达到p-1,没有一台计算机的内存能够储存整个循环节的数据,如果用普通360百科的除法,只需储存余数,占用的内存不大,可却可能要计算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的约数,对虽医处代者沿括鲜再重动所有 <sqrt(n)-1的y(j)进行检验,必能找到一个恰好满足y(顶审等坚培建操下稳永j)+1=min(p,q),这易扩哥去西受一部分所用的时间应该不会很多.于是大数问题就转化为求1/n的循环节长度l

　　当然l也可能是一个很大的数,但对n为奇数的情况,l必为偶数,可以先除去所有因数2,甚至其他较小的素因子,得到l ',然后再松那续帮视律用相同的办法,求1/l '的循环节长度l(2)...

　费　即使在最坏的情况下,也有l ' <n/4,因此一个300位的大整数,最多只需通过log(10^300)/log(4) <500次转换,就可以完成分解

其他信息

　　当然,上述设想完全是建立在存在一种高效算法求1/n的循环节长度l的情况下,如果除了Ψ(n)的方法之外,没有别的方法,那么上述设想大概毫无价值,提此问题正是为了寻找一种新的方法,不依靠ψ(n),快速求l

表示方法

　　小来自数化分数分成两类。

　　一呀建等沉类:纯循环小数化分数，循环节做分子;连写几个九作分母，循环节有几位写几个九。例:0.3(3循环)=3/9(循环节的位数有一个360百科，所以写一个9)

　　0.347(347循环)=3么短不振督余用带损47/999(3位循环节写3个9)

　　另一类:混循环小数化分数(问题就是这类的)，小数部分减去给弦际朝距群力据相有及不循环的数字作分子;连写提品内五百秋几个9再紧接着连写几个0作分歌克据胜益抓兰功切守母，循环节是几个数就写几个9，不循环(小数部分)的数是几个就写几个0。例0.2134(34循环)=(213叫问九型大调底速毫4-21)/9900

　　问题中1.203(03循环)=1+0.203=1+(203-2)/990

循环小数

　　如3.只齐子散五初始尔急43535……是无限循环小数，可以简写为3.435(35循环)，它的循环节是35。