专栏首页ICSOC.TECH有限域的基本概念和质数、不可分解多项式的搜寻算法

有限域的基本概念和质数、不可分解多项式的搜寻算法

关于有限域的两个有趣应用的旧文,排个版重发。

有限域的概念

有限域(Finite Field)在数学上属于群论(Group Theory)的范畴,又称伽罗瓦域(Galois Field)。简单来说,就是包含有限个元素的域。例如GF(2^8)这个AES加密算法中涉及的有限域,包含了256个元素。在这个有限域中可以定义乘法和加法操作,那么这256个元素中的乘积和加和都不能超出这256个元素的范围。

有限域的多项式表示

表示有限域中元素的一种方式是多项式。例如GF(2^2)中的所有四个元素,可以用{0,1,x,x+1}四个多项式来表示,而且需要注意到这些多项式系数不是1就是0,这样多项式中的每一个degree项就对应了二进制的每一个bit的权重,而系数就对应了这个bit的具体取值。

有限域中的运算

那么元素的加法,可以用对应多项式的系数的加法来表示,通常定义成对应系数的异或操作。元素的乘法呢,先采用普通的算术乘法。这样就会出现x*(x+1)=x^2+x,这样的结果是超出了GF(2^2)的范围。为了使这个结果回到有限域的范围,需要再对这个算术积做一次模运算(modulo)。模运算其实就是选择一个特殊的除数,和算术积做除法,然后取余数作为模运算的结果。做模运算的除数多项式称之为 reduction polynomial

有限域中的不可分解多项式

这个reduction polynomial必须是一个不可分解的多项式(prime reduction polynomial)。如果可以分解,那么模运算的结果就会出现0(即算术积可以被整除),这在有限域中是不允许出现的。所以找到有限域中的prime reduction polynomial,就成为完成该有限域中的乘法和加法定义的关键步骤。

质数搜索算法

微软一位工程师的博客[1]上介绍了一种方法,称之为A Sieve of Eratosthenes method。这种方法可以用于搜寻质数(素数,primes),理解了搜寻质数的算法原理,那么就可以同样用这种方法来搜寻不可分解多项式了。

所以首先看一下如何搜寻质数。用这种方法搜寻不超过某个正整数N的所有质数的原理大概是这样子的:

1.先把这N个整数都列出来,首先把1划掉,因为1很特殊,但我们知道1不是质数。首先把这N-1个数都标记为质数(假设)。2.从最小的质数2开始,把不大于N的该质数所有倍数2、3、4、。。。都标记为合数(非质数)。3.从下一个质数开始,重复步骤2,直到最后一个质数。4.那么N-1个整数的质数和合数就都分别得到了正确的标记。

这种方法的原理比较直白,如果一个正整数N是合数,那么在前面的N-2Sieving中,肯定会被标记为合数。否则,开始它的假设标记是质数,就是成立的。这种方法看起来只适合寻找比较小的质数,如果质数很大,需要的计算次数就是海量的了,实际不太可行。

质数搜索算法的改进

仔细研究的话,上面描述的方法中有很多步骤是冗余的,可以精简。例如步骤2在用程序实现算法时,本来是个从2N的循环。但是从2开始没有必要,可以从当前质数的平方开始,直到N循环结束。因为当前质数为2时,可以看出,4、6、8将被标记为合数。这样下一个质数3的倍数循环中,可以直接从9开始循环,前面的6已经没有必要再次计算了。质数越大,减少的计算次数越多。

另外,因数中有2的合数在第一次循环中就都已经被标记为合数了。后面开始下一个质数的循环时,倍数可以跳过偶数倍,只用奇数倍。

质数搜索算法的TCL源代码

作者用数字前端工程师最爱的TCL脚本分别实现了原版和简化版的代码,放在了作者的github[2],感兴趣的可以看看。不过没有怎么关注计算时间的比较。点击阅读原文也可以跳转过去。

好吧。到这里就可以继续之前的搜寻不可分解多项式的问题了。

不可分解多项式的搜索算法

