千萬不要迷信規(guī)律——大反例合集-文庫吧資料
2024-08-17 14:35本頁面
【正文】 ，并沒有算出這個反例的具體值。他證明了 P243。到了 1958 年，英國數學家 C. B. Haselgrove 發(fā)現， P243。lya 猜想看上去非常合理——每個有偶數個質因子的數，必然都已經提前經歷過了“有奇數個質因子”這一步。lya 猜想。也就是說，對于任意一個大于 1 的自然數 n ，從 2 到 n 的數中有奇數個質因子的數不少于有偶數個質因子的數。1919 年，George P243。其中，10 包含偶數個質因子，其余的數都包含奇數個質因子。下面是大于 1 的正整數分解質因數后的結果：2 = 23 = 34 = 2 25 = 56 = 2 37 = 78 = 2 2 29 = 3 310 = 2 5...這種反例被稱為 Perrin 偽素數。直到 1982 年， Adams 和 Shanks 才發(fā)現第一個反例 n = 271 441 ，它等于 521 521 ，卻也能整除 f(271 441) 。如果這個規(guī)律成立的話，我們也將獲得一個效率非常高的素數檢驗方法。這個數列叫做 Perrin 數列。事實上，著名的 MillerRabin 素性測試算法就是用的這個原理。我們把這種數叫做以 2 為底的偽素數。事實上，根據 Fermat 小定理，如果 p 是素數，那么 p 一定能整除 2n 2。再后來人們發(fā)現，這個規(guī)律竟然是錯誤的。如果真是這樣的話，我們無疑有了一種超級高效的素數判定算法（ 2n 可以用二分法速算，期間可以不斷模 n ）。下面是當 n 較小的時候， n 與 2n 2 的值。以 2 為底的偽素數悲劇的是，這個猜想是錯誤的，第一個反例出現在 n = 105 的情況， x105 1 分解出來等于(x 1) (x2 + x + 1) (x4 + x3 + x2 + x + 1) (x6 + x5 + x4 + x3 + x2 + x + 1)(x8 x7 + x5 x4 + x3 x + 1) (x12 x11 + x9 x8 +
畢業(yè)設計相關推薦
鄂ICP備17016276號-1