設
定理1:
定理2: 是合數
本來 定義的式子,即使說它是設出來的,但也會很奇怪它為什麼要這麼設。不少人可以看出來,確實 就是641。如果我們知道了 以及 ,其實湊都能湊出來了。只不過我們是透過因式分解驗證而不是除法驗證而已。另外,只是證明是否是合數倒可以考慮同餘,但是要完全找到這些因子是十分困難的。
另外 是有定理基礎的,對於 來說,這個定理的數字很恰當:
引理:若 是費馬數 的素因子,則 形如 。
,即 的素因子是一個 。
此外
因此,普通地判斷大概需要判斷將近512(實際上是511)個數,不過另外的同時也要判斷 是否為素數,總的判斷量其實在可觀範圍內是少的,不過這隻限於 。
可以看見,實際上判斷第一個是 ,下一個就是熟悉641了,但它剛好就撞到了,它正是 的素因子。
不過有些比較有趣的地方:
若
另外設 成立。
可見要想整個式子能夠提取出 ,則 ,即 為偶數。那麼到底什麼的 , 與 能夠使得 這些都成立?
關於不知道 =641 的前提下:
此前我想透過哪種花式方法來確切地求出641,比如連分數因式法。但是這個不行,如果你嘗試使用它會出現這樣的情況:
這意味著
且得到
整個 的簡單連分數大概長這個樣子:
特別地,要利用連分數因式分解需要考慮 的 序列,
但可發現, ,從而根據 ,並取 為1:
這個和沒求一個樣,以上說明連分數因式法行不通。事實上連分數是幹不了滿足 的N的。關於連分數因式的修正與改進,我待查詢相關文獻,如果未來不小心看到了的話會補上。
另外可以透過偽素數的素性檢驗來判斷 是否是素數(如最簡單的費馬小定理或者擴充套件的米勒拉賓)。這個其他答主已經回答了,不過注意需要確切知道 不是Carmichael數。畢竟偽素數素性檢驗演算法並不具備逆命題,且就體現在Carmichael數上。雖然不記前提下可以首先把那些Carmichael數全部找出。
我另外給出一個比較騷的解法,也許還是需要計算機的。
波拉德ρ演算法(被算作一個蒙特卡羅演算法):
令
在 中隨機選擇一個數 ,不妨取450。記 ,並遞迴定義 即 。
得到
則若 ,則 是 的一個因數。
注: 是指 與 最大公因數。
,另外如果你的 選得夠好的話,這個所需步驟會有所變化,總之是步驟有限(有上界)但效率隨機的演算法。對了,這個期望效率是比偽素數的素性檢驗演算法(相比之米勒拉賓素檢法)慢的,甚至是遠比之慢。這個屬於把具有的可能的因數找出的演算法。
另外傳統上流行這麼一種完整的素數判定(準確說是因數分解)過程:
參考文獻:
[1]《Elementary Number Theory and Its Applications》(6th)--Kenneth H.Rosen
設
定理1:
證:由 得到 另外 從而 ,證畢。定理2: 是合數
證: 且易證 是整數且不為 ,從而 整除 ,即 是 的因子。從而 不是素數,證畢。本來 定義的式子,即使說它是設出來的,但也會很奇怪它為什麼要這麼設。不少人可以看出來,確實 就是641。如果我們知道了 以及 ,其實湊都能湊出來了。只不過我們是透過因式分解驗證而不是除法驗證而已。另外,只是證明是否是合數倒可以考慮同餘,但是要完全找到這些因子是十分困難的。
另外 是有定理基礎的,對於 來說,這個定理的數字很恰當:
引理:若 是費馬數 的素因子,則 形如 。
,即 的素因子是一個 。
此外
因此,普通地判斷大概需要判斷將近512(實際上是511)個數,不過另外的同時也要判斷 是否為素數,總的判斷量其實在可觀範圍內是少的,不過這隻限於 。
可以看見,實際上判斷第一個是 ,下一個就是熟悉641了,但它剛好就撞到了,它正是 的素因子。
不過有些比較有趣的地方:
若
另外設 成立。
可見要想整個式子能夠提取出 ,則 ,即 為偶數。那麼到底什麼的 , 與 能夠使得 這些都成立?
關於不知道 =641 的前提下:
此前我想透過哪種花式方法來確切地求出641,比如連分數因式法。但是這個不行,如果你嘗試使用它會出現這樣的情況:
這意味著
且得到
整個 的簡單連分數大概長這個樣子:
特別地,要利用連分數因式分解需要考慮 的 序列,
但可發現, ,從而根據 ,並取 為1:
這個和沒求一個樣,以上說明連分數因式法行不通。事實上連分數是幹不了滿足 的N的。關於連分數因式的修正與改進,我待查詢相關文獻,如果未來不小心看到了的話會補上。
另外可以透過偽素數的素性檢驗來判斷 是否是素數(如最簡單的費馬小定理或者擴充套件的米勒拉賓)。這個其他答主已經回答了,不過注意需要確切知道 不是Carmichael數。畢竟偽素數素性檢驗演算法並不具備逆命題,且就體現在Carmichael數上。雖然不記前提下可以首先把那些Carmichael數全部找出。
我另外給出一個比較騷的解法,也許還是需要計算機的。
波拉德ρ演算法(被算作一個蒙特卡羅演算法):
令
在 中隨機選擇一個數 ,不妨取450。記 ,並遞迴定義 即 。
得到
則若 ,則 是 的一個因數。
注: 是指 與 最大公因數。
,另外如果你的 選得夠好的話,這個所需步驟會有所變化,總之是步驟有限(有上界)但效率隨機的演算法。對了,這個期望效率是比偽素數的素性檢驗演算法(相比之米勒拉賓素檢法)慢的,甚至是遠比之慢。這個屬於把具有的可能的因數找出的演算法。
另外傳統上流行這麼一種完整的素數判定(準確說是因數分解)過程:
小素數範圍(比如10000以內),直接查表判斷。較大數(比如>10000,但長度小於15的),透過波拉德ρ演算法分解。更大的數(比如長度有幾十位甚至幾百位的),透過二次篩法,橢圓曲線或數域篩法。參考文獻:
[1]《Elementary Number Theory and Its Applications》(6th)--Kenneth H.Rosen