標籤:小數循環小數

如果無限小數的小數點后,從某一位起向右進行到某一位止的一節數字循環出現,首尾銜接,稱這種小數為循環小數,這一節數字稱為循環節. 把循環小數寫成個別項與一個無窮等比數列的和的形式后可以化成一個分數.

1長度

對一個大整數求倒數,用牛頓法可以快速達到很高的精度,但需要的空間很大,如果求一個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次轉換,就可以完成分解

2其他信息

當然,上述設想完全是建立在存在一種高效演算法求1/n的循環節長度l的情況下,如果除了Ψ(n)的方法之外,沒有別的方法,那麼上述設想大概毫無價值,提此問題正是為了尋找一種新的方法,不依靠ψ(n),快速求l

3表示方法

小數化分數分成兩類。
一類:純循環小數化分數,循環節做分子;連寫幾個九作分母,循環節有幾位寫幾個九。例:0.3(3循環)=3/9(循環節的位數有一個,所以寫一個9)
0.347(347循環)=347/999(3位循環節寫3個9)
另一類:混循環小數化分數(問題就是這類的),小數部分減去不循環的數字作分子;連寫幾個9再緊接著連寫幾個0作分母,循環節是幾個數就寫幾個9,不循環(小數部分)的數是幾個就寫幾個0。例0.2134(34循環)=(2134-21)/9900
問題中1.203(03循環)=1+0.203=1+(203-2)/990

4循環小數

如3.43535……是無限循環小數,可以簡寫為3.435(35循環),它的循環節是35。
上一篇[混合層聲道]    下一篇 [保險單]

相關評論

同義詞:暫無同義詞