有限域的Fast Multiplication和Modular Reduction算法实现

这篇具有很好参考价值的文章主要介绍了有限域的Fast Multiplication和Modular Reduction算法实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 引言

关于有限域的基础知识,可参考:

  • RISC Zero团队2022年11月视频 Intro to Finite Fields: RISC Zero Study Club
    有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM

有限域几乎是密码学中所有数学的基础。
ZKP证明系统中的所有运算都是基于有限域的:

  • 使用布尔运算的数字电路:如AND、OR、NOT。
  • 使用有限域运算的算术电路:如addition、multiplication、negation。

但是,真实的计算机没有有限域电路装置,只有:

  • ADD rax, rbx
  • MUL rax
  • SHR rax, CL
  • 等等

因此,需基于以上运算来构建有限域运算。
有限域运算的速度很关键,原因在于:

  • 影响ZKP可用性的最大障碍在于证明开销。
  • 几乎所有的证明时间都用于有限域运算了。为提升ZKP证明速度:
    • 减少有限域运算次数(如,更高效的NTT或MSM算法)
    • 让有限域运算更高效(如,使用优化的有限域表示)

本文主要关注内容有:

  • BigInts
  • BigInts经典加法运算
  • BigInts经典乘法运算
  • Modular reduction(Barrett算法):当无法更改数字表示时,最有用。
  • Montgomery form
  • Multiplication and reduction(Montgomery算法):最常用算法。
  • 其它multiplication算法

并对大整数乘法运算的经典算法、Barrett算法、Montgomery算法进行了对比:
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM

2. 大整数及其加法和乘法运算

大整数,又名BigInt或Multiprecision Integers。
真实计算机的运算符是基于word的:

  • 几乎所有的现代计算机都使用64-bit words
  • 但32-bit words并未完全过时。比如在IoT世界。

对于更大(如256位)的域,会将其切分为words来表示:

  • 如,通常以4个64-bit word来表示256-bit数字。
  • 如十进制的8位数字,可 以4个2-digit word来表示。

如以100进制的digit来表示大整数27311837,对应为:
( 27   31   18   37 ) 100 (27\ 31\ 18\ 37)_{100} (27 31 18 37)100

2.1 大整数经典加法运算

对应的大整数加法运算,如 ( 27   31   18   37 ) 100 + ( 88   68   97   89 ) 100 (27\ 31\ 18\ 37)_{100} + (88\ 68\ 97\ 89)_{100} (27 31 18 37)100+(88 68 97 89)100,计算规则为:
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
具体见Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 10.3算法:
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM

2.2 大整数经典乘法运算

( 54   12 ) 100 ∗ ( 36   29 ) 100 (54\ 12)_{100}*(36\ 29)_{100} (54 12)100(36 29)100大整数乘法运算为例,具体见Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 10.8算法:
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
对应各个step的计算数据为:
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM

3. Modular Reduction

需注意,以上加法和乘法运算结果均为更大的值,需将这些大的结果值reduce为相应的canonical表示,如:
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
常见的Modular Reduction算法有:

  • 1)Barret reduction算法:当无法更改数字表示时,最有用。
  • 2)Montgomery multiplication and reduction算法:最常用算法。

相关博客有:

  • 基础算法优化——Fast Modular Multiplication
  • GPU/CPU友好的模乘算法:Multi-Precision Fast Modular Multiplication
  • Montgomery reduction——多精度模乘法运算算法

3.1 Barret reduction算法

做reduction最明显的方式是做除法,但除法运算昂贵,且可能不是constant time的。以single-word除法运算 b = 1 , R = 2 k b=1,R=2^k b=1R=2k 为例:

func reduce(a uint) uint {
    q:= a / n  // Division implicitly returns the floor of the result.
    return a - q * n
}

非constant time会存在timing attack攻击问题。
Barrett reduction为将 1 / n 1/n 1/n近似为 m / 2 k m/2^k m/2k,因为 m / 2 k m/2^k m/2k中的除法实际是右移运算,要便宜得多。【可近似计算 m m m值为 m = ⌊ 2 k / n ⌋ m=\left \lfloor 2^k/n\right \rfloor m=2k/n

func reduce(a uint) uint {
    q := (a * m) >> k // ">> k" denotes bitshift by k.
    return a - q * n
}

