缘起
最近浏览<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳golang练习之
素性测试, 费马测试
素性测试是判断一个自然数是否为素数的测试。素数（prime number）就是只能被1和其本身整除，且大于1的自然数。目前在加密技术中被广泛应用的RSA算法就会用到大素数，因而“素性测试”在该算法中起到了重要的作用。费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。对于任意素数p, 以及小于p的自然数n, 必然有: (n^p) % p = n,这就是"费马小定理"。依据是否满足费马小定理来判断一个数是否为素数的办法就是“费马测试”。摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一- 费马测试是素性测试的必要非充分条件
- 因为素数在所有自然数中的占比是多数, 因而面对大数区间时, 使用费马测试能够大大减速素性测试的判断
疾速幂取余
- 费马测试须要计算n的p次幂, n是任意小于p的自然数, p通常是大数, 因而计算结果十分微小, 很容易溢出
- 可依据数学定理将大数合成为屡次小数的计算: 积的余=余的积取余, 即 (ab)%p = ((a%p)(b%p)) % p
设计
- IPrimeTester: 素性测试器接口
- tSimplePrimeTester: 循环整除法进行素性测试,. 实现IPrimeTester接口
- tFermatTester: 费马测试器, 实现IPrimeTester接口
单元测试
fermat_test.go, 验证和比照循环整除法和费马测试的效率, 尤其是大于2^32以上的大整数
package othersimport ( "fmt" "learning/gooop/others/fermat_test" "testing" "time")func Test_FermatTest(t *testing.T) { fnAssertTrue := func(b bool, msg string) { if !b { t.Fatal(msg) } } fnTestPrime := func(tester fermat_test.IPrimeTester) { primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97} set := make(map[int]bool, 0) for _,v := range primes { fnAssertTrue(tester.IsPrime(v), fmt.Sprintf("expecting %v is prime", v)) set[v] = true } for i := 0;i < 100;i++ { if _,ok := set[i];!ok { fnAssertTrue(!tester.IsPrime(i), fmt.Sprintf("expecting %v is not prime", i)) } } } s := fermat_test.SimplePrimeTester f := fermat_test.FermatPrimeTester t.Log("testing SimplePrimeTester range 0-100") fnTestPrime(s) t.Log("testing FermatPrimeTester range 0-100") fnTestPrime(f) t.Log("testing range 100-100_000") for i := 100;i < 100_000;i++ { fnAssertTrue(s.IsPrime(i) == f.IsPrime(i), fmt.Sprintf("failed testing %v", i)) } fnTestCost := func(tester fermat_test.IPrimeTester, from, to int) { t0 := time.Now().UnixNano() fnAssertTrue(tester.IsPrime(2147483647), "expecting 2147483647 is prime") for i := from;i <= to;i++ { tester.IsPrime(i) } cost := (time.Now().UnixNano() - t0) / 1000_000 t.Logf("cost = %v ms", cost) } t.Log("testing SimplePrimeTester range 0xffff_fffff000 to 0xffff_ffffffff") fnTestCost(s, 0xffff_fffff000, 0xffff_ffffffff) t.Log("testing FermatPrimeTester range 0xffff_fffff000 to 0xffff_ffffffff") fnTestCost(f, 0xffff_fffff000, 0xffff_ffffffff) t.Log(f)}测试输入
因为质数在自然数中的占比是多数, 因而使用费马测试进行过滤, 能大大减速大数区间的质数筛选
$ go test -v fermat_test.go === RUN Test_FermatTest fermat_test.go:34: testing SimplePrimeTester range 0-100 fermat_test.go:36: testing FermatPrimeTester range 0-100 fermat_test.go:39: testing range 100-100_000 fermat_test.go:54: testing SimplePrimeTester range 0xffff_fffff000 to 0xffff_ffffffff fermat_test.go:51: cost = 23752 ms fermat_test.go:57: testing FermatPrimeTester range 0xffff_fffff000 to 0xffff_ffffffff fermat_test.go:51: cost = 6 ms fermat_test.go:59: Fermat(fail=94464, pass=9629)--- PASS: Test_FermatTest (23.88s)PASSok command-line-arguments 23.885sIPrimeTester.go
素性测试器接口
package fermat_testtype IPrimeTester interface { IsPrime(int) bool}tSimplePrimeTester.go
循环整除法进行素性测试,. 实现IPrimeTester接口
package fermat_testimport "math"type tSimplePrimeTester struct {}func newSimplePrimeTester() IPrimeTester { return &tSimplePrimeTester{}}func (me *tSimplePrimeTester) IsPrime(x int) bool { if x <= 1 { return false } if x <= 3 { return true } for i, q := 2,int(math.Floor(math.Sqrt(float64(x))));i <= q;i++ { if x % i == 0 { return false } } return true}var SimplePrimeTester = newSimplePrimeTester()tFermatTester.go
费马测试器, 实现IPrimeTester接口
package fermat_testimport "fmt"type tFermatTester struct { iFailedCount int iPassedCount int}func newFermatTester() IPrimeTester { return &tFermatTester{}}var arrSampleNum = []int{ 1,2,3,4,5,6,7,8,9 }func (me *tFermatTester) IsPrime(x int) bool { if x <= 1 { return false } if x <= 3 { return true } for i,size := 0, len(arrSampleNum);i < size;i++ { x1 := x * arrSampleNum[i] / 10 if x1 <= 1 { break } if !me.fermatTest(x1, x) { me.iFailedCount++ return false } } me.iPassedCount++ return SimplePrimeTester.IsPrime(x)}// 费马测试func (me *tFermatTester) fermatTest(n int, p int) bool { // n^p % p == n ? return n == fastMod(n, p, p)}// 疾速幂取余func fastMod(n int, p int, mod int) int { sum := 1 for p > 0 { if (p & 1) > 0 { sum = (sum * n) % mod p-- } else { p /= 2 n = (n * n) % mod } } return sum}func (me *tFermatTester) String() string { return fmt.Sprintf("Fermat(fail=%v, pass=%v)", me.iFailedCount, me.iPassedCount)}var FermatPrimeTester = newFermatTester()(end)