程序员经验分享-hwhale

伽罗华域（Galois Field）理解、基于伽罗华域的四则运算（附详细python代码）

2023-10-29

参考链接：https://blog.csdn.net/luotuo44/article/details/41645597
参考链接：https://blog.csdn.net/shelldon/article/details/54729687

伽罗华域定义

在这里插入图片描述
我对伽罗华域的理解就是，给定一个域，比如4位，在4位之内的数字，不管加、减、乘、除，结果都在域里面，不会溢出，并且。运算时可逆的，能够还原
比如4位最大数字为15，那么13+14 = a不能超过15，并且运算可逆：a - 13 = 14, a - 14 = 13
同样13 x 14 = a，a不能超过15，a / 13 = 14

伽罗华域的计算

在这里插入图片描述

有限域

在密码学中，有限域GF(.p)是一个很重要的域，其中p为素数。简单来说，GF(.p)就是 mod p，因为一个数模p后，结果在[0, p-1]之间。对于元素a和b，那么(a+b) mod p和(a*b)mod p，其结果都是域中的元素。GF§里面的加法和乘法都是平时用的加法和乘法。
为什么p必须是素数？
是因为当p为素数时，才能保证集合中的所有的元素都有加法和乘法逆元(0除外)。
举个例子：加入p = 10，那么我们需要计算1 / 2，也就是计算a，使得(a * 2) mod 10 = 1，但是显然没有这样的a成立。

本原多项式

既然要求p是素数，那么有没有对不同的域的大小一个特定的素数呢，这个是有一些经常使用的素数的，转换成多项式叫做本原多项式
例如在24域里面，多项式为：x4+x+1，也就是二进制10011，因为需要异或这个多项式，所以多项式的最高位肯定是2w，然后后面加一个素数，在w为4的时候，这个素数就是3。
在这里插入图片描述

通过本原多项式生成元素

按照之前的算法
在这里插入图片描述
在这里插入图片描述
GF(24)含有16个元素，本原多项式为P(x)=x^4+x+1，除了 0、1外，另外14个符号均由本原多项式生成。
可以看到最后一个元素的计算过程，正好对P(x)取模之后，结果为1

在这里插入图片描述

生成元素代码（正表构造）

for i in range(1, gf_element_total_number - 1):
    temp = gfilog[i - 1] << 1  # g(i) = g(i-1) * 2
    if temp & gf_element_total_number:  # 判断溢出
        temp ^= primitive_polynomial  # 异或本原多项式
    gfilog.append(temp)

结果
在这里插入图片描述
这个将生成元变为多项式，然后映射到十进制的形式，也就是将生成元的系数映射成十进制的形式。

反表构造

当我们需要逆元的时候，就需要将十进制变为多项式，例如我们知道gfilog[0] = 1，那么我们需要知道gfilog[x] = 1的x
这个时候就需要构建反表gflog
gflog的构造方式为：gflog[gfilog[i]] = i
也就是根据二进制，转换为生成元。

for i in range(0, gf_element_total_number - 1):
    gflog[gfilog[i]] = i

结果：
在这里插入图片描述
那么就构造出来了两个表了。
在这里插入图片描述

伽罗华域四则运算

1.加法运算

异或然后对2w取模即可

2. 减法运算

与加法一样，异或然后对2w取模即可

    def add(self, a, b):
        return (a ^ b) % self.total

    def sub(self, a, b):
        return (a ^ b) % self.total
3. 乘法运算
  1. 将十进制变为多项式：查gflog表
  2. 两个多项式相加，如果溢出，对2w取模
  3. 将多项式变为生成元：查gfilog表
    def mul(self, a, b):
        return self.gfilog[(self.gflog[a] + self.gflog[b]) % self.total]
4. 除法运算

既然乘法是相加，那么除法就反过来相减。

  1. 将十进制变为多项式：查gflog表
  2. 两个多项式相减，如果溢出，对2w取模
  3. 将多项式变为生成元：查gfilog表
    def div(self, a, b):
        return self.gfilog[(self.gflog[a] - self.gflog[b]) % self.total]

完整程序

输入：伽罗华域位大小4、8、16、32、64
输入：两个数字
输出：四则远算的结果

primitive_polynomial_dict = {4: 0b10011,  # x**4  + x  + 1
                             8: (1 << 8) + 0b11101,  # x**8  + x**4  + x**3 + x**2 + 1
                             16: (1 << 16) + (1 << 12) + 0b1011,  # x**16 + x**12 + x**3 + x + 1
                             32: (1 << 32) + (1 << 22) + 0b111,  # x**32 + x**22 + x**2 + x + 1
                             64: (1 << 64) + 0b11011  # x**64 + x**4 + x**3 + x + 1
                             }
class GF:
    def __init__(self, w):
        self.w = w
        self.total = (1 << self.w) - 1
        self.gflog = []
        self.gfilog = [1] # g(0) = 1
        self.make_gf_dict(self.w, self.gflog, self.gfilog)

    def make_gf_dict(self, w, gflog, gfilog):
        gf_element_total_number = 1 << w
        primitive_polynomial = primitive_polynomial_dict[w]
        for i in range(1, gf_element_total_number - 1):
            temp = gfilog[i - 1] << 1  # g(i) = g(i-1) * 2
            if temp & gf_element_total_number:  # 判断溢出
                temp ^= primitive_polynomial  # 异或本原多项式
            gfilog.append(temp)

        assert (gfilog[gf_element_total_number - 2] << 1) ^ primitive_polynomial
        gfilog.append(None)

        for i in range(gf_element_total_number):
            gflog.append(None)

        for i in range(0, gf_element_total_number - 1):
            gflog[gfilog[i]] = i
        print(gflog)
        print(gfilog)

    def add(self, a, b):
        return (a ^ b) % self.total

    def sub(self, a, b):
        return (a ^ b) % self.total

    def mul(self, a, b):
        return self.gfilog[(self.gflog[a] + self.gflog[b]) % self.total]

    def div(self, a, b):
        return self.gfilog[(self.gflog[a] - self.gflog[b]) % self.total]

测试

gf = GF(4)
import random
t = 0
while t <= 20:
    a = random.randint(1, 15)
    b = random.randint(1, 15)
    c = gf.add(a, b)
    d = gf.mul(a, b)
    print('%d + %d = %d' % (a, b, c))
    print('%d - %d = %d' % (c, a, gf.sub(c, a)))
    print('%d * %d = %d' % (a, b, d))
    print('%d / %d = %d' % (d, a, gf.div(d, a)))
    print()
    t += 1

在这里插入图片描述

从结果中可以看到2+10=8
8-10=2，说明加减法是可逆的
2 x 10 = 7
7 / 2 = 10，说明乘法除法是可逆的

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

mininet

伽罗华域（Galois Field）理解、基于伽罗华域的四则运算（附详细python代码） 的相关文章

随机推荐

  • Zero-shot Learning / One-shot Learning

    Introduction 在 迁移学习 中 由于传统深度学习的 学习能力弱 往往需要 海量数据 和 反复训练 才能修得 泛化神功 为了 多快好省 地通往炼丹之路 炼丹师们开始研究 Zero shot Learning One shot Le

  • altium designer 中走线宽度设置的方法

    1 设计 gt 类 gt Net Class gt 鼠标右键添加类 gt 把比如电源和地线归为一类 命名为GND VCC 2 设计 gt 规则 gt Routing gt Width gt 选中网络类 gt 选择GND VCC 然后选择好要

  • $.post 提交长度过大问题

    Json 参数长度过大 无法反序列化为Json

  • NCBI Genbank核苷酸序列数据库检索基因序列解读

    核酸数据库 Genbank数据库 Nucleotide数据库 一 基因序列注释内容解析 以dut基因编码的大肠杆菌酶dutpase为例 在Nucleotide数据库search X01714或者dutpase 检索链接https www n

  • vue2自定义loading组件

    概要 通常情况下 我们在使用element ui时会使用到loading组件 一般用于对表格请求响应时间过长的时候使用loading 然而依然有一些其他情况需要用的loading 这个时候 v loading指令在其他组件上不生效了 所以官

  • python seaborn 散点图矩阵_Python绘图总结(seaborn库的使用)（下）

    上部分介绍了pie以及kdeplot distplot jointplot pairplot的用法分别绘制出数据的饼图 核密度分布图 柱状图 散点图 以及用jointplot绘制组合图 下面开始总结 散点图 二维 三维 折线图 并列 叠加

  • 彻底理解webservice SOAP WSDL

    WebServices简介 先给出一个概念 SOA 即Service Oriented Architecture 中文一般理解为面向服务的架构 既然说是一种架构的话 所以一般认为 SOA 是包含了运行环境 编程模型 架构风格和相关方法论等在

  • 夜神模拟器：新建android模拟器并安装apk文件

    1 安装夜神模拟器 下载地址 https www yeshen com a 直接双击nox xxx exe一步步安装模拟器 b adb devices查看结果 如果出现如下错误 解决方法 夜神模拟器的adb版本和androidsdk的adb

  • 数论初探--中国剩余定理（一）

    数论 很简单 小学奥数而已 中国剩余定理 小学五年级奥数内容 在一千多年前的 孙子算经 中 有这样一道算术题 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 按照今天的话来说 一个数除以3余2 除以5余3 除以7余2 求

  • Anaconda------环境管理

    Anaconda 中的Conda核心功能就是包管理和环境管理 可以根据需要安装不同版本的python 而且能自由切换 先着重介绍一个概念 虚拟环境 virtual environment 它是一个虚拟化 从电脑独立开辟出来的环境 以Dock

  • 前端解决防盗链

    防盗链浅谈 由于利用百度新闻请求接口 导致部分图片请求失败 状态码403 服务被拒绝 之前一直用python写爬虫 所以很自然的就想到了伪装请求头 于是乎想到解决该问题的第一种方法就是创建vue config js 在里面配置代理 现在是学

  • matlab怎么产生一个随机数,matlab怎么产生随机数

    matlab是我们常用一种软件 对于做随机过程或者概率的朋友 常常会用到一些随机数 但是这些数据怎么生成呢 下面介绍下matlab中一些常见的随机数 matlab产生随机数可以使用的方法 1 均匀分布 unifrnd a b m n 产生m

  • Oracle vm virtualbox安装

    Oracle vm virtualbox安装 VirtualBox 簡介 下載安裝包 VirtualBox 簡介 VirtualBox 是一款开源虚拟机软件 VirtualBox 是由德国 Innotek 公司开发 由Sun Microsy

  • 继电器控制电路

    继电器控制电路 原理 控制方式 继电器种类 案例 原理 使用控制电器的触点 按钮 开关或继电器触点 控制用电器工作 控制方式 手动控制 触点通 断用人工控制 比如按钮 手动开关 自动控制 触点通断可以自动实现 如行程开关 继电器 继电器种类

  • UE4之HTTP请求

    UE4中的HTTP模块封装了libcurl的HTTP功能 很容易实现HTTP下载和上传功能 代码如下 class FHttpRequestTest void Download const FString URL TSharedRef Htt

  • JS /JQ文件、图片上传+图片预览（二进制、base64）

    一 base64

  • unity刘海屏适配

    public class SafeArea MonoBehaviour private Rect safeArea public Action

  • 安装chromadb遇到的问题与python3升级

    环境 python 3 10 centos 7 x 使用 pip3 install chromadb 时 遇到以下问题 问题1 gcc note This error originates from a subprocess and is

  • 系统建模与仿真项目驱动设计报告-基于MATLAB的GUI界面设计

    摘 要 MATLAB语言是一种十分有效得工具 能够容易解决在系统仿真以及控制系统计算机辅助设计领域的解决问题 在本次的系统建模与仿真设计中 需要使用人机交互界面 MATLAB GUI功能设计一个系统仿真GUI界面 由于GUI本身提供了Win

  • 伽罗华域（Galois Field）理解、基于伽罗华域的四则运算（附详细python代码）

    参考链接 https blog csdn net luotuo44 article details 41645597 参考链接 https blog csdn net shelldon article details 54729687 伽罗

热门标签