缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

素性测试, 费马测试

素性测试是判断一个自然数是否为素数的测试。
素数（prime number）就是只能被1和其自身整除，且大于1的自然数。
目前在加密技术中被广泛应用的RSA算法就会用到大素数，
因此“素性测试”在该算法中起到了重要的作用。

费马测试被称为概率性素性测试，
它判断的是“某个数是素数的概率大不大”。

对于任意素数p, 以及小于p的自然数n, 
必定有: (n^p) % p = n,
这就是"费马小定理"。

根据是否满足费马小定理来判断一个数是否为素数的方法就是“费马测试”。

摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

fermat.jpg

• 费马测试是素性测试的必要非充分条件
• 由于素数在所有自然数中的占比是少数, 因此面对大数时, 使用费马测试可以加速素性测试的计算

快速幂取余

• 费马测试需要计算n的p次幂, n是任意小于p的自然数, p通常是大数, 因此计算结果非常巨大, 很容易溢出
• 可根据数学定理将大数分解为多次小数的计算: 积的余=余的积取余, 即 (ab)%p = ((a%p)(b%p)) % p

设计

• IPrimeTester: 素性测试器接口
• tSimplePrimeTester: 循环整除法进行素性测试,. 实现IPrimeTester接口
• tFermatTester: 费马测试器, 实现IPrimeTester接口

单元测试