前面说到搜寻质数的一个算法,其实就是先把一定范围内的整数都列出来,然后从小到大,按一定的遍历顺序计算乘积,然后把对应该乘积的整数标记为合数。计算到最后,剩下的就是质数了。背后的原则就是一个合数肯定是由比它小的两个数相乘得来的。

这个原则同样可以推广到搜寻有限域的不可分解多项式。把一定范围的(通常是不高于N阶)多项式全部列出来,从阶数最小的多项式开始遍历计算乘积,把结果标记为可分解多项式,最后剩下的就是不可分解多项式。

不可分解多项式搜索算法的TCL源代码

用程序实现这个过程,首先要实现基本的几个操作。例如多项式的加法和乘法操作。加法比较简单,就是对应项系数做个异或。乘法就是移位和加法。另外,为了方便遍历,把每个多项式都对应成一个整数,在每一个循环过程中,把当前的整数转换回多项式,进行乘法操作。具体的实现可以参考TCL脚本中的各个PROC子过程。相关源码仍放在作者的github[3]。

有同学说琢磨这些有啥用,我竟无言以对,也许是补补小时候的奥数课吧哈哈。其实也就是个兴趣,解开心中的一个疑惑,不亚于跑个五公里所分泌的多巴胺带来的快感。记录更多的是为自己,而不是为了传播。

常怀好奇之心,常怀感恩之心,与诸君共勉。

References

[1] 微软一位工程师的博客: https://blogs.msdn.microsoft.com/matthew_van_eerde/2011/11/11/generating-primes-using-the-sieve-of-eratosthenes-plus-a-few-optimizations/ [2] github: https://github.com/hanjingfei/tcl.primes [3] github: https://github.com/hanjingfei/tcl.poly_sieve

本文分享自微信公众号 - icsoc(ic-soc),作者:韩京飞

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 当我们做后仿时我们究竟在仿些什么(四)

    就像人类容易接受自然数,但对于负数缺乏某种直觉上的认识一样;后仿过程中经常出现的 Negative Delay 和 Negative Timing Check ...

    icsoc
  • 君子善器之按行号跳转:用vim查阅verilog编译信息的一个小技巧

    前段时间请求IT把Linux服务器上的vim升级到vim7.4,一个想法是可以用vim7.0之后加入的特性gF,可以实现跳转到光标所在文件的指定行,如果文件名后...

    icsoc
  • 关于 Verilog 的 TimeScale

    最近做芯片的功耗分析,需要用 PTPX 读入门级仿真写出的 VCD 文件。门级仿真的速度非常慢,所以关注了一下和速度相关的 TimeScale 的东西。

    icsoc
  • C#版 - Leetcode 762. 二进制表示中质数个1置位 - 题解

    762.Prime Number of Set Bits in Binary Representation

    Enjoy233
  • 【Android】Realm详解

    Gavin-ZYX
  • 漫画:王者新赛季 “镜” 给大家出的算法题!

    第858题:有一个特殊的正方形房间,每面墙上都有一面镜子。除西南角以外,每个角落都放有一个接受器,编号为 0,1,以及 2。正方形房间的墙壁长度为 p,一束激光...

    程序员小浩
  • 谈一谈|下载软件的门道你懂吗?

    当我们在下载一些软件时我们经常会遇到这样一个问题—软件的后缀为什么有这么多?该下载哪一个?这些后缀是什么意思?如图:

    算法与编程之美
  • 你问我答 | 云直播(CSS)年度关心问题解答

    年度云直播(CSS)最为关心的问题汇总整理,希望可以帮助到您。 ?

    腾讯云视频
  • 20年的目标检测大综述(章节1)

    不知不觉2020年“计算机视觉战队”陪伴大家快两个月了,由于疫情大家最近估计都没有吃好喝好,但是大家肯定玩的很High,我们也一直在陪伴,分享最好最有质量的知识...

    计算机视觉研究院
  • 【原创】Java并发编程系列29 | ConcurrentLinkedQueue

    J.U.C 为常用的集合提供了并发安全的版本,前面讲解了 map 的并发安全集合 ConcurrentHashMap,List 并发安全集合 CopyOnWri...

    java进阶架构师

扫码关注云+社区

领取腾讯云代金券