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

质数域的算数运算[通俗易懂]本文介绍了在质数域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)


相关推荐

  • 每天一个linux命令(43):killall命令

    每天一个linux命令(43):killall命令

  • 情感的强度分类_情感量表

    情感的强度分类_情感量表一、SO-HowNet   情感倾向强度值计算公式为:其中,Pwords代表正面情感种子词语集合,Nwords代表负面种子词语集合。word1和word2相似度就是各概念之间相似度的最大值。计算两个义原相似度公式如下:其中,p1,p2为两个需要计算比较的义原,Depth(p)是义原层次体系中的深度,Spd

  • c语言xml解析器libxm2

    c语言xml解析器libxm2写这篇文章的原因有如下几点:1)C++标准库中没有操作XML的方法,用C++操作XML文件必须熟悉一种函数库,LIBXML2是其中一种很优秀的XML库,而且它同时支持多种编程语言;2)LIBXML2库的Tutorial写得不太好,尤其是编码转换的部分,不适用于中文编码的转换;3)网上的大多数关于Libxml2的介绍仅仅是翻译了自带的资料,没有详细介绍如何在windows平台下进行编程,更很少提到如

  • 【Java 8 新特性】Java LocalDate 转 Date

    【Java 8 新特性】Java LocalDate 转 DateJavaLocalDate转Date1.使用LocalDate.atTime2.使用LocalDate.atStartOfDay3.使用LocalDateTime.of4.使用Timestamp.valueOf完整示例参考文献在这一页,我们将提供如何将java.time.LocalDate转换成java.util.Date。LocalDate表示一个格式为yyyy-MM-dd的日期,如2019-05-08。我们可以使用以下方法和构造函数来创建一个Date对象。1.Date.f

  • 字符串转json对象 java_js中对象转字符串的方法

    字符串转json对象 java_js中对象转字符串的方法1.JSON数据和Java对象的相互转换JSON数据和Java对象的相互转换*JSON解析器:*常见的解析器:Jsonlib,Gson,fastjson,jackson1.Java对象转换JSON1.使用步骤:1.导入jackson的相关jar包2.创建Jackson核心对象ObjectMapper3.调用ObjectMapper的相关方法进行转换…

  • 数据库副本的自动种子设定(自增长)

    数据库副本的自动种子设定(自增长)

    2021年11月24日

发表回复

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

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