质数域的算数运算[通俗易懂]

质数域的算数运算[通俗易懂]本文介绍了在质数域FpF_pFp​中的算数运算执行算法。包括任意质数p的算法,当模数p具有特性形式时,该算法揭示约化步骤的执行效率能够获得提升;还提出了针对NIST质数的高效约化算法,对诸如p=2192−264−1p=2^{192}-2^{64}-1p=2192−264−1形式的质数具有适用性。本文提出的算法尤适合软件执行。假设工作台通常为64位或32位,算法运行在WWW-位(W-位,W是8的倍数)框架基础上。低位或更廉价的组件的W值更小,比如嵌入式系统一般是16位,智能卡一般是8位。W-位的位数词U从0

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

“有限域算数运算”介绍了有限域的基本概念,进一步阐述了椭圆曲线系统的三种经典有限域(质数域,二元域和扩展域)以及其相应的算数运算方法(加法,减法,乘法和求逆运算)。本文重点阐述在质数域 F p F_p Fp中的算数运算执行算法,包括任意质数p的算法,当模数p具有特性形式时,该算法揭示约化步骤的执行效率能够获得提升;还提出了针对NIST质数的高效约化算法,对诸如 p = 2 192 − 2 64 − 1 p=2^{192}-2^{64}-1 p=21922641形式的质数具有适用性。
以上算法适合软件执行:假设工作台通常为64位或32位,算法运行在 W W W-位(W-位,W是8的倍数)框架基础上。低位或更廉价的组件的W值更小,比如嵌入式系统一般是16位,智能卡一般是8位。W-位的位数词U从0到W-1编号,个位数约定为位0。
F p F_p Fp的元素是从0到 p − 1 p-1 p1的整数。用 m = [ log ⁡ [ 2 ] p ] m=[\log [2]{p} ] m=[log[2]p]表示p的位数, t = [ m / W ] t=[m/W] t=[m/W]表示字节长度。下图展示的例子是用二进制存储单元 A = ( A [ t − 1 ] , . . . , A [ 2 ] , A [ 1 ] , A [ 0 ] ) A=(A[t-1],…,A[2],A[1],A[0]) A=(A[t1],...,A[2],A[1],A[0])表示字节长度t的元素a。其中,整数a表示为: a = 2 ( t − 1 ) W A [ t − 1 ] + . . . + 2 2 W A [ 2 ] + 2 W A [ 1 ] + A [ 0 ] a=2^{(t-1)^W}A[t-1]+…+2^{2W}A[2]+2^WA[1]+A[0] a=2(t1)WA[t1]+...+22WA[2]+2WA[1]+A[0]
字节元素存储

加法和减法

我们按照用多字节表示整数的方法来介绍有限域的加法和减法算法。以下是常用的术语定义,对于整数 ω \omega ω ” ( ε , z ) ← ω ” ”(\varepsilon ,z)\leftarrow \omega” (ε,z)ω有如下约定:
z ← ω m o d    2 W z\leftarrow \omega \mod 2^W zωmod2W ε ← 0 \varepsilon \leftarrow 0 ε0 如果 ω ∈ [ 0 , 2 W ) \omega \in [0,2^W) ω[0,2W),否则 ε ← 1 \varepsilon \leftarrow 1 ε1
对任意 x , y ∈ [ 0 , 2 W ) x,y\in [0,2^W) x,y[0,2W)如果 ω = x + y + ε ′ \omega = x+y+\varepsilon ‘ ω=x+y+ε ε ′ ∈ 0 , 1 \varepsilon ‘\in {0,1} ε0,1,于是 ω = ε 2 W + z \omega =\varepsilon 2^W+z ω=ε2W+z,且 ε \varepsilon ε称为单字节加法的传送位(carry bit, ε = 1 \varepsilon =1 ε=1当且仅当 z < x + ε ′ z<x+\varepsilon ‘ z<x+ε)。
多字节整数加法的算法描述如下。
在这里插入图片描述需要指出的是,处理传送指令的处理器并不一定需要对传送处理进行事无巨细的检查。多字节减法与加法操作类似,只是将传送位改称为借位而已。
质数域的算数运算[通俗易懂]
加法模运算 ( ( x + y ) m o d    p ) ((x+y)\mod p) ((x+y)modp)和减法模运算 ( ( x − y ) m o d    p ) ((x-y)\mod p) ((xy)modp)都适用于以上的算法,只是将加法替换成减法并取模。
质数域的算数运算[通俗易懂]

