循環節

對一個大整數求倒數，用牛頓法可以快速達到很高的精度，但需要的空間很大。如果求一個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）純循環小數化分數，循環節做分子

連寫幾個九作分母，循環節有幾位寫幾個九。例：

（循環節的位數有一個，所以寫一個9）

（3位循環節寫3個9）

（2）混循環小數化分數，小數部分減去不循環的數字作分子

連寫幾個9再緊接着連寫幾個0作分母，循環節是幾個數就寫幾個9，不循環（小數部分）的數是幾個就寫幾個0。例如，

。

判斷一個小數是否循環小數，其關鍵是首先判斷這個小數是否無限小數，其次看這個小數 的小數部分是否有重複出現的數字，但是如何正確判斷小數部分重複出現的數字，可根據以下幾點進行判斷 ^[1]  ：

方法一：按照循環小數的意義來確定。即根據“一個無限小數，如果它的小數部分從某一位起，都是由一個或者幾個數字依次不斷地重複出現，這樣的小數叫做循環小數。”這一意義來確定循環小數的循環節。例如：13÷99=0.1313……，這個商就是一個循環小數，它的循環節是13。

方法二：可以用看餘數的方法來確定循環小數的循環節。例如：11÷9=1.……2。我們通過豎式計算可看出：餘數“2”重複出現，商就重複出現，那麼循環節就是從第一次出現餘數“2”所得的商“2 ”。所以我們可以用看餘數的方法來確定循環節 ^[2]  。

如3.43535……是無限循環小數，可以簡寫為

，它的循環節是35。