fermat_test.go, 验证和对比循环整除法和费马测试

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

        items := make([]int, 0)
        for i := from;i <= to;i++ {
            if tester.IsPrime(i) {
                items = append(items, i)
            }
        }
        cost := (time.Now().UnixNano() - t0) / 1000_000
        t.Logf("cost = %v ms, %v", cost, items)
    }

    t.Log("testing SimplePrimeTester range 0x7ffff000 to 0x7fffffff")
    fnTestCost(s, 0x7ffff000, 0x7fffffff)

    t.Log("testing FermatPrimeTester range 0x7ffff000 to 0x7fffffff")
    fnTestCost(f, 0x7ffff000, 0x7fffffff)
    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:58: testing SimplePrimeTester range 0xffff_fffff000 to 0xffff_ffffffff
    fermat_test.go:55: cost = 101 ms, [2147479573 2147479589 2147479601 2147479619 2147479637 2147479643 2147479657 2147479681 2147479751 2147479753 2147479757 2147479781 2147479787 2147479819 2147479823 2147479879 2147479891 2147479897 2147479907 2147479937 2147479991 2147480009 2147480011 2147480039 2147480161 2147480197 2147480207 2147480219 2147480227 2147480297 2147480299 2147480311 2147480327 2147480369 2147480429 2147480437 2147480459 2147480471 2147480507 2147480519 2147480527 2147480551 2147480591 2147480611 2147480623 2147480641 2147480651 2147480677 2147480683 2147480707 2147480723 2147480743 2147480747 2147480791 2147480837 2147480843 2147480849 2147480893 2147480897 2147480899 2147480921 2147480927 2147480941 2147480957 2147480969 2147480971 2147480989 2147481019 2147481031 2147481053 2147481071 2147481139 2147481143 2147481151 2147481173 2147481179 2147481199 2147481209 2147481247 2147481263 2147481269 2147481283 2147481311 2147481317 2147481337 2147481353 2147481359 2147481367 2147481373 2147481487 2147481491 2147481499 2147481509 2147481529 2147481563 2147481571 2147481629 2147481673 2147481793 2147481797 2147481811 2147481827 2147481863 2147481883 2147481893 2147481899 2147481901 2147481907 2147481937 2147481949 2147481967 2147481997 2147482021 2147482063 2147482081 2147482091 2147482093 2147482121 2147482223 2147482231 2147482237 2147482273 2147482291 2147482327 2147482343 2147482349 2147482361 2147482367 2147482409 2147482417 2147482481 2147482501 2147482507 2147482577 2147482583 2147482591 2147482621 2147482661 2147482663 2147482681 2147482693 2147482697 2147482739 2147482763 2147482801 2147482811 2147482817 2147482819 2147482859 2147482867 2147482873 2147482877 2147482921 2147482937 2147482943 2147482949 2147482951 2147483029 2147483033 2147483053 2147483059 2147483069 2147483077 2147483123 2147483137 2147483171 2147483179 2147483237 2147483249 2147483269 2147483323 2147483353 2147483399 2147483423 2147483477 2147483489 2147483497 2147483543 2147483549 2147483563 2147483579 2147483587 2147483629 2147483647]
    fermat_test.go:61: testing FermatPrimeTester range 0xffff_fffff000 to 0xffff_ffffffff
    fermat_test.go:55: cost = 85 ms, [2147479573 2147479589 2147479601 2147479619 2147479637 2147479643 2147479657 2147479681 2147479751 2147479753 2147479757 2147479781 2147479787 2147479819 2147479823 2147479879 2147479891 2147479897 2147479907 2147479937 2147479991 2147480009 2147480011 2147480039 2147480161 2147480197 2147480207 2147480219 2147480227 2147480297 2147480299 2147480311 2147480327 2147480369 2147480429 2147480437 2147480459 2147480471 2147480507 2147480519 2147480527 2147480551 2147480591 2147480611 2147480623 2147480641 2147480651 2147480677 2147480683 2147480707 2147480723 2147480743 2147480747 2147480791 2147480837 2147480843 2147480849 2147480893 2147480897 2147480899 2147480921 2147480927 2147480941 2147480957 2147480969 2147480971 2147480989 2147481019 2147481031 2147481053 2147481071 2147481139 2147481143 2147481151 2147481173 2147481179 2147481199 2147481209 2147481247 2147481263 2147481269 2147481283 2147481311 2147481317 2147481337 2147481353 2147481359 2147481367 2147481373 2147481487 2147481491 2147481499 2147481509 2147481529 2147481563 2147481571 2147481629 2147481673 2147481793 2147481797 2147481811 2147481827 2147481863 2147481883 2147481893 2147481899 2147481901 2147481907 2147481937 2147481949 2147481967 2147481997 2147482021 2147482063 2147482081 2147482091 2147482093 2147482121 2147482223 2147482231 2147482237 2147482273 2147482291 2147482327 2147482343 2147482349 2147482361 2147482367 2147482409 2147482417 2147482481 2147482501 2147482507 2147482577 2147482583 2147482591 2147482621 2147482661 2147482663 2147482681 2147482693 2147482697 2147482739 2147482763 2147482801 2147482811 2147482817 2147482819 2147482859 2147482867 2147482873 2147482877 2147482921 2147482937 2147482943 2147482949 2147482951 2147483029 2147483033 2147483053 2147483059 2147483069 2147483077 2147483123 2147483137 2147483171 2147483179 2147483237 2147483249 2147483269 2147483323 2147483353 2147483399 2147483423 2147483477 2147483489 2147483497 2147483543 2147483549 2147483563 2147483579 2147483587 2147483629 2147483647]
    fermat_test.go:63: Fermat(fail=94302, pass=9791)
--- PASS: Test_FermatTest (0.31s)
PASS
ok      command-line-arguments  0.310s

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 gSamples = genSamples(3, 10)
var gSampleCount = len(gSamples)

func genSamples(from, to int) []int {
    items := make([]int, to - from + 1)
    for i := from;i<=to;i++ {
        items[i - from] = i
    }
    return items
}
func (me *tFermatTester) IsPrime(x int) bool {
    if x > 0x7fffffff {
        panic("too large number, max 0x7fffffff")
    }

    if x <= 1 {
        return false
    }

    if x <= 3 {
        return true
    }

    for i:= 0;i < gSampleCount;i++ {
        n := gSamples[i]
        if n >= x || n <= 1 {
            break
        }

        if !me.fermatTest(n, 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)

有疑问加站长微信联系（非本文作者）