网站地图
循环节

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

对一个大整数求倒数,用牛顿法可以快速达到很高的精度,但需要的空间很大。如果求一个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的约数。对所有 <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)纯循环小数化分数,循环节做分子

连写几个九作分母,循环节有几位写几个九。例:0.3(3循环)=3/9(循环节的位数有一个,所以写一个9)

0.347(347循环)=347/999(3位循环节写3个9)

(2)混循环小数化分数,小数部分减去不循环的数字作分子

连写几个9再紧接着连写几个0作分母,循环节是几个数就写几个9,不循环(小数部分)的数是几个就写几个0。例如,0.2134(34循环)=(2134-21)/9900。

判断一个小数是否循环小数,其关键是首先判断这个小数是否无限小数,其次看这个小数 的小数部分是否有重复出现的数字,但是如何正确判断小数部分重复出现的数字,可根据以下几点进行判断 [1]

方法一:按照循环小数的意义来确定。即根据“一个无限小数,如果它的小数部分从某一位起,都是由一个或者几个数字依次不断地重复出现,这样的小数叫做循环小数。”这一意义来确定循环小数的循环节。例如:13÷99=0.1313……,这个商就是一个循环小数,它的循环节是13。

方法二:可以用看余数的方法来确定循环小数的循环节。例如:11÷9=1.……2。我们通过竖式计算可看出:余数“2”重复出现,商就重复出现,那么循环节就是从第一次出现余数“2”所得的商“2 ”。所以我们可以用看余数的方法来确定循环节 [2]

如3.43535……是无限循环小数,可以简写为3.435(35循环),它的循环节是35。


相关文章推荐:
无限小数 | 小数点 | 循环小数 | 无穷等比数列 | 纯循环小数 | 混循环小数 | 牛顿法 | 精度 | 质数 | 除法 | 余数 | 内存 | 纯循环小数 | 混循环小数 | 循环小数 |
相关词汇词典