不过这样reduce之后的结果在 [ 0 , 2 n ) [0,2n) [0,2n),而不是 [ 0 , n ) [0,n) [0,n),因此需进一步reduce:

func reduce(a uint) uint {
    q := (a * m) >> k
    a -= q * n
    if a >= n {
        a -= n
    }
    return a
}

Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 10.17算法,将其扩展为了multi-word Barrett Reduction算法,且在以上最后一步reduce之前的结果不再是 [ 0 , 2 n ) [0,2n) [0,2n)而是可能更大的范围值,因此在Algorithm 10.17算法中第4步采用的是while
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM

3.2 Montgomery multiplication and reduction算法

Montgomery Form为另一种有限域表示,其支持快速combined multiplication and reduction算法。

之前将有限域元素表示为:
x ∈ [ 0 , N − 1 ] x\in [0,N-1] x[0,N1]

而Montgomery Form表示定义为:
[ x ] = ( x R ) m o d    N [x]=(xR)\mod N [x]=(xR)modN

Montgomery Reduction算法计算的是:
R E D C ( u ) = ( u R − 1 ) m o d    N REDC(u)=(uR^{-1})\mod N REDC(u)=(uR1)modN
而不是之前Barrett Reduction计算的 u m o d    N u\mod N umodN

R E D C REDC REDC是一个非常多功能的公式:

  • 1)将经典转换为Montgomery: [ x ] = R E D C ( ( x R 2 ) m o d    N ) [x]=REDC((xR^2)\mod N) [x]=REDC((xR2)modN)
  • 2)将Montgomery转换为经典: R E D C ( [ x ] ) = x REDC([x])=x REDC([x])=x
  • 3)对Montgomery Form表示的乘法运算: ( ( x R m o d    N ) ∗ ( y R m o d    N ) ∗ R − 1 m o d    N ) = ( x y R ) m o d    N ((xR\mod N)*(yR\mod N)*R^{-1}\mod N)=(xyR)\mod N ((xRmodN)(yRmodN)R1modN)=(xyR)modN,对应在Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 11.3算法中做了相应实现:
    有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM

其中 Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 10.22算法中所实现的Montgomery reduction算法为:
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM
有限域的Fast Multiplication和Modular Reduction算法实现,zkVM,zkVM

4. 其它multiplication算法

Multiplication算法的演变过程为:

  • multiplication算法曾被认为其runtime约为 O ( n 2 ) O(n^2) O(n2)
  • Karatsuba发明了一种divide-and-conquer算法,其runtime为 O ( n 1.58 ) O(n^{1.58}) O(n1.58)
  • Toom-Cook乘法算法与Karatsuba算法类似,性能略好一点。
  • Schönhage–Strassen 发明了一种NTT算法,其runtime为 O ( n ⋅ log ⁡ n ⋅ log ⁡ log ⁡ n ) O(n\cdot \log n\cdot \log\log n) O(nlognloglogn)
  • 当对大整数做乘法运算时,其速度要更慢,如4096位RSA密钥。

参考资料

[1] RISC Zero团队2023年2月视频 Finite Field Implementations: Barrett & Montgomery【slide见Finite Field Implementations】
[2] 维基百科Barrett reduction文章来源地址https://www.toymoban.com/news/detail-753458.html

RISC Zero系列博客

  • RISC0:Towards a Unified Compilation Framework for Zero Knowledge
  • Risc Zero ZKVM:zk-STARKs + RISC-V
  • 2023年 ZK Hack以及ZK Summit 亮点记
  • RISC Zero zkVM 白皮书
  • Risc0:使用Continunations来证明任意EVM交易
  • Zeth:首个Type 0 zkEVM
  • RISC Zero项目简介
  • RISC Zero zkVM性能指标
  • Continuations:扩展RISC Zero zkVM支持(无限)大计算
  • A summary on the FRI low degree test前2页导读
  • Reed-Solomon Codes及其与RISC Zero zkVM的关系
  • RISC Zero zkVM架构
  • RISC-V与RISC Zero zkVM的关系

