barret reduction原理详解及硬件优化
背景介绍
约减算法,通常应用在硬件领域,因为模运算mod是一个除法运算,在硬件中实现速度会比乘法慢的多,并且还会占用大量资源,因此需要想办法用乘法及其它简单运算来替代模运算。模约减算法可以利用乘法、加法和移位等操作实现大数的取模,规避了模运算中的除法,常见方法有蒙哥马利模约减,barret模约减等,本篇文章介绍barret 模约减算法原理。
barret reduction
约减就是用简单运算来规避除法运算,以便于硬件实现,以A mod q为例,如果要计算A对q取模的结果使用barret reduction算法应该怎么做?
先规定A mod q,则称A为模数,q为基。
假设A的位宽是,q的位宽是
,对于硬件实现来说需要预计算出两个常数:
和
在进行预计算的时候,都需要对计算结果进行取下整,进而
和
满足如下不等式:
令,则有如下不等式成立:
令,即对上面
不等式,两边同时除以
,得到:
由于A的位宽是,q的位宽是
,所以A和q满足如下不等式:
把A和q所满足的不等式,带入不等式中,得到:
所以两边同时乘以q得到:
因此得到模运算可以化简为:
又由于是在A-3q和A之间的,所以它对q取模,只需要判断它在[0,q)、[q,2q)、[2q,3q)的哪个区间,若
落在[q,2q)区间,则:
以上,完成了barret模约减,同样的,该模约减算法可以应用在模乘领域,即实现barret模乘。而相对于模乘,AB mod q,可以直接把AB的乘积看作是上面公式推导的A,然后再进行模乘。
barret模约减计算流程大体如下图所示:

硬件实现
看完模约减公式推导过程,肯定有人会疑问:
先前预计算了两个常数,我后面的约减推导全都是依赖于这两个常数。先来看H,为了将多项式系数约束在基的范围内,进而能够实现密码学领域中的一些同态加密算法,选取的基q,通常是定值,因此H的计算量很少可以直接预计算并存储到RAM中,哪怕我A的取值范围是1-200bit,在基q确定的情况下我最多也只需要预计算200个H的值。
选取基q确定的情况下H好计算,但A是输入变量,有任意种可能,那么该怎么预计算?
事实上不需要预计算,因为
是A除以2的幂次,在硬件中,除以2的幂次可以通过移位操作来实现,至于
计算需要对结果向下取整,只需要对A进行移位操作即可。例如
计算对结果向下取整,可以直接用A移位来替代。
综上,的值和
的值我们都可以轻易得到了,并且不怎么消耗计算资源,也没有多少计算delay,并且后面
的计算也是除以2的次幂,也可以转化为移位操作,因此barret模约减主要的计算量在于:
主要计算量在于上面的两个乘法,q2 = q1*H,和q3*q的计算。
硬件优化
在之前已经推导出barret模约减主要计算量在两个乘法,q2 = q1*H,和q3*q的计算。
对于硬件实现来说,第二个计算可以进行优化,因为A-q3*q之后还要对其的范围进行判断,若落在[q,2q)范围,则A mod q = A-q3*q-q,事实上我们关心其落在那个范围,并不需要比较所有bit位,q的位宽为,我们只需要比较低
位的大小就可以判断其落在哪个范围,甚至对于q3*q也可以通过取q3的低
位的数据和q进行乘运算,再取运算结果的低
位进行比较,从而确定范围。
因此在硬件实现上,利用barret模约减,成功将除法化简为了两个乘法和一(两)个加法计算。
相关文章:
barret reduction原理详解及硬件优化
背景介绍 约减算法,通常应用在硬件领域,因为模运算mod是一个除法运算,在硬件中实现速度会比乘法慢的多,并且还会占用大量资源,因此需要想办法用乘法及其它简单运算来替代模运算。模约减算法可以利用乘法、加法和移位等…...
NLP / LLMs中的Temperature 是什么?
ChatGPT, GPT-3, GPT-3.5, GPT-4, LLaMA, Bard等大型语言模型的一个重要的超参数 大型语言模型能够根据给定的上下文或提示生成新文本,由于神经网络等深度学习技术的进步,这些模型越来越受欢迎。可用于控制生成语言模型行为的关键参数之一是Temperature …...
c#快速入门~在java基础上,知道C#和JAVA 的不同即可
☺ 观看下文前提:如果你的主语言是java,现在想再学一门新语言C#,下文是在java基础上,对比和java的不同,快速上手C#,当然不是说学C#的前提是需要java,而是下文是从主语言是java的情况下ÿ…...
nginx--基本配置
目录 1.安装目录 2.文件详解 2.编译参数 3.Nginx基本配置语法 1./etc/nginx/nginx.conf 2./etc/nginx/conf.d/default.conf 3.启动重启命令 4.设置404跳转页面 1./etc/nginx/conf.d/default.conf修改 2. 重启 5.最前面内容模块 6.事件模块 1.安装目录 # etc cd …...
R语言中apply系列函数详解
文章目录applylapply, sapply, vapplyrapplytapplymapplyR语言系列: 编程基础💎循环语句💎向量、矩阵和数组💎列表、数据帧排序函数💎apply系列函数 R语言的循环效率并不高,所以并不推荐循环以及循环嵌套…...
红黑树探险:从理论到实践,一站式掌握C++红黑树
红黑树揭秘:从理论到实践,一站式掌握C红黑树引言为什么需要了解红黑树?红黑树在现代C编程中的应用场景树与平衡二叉搜索树树的基本概念:二叉搜索树的定义与性质:平衡二叉搜索树的特点与需求:红黑树基础红黑…...
CDH6.3.2大数据集群生产环境安装(七)之PHOENIX组件安装
添加phoenix组件 27.1. 准备安装资源包 27.2. 拷贝资源包到相应位置 拷贝PHOENIX-1.0.jar到/opt/cloudera/csd/ 拷贝PHOENIX-5.0.0-cdh6.2.0.p0.1308267-el7.parcel.sha、PHOENIX-5.0.0-cdh6.2.0.p0.1308267-el7.parcel到/opt/cloudera/parcel-repo 27.3. 进入cm页面进行分发、…...
【C++要笑着学】搜索二叉树 (SBTree) | K 模型 | KV 模型
C 表情包趣味教程 👉 《C要笑着学》 💭 写在前面:半年没更 C 专栏了,上一次更新还是去年九月份,被朋友催更很久了hhh 本章倒回数据结构专栏去讲解搜索二叉树,主要原因是讲解 map 和 set 的特性需要二叉搜索…...
微信小程序开发 | 小程序开发框架
小程序开发框架7.1 小程序模块化开发7.1.1 模块7.1.2 模板7.1.3 自定义组件7.1.4插件7.2 小程序基础样式库—WeUI7.2.1 初识WeUI7.2.2【案例】电影信息展示7.3 使用vue.js开发小程序7.3.1 初识mpvue7.3.2 开发工具7.3.3 项目结构7.3.4【案例】计数器7.4 小程序组件化开发框架7.…...
气候系统设计
基础概念 一个星球(例如地球)的气候系统主要是一些基本参数基于公转周期(年)和自转周期(日)的变化,这其中会有两个变化因素:地理位置(经纬度)和天气变化&…...
如何使用Thymeleaf给web项目中的网页渲染显示动态数据?
编译软件:IntelliJ IDEA 2019.2.4 x64 操作系统:win10 x64 位 家庭版 服务器软件:apache-tomcat-8.5.27 目录一. 什么是Thymeleaf?二. MVC2.1 为什么需要MVC?2.2 MVC是什么?2.3 MVC和三层架构之间的关系及工…...
01 | 电机常用语
1 电机常用术语 1.1 原点 原点是指步进电机在驱动直线运动机构时的起始点。 1.2 点动 点动是电动机控制方式中的一种。 点动由于在这一控制回路中没有自保,也没有并接其它的自动装置,只是按下控制回路的启动按钮,主回路才通电,松开启动按钮,主回路就没电了。最典型的是…...
Leetcode.2601 质数减法运算
题目链接 Leetcode.2601 质数减法运算 Rating : 1779 题目描述 给你一个下标从 0 开始的整数数组 nums,数组长度为 n 。 你可以执行无限次下述运算: 选择一个之前未选过的下标 i ,并选择一个 严格小于 nums[i]的质数 ppp &…...
DP7416国产192K数字音频接收芯片兼容替代CS8416
目录192K 数字音频应用DP7416简介芯片特性192K 数字音频应用 采样率192khz,能将192,000hz以下的频率都录下来,而且对声波每秒连续采样192,000次。在回放的时候,这192,000个采样点按顺序播放,从而还原原来的声音。 过采样技术除…...
全球土壤湿度数据获取方法
土壤湿度亦称土壤含水率,表示土壤干湿程度的物理量。是土壤含水量的一种相对变量。通常用土壤含水量占干土重的百分数是示,亦称土壤质量湿度,如用土壤水分容积占土壤总容积的百分数表示,则称土壤容积湿度。通常说的土壤湿度&#…...
在proteus中仿真arduino实现矩阵键盘程序
矩阵键盘是可以解决我们端口缺乏的问题,当然,如果我们使用芯片来实现矩阵键盘的输入端口缺乏的问题将更加划算了,本文暂时不使用芯片来解决问题,而使用纯朴的8根线来实现矩阵键盘,目的是使初学者掌握原理。想了解使用芯…...
【ROS2指南-5】理解ROS2服务
目标:使用命令行工具了解 ROS 2 中的服务。 教程级别:初学者 时间: 10分钟 内容 背景 先决条件 任务 1 设置 2 ros2服务列表 3 ros2服务类型 4 ros2 服务查找 5 ros2界面展示 6 ros2 服务调用 概括 下一步 相关内容 背景 服务是 …...
探索Apache Hudi核心概念 (3) - Compaction
Compaction是MOR表的一项核心机制,Hudi利用Compaction将MOR表产生的Log File合并到新的Base File中。本文我们会通过Notebook介绍并演示Compaction的运行机制,帮助您理解其工作原理和相关配置。 1. 运行 Notebook 本文使用的Notebook是:《A…...
100Wqps异地多活,得物是怎么架构的?
说在前面 在40岁老架构师尼恩的数千读者群中,一直在指导大家简历和职业升级,前几天,指导了一个华为老伙伴的简历,小伙伴的优势在异地多活,但是在简历指导的过程中,尼恩发现: 异地多活的概念、异…...
35岁的测试工程师被公司强行辞退,感叹道:我以前就该好好努力了
曾经的高薪软件测试工程师,今年35岁了,被公司劝退了,外卖跑到凌晨,很累,但还是有一种想诉说的冲动。哪怕让大家觉得已经说得太多了,烦了,都成祥林嫂了,但是,我是真的想说…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
