跳至內容

更大篩法

維基百科,自由的百科全書

在數論中,更大篩法(larger sieve)是一個由派屈克·X·加拉格爾英語Patrick X. Gallagher發明的篩法,其名稱表明這是一種大篩法塞爾伯格篩法之類的組合篩法在只移除數個同餘類時能得到最強的結果;而大篩法之名表明了這類的篩法能移除大量、多達半數的同餘類;而更大篩法則是一個可移除任意多同餘類的篩法。

描述

假定是一個質數及其冪次所組成的集合、是一個整數、該區間當中的整數的集合,且對於而言,至多只有個包含的元素的模同餘類的話,那麼有以下關係式:

上式中,右側的分母為正數。[1]

應用

根據加拉葛的結果,更大篩法用於下列大篩法失效的狀況,尤其適用於的狀況:[2]

使得對所有質數而言,的階的數的數量。

假若排除掉的模同餘類的數量隨變化的話,那麼更大篩法常會與大篩法結合使用。其中更大篩法會用於如上定義的以做為許多同餘類被移除掉的集合;而大篩法則用套用在落於之外的質數上,以得這些質數的資訊。[3]

註解

  1. ^ Gallagher 1971, Theorem 1
  2. ^ Gallagher, 1971, Theorem 2
  3. ^ Croot, Elsholtz, 2004

參考資料