到了这里,关于有限域的Fast Multiplication和Modular Reduction算法实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • KMP算法 - 确定有限状态自动机

    子串匹配问题,拍脑袋一下子想出来的暴力解法大抵都是两重for循环,不断重复扫描主串,与子串进行匹配,重复换句话讲就是冗余,会有很高的时间复杂度 我先前博客大作业发的 模糊查找算法 就是如此,我那里是在计算一个匹配度的问题,通过相同定位到相同字母判定开

    2024年02月09日
    浏览(45)
  • 有限字符集的字符串压缩算法

    在开发中,经常有上报线上堆栈来分析处理线上问题的场景,所以,对堆栈的压缩和加密也是必不可少的。加密:可以使用AES对称加密算法,压缩:可以在上传时利用protobuf天生的压缩性对字符串进行压缩。 不过,出于对流量的节省和传输效率的提升,可以通过在堆栈上传前

    2024年02月11日
    浏览(66)
  • 【NLP】有限自动机的KMP算法

    目录 一、说明 二、无策略直接匹配法 2.1  简单粗暴的无脑匹配: 2.2 跳过外循环的思路

    2024年02月08日
    浏览(40)
  • 实现跨域的几种方式

    前后端的分离导致了跨域的产生  跨域的三要素:协议 域名 端口 三者有一个不同即产生跨域 例如: http ://www.csdn.com https ://www.csdn.com 由于协议不同,端口不同而产生跨域 注:http的默认端口80,https的默认端口443 跨域的解决方案 前端:webpack proxy,jsonp,ngix反向代理,webpac

    2024年02月13日
    浏览(47)
  • springboot实现跨域的五种方式

    出于浏览器的同源策略限制。同源策略(Sameoriginpolicy)是一种约定,它是浏览器最核心也最基本的安全功能,如果缺少了同源策略,则浏览器的正常功能可能都会受到影响。可以说Web是构建在同源策略基础之上的,浏览器只是针对同源策略的一种实现。 同源策略 同源策略会

    2024年02月05日
    浏览(52)
  • SpringBoot 实现跨域的六种方式

    目录 1.通过SpringSecurity方式配置 2.使用Spring提供的CorsFilter注入Bean(推荐) 3.使用注解@CrossOrigin注解(繁琐) 4.通过ResponseBodyAdvice 实现跨域 5.通过HttpServletResponse设置跨域 6.通过WebMvcConfigurer 实现跨域 与第5类似

    2024年02月14日
    浏览(49)
  • 【SpringBoot系列】实现跨域的几种方式

    前言 在Web开发中,跨域是一个常见的问题。由于浏览器的同源策略,一个Web应用程序只能访问与其自身同源(即,相同协议、主机和端口)的资源。 这种策略的存在是为了保护用户的安全,防止恶意网站读取或修改用户的数据。 然而,现代Web应用程序经常需要访问不同源的

    2024年02月01日
    浏览(55)
  • FGSM(Fast Gradient Sign Method)算法源码解析

    论文链接:https://arxiv.org/abs/1412.6572 源码出处:https://github.com/Harry24k/adversarial-attacks-pytorch/tree/master FGSM的全称是Fast Gradient Sign Method(快速梯度下降法),在白盒环境下,通过求出损失 cost 对输入的导数,然后用符号函数 sign() 得到其具体的梯度方向,接着乘以一个步长 eps ,得

    2024年02月08日
    浏览(72)
  • Java实现后端跨域的常见解决方式

    1.1、maven依赖 pom.xml 1.2、接口 1.3、配置 application.properties   至此我们就提供了一个接口: http://localhost:8080/crossServer/cross/request 2.1、maven依赖 pom.xml 2.2、接口 2.3、页面 2.4、配置 application.properties   至此我们就提供了一个接口: http://localhost:8081/crossWeb/test/request ,访问此页

    2024年02月09日
    浏览(45)
  • 4.2 MATRIX MULTIPLICATION

    矩阵-矩阵乘法,或简称矩阵乘法,在 i X j(i 行 by j 列)矩阵 M 和 j x k 矩阵 N 之间产生 i X k 矩阵P。矩阵乘法是基本线性代数子程序(BLAS)标准的重要组成部分(见第3章中的“线性代数函数”边栏:可扩展并行执行)。该函数是许多线性代数求解器(如LU分解)的基础。正如

    2024年01月23日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包