​密码学数学基础(九)

admin 2023年1月12日08:37:08CTF专场评论11 views2412字阅读8分2秒阅读模式

密码学数学基础(九)

​密码学数学基础(九)

好久没有写这个系列的文章了,这次咱们来聊聊素性检验的知识吧,友情提示,这节文章需要一点点数论的知识,这里就不给先补一下了,用的的知识其实在之前的文章当中也都提到过。

Fermat素性检验

我们先来回顾下Fermat小定理的内容,如果n是一个素数,则对任意的整数b, ,有

由此可知,如果有一个整数b,使得

则n是一个合数。

现在,我们给出一个通过上面的方案来判定一个数字n是否为素数的方法。

Fermat素性检验算法

  • 1)随机选择一个整数,计算

  • 2)如果则n不是素数

  • 3)如果计算检查上面的同余式是否成立

    • 如果不成立,则n不是素数

    • 如果成立,则n是合数的可能性小于,或者说n是素数的可能性大于

  • 4)重复上述步骤t次

  • 如果说t次都被判定为素数,则我们说n是合数的可能性小于

Carmicheal数

当然,Fermat素性检验在一定条件下是可能存在无效的,我们称这类数为Carmicheal数。

「定义1」 合数n,如果对于所有的正整数b, 都有成立,我们称合数n为「Carmicheal」数。

目前已知的最小的Carmicheal数为561。

好了,这里我们不用代码写了,相信大多数读者可能也不会去写,还是来推广下我的工具箱吧。

​密码学数学基础(九)
Fermat素性检验

如果读者发现某个数字可以通过素性检验,测试次数需要不小于100,并且确定是合数(需要给出一个因子),并且这个数字不是已知的Carmicheal数的话,大概率是我这算法写错了,或者说您的运气实在是太好了,在这个概率下的事件被您给踩中了,建议可以考虑买个彩票玩玩,当然,发现我算法错误,也欢迎联系我 ~~。

Lehmann素性检验

设n是奇素数,我们有同余式

对于任意的整数b成立,因此如果存在整数b,,使得

则n是一个合数,下面给出另一个素数判定的方法,「Lehmann」算法

算法过程

参数

  • 需要检测的数字n(

  • 安全参数t(

执行过程

  • 1)随机选取整数b,

  • 2)计算

  • 3)如果以及,则r是合数

  • 4)如果或者,则r有的概率为素数

  • 5)重复上述操作t次,则n为素数的概率为

同样的,这里还是用我的工具箱来演示一下

​密码学数学基础(九)
Lehmann素性检验算法样例

然后,我们再来看一个相似的素性检验算法,「Solovay-Stassen」素性检验。

Solovay-Stassen素性检验

给定正奇数和安全参数t,按照如下的方式进行计算。

  • 1)随机选取整数b,

  • 2)计算

  • 3)如果以及,则r是合数

  • 4)计算Jacobi符号

  • 5)如果则n是合数

  • 6)重复上面的操作t次

​密码学数学基础(九)
Solovay-Stassen素性检验样例

Miller-Rabin素性检验

设n为奇素数,并且有则有如下的因数分解式:

因此,如果有同余式

则以下的同余式至少有一个成立。

因此,如果说我们可以找到一个整数b使得

那么n是合数。

算法

这里我们同样的要求了,虽然的时候算法也是对的,但是明显,我们没必要判断3是否为素数。

参数

  • 需要检测的数字n(

  • 安全参数t(

执行过程

  • 1)计算s, k使得

  • 2)随机选取整数b,

  • 3)计算

  • 4)判断

    • a)如果或者通过校验,n可能为素数,返回2)

    • b)否则,有或者,计算

    • c)如果则通过校验,n可能为素数,返回1)

    • d)否则,重新计算,回到c)

    • e)如果重复s轮依然没有结果,则返回n是合数

  • 5)重复上述2)~4)操作t次,则n为素数的概率为

​密码学数学基础(九)
Miller-Rabin素性检验样例

工具箱链接

链接: https://pan.baidu.com/s/1W4iVPY9zDu5nRYGmZUBudA 提取码: 1387

参考资料

  • 信息安全数学基础 第二版 陈恭亮

  • https://en.wikipedia.org/wiki/Primality_test[1]

  • https://en.wikipedia.org/wiki/Solovay–Strassen_primality_test[2]

  • https://stackoverflow.com/questions/8357687/lehmann-test-for-prime-numbers[3]

  • https://math.stackexchange.com/questions/2275905/what-is-the-difference-between-the-lehmann-algorithm-and-lucas-primality-test[4]

Reference

[1]

https://en.wikipedia.org/wiki/Primality_test: https://en.wikipedia.org/wiki/Primality_test

[2]

https://en.wikipedia.org/wiki/Solovay–Strassen_primality_test: https://en.wikipedia.org/wiki/Solovay–Strassen_primality_test

[3]

https://stackoverflow.com/questions/8357687/lehmann-test-for-prime-numbers: https://stackoverflow.com/questions/8357687/lehmann-test-for-prime-numbers

[4]

https://math.stackexchange.com/questions/2275905/what-is-the-difference-between-the-lehmann-algorithm-and-lucas-primality-test: https://math.stackexchange.com/questions/2275905/what-is-the-difference-between-the-lehmann-algorithm-and-lucas-primality-test


原文始发于微信公众号(Coder小Q):​密码学数学基础(九)

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年1月12日08:37:08
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  ​密码学数学基础(九) http://cn-sec.com/archives/1441477.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: