首页 > 其他分享 >Xor-FWT 的另一种理解方式

Xor-FWT 的另一种理解方式

时间:2024-10-31 21:30:36浏览次数:5  
标签:Xor text bmod times 理解 FWT hat

Xor-FWT 的另一种理解方式

学习 \(\text{Fennec's Algorithm}\) 的额外收获,顺手记录一下。

假设我们要求两个长度为 \(n\) 的数组的异或卷积,为方便起见令 \(n = 2^m\),也就是类似下面的形式

\[C_k = \sum\limits_{i \oplus j} A_i \times B_j \]

考虑构造 \(\mathbb{Z}_2^n\) 中的向量表达异或运算。对于两条向量 \(u, v\),它们的加法 \(u + v\) 恰好就是原本的 \(i \oplus j\)(因为是 \(\bmod 2\) 意义下所以自然不会进位)。

类似的定义向量点乘 \(u \cdot v = u_0 \times v_0 + u_1 \times v_1 + \ldots u_{m - 1} \times v_{m - 1}\),同样是在 \(\bmod 2\) 意义下。所以结果相当于 \(\text{pocount}(i \ \text{and} \ j) \bmod 2\)。我们发现其恰好对应 \(\text{FWT}\) 的贡献系数。下面简记 \(\langle i, j \rangle = \text{pocount}(i \ \text{and} \ j) \bmod 2\)。

设 \(\hat{A}_i = \sum\limits_{j} A_i (-1)^{\langle i, j \rangle}\)。\(\text{Xor-FWT}\) 的主流程即将 \(\hat{A}\) 和 \(\hat{B}\) 的对应位置乘起来,得到 \(\hat{C}\)。

现在考虑 \(A_u\) 对 \(\hat{A}_w\) 的贡献,系数为 \((-1)^{u \cdot w}\),类似的 \(B_v\) 对 \(\hat{B}_w\) 的贡献系数 \((-1)^{v \cdot w}\),而对应位置系数相乘相当于指数相加,即 \(A_u \times B_v\) 对 \(C_w\) 的贡献系数 \((-1)^{(u + v) \cdot w}\),即先将 \(u\) 和 \(v\) 做异或卷积(\(u + v\)),再考察其对 \(\hat{C}_w\) 的贡献。

标签:Xor,text,bmod,times,理解,FWT,hat
From: https://www.cnblogs.com/estruct/p/18518942

相关文章

  • 深入理解计算机系统 3.6 数组分配和访问
    C语言中的数组是一种将标量数据聚集成更大数据类型的方式。C语言实现数组的方式非常简单,因此很容易翻译成机器代码。C语言一个不同寻常的特点是可以产生指向数组中元素的指针,并对这些指针进行运算。在机器代码中,这些指针会被翻译成地址计算。3.6.1 基本原则对于数据类型T和......
  • Vue 组件开发:深入理解与实践
    在Vue.js的强大生态系统中,组件开发是构建高效、可维护和可复用用户界面的核心。本文将带你深入了解Vue组件开发的方方面面,从基础概念到实际应用,让你掌握这一关键技能。一、Vue组件基础概念1.什么是组件组件是Vue.js中可复用的最小单位,它将HTML、CSS和JavaScri......
  • 《程序员修炼之道:从小工到专家》阅读笔记2---软件熵的理解与警惕
    《程序员修炼之道:从小工到专家》中提出的“软件熵”概念,犹如一记警钟,在我的脑海中久久回荡。软件熵,即系统中“无序”的总量。随着时间的推移,如果不及时处理低劣的设计、糟糕的代码和低质的文档等问题,软件就会像一个无人打理的房间一样,逐渐变得混乱不堪。这种无序状态不仅会影......
  • Python学习的自我理解和想法(24)
    学的是b站的课程(千锋教育),跟老师写程序,不是自创的代码!今天是学Python的第24天,学的内容是python对Excel的操作。开学了,时间不多,写得不详细,见谅。目录1.插件介绍2.安装openpyxl3.读取Excel文件内容(1).加载一个工作簿(2).获取工作表名称(3).获取具体的工作表(4).获......
  • Python学习的自我理解和想法(23)
    学的是b站的课程(麦叔),跟老师写程序,不是自创的代码!今天是学Python的第23天,学的内容是正则表达式。开学了,时间不多,写得不多,见谅。目录1.七个境界level1固定的字符串level2 某一类字符串level3 重复某一类字符level4 组合level2level5 多种情况level6 限定位......
  • Kyber原理解析
    Kyber是一种IND-CCA2安全的密钥封装机制。Kyber的安全性基于在模格(MLWE问题)中解决LWE问题的难度。Kyber的构造采⽤两阶段⽅法:⾸先介绍⼀种⽤来加密固定32字节⻓度的消息原⽂的IND-CPA安全性的公钥加密⽅案,我们称之为CPAPKE,CPAPKE由密钥生成(CPAPKE.KeyGen)、加密(CPAPKE.Encry......
  • 深入理解Docker,从入门到精通-Part3(高级进阶)
    一、仓库管理docker的仓库,存的就是镜像,所以仓库管理就是对镜像进行管理。在Docker里面一般有两类仓库:公共仓库(DockerHub官方仓库)和私人仓库(Registry和harbor)下面分别对这三种仓库进行介绍1、DockerHub仓库管理DockerHub是Docker公司维护的公共Registry,用户可以将......
  • [GWCTF 2019]xxor
    [GWCTF2019]xxor首先可以到汇编界面从新定义(U+P)一下main函数,不然看着会有点乱分析追踪input变量可以看到每次循环是获取四字节的输入但后面对于tmp变量的赋值我就有点看不懂了,不要紧,直接动调动态调试连接linux,下断点开调我不知道为什么输入字符会直接跳出循环,所以输入......
  • 如何理解RAG的尽头是Agent
    理解“RAG的尽头是Agent”这一观点,需要从检索增强生成(Retrieval-AugmentedGeneration,RAG)和智能代理(Agent)这两个概念的演进和融合来分析。什么是RAG?RAG是一种将大型语言模型(LLM)与外部知识库相结合的框架。在返回内容生成过程中,模型不仅依赖于训练数据,还能实时检索相关信......
  • RAID篇:理解磁盘阵列原理并配置RAID5
    RAID(独立磁盘阵列冗余):一种存储技术,通过将两个或多个硬盘驱动器(HDD)或固态硬盘(SSD)合并成一个协调的存储单元或阵列,从而创建数据丢失的故障安全机制。RAID0:条带化(数据分块),没有冗余,提供较高的读写性能。适用场景:需要高性能而不关心数据冗余的场景(视频编辑和处理、大型数据库应......