整数乘法

a , b ∈ F p a,b\in F_p a,bFp的有限域乘法能够通过 a a a b b b的乘积,得到一个整数值,然后采用约化模p来获得结果。以下算法展示了整数乘法的思路,包括基本的操作数乘法扫描方法。每种算法都是通过用 W W W-位连接将U和V连接起来,将 ( U V ) (U V) (UV)表示成一个 ( 2 W ) (2W) (2W)-位的量。
质数域的算数运算[通俗易懂]
在步骤2.2中, C [ i + j ] + A [ i ] ⋅ B [ j ] + U C[i+j]+A[i]\cdot B[j]+U C[i+j]+A[i]B[j]+U称为内积操作。操作数是W-位值,内积的界限是 2 ( 2 W − 1 ) + ( 2 W − 1 ) 2 = 2 2 W − 1 2(2^W-1)+(2^W-1)^2=2^{2W}-1 2(2W1)+(2W1)2=22W1,表示为 ( U V ) (U V) (UV)。以下算法描述了内积 c = a b c=ab c=ab从右到左的计算方法。正如前述算法所示,W-位的 ( 2 W ) (2W) (2W)-位内积的操作数是必须的,包括 R 0 , R 1 , R 2 , U R_0,R_1,R_2,U R0,R1,R2,U和V。
质数域的算数运算[通俗易懂]

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234646.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • php安装

    php安装

  • c# 进度条的使用(例子)[通俗易懂]

    c# 进度条的使用(例子)[通俗易懂]2012-05-2320:21在用c#做WinFrom开发的过程中。我们经常需要用到进度条(ProgressBar)用于显示进度信息。这时候我们可能就需要用到多线程,如果不采用多线程控制进度条,窗口很容易假死(无法适时看到进度信息)。下面我就简单结合一个我写的例子给大家做一个介绍。首先看一下程序界面第一步:设计界面不说了…注意需要引用usingSyst

  • 最大公约数和最小公倍数

    最大公约数和最小公倍数最大公约数和最小公倍数

  • python二级考试考生必看[通俗易懂]

    python二级考试考生必看[通俗易懂]考试环境:Windows7操作系统,Python3.5版本。已经预装idle开发环境(没有pycharm、spyder)涉及到考试中需要使用的库,无需考生安装,已经安装调试完毕,考试全程采用物理断网,

  • 游戏开发怎么做(游戏开发流程详解)

    本文来自作者goto先生在GitChat上分享「如何开发一款游戏:游戏开发流程及所需工具」,「阅读原文」查看交流实录。「文末高能」编辑|哈比游戏作为娱乐生活的一个方面,参与其中的人越来越多,而大部分参与其中的人都是以玩家的身份。他们热爱一款游戏,或是被游戏的故事情节、炫丽的场景、动听的音乐所艳羡,亦或是被游戏中角色扮演、炫酷的技能、有趣的任务所吸引,然而他们中的大多数可能并不了解如此

  • 一维卷积神经网络案例_matlab 卷积神经网络

    一维卷积神经网络案例_matlab 卷积神经网络基于一维卷积神经网络对机械振动信号进行分类并加以预测*使用一维卷积神经网络训练振动信号进行二分类2020年7月16日,一学期没等到开学,然而又放假了。总览CSDN中大多数卷积神经网络都是对二维图片进行分类的,而图片也都是常见的猫狗分类,minst手写数字分类。一维卷积神经网络的使用非常少见,有也是IDMB情感分类,和鸢尾花分类的。作者研究生就读于河北一所双飞,全国排名270多,哈哈哈,不吹不黑。在网上翻来翻去找不到一篇可以利用的代码去研究我的机械故障诊断,后来在无奈下到某宝搜寻到一段代码,可以利用

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号