缘起

最近浏览 << 我的第一本算法书 >>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳 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 others

import (
    "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)
PASS
ok      command-line-arguments  23.885s

IPrimeTester.go

素性测试器接口

package fermat_test

type IPrimeTester interface {IsPrime(int) bool
}

tSimplePrimeTester.go

循环整除法进行素性测试,. 实现 IPrimeTester 接口

package fermat_test

import "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_test

import "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)