| 語言 : |
|
| 百科社區 |百科問答 |提交問題 |詞彙知識 |上傳知識 |
循環節 |
 |
|
如果無限小數的小數點後，從某一位起向右進行到某一位止的一節數字循環出現，首尾銜接，稱這種小數為循環小數，這一節數字稱為循環節．把循環小數寫成個別項與一個無窮等比數列的和的形式後可以化成一個分數． 長度 對一個大整數求倒數,用牛頓法可以快速達到很高的精度,但需要的空間很大,如果求一個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/n的循環節長度l的情況下,如果除了Ψ(n)的方法之外,沒有別的方法,那麼上述設想大概毫無價值,提此問題正是為了尋找一種新的方法,不依靠ψ(n),快速求l 表示方法 小數化分數分成兩類。 一類：純循環小數化分數，循環節做分子；連寫幾個九作分母，循環節有幾位寫幾個九。例：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 循環小數 如3.43535……是無限循環小數，可以簡寫為3.435（35循環），它的循環節是35。 |
| 用戶 評論 |
|
還沒有評論 |
