長度
對一個大整數求倒數,用牛頓法可以快速達到很高的精度,但需要的空間很大,如果求一個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的約數,對所有
