跳转到内容
标准库Zig 0.17.1官方原文
源码std/crypto/ff.zig

第 1 行

无需分配、尽力保持常数时间的大整数有限域算术。

与 std.math.big 不同,这些整数具有固定的最大长度,且仅用于模算术。 算术操作旨在对给定模数以常数时间运行,因此适用于密码学。

名称中包含 Public 的函数除外。

部分代码移植自 Go 语言中采用 BSD 许可证的 crypto/internal/bigmod/nat.go 文件;该文件本身受 BearSSL 启发。

std.crypto.ff.assert

别名

第 16 行

别名目标 std.debug.assert

std.crypto.ff.builtin

常量

第 11 行

std.crypto.ff.carry_bits

常量

第 23 行

std.crypto.ff.crypto

别名

第 12 行

别名目标 std.crypto

std.crypto.ff.ct

类型

第 1086 行

std.crypto.ff.ct_protected

命名空间

第 1088 行

std.crypto.ff.ct_protected.eql

函数

第 1096 行

fn eql(x: anytype, y: @TypeOf(x)) bool

参数

y: @TypeOf(x)

std.crypto.ff.ct_protected.limbsCmpGeq

函数

第 1112 行

fn limbsCmpGeq(x: anytype, y: @TypeOf(x)) bool

参数

y: @TypeOf(x)

std.crypto.ff.ct_protected.limbsCmpLt

函数

第 1103 行

fn limbsCmpLt(x: anytype, y: @TypeOf(x)) bool

参数

y: @TypeOf(x)

std.crypto.ff.ct_protected.mulWide

函数

第 1117 行

fn mulWide(x: Limb, y: Limb) WideLimb

参数

x: Limb
y: Limb

std.crypto.ff.ct_protected.select

函数

第 1090 行

fn select(on: bool, x: Limb, y: Limb) Limb

参数

on: bool
x: Limb
y: Limb

std.crypto.ff.ct_unprotected

命名空间

第 1135 行

std.crypto.ff.ct_unprotected.eql

函数

第 1142 行

fn eql(x: anytype, y: @TypeOf(x)) bool

参数

y: @TypeOf(x)

std.crypto.ff.ct_unprotected.limbsCmpGeq

函数

第 1163 行

fn limbsCmpGeq(x: anytype, y: @TypeOf(x)) bool

参数

y: @TypeOf(x)

std.crypto.ff.ct_unprotected.limbsCmpLt

函数

第 1147 行

fn limbsCmpLt(x: anytype, y: @TypeOf(x)) bool

参数

y: @TypeOf(x)

std.crypto.ff.ct_unprotected.mulWide

函数

第 1168 行

fn mulWide(x: Limb, y: Limb) WideLimb

参数

x: Limb
y: Limb

std.crypto.ff.ct_unprotected.select

函数

第 1137 行

fn select(on: bool, x: Limb, y: Limb) Limb

参数

on: bool
x: Limb
y: Limb

std.crypto.ff.decodeBytes

函数

第 512 行

fn decodeBytes(limbs: []Limb, bytes: []const u8, comptime endian: Endian) Limb

参数

limbs: []Limb
bytes: []const u8
endian: Endian

std.crypto.ff.DivisionByZeroError

错误集合

第 56 行

错误

DivisionByZero

std.crypto.ff.Endian

别名

第 17 行

别名目标 std.lang.Endian

std.crypto.ff.Error

错误集合

第 59 行

std.crypto.ff 函数可能返回的全部错误集合。

错误

DivisionByZero DivisionByZeroError
EvenModulus InvalidModulusError
ModulusTooSmall InvalidModulusError
NonCanonical FieldElementError
NullExponent NullExponentError
Overflow OverflowError
UnexpectedRepresentation RepresentationError

std.crypto.ff.expectWellFormedLimbs

函数

第 1298 行

fn expectWellFormedLimbs(x: anytype) !void

std.crypto.ff.Fe_

类型函数

第 425 行

域元素。

fn Fe_(comptime bits: comptime_int) type

参数

bits: comptime_int

字段

v: FeUint

以 Uint 表示的元素值。

montgomery: bool = false

若元素采用蒙哥马利形式,则为 true。

std.crypto.ff.Fe_.compare

函数

第 492 行

以恒定时间比较两个域元素。

pub fn compare(x: Self, y: Self) math.Order

参数

x: Self
y: Self

std.crypto.ff.Fe_.encoded_bytes

常量

第 438 行

编码域元素所需的最大字节数。

std.crypto.ff.Fe_.eql

函数

第 486 行

以常量时间判断域元素是否相等,并返回 true。 不同表示形式的元素比较结果为不等;要比较数值,应先将其转换为相同形式。

pub fn eql(x: Self, y: Self) bool

参数

x: Self
y: Self

std.crypto.ff.Fe_.FeUint

类型

第 429 行

std.crypto.ff.Fe_.fromBytes

函数

第 467 行

从字节串创建域元素。

pub fn fromBytes(m: Modulus(bits), bytes: []const u8, comptime endian: Endian) (OverflowError || FieldElementError)!Self

参数

m: Modulus(bits)
bytes: []const u8
endian: Endian

std.crypto.ff.Fe_.fromPrimitive

函数

第 447 行

从原始值创建域元素。 此函数可能不是常量时间。

pub fn fromPrimitive(comptime T: type, m: Modulus(bits), x: T) (OverflowError || FieldElementError)!Self

参数

T: type
m: Modulus(bits)
x: T

std.crypto.ff.Fe_.isOdd

函数

第 504 行

若元素为奇数,则返回 true。 要求使用普通表示形式,因为蒙哥马利编码不保留奇偶性。

pub fn isOdd(self: Self) bool

参数

self: Self

std.crypto.ff.Fe_.isZero

函数

第 498 行

若元素为零,则返回 true。

pub fn isZero(self: Self) bool

参数

self: Self

std.crypto.ff.Fe_.limbs_count

函数

第 441 行

fn limbs_count(self: Self) usize

参数

self: Self

std.crypto.ff.Fe_.Self

别名

第 427 行

别名目标 std.crypto.ff.Fe_

std.crypto.ff.Fe_.toBytes

函数

第 477 行

将域元素转换为字节串。 如果元素采用蒙哥马利形式,则返回错误。

pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) (OverflowError || RepresentationError)!void

参数

self: Self
bytes: []u8
endian: Endian

std.crypto.ff.Fe_.toPrimitive

函数

第 459 行

将域元素转换为原始值。 此函数可能不是常量时间。 若元素采用 Montgomery 形式,则返回错误。

pub fn toPrimitive(self: Self, comptime T: type) (OverflowError || RepresentationError)!T

参数

self: Self
T: type

std.crypto.ff.FieldElementError

错误集合

第 51 行

对于给定模数,域元素无效。

错误

NonCanonical

std.crypto.ff.InvalidModulusError

错误集合

第 43 行

模数无效。模数必须是奇数。

错误

EvenModulus
ModulusTooSmall

std.crypto.ff.Limb

类型

第 20 行

std.crypto.ff.math

别名

第 13 行

别名目标 std.math

std.crypto.ff.maxUintBytes

函数

第 1308 行

fn maxUintBytes(comptime U: type) [@divCeil(U.capacity_bits, 8)]u8

参数

U: type

std.crypto.ff.mem

别名

第 14 行

别名目标 std.mem

std.crypto.ff.Modulus

类型函数

第 579 行

定义有限域的模数。 域内全部运算均对此模数取模,不进行堆分配。 max_bits 表示模数可设置的最大值的位数。

pub fn Modulus(comptime max_bits: comptime_int) type

参数

max_bits: comptime_int

字段

zero: Fe

单位元。

v: FeUint

模数值。

rr: Fe

蒙哥马利表示的 R^2。

m0inv: Limb

第一个 limb 的逆元

leading: usize

模数中的前导零位数。

std.crypto.ff.Modulus.add

函数

第 746 行

将两个域元素相加(对 m 取模)。

pub fn add(self: Self, x: Fe, y: Fe) Fe

参数

self: Self
x: Fe
y: Fe

std.crypto.ff.Modulus.bits

函数

第 608 行

模数的实际大小,单位为位。

pub fn bits(self: Self) usize

参数

self: Self

std.crypto.ff.Modulus.computeRR

函数

第 706 行

fn computeRR(self: *Self) void

参数

self: *Self

std.crypto.ff.Modulus.encodedLen

函数

第 613 行

返回编码后的长度,单位为字节。

pub fn encodedLen(self: Self) usize

参数

self: Self

std.crypto.ff.Modulus.Fe

类型

第 585 行

一个域元素,表示由该模数定义的域中的值。 元素只能与创建它的模数一起使用,即使另一个模数大小相同也不例外。

std.crypto.ff.Modulus.FeUint

常量

第 587 行

std.crypto.ff.Modulus.fromBytes

函数

第 670 行

从字节串创建新的模数。

pub fn fromBytes(bytes: []const u8, comptime endian: Endian) (InvalidModulusError || OverflowError)!Self

参数

bytes: []const u8
endian: Endian

std.crypto.ff.Modulus.fromMontgomery

函数

第 801 行

将域元素从 Montgomery 形式转换出来。

pub fn fromMontgomery(self: Self, x: *Fe) RepresentationError!void

参数

self: Self
x: *Fe

错误

UnexpectedRepresentation

std.crypto.ff.Modulus.fromPrimitive

函数

第 663 行

从原始值创建新模数。模数必须为奇数且大于 2。

pub fn fromPrimitive(comptime T: type, x: T) (InvalidModulusError || OverflowError)!Self

参数

T: type
x: T

std.crypto.ff.Modulus.fromUint

函数

第 626 行

由 Uint 值创建新的模数。 模数必须为大于 2 的奇数。

pub fn fromUint(v_: FeUint) InvalidModulusError!Self

参数

v_: FeUint

错误

EvenModulus
ModulusTooSmall

std.crypto.ff.Modulus.limbs_count

函数

第 603 行

fn limbs_count(self: Self) usize

参数

self: Self

std.crypto.ff.Modulus.max_encoded_bytes

常量

第 1040 行

std.crypto.ff.Modulus.montgomeryLoop

函数

第 830 行

fn montgomeryLoop(self: Self, d: *Fe, x: Fe, y: Fe) u1

参数

self: Self
d: *Fe
x: Fe
y: Fe

std.crypto.ff.Modulus.montgomeryMul

函数

第 877 行

fn montgomeryMul(self: Self, x: Fe, y: Fe) Fe

参数

self: Self
x: Fe
y: Fe

std.crypto.ff.Modulus.montgomerySq

函数

第 890 行

fn montgomerySq(self: Self, x: Fe) Fe

参数

self: Self
x: Fe

std.crypto.ff.Modulus.mul

函数

第 1004 行

计算两个域元素的乘积。 结果保留第一个操作数的表示形式。

pub fn mul(self: Self, x: Fe, y: Fe) Fe

参数

self: Self
x: Fe
y: Fe

std.crypto.ff.Modulus.one

函数

第 618 行

返回元素 1。

pub fn one(self: Self) Fe

参数

self: Self

std.crypto.ff.Modulus.pow

函数

第 1043 行

以常量时间返回 x^e (mod m)。

pub fn pow(self: Self, x: Fe, e: Fe) (NullExponentError || RepresentationError)!Fe

参数

self: Self
x: Fe
e: Fe

std.crypto.ff.Modulus.powPublic

函数

第 1056 行

返回 x^e (mod m),假定指数公开。 对于 x,此函数仍为常量时间。

pub fn powPublic(self: Self, x: Fe, e: Fe) (NullExponentError || RepresentationError)!Fe

参数

self: Self
x: Fe
e: Fe

std.crypto.ff.Modulus.powWithEncodedExponent

函数

第 1071 行

返回 x^e (mod m),指数以字节字符串提供。 指数通常较小,因此若已有序列化表示,此函数无需创建域元素,比 powPublic 更快。

若指数公开,可以改用 powWithEncodedPublicExponent(),略微提高速度。

pub fn powWithEncodedExponent(self: Self, x: Fe, e: []const u8, endian: Endian) NullExponentError!Fe

参数

self: Self
x: Fe
e: []const u8
endian: Endian

错误

NullExponent

std.crypto.ff.Modulus.powWithEncodedExponentInternal

函数

第 903 行

fn powWithEncodedExponentInternal(self: Self, x: Fe, e: []const u8, endian: Endian, comptime public: bool) NullExponentError!Fe

参数

self: Self
x: Fe
e: []const u8
endian: Endian
public: bool

错误

NullExponent

std.crypto.ff.Modulus.powWithEncodedPublicExponent

函数

第 1080 行

返回 x^e (mod m),指数为公开值,以字节串提供。 指数通常较小,因此当已有序列化表示时,无需创建域元素, 此函数比 powPublic 更快。

如果指数为秘密值,则必须改用 powWithEncodedExponent。

pub fn powWithEncodedPublicExponent(self: Self, x: Fe, e: []const u8, endian: Endian) NullExponentError!Fe

参数

self: Self
x: Fe
e: []const u8
endian: Endian

错误

NullExponent

std.crypto.ff.Modulus.reduce

函数

第 811 行

约减任意 Uint,将其转换为域元素。

pub fn reduce(self: Self, x: anytype) Fe

参数

self: Self

std.crypto.ff.Modulus.rejectNonCanonical

函数

第 686 行

拒绝非规范形式的域元素。

pub fn rejectNonCanonical(self: Self, fe: Fe) error{NonCanonical}!void

参数

self: Self
fe: Fe

错误

NonCanonical

std.crypto.ff.Modulus.Self

别名

第 581 行

别名目标 std.crypto.ff.Modulus

std.crypto.ff.Modulus.shiftIn

函数

第 717 行

计算 x << t_bits + y (mod m)

fn shiftIn(self: Self, x: *Fe, y: Limb) void

参数

self: Self
x: *Fe
y: Limb

std.crypto.ff.Modulus.shrink

函数

第 693 行

fn shrink(self: Self, fe: *Fe) OverflowError!void

参数

self: Self
fe: *Fe

错误

Overflow

std.crypto.ff.Modulus.sq

函数

第 1028 行

将域元素平方。

pub fn sq(self: Self, x: Fe) Fe

参数

self: Self
x: Fe

std.crypto.ff.Modulus.sub

函数

第 771 行

两域元素相减(模 m)。

pub fn sub(self: Self, x: Fe, y: Fe) Fe

参数

self: Self
x: Fe
y: Fe

std.crypto.ff.Modulus.toBytes

函数

第 676 行

将模数序列化为字节串。

pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) OverflowError!void

参数

self: Self
bytes: []u8
endian: Endian

错误

Overflow

std.crypto.ff.Modulus.toMontgomery

函数

第 791 行

将域元素转换为 Montgomery 形式。

pub fn toMontgomery(self: Self, x: *Fe) RepresentationError!void

参数

self: Self
x: *Fe

错误

UnexpectedRepresentation

std.crypto.ff.Modulus.toUint

函数

第 681 行

将模数作为整数返回

pub fn toUint(self: Self) FeUint

参数

self: Self

std.crypto.ff.mulAddLimb

函数

第 553 行

fn mulAddLimb(z: []Limb, x: []const Limb, y: Limb) Limb

参数

z: []Limb
x: []const Limb
y: Limb

std.crypto.ff.mulAddWide

函数

第 569 行

fn mulAddWide(z: []Limb, x: []const Limb, y: []const Limb) void

参数

z: []Limb
x: []const Limb
y: []const Limb

std.crypto.ff.native_endian

常量

第 31 行

std.crypto.ff.NullExponentError

错误集合

第 48 行

使用零指数求幂。 密码协议中出现零指数求幂,几乎总是存在可能导致轻易被攻击的缺陷。 因此,此模块遇到零指数时返回错误,促使应用程序显式处理这种情况。

错误

NullExponent

std.crypto.ff.orLimbs

函数

第 544 行

fn orLimbs(limbs: []const Limb) Limb

参数

limbs: []const Limb

std.crypto.ff.OverflowError

错误集合

第 40 行

值过大,无法写入目标位置。

错误

Overflow

std.crypto.ff.RepresentationError

错误集合

第 54 行

表示形式无效(Montgomery 域与非 Montgomery 域不一致)。

错误

UnexpectedRepresentation

std.crypto.ff.std

别名

第 10 行

别名目标 std

std.crypto.ff.t_bits

常量

第 26 行

usize

std.crypto.ff.testCt

函数

第 1275 行

fn testCt(ct_: anytype) !void

std.crypto.ff.testing

别名

第 15 行

别名目标 std.testing

std.crypto.ff.TLimb

常量

第 29 行

std.crypto.ff.Uint

类型函数

第 64 行

最大大小固定为 max_bits 的无符号大整数,适用于密码学操作。 存储大小向上取整到完整的 limb,可容纳至多 capacity_bits 位。 除非明确禁用侧信道防护,否则各操作均按恒定时间设计。

pub fn Uint(comptime max_bits: comptime_int) type

参数

max_bits: comptime_int

字段

limbs_buffer: [max_limbs_count]Limb
limbs_len: usize

有效 limb 的数量。

std.crypto.ff.Uint.addWithOverflow

函数

第 236 行

将 y 加到 x 上,并在较大的活动位宽处回绕。溢出时返回 1。

pub fn addWithOverflow(x: *Self, y: Self) u1

参数

x: *Self
y: Self

std.crypto.ff.Uint.bitLenPublic

函数

第 261 行

返回位长度;零则返回 0。

pub fn bitLenPublic(x: Self) usize

参数

x: Self

std.crypto.ff.Uint.capacity_bits

常量

第 72 行

std.crypto.ff.Uint.cmov

函数

第 358 行

fn cmov(x: *Self, on: bool, y: Self) void

参数

x: *Self
on: bool
y: Self

std.crypto.ff.Uint.compare

函数

第 211 行

比较两个整数。

pub fn compare(x: Self, y: Self) math.Order

参数

x: Self
y: Self

std.crypto.ff.Uint.conditionalAddWithOverflow

函数

第 365 行

fn conditionalAddWithOverflow(x: *Self, on: bool, y: Self) u1

参数

x: *Self
on: bool
y: Self

std.crypto.ff.Uint.conditionalSubWithOverflow

函数

第 377 行

fn conditionalSubWithOverflow(x: *Self, on: bool, y: Self) u1

参数

x: *Self
on: bool
y: Self

std.crypto.ff.Uint.divRemPublic

函数

第 305 行

原地除以 divisor 并返回余数。 若 divisor 为零,则返回 error.DivisionByZero,不修改整数。

pub fn divRemPublic(x: *Self, divisor: usize) DivisionByZeroError!usize

参数

x: *Self
divisor: usize

错误

DivisionByZero

std.crypto.ff.Uint.encoded_bytes

常量

第 79 行

序列化整数所需的字节数。

std.crypto.ff.Uint.eql

函数

第 206 行

若两个整数相等则返回 true。

pub fn eql(x: Self, y: Self) bool

参数

x: Self
y: Self

std.crypto.ff.Uint.expandTo

函数

第 351 行

fn expandTo(x: *Self, new_len: usize) void

参数

x: *Self
new_len: usize

std.crypto.ff.Uint.fromBytes

函数

第 197 行

从字节数组创建新的大整数。

pub fn fromBytes(bytes: []const u8, comptime endian: Endian) OverflowError!Self

参数

bytes: []const u8
endian: Endian

错误

Overflow

std.crypto.ff.Uint.fromPrimitive

函数

第 112 行

从原始类型创建新的大整数。 此函数可能不是常量时间运行。

pub fn fromPrimitive(comptime T: type, init_value: T) OverflowError!Self

参数

T: type
init_value: T

错误

Overflow

std.crypto.ff.Uint.gcdPublic

函数

第 322 行

返回最大公约数,其中 gcd(x, 0) = x。 若两个操作数均为零,返回 error.DivisionByZero。

pub fn gcdPublic(x: Self, y: Self) DivisionByZeroError!Self

参数

x: Self
y: Self

错误

DivisionByZero

std.crypto.ff.Uint.isOdd

函数

第 226 行

若整数为奇数则返回 true。

pub fn isOdd(x: Self) bool

参数

x: Self

std.crypto.ff.Uint.isOne

函数

第 230 行

pub fn isOne(x: Self) bool

参数

x: Self

std.crypto.ff.Uint.isZero

函数

第 221 行

若整数为零则返回 true。

pub fn isZero(x: Self) bool

参数

x: Self

std.crypto.ff.Uint.limbs

函数

第 87 行

活动 Limb 的可变切片。

fn limbs(self: *Self) []Limb

参数

self: *Self

std.crypto.ff.Uint.limbsConst

函数

第 82 行

活动 Limb 的常量切片。

fn limbsConst(self: *const Self) []const Limb

参数

self: *const Self

std.crypto.ff.Uint.max_limbs_count

常量

第 70 行

std.crypto.ff.Uint.mulAddWithOverflow

函数

第 249 行

将 x 与 y 的乘积加到 acc,按当前有效位宽回绕。 若结果有任何部分被丢弃,则返回 1。

pub fn mulAddWithOverflow(acc: *Self, x: Self, y: Self) u1

参数

acc: *Self
x: Self
y: Self

std.crypto.ff.Uint.normalize

函数

第 92 行

fn normalize(self: Self) Self

参数

self: Self

std.crypto.ff.Uint.Self

别名

第 69 行

别名目标 std.crypto.ff.Uint

std.crypto.ff.Uint.shiftLeft

函数

第 388 行

fn shiftLeft(x: *Self, shift: usize) void

参数

x: *Self
shift: usize

std.crypto.ff.Uint.shiftRightByOneWithCarry

函数

第 409 行

fn shiftRightByOneWithCarry(x: *Self, carry: u1) u1

参数

x: *Self
carry: u1

std.crypto.ff.Uint.shiftRightPublic

函数

第 283 行

pub fn shiftRightPublic(x: *Self, shift: usize) void

参数

x: *Self
shift: usize

std.crypto.ff.Uint.subWithOverflow

函数

第 242 行

从 x 减去 y,按两者中较大的有效位宽回绕。下溢时返回 1。

pub fn subWithOverflow(x: *Self, y: Self) u1

参数

x: *Self
y: Self

std.crypto.ff.Uint.toBytes

函数

第 150 行

将大整数编码为字节数组。

pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) OverflowError!void

参数

self: Self
bytes: []u8
endian: Endian

错误

Overflow

std.crypto.ff.Uint.toPrimitive

函数

第 131 行

将大整数转换为基本类型。 此函数可能不以常数时间运行。

pub fn toPrimitive(self: Self, comptime T: type) OverflowError!T

参数

self: Self
T: type

错误

Overflow

std.crypto.ff.Uint.trailingZeroBitsPublic

函数

第 274 行

返回尾随零位的数量;输入为零时返回有效位宽。

pub fn trailingZeroBitsPublic(x: Self) usize

参数

x: Self

std.crypto.ff.Uint.zero

常量

第 105 行

整数零。

Self

std.crypto.ff.WideLimb

容器

第 34 行

字段

hi: Limb
lo: Limb
源码

std/crypto/ff.zig

//! 无需分配、尽力保持常数时间的大整数有限域算术。
//!
//! 与 `std.math.big` 不同,这些整数具有固定的最大长度,且仅用于模算术。
//! 算术操作旨在对给定模数以常数时间运行,因此适用于密码学。
//!
//! 名称中包含 `Public` 的函数除外。
//!
//! 部分代码移植自 Go 语言中采用 BSD 许可证的 crypto/internal/bigmod/nat.go 文件;该文件本身受 BearSSL 启发。

const std = @import("std");
const builtin = @import("builtin");
const crypto = std.crypto;
const math = std.math;
const mem = std.mem;
const testing = std.testing;
const assert = std.debug.assert;
const Endian = std.builtin.Endian;

// Limb 是大整数中的单个数位。
const Limb = usize;

// Limb 中的保留位数。
const carry_bits = 1;

// Limb 中的活动位数。
const t_bits: usize = @bitSizeOf(Limb) - carry_bits;

// TLimb 是截断到 t_bits 的 Limb。
const TLimb = @Int(.unsigned, t_bits);

const native_endian = builtin.target.cpu.arch.endian();

// WideLimb 的位宽是普通 Limb 的两倍。
const WideLimb = struct {
    hi: Limb,
    lo: Limb,
};

/// 值过大,无法写入目标位置。
pub const OverflowError = error{Overflow};

/// 模数无效。模数必须是奇数。
pub const InvalidModulusError = error{ EvenModulus, ModulusTooSmall };

/// 使用零指数求幂。
/// 密码协议中出现零指数求幂,几乎总是存在可能导致轻易被攻击的缺陷。
/// 因此,此模块遇到零指数时返回错误,促使应用程序显式处理这种情况。
pub const NullExponentError = error{NullExponent};

/// 对于给定模数,域元素无效。
pub const FieldElementError = error{NonCanonical};

/// 表示形式无效(Montgomery 域与非 Montgomery 域不一致)。
pub const RepresentationError = error{UnexpectedRepresentation};

pub const DivisionByZeroError = error{DivisionByZero};

/// `std.crypto.ff` 函数可能返回的全部错误集合。
pub const Error = OverflowError || InvalidModulusError || NullExponentError || FieldElementError || RepresentationError || DivisionByZeroError;

/// 最大大小固定为 `max_bits` 的无符号大整数,适用于密码学操作。
/// 存储大小向上取整到完整的 limb,可容纳至多 `capacity_bits` 位。
/// 除非明确禁用侧信道防护,否则各操作均按恒定时间设计。
pub fn Uint(comptime max_bits: comptime_int) type {
    comptime assert(@bitSizeOf(Limb) % 8 == 0); // Limb 的大小必须是 8 的倍数
    comptime assert(max_bits > 0);

    return struct {
        const Self = @This();
        const max_limbs_count = @divCeil(max_bits, t_bits);

        pub const capacity_bits = max_limbs_count * t_bits;

        limbs_buffer: [max_limbs_count]Limb,
        /// 有效 limb 的数量。
        limbs_len: usize,

        /// 序列化整数所需的字节数。
        pub const encoded_bytes = @divCeil(max_bits, 8);

        /// 活动 Limb 的常量切片。
        fn limbsConst(self: *const Self) []const Limb {
            return self.limbs_buffer[0..self.limbs_len];
        }

        /// 活动 Limb 的可变切片。
        fn limbs(self: *Self) []Limb {
            return self.limbs_buffer[0..self.limbs_len];
        }

        // 从有效 limb 中移除值为零的 limb。
        fn normalize(self: Self) Self {
            var res = self;
            if (self.limbs_len < 2) {
                return res;
            }
            var i = self.limbs_len - 1;
            while (i > 0 and res.limbsConst()[i] == 0) : (i -= 1) {}
            res.limbs_len = i + 1;
            assert(res.limbs_len <= res.limbs_buffer.len);
            return res;
        }

        /// 整数零。
        pub const zero: Self = .{
            .limbs_buffer = @splat(0),
            .limbs_len = max_limbs_count,
        };

        /// 从原始类型创建新的大整数。
        /// 此函数可能不是常量时间运行。
        pub fn fromPrimitive(comptime T: type, init_value: T) OverflowError!Self {
            const U = @Int(.unsigned, @bitSizeOf(T));
            var x = math.cast(U, init_value) orelse return error.Overflow;
            var out: Self = .{
                .limbs_buffer = undefined,
                .limbs_len = max_limbs_count,
            };
            for (&out.limbs_buffer) |*limb| {
                limb.* = if (@bitSizeOf(T) > t_bits) @as(TLimb, @truncate(x)) else x;
                x = math.shr(U, x, t_bits);
            }
            if (x != 0) {
                return error.Overflow;
            }
            return out;
        }

        /// 将大整数转换为基本类型。
        /// 此函数可能不以常数时间运行。
        pub fn toPrimitive(self: Self, comptime T: type) OverflowError!T {
            const U = @Int(.unsigned, @bitSizeOf(T));
            var x: U = 0;
            var i = self.limbs_len - 1;
            while (true) : (i -= 1) {
                // 即使目标窄于一个字,也要在移位前检查溢出。
                const discarded = if (@bitSizeOf(U) >= t_bits) math.shr(U, x, @bitSizeOf(U) - t_bits) else x;
                if (discarded != 0) {
                    return error.Overflow;
                }
                x = math.shl(U, x, t_bits);
                const v = math.cast(U, self.limbsConst()[i]) orelse return error.Overflow;
                x |= v;
                if (i == 0) break;
            }
            return math.cast(T, x) orelse error.Overflow;
        }

        /// 将大整数编码为字节数组。
        pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) OverflowError!void {
            if (bytes.len == 0) {
                if (self.isZero()) return;
                return error.Overflow;
            }
            @memset(bytes, 0);
            var shift: usize = 0;
            var out_i: usize = switch (endian) {
                .big => bytes.len - 1,
                .little => 0,
            };
            for (0..self.limbs_len) |i| {
                var remaining_bits = t_bits;
                var limb = self.limbsConst()[i];
                while (remaining_bits >= 8) {
                    bytes[out_i] |= math.shl(u8, @truncate(limb), shift);
                    const consumed = 8 - shift;
                    limb >>= @truncate(consumed);
                    remaining_bits -= consumed;
                    shift = 0;
                    switch (endian) {
                        .big => {
                            if (out_i == 0) {
                                if (limb | orLimbs(self.limbsConst()[i + 1 ..]) != 0) {
                                    return error.Overflow;
                                }
                                return;
                            }
                            out_i -= 1;
                        },
                        .little => {
                            out_i += 1;
                            if (out_i == bytes.len) {
                                if (limb | orLimbs(self.limbsConst()[i + 1 ..]) != 0) {
                                    return error.Overflow;
                                }
                                return;
                            }
                        },
                    }
                }
                bytes[out_i] |= @truncate(limb);
                shift = remaining_bits;
            }
        }

        /// 从字节数组创建新的大整数。
        pub fn fromBytes(bytes: []const u8, comptime endian: Endian) OverflowError!Self {
            var out = Self.zero;
            if (decodeBytes(out.limbs(), bytes, endian) != 0) {
                return error.Overflow;
            }
            return out;
        }

        /// 若两个整数相等则返回 `true`。
        pub fn eql(x: Self, y: Self) bool {
            return crypto.timing_safe.eql([max_limbs_count]Limb, x.limbs_buffer, y.limbs_buffer);
        }

        /// 比较两个整数。
        pub fn compare(x: Self, y: Self) math.Order {
            return crypto.timing_safe.compare(
                Limb,
                &x.limbs_buffer,
                &y.limbs_buffer,
                .little,
            );
        }

        /// 若整数为零则返回 `true`。
        pub fn isZero(x: Self) bool {
            return ct.eql(orLimbs(x.limbsConst()), 0);
        }

        /// 若整数为奇数则返回 `true`。
        pub fn isOdd(x: Self) bool {
            return @as(u1, @truncate(x.limbsConst()[0])) != 0;
        }

        pub fn isOne(x: Self) bool {
            const x_limbs = x.limbsConst();
            return ct.eql((x_limbs[0] ^ 1) | orLimbs(x_limbs[1..]), 0);
        }

        /// 将 `y` 加到 `x` 上,并在较大的活动位宽处回绕。溢出时返回 1。
        pub fn addWithOverflow(x: *Self, y: Self) u1 {
            x.expandTo(@max(x.limbs_len, y.limbs_len));
            return x.conditionalAddWithOverflow(true, y);
        }

        /// 从 `x` 减去 `y`,按两者中较大的有效位宽回绕。下溢时返回 1。
        pub fn subWithOverflow(x: *Self, y: Self) u1 {
            x.expandTo(@max(x.limbs_len, y.limbs_len));
            return x.conditionalSubWithOverflow(true, y);
        }

        /// 将 `x` 与 `y` 的乘积加到 `acc`,按当前有效位宽回绕。
        /// 若结果有任何部分被丢弃,则返回 1。
        pub fn mulAddWithOverflow(acc: *Self, x: Self, y: Self) u1 {
            assert(x.limbs_len == acc.limbs_len);
            assert(y.limbs_len == acc.limbs_len);
            const n = acc.limbs_len;
            var wide: [2 * max_limbs_count]Limb = undefined;
            @memcpy(wide[0..n], acc.limbsConst());
            mulAddWide(wide[0 .. 2 * n], x.limbsConst(), y.limbsConst());
            @memcpy(acc.limbs(), wide[0..n]);
            return @intFromBool(!ct.eql(orLimbs(wide[n..][0..n]), 0));
        }

        /// 返回位长度;零则返回 0。
        pub fn bitLenPublic(x: Self) usize {
            var i = x.limbs_len;
            while (i != 0) {
                i -= 1;
                const limb = x.limbsConst()[i];
                if (limb != 0) {
                    return i * t_bits + t_bits - @clz(@as(TLimb, @intCast(limb)));
                }
            }
            return 0;
        }

        /// 返回尾随零位的数量;输入为零时返回有效位宽。
        pub fn trailingZeroBitsPublic(x: Self) usize {
            for (x.limbsConst(), 0..) |limb, i| {
                if (limb != 0) {
                    return i * t_bits + @ctz(@as(TLimb, @intCast(limb)));
                }
            }
            return x.limbs_len * t_bits;
        }

        pub fn shiftRightPublic(x: *Self, shift: usize) void {
            const limb_shift = shift / t_bits;
            const bit_shift = shift % t_bits;
            const x_limbs = x.limbs();
            if (limb_shift >= x_limbs.len) {
                @memset(x_limbs, 0);
                return;
            }
            const active = x_limbs.len - limb_shift;
            for (0..active) |i| {
                const lo = math.shr(Limb, x_limbs[i + limb_shift], bit_shift);
                const hi = if (i + limb_shift + 1 < x_limbs.len)
                    math.shl(Limb, x_limbs[i + limb_shift + 1], t_bits - bit_shift)
                else
                    0;
                x_limbs[i] = @as(TLimb, @truncate(lo | hi));
            }
            @memset(x_limbs[active..], 0);
        }

        /// 原地除以 `divisor` 并返回余数。
        /// 若 `divisor` 为零,则返回 `error.DivisionByZero`,不修改整数。
        pub fn divRemPublic(x: *Self, divisor: usize) DivisionByZeroError!usize {
            if (divisor == 0) return error.DivisionByZero;
            const Wide = @Int(.unsigned, 2 * @bitSizeOf(Limb));
            const x_limbs = x.limbs();
            var rem: Limb = 0;
            var i = x.limbs_len;
            while (i != 0) {
                i -= 1;
                const num = (@as(Wide, rem) << t_bits) | x_limbs[i];
                x_limbs[i] = @intCast(num / divisor);
                rem = @intCast(num % divisor);
            }
            return rem;
        }

        /// 返回最大公约数,其中 gcd(x, 0) = x。
        /// 若两个操作数均为零,返回 `error.DivisionByZero`。
        pub fn gcdPublic(x: Self, y: Self) DivisionByZeroError!Self {
            if (x.isZero() and y.isZero()) return error.DivisionByZero;
            if (x.isZero()) return y;
            if (y.isZero()) return x;

            var a = x;
            var b = y;
            const len = @max(a.limbs_len, b.limbs_len);
            a.expandTo(len);
            b.expandTo(len);

            const a_shift = a.trailingZeroBitsPublic();
            const b_shift = b.trailingZeroBitsPublic();
            a.shiftRightPublic(a_shift);
            b.shiftRightPublic(b_shift);
            while (true) {
                switch (a.compare(b)) {
                    .eq => break,
                    .lt => mem.swap(Self, &a, &b),
                    .gt => {},
                }
                _ = a.subWithOverflow(b);
                a.shiftRightPublic(a.trailingZeroBitsPublic());
            }

            a.shiftLeft(@min(a_shift, b_shift)); // 最大公约数始终可由任一输入容纳,不会有溢出问题。
            return a;
        }

        fn expandTo(x: *Self, new_len: usize) void {
            assert(new_len >= x.limbs_len and new_len <= x.limbs_buffer.len);
            @memset(x.limbs_buffer[x.limbs_len..new_len], 0);
            x.limbs_len = new_len;
        }

        // 若 `on` 为 `true`,用 `y` 的 limb 替换 `x` 的 limb。
        fn cmov(x: *Self, on: bool, y: Self) void {
            for (x.limbs(), y.limbsConst()) |*x_limb, y_limb| {
                x_limb.* = ct.select(on, y_limb, x_limb.*);
            }
        }

        // 未使用的 limb 会被清零,因此 `y` 可以比 `x` 更窄。
        fn conditionalAddWithOverflow(x: *Self, on: bool, y: Self) u1 {
            var carry: u1 = 0;
            assert(y.limbs_len <= x.limbs_len);
            for (x.limbs(), 0..) |*x_limb, i| {
                const res = x_limb.* + y.limbs_buffer[i] + carry;
                x_limb.* = ct.select(on, @as(TLimb, @truncate(res)), x_limb.*);
                carry = @truncate(res >> t_bits);
            }
            return carry;
        }

        // 未使用的 limb 会被清零,因此 `y` 可以比 `x` 更窄。
        fn conditionalSubWithOverflow(x: *Self, on: bool, y: Self) u1 {
            var borrow: u1 = 0;
            assert(y.limbs_len <= x.limbs_len);
            for (x.limbs(), 0..) |*x_limb, i| {
                const res = x_limb.* -% y.limbs_buffer[i] -% borrow;
                x_limb.* = ct.select(on, @as(TLimb, @truncate(res)), x_limb.*);
                borrow = @truncate(res >> t_bits);
            }
            return borrow;
        }

        fn shiftLeft(x: *Self, shift: usize) void {
            assert(x.bitLenPublic() + shift <= x.limbs_len * t_bits);
            const limb_shift = shift / t_bits;
            const bit_shift = shift % t_bits;
            const x_limbs = x.limbs();
            var i = x_limbs.len;
            while (i != 0) {
                i -= 1;
                const hi = if (i >= limb_shift)
                    math.shl(Limb, x_limbs[i - limb_shift], bit_shift)
                else
                    0;
                const lo = if (i >= limb_shift + 1)
                    math.shr(Limb, x_limbs[i - limb_shift - 1], t_bits - bit_shift)
                else
                    0;
                x_limbs[i] = @as(TLimb, @truncate(hi | lo));
            }
        }

        // 从高位移入 `carry`,并返回移出的最低位。
        fn shiftRightByOneWithCarry(x: *Self, carry: u1) u1 {
            var c: Limb = carry;
            var i = x.limbs_len;
            const x_limbs = x.limbs();
            while (i != 0) {
                i -= 1;
                const limb = x_limbs[i];
                x_limbs[i] = (limb >> 1) | (c << (t_bits - 1));
                c = @as(u1, @truncate(limb));
            }
            return @truncate(c);
        }
    };
}

/// 域元素。
fn Fe_(comptime bits: comptime_int) type {
    return struct {
        const Self = @This();

        const FeUint = Uint(bits);

        /// 以 `Uint` 表示的元素值。
        v: FeUint,

        /// 若元素采用蒙哥马利形式,则为 `true`。
        montgomery: bool = false,

        /// 编码域元素所需的最大字节数。
        pub const encoded_bytes = FeUint.encoded_bytes;

        // 表示该域元素所用的有效 limb 数。
        fn limbs_count(self: Self) usize {
            return self.v.limbs_len;
        }

        /// 从原始值创建域元素。
        /// 此函数可能不是常量时间。
        pub fn fromPrimitive(comptime T: type, m: Modulus(bits), x: T) (OverflowError || FieldElementError)!Self {
            comptime assert(@bitSizeOf(T) <= bits); // 基本类型大于模数类型。
            const v = try FeUint.fromPrimitive(T, x);
            var fe = Self{ .v = v };
            try m.shrink(&fe);
            try m.rejectNonCanonical(fe);
            return fe;
        }

        /// 将域元素转换为原始值。
        /// 此函数可能不是常量时间。
        /// 若元素采用 Montgomery 形式,则返回错误。
        pub fn toPrimitive(self: Self, comptime T: type) (OverflowError || RepresentationError)!T {
            if (self.montgomery) {
                return error.UnexpectedRepresentation;
            }
            return self.v.toPrimitive(T);
        }

        /// 从字节串创建域元素。
        pub fn fromBytes(m: Modulus(bits), bytes: []const u8, comptime endian: Endian) (OverflowError || FieldElementError)!Self {
            const v = try FeUint.fromBytes(bytes, endian);
            var fe = Self{ .v = v };
            try m.shrink(&fe);
            try m.rejectNonCanonical(fe);
            return fe;
        }

        /// 将域元素转换为字节串。
        /// 如果元素采用蒙哥马利形式,则返回错误。
        pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) (OverflowError || RepresentationError)!void {
            if (self.montgomery) {
                return error.UnexpectedRepresentation;
            }
            return self.v.toBytes(bytes, endian);
        }

        /// 以常量时间判断域元素是否相等,并返回 `true`。
        /// 不同表示形式的元素比较结果为不等;要比较数值,应先将其转换为相同形式。
        pub fn eql(x: Self, y: Self) bool {
            const values_equal = x.v.eql(y.v);
            return x.montgomery == y.montgomery and values_equal;
        }

        /// 以恒定时间比较两个域元素。
        pub fn compare(x: Self, y: Self) math.Order {
            assert(!x.montgomery and !y.montgomery);
            return x.v.compare(y.v);
        }

        /// 若元素为零,则返回 `true`。
        pub fn isZero(self: Self) bool {
            return self.v.isZero();
        }

        /// 若元素为奇数,则返回 `true`。
        /// 要求使用普通表示形式,因为蒙哥马利编码不保留奇偶性。
        pub fn isOdd(self: Self) bool {
            assert(!self.montgomery);
            return self.v.isOdd();
        }
    };
}

// 解码到已清零的数位中,并返回无法容纳的各位按位或的结果。
fn decodeBytes(limbs: []Limb, bytes: []const u8, comptime endian: Endian) Limb {
    var acc: Limb = 0;
    var shift: usize = 0;
    var out_i: usize = 0;
    for (0..bytes.len) |k| {
        const bi = bytes[
            switch (endian) {
                .big => bytes.len - 1 - k,
                .little => k,
            }
        ];
        if (out_i >= limbs.len) {
            acc |= bi;
            continue;
        }
        limbs[out_i] |= math.shl(Limb, bi, shift);
        shift += 8;
        if (shift >= t_bits) {
            shift -= t_bits;
            limbs[out_i] = @as(TLimb, @truncate(limbs[out_i]));
            const spill = math.shr(Limb, bi, 8 - shift);
            out_i += 1;
            if (out_i < limbs.len) {
                limbs[out_i] = spill;
            } else {
                acc |= spill;
            }
        }
    }
    return acc;
}

fn orLimbs(limbs: []const Limb) Limb {
    var t: Limb = 0;
    for (limbs) |limb| {
        t |= limb;
    }
    return t;
}

// 将 `x * y` 加到 `z` 并返回进位。
fn mulAddLimb(z: []Limb, x: []const Limb, y: Limb) Limb {
    assert(z.len == x.len);
    var carry: Limb = 0;
    for (z, x) |*z_limb, x_limb| {
        const wide = ct.mulWide(x_limb, y);
        var z_lo = @addWithOverflow(z_limb.*, wide.lo);
        var z_hi = wide.hi +% z_lo[1];
        z_lo = @addWithOverflow(z_lo[0], carry);
        z_hi +%= z_lo[1];
        z_limb.* = @as(TLimb, @truncate(z_lo[0]));
        carry = (z_hi << 1) | (z_lo[0] >> t_bits);
    }
    return carry;
}

// 将 `x * y` 加到 `z` 的低 `x.len` 个数位中。高位数位无需初始化。
fn mulAddWide(z: []Limb, x: []const Limb, y: []const Limb) void {
    assert(z.len == x.len + y.len);
    for (y, 0..) |y_limb, i| {
        z[i + x.len] = mulAddLimb(z[i..][0..x.len], x, y_limb);
    }
}

/// 定义有限域的模数。
/// 域内全部运算均对此模数取模,不进行堆分配。
/// `max_bits` 表示模数可设置的最大值的位数。
pub fn Modulus(comptime max_bits: comptime_int) type {
    return struct {
        const Self = @This();

        /// 一个域元素,表示由该模数定义的域中的值。
        /// 元素只能与创建它的模数一起使用,即使另一个模数大小相同也不例外。
        pub const Fe = Fe_(max_bits);

        const FeUint = Fe.FeUint;

        /// 单位元。
        zero: Fe,

        /// 模数值。
        v: FeUint,

        /// 蒙哥马利表示的 R^2。
        rr: Fe,
        /// 第一个 limb 的逆元
        m0inv: Limb,
        /// 模数中的前导零位数。
        leading: usize,

        // 模数中活动 limb 的数量。
        fn limbs_count(self: Self) usize {
            return self.v.limbs_len;
        }

        /// 模数的实际大小,单位为位。
        pub fn bits(self: Self) usize {
            return self.limbs_count() * t_bits - self.leading;
        }

        /// 返回编码后的长度,单位为字节。
        pub fn encodedLen(self: Self) usize {
            return @divCeil(self.bits(), 8);
        }

        /// 返回元素 `1`。
        pub fn one(self: Self) Fe {
            var fe = self.zero;
            fe.v.limbs()[0] = 1;
            return fe;
        }

        /// 由 `Uint` 值创建新的模数。
        /// 模数必须为大于 2 的奇数。
        pub fn fromUint(v_: FeUint) InvalidModulusError!Self {
            if (!v_.isOdd()) return error.EvenModulus;

            var v = v_.normalize();
            const hi = v.limbsConst()[v.limbs_len - 1];
            const lo = v.limbsConst()[0];

            if (v.limbs_len < 2 and lo < 3) {
                return error.ModulusTooSmall;
            }

            const leading = @clz(hi) - carry_bits;

            var y = lo;

            inline for (0..comptime math.log2_int(usize, t_bits)) |_| {
                y = y *% (2 -% lo *% y);
            }
            const m0inv = (@as(Limb, 1) << t_bits) - (@as(TLimb, @truncate(y)));

            const zero = Fe{ .v = FeUint.zero };

            var m = Self{
                .zero = zero,
                .v = v,
                .leading = leading,
                .m0inv = m0inv,
                .rr = undefined, // 将在紧接着的位置计算
            };
            m.shrink(&m.zero) catch unreachable;
            computeRR(&m);

            return m;
        }

        /// 从原始值创建新模数。模数必须为奇数且大于 2。
        ///
        pub fn fromPrimitive(comptime T: type, x: T) (InvalidModulusError || OverflowError)!Self {
            comptime assert(@bitSizeOf(T) <= max_bits); // 基本类型大于模数类型。
            const v = try FeUint.fromPrimitive(T, x);
            return try Self.fromUint(v);
        }

        /// 从字节串创建新的模数。
        pub fn fromBytes(bytes: []const u8, comptime endian: Endian) (InvalidModulusError || OverflowError)!Self {
            const v = try FeUint.fromBytes(bytes, endian);
            return try Self.fromUint(v);
        }

        /// 将模数序列化为字节串。
        pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) OverflowError!void {
            return self.v.toBytes(bytes, endian);
        }

        /// 将模数作为整数返回
        pub fn toUint(self: Self) FeUint {
            return self.v;
        }

        /// 拒绝非规范形式的域元素。
        pub fn rejectNonCanonical(self: Self, fe: Fe) error{NonCanonical}!void {
            if (fe.limbs_count() != self.limbs_count() or ct.limbsCmpGeq(fe.v, self.v)) {
                return error.NonCanonical;
            }
        }

        // 使域元素中的有效数位数量与模数相同。
        fn shrink(self: Self, fe: *Fe) OverflowError!void {
            const new_len = self.limbs_count();
            if (fe.limbs_count() < new_len) return error.Overflow;
            var acc: Limb = 0;
            for (fe.v.limbsConst()[new_len..]) |limb| {
                acc |= limb;
            }
            if (acc != 0) return error.Overflow;
            if (new_len > fe.v.limbs_buffer.len) return error.Overflow;
            fe.v.limbs_len = new_len;
        }

        // 计算 Montgomery 表示所需的 R^2。
        fn computeRR(self: *Self) void {
            self.rr = self.zero;
            const n = self.rr.limbs_count();
            self.rr.v.limbs()[n - 1] = 1;
            for ((n - 1)..(2 * n)) |_| {
                self.shiftIn(&self.rr, 0);
            }
            self.shrink(&self.rr) catch unreachable;
        }

        /// 计算 x << t_bits + y (mod m)
        fn shiftIn(self: Self, x: *Fe, y: Limb) void {
            var d = self.zero;
            const x_limbs = x.v.limbs();
            const d_limbs = d.v.limbs();
            const m_limbs = self.v.limbsConst();

            var need_sub = false;
            var i: usize = t_bits - 1;
            while (true) : (i -= 1) {
                var carry: u1 = @truncate(math.shr(Limb, y, i));
                var borrow: u1 = 0;
                for (0..self.limbs_count()) |j| {
                    const l = ct.select(need_sub, d_limbs[j], x_limbs[j]);
                    var res = (l << 1) + carry;
                    x_limbs[j] = @as(TLimb, @truncate(res));
                    carry = @truncate(res >> t_bits);

                    res = x_limbs[j] -% m_limbs[j] -% borrow;
                    d_limbs[j] = @as(TLimb, @truncate(res));

                    borrow = @truncate(res >> t_bits);
                }
                need_sub = ct.eql(carry, borrow);
                if (i == 0) break;
            }
            x.v.cmov(need_sub, d.v);
        }

        /// 将两个域元素相加(对 m 取模)。
        pub fn add(self: Self, x: Fe, y: Fe) Fe {
            var out = x;
            if (x.montgomery == y.montgomery) {
                @branchHint(.likely);
                const overflow = out.v.addWithOverflow(y.v);
                const underflow: u1 = @bitCast(ct.limbsCmpLt(out.v, self.v));
                const need_sub = ct.eql(overflow, underflow);
                _ = out.v.conditionalSubWithOverflow(need_sub, self.v);
                return out;
            } else {
                var y_ = y;
                if (y.montgomery) {
                    self.fromMontgomery(&y_) catch unreachable;
                } else {
                    self.toMontgomery(&y_) catch unreachable;
                }
                const overflow = out.v.addWithOverflow(y_.v);
                const underflow: u1 = @bitCast(ct.limbsCmpLt(out.v, self.v));
                const need_sub = ct.eql(overflow, underflow);
                _ = out.v.conditionalSubWithOverflow(need_sub, self.v);
                return out;
            }
        }

        /// 两域元素相减(模 m)。
        pub fn sub(self: Self, x: Fe, y: Fe) Fe {
            var out = x;
            if (x.montgomery == y.montgomery) {
                const underflow: bool = @bitCast(out.v.subWithOverflow(y.v));
                _ = out.v.conditionalAddWithOverflow(underflow, self.v);
                return out;
            } else {
                var y_ = y;
                if (y.montgomery) {
                    self.fromMontgomery(&y_) catch unreachable;
                } else {
                    self.toMontgomery(&y_) catch unreachable;
                }
                const underflow: bool = @bitCast(out.v.subWithOverflow(y_.v));
                _ = out.v.conditionalAddWithOverflow(underflow, self.v);
                return out;
            }
        }

        /// 将域元素转换为 Montgomery 形式。
        pub fn toMontgomery(self: Self, x: *Fe) RepresentationError!void {
            if (x.montgomery) {
                return error.UnexpectedRepresentation;
            }
            self.shrink(x) catch unreachable;
            x.* = self.montgomeryMul(x.*, self.rr);
            x.montgomery = true;
        }

        /// 将域元素从 Montgomery 形式转换出来。
        pub fn fromMontgomery(self: Self, x: *Fe) RepresentationError!void {
            if (!x.montgomery) {
                return error.UnexpectedRepresentation;
            }
            self.shrink(x) catch unreachable;
            x.* = self.montgomeryMul(x.*, self.one());
            x.montgomery = false;
        }

        /// 约减任意 `Uint`,将其转换为域元素。
        pub fn reduce(self: Self, x: anytype) Fe {
            var out = self.zero;
            var i = x.limbs_len - 1;
            if (self.limbs_count() >= 2) {
                const start = @min(i, self.limbs_count() - 2);
                var j = start;
                while (true) : (j -= 1) {
                    out.v.limbs()[j] = x.limbsConst()[i];
                    i -= 1;
                    if (j == 0) break;
                }
            }
            while (true) : (i -= 1) {
                self.shiftIn(&out, x.limbsConst()[i]);
                if (i == 0) break;
            }
            return out;
        }

        fn montgomeryLoop(self: Self, d: *Fe, x: Fe, y: Fe) u1 {
            assert(d.limbs_count() == x.limbs_count());
            assert(d.limbs_count() == y.limbs_count());
            assert(d.limbs_count() == self.limbs_count());

            const a_limbs = x.v.limbsConst();
            const b_limbs = y.v.limbsConst();
            const d_limbs = d.v.limbs();
            const m_limbs = self.v.limbsConst();

            var overflow: u1 = 0;
            for (0..self.limbs_count()) |i| {
                var carry: Limb = 0;

                var wide = ct.mulWide(a_limbs[i], b_limbs[0]);
                var z_lo = @addWithOverflow(d_limbs[0], wide.lo);
                const f = @as(TLimb, @truncate(z_lo[0] *% self.m0inv));
                var z_hi = wide.hi +% z_lo[1];
                wide = ct.mulWide(f, m_limbs[0]);
                z_lo = @addWithOverflow(z_lo[0], wide.lo);
                z_hi +%= z_lo[1];
                z_hi +%= wide.hi;
                carry = (z_hi << 1) | (z_lo[0] >> t_bits);

                for (1..self.limbs_count()) |j| {
                    wide = ct.mulWide(a_limbs[i], b_limbs[j]);
                    z_lo = @addWithOverflow(d_limbs[j], wide.lo);
                    z_hi = wide.hi +% z_lo[1];
                    wide = ct.mulWide(f, m_limbs[j]);
                    z_lo = @addWithOverflow(z_lo[0], wide.lo);
                    z_hi +%= z_lo[1];
                    z_hi +%= wide.hi;
                    z_lo = @addWithOverflow(z_lo[0], carry);
                    z_hi +%= z_lo[1];
                    if (j > 0) {
                        d_limbs[j - 1] = @as(TLimb, @truncate(z_lo[0]));
                    }
                    carry = (z_hi << 1) | (z_lo[0] >> t_bits);
                }
                const z = overflow + carry;
                d_limbs[self.limbs_count() - 1] = @as(TLimb, @truncate(z));
                overflow = @as(u1, @truncate(z >> t_bits));
            }
            return overflow;
        }

        // 蒙哥马利乘法。
        fn montgomeryMul(self: Self, x: Fe, y: Fe) Fe {
            var d = self.zero;
            assert(x.limbs_count() == self.limbs_count());
            assert(y.limbs_count() == self.limbs_count());
            const overflow = self.montgomeryLoop(&d, x, y);
            const underflow = 1 -% @intFromBool(ct.limbsCmpGeq(d.v, self.v));
            const need_sub = ct.eql(overflow, underflow);
            _ = d.v.conditionalSubWithOverflow(need_sub, self.v);
            d.montgomery = x.montgomery == y.montgomery;
            return d;
        }

        // 蒙哥马利平方。
        fn montgomerySq(self: Self, x: Fe) Fe {
            var d = self.zero;
            assert(x.limbs_count() == self.limbs_count());
            const overflow = self.montgomeryLoop(&d, x, x);
            const underflow = 1 -% @intFromBool(ct.limbsCmpGeq(d.v, self.v));
            const need_sub = ct.eql(overflow, underflow);
            _ = d.v.conditionalSubWithOverflow(need_sub, self.v);
            d.montgomery = true;
            return d;
        }

        // 返回 x^e (mod m),指数以字节串形式提供。
        // 若指数是秘密,必须将 `public` 设为 `false`。
        fn powWithEncodedExponentInternal(self: Self, x: Fe, e: []const u8, endian: Endian, comptime public: bool) NullExponentError!Fe {
            var acc: u8 = 0;
            for (e) |b| acc |= b;
            if (acc == 0) return error.NullExponent;

            const was_montgomery = x.montgomery;

            var out = self.one();
            self.toMontgomery(&out) catch unreachable;

            if (public and
                (e.len < 3 or (e.len == 3 and e[if (endian == .big) 0 else 2] <= 0b1111)))
            {
                // 对于短的公开指数,不使用预计算表
                var x_m = x;
                if (!x.montgomery) {
                    self.toMontgomery(&x_m) catch unreachable;
                }
                var s = switch (endian) {
                    .big => 0,
                    .little => e.len - 1,
                };
                while (true) {
                    const b = e[s];
                    var j: u3 = 7;
                    while (true) : (j -= 1) {
                        out = self.montgomerySq(out);
                        const k: u1 = @truncate(b >> j);
                        if (k != 0) {
                            const t = self.montgomeryMul(out, x_m);
                            @memcpy(out.v.limbs(), t.v.limbsConst());
                        }
                        if (j == 0) break;
                    }
                    switch (endian) {
                        .big => {
                            s += 1;
                            if (s == e.len) break;
                        },
                        .little => {
                            if (s == 0) break;
                            s -= 1;
                        },
                    }
                }
            } else {
                // 对较大的指数使用预计算表
                var pc: [15]Fe = [1]Fe{x} ++ @as([14]Fe, @splat(self.zero));
                if (!x.montgomery) {
                    self.toMontgomery(&pc[0]) catch unreachable;
                }
                for (1..pc.len) |i| {
                    pc[i] = self.montgomeryMul(pc[i - 1], pc[0]);
                }
                var t0 = self.zero;
                var s = switch (endian) {
                    .big => 0,
                    .little => e.len - 1,
                };
                while (true) {
                    const b = e[s];
                    for ([_]u3{ 4, 0 }) |j| {
                        for (0..4) |_| {
                            out = self.montgomerySq(out);
                        }
                        const k = (b >> j) & 0b1111;
                        if (public or std.options.side_channels_mitigations == .none) {
                            if (k == 0) continue;
                            t0 = pc[k - 1];
                        } else {
                            for (pc, 0..) |t, i| {
                                t0.v.cmov(ct.eql(k, @as(u8, @truncate(i + 1))), t.v);
                            }
                        }
                        const t1 = self.montgomeryMul(out, t0);
                        if (public) {
                            @memcpy(out.v.limbs(), t1.v.limbsConst());
                        } else {
                            out.v.cmov(!ct.eql(k, 0), t1.v);
                        }
                    }
                    switch (endian) {
                        .big => {
                            s += 1;
                            if (s == e.len) break;
                        },
                        .little => {
                            if (s == 0) break;
                            s -= 1;
                        },
                    }
                }
            }
            if (!was_montgomery) {
                self.fromMontgomery(&out) catch unreachable;
            }
            return out;
        }

        /// 计算两个域元素的乘积。
        /// 结果保留第一个操作数的表示形式。
        pub fn mul(self: Self, x: Fe, y: Fe) Fe {
            if (x.montgomery) {
                const y_ = if (!y.montgomery) blk: {
                    var yy = y;
                    self.toMontgomery(&yy) catch unreachable;
                    break :blk yy;
                } else y;
                return self.montgomeryMul(x, y_);
            } else {
                var x_m = x;
                var y_m = if (y.montgomery) blk: {
                    var yy = y;
                    self.fromMontgomery(&yy) catch unreachable;
                    break :blk yy;
                } else y;
                self.toMontgomery(&x_m) catch unreachable;
                self.toMontgomery(&y_m) catch unreachable;
                var out = self.montgomeryMul(x_m, y_m);
                self.fromMontgomery(&out) catch unreachable;
                return out;
            }
        }

        /// 将域元素平方。
        pub fn sq(self: Self, x: Fe) Fe {
            if (x.montgomery) {
                return self.montgomerySq(x);
            } else {
                var out = x;
                self.toMontgomery(&out) catch unreachable;
                out = self.montgomerySq(out);
                self.fromMontgomery(&out) catch unreachable;
                return out;
            }
        }

        const max_encoded_bytes = @divCeil(FeUint.capacity_bits, 8);

        /// 以常量时间返回 x^e (mod m)。
        pub fn pow(self: Self, x: Fe, e: Fe) (NullExponentError || RepresentationError)!Fe {
            if (e.montgomery) {
                return error.UnexpectedRepresentation;
            }

            var buf: [max_encoded_bytes]u8 = undefined;
            const len = self.encodedLen();
            e.toBytes(buf[0..len], native_endian) catch unreachable;
            return self.powWithEncodedExponent(x, buf[0..len], native_endian);
        }

        /// 返回 x^e (mod m),假定指数公开。
        /// 对于 `x`,此函数仍为常量时间。
        pub fn powPublic(self: Self, x: Fe, e: Fe) (NullExponentError || RepresentationError)!Fe {
            if (e.montgomery) {
                return error.UnexpectedRepresentation;
            }
            var buf_: [max_encoded_bytes]u8 = undefined;
            const buf = buf_[0..@divCeil(e.v.bitLenPublic(), 8)];
            e.toBytes(buf, .little) catch unreachable;
            return self.powWithEncodedPublicExponent(x, buf, .little);
        }

        /// 返回 x^e (mod m),指数以字节字符串提供。
        /// 指数通常较小,因此若已有序列化表示,此函数无需创建域元素,比 `powPublic` 更快。
        ///
        /// 若指数公开,可以改用 `powWithEncodedPublicExponent()`,略微提高速度。
        ///
        pub fn powWithEncodedExponent(self: Self, x: Fe, e: []const u8, endian: Endian) NullExponentError!Fe {
            return self.powWithEncodedExponentInternal(x, e, endian, false);
        }

        /// 返回 x^e (mod m),指数为公开值,以字节串提供。
        /// 指数通常较小,因此当已有序列化表示时,无需创建域元素,
        /// 此函数比 `powPublic` 更快。
        ///
        /// 如果指数为秘密值,则必须改用 `powWithEncodedExponent`。
        pub fn powWithEncodedPublicExponent(self: Self, x: Fe, e: []const u8, endian: Endian) NullExponentError!Fe {
            return self.powWithEncodedExponentInternal(x, e, endian, true);
        }
    };
}

const ct = if (std.options.side_channels_mitigations == .none) ct_unprotected else ct_protected;

const ct_protected = struct {
    // 若 on 为 true,则返回 x,否则返回 y。
    fn select(on: bool, x: Limb, y: Limb) Limb {
        const mask = @as(Limb, 0) -% @intFromBool(on);
        return y ^ (mask & (y ^ x));
    }

    // 以恒定时间比较两个值。
    fn eql(x: anytype, y: @TypeOf(x)) bool {
        const c1 = @subWithOverflow(x, y)[1];
        const c2 = @subWithOverflow(y, x)[1];
        return @as(bool, @bitCast(1 - (c1 | c2)));
    }

    // 以常量时间比较两个大整数;若 x < y 则返回 true。
    fn limbsCmpLt(x: anytype, y: @TypeOf(x)) bool {
        var c: u1 = 0;
        for (x.limbsConst(), y.limbsConst()) |x_limb, y_limb| {
            c = @truncate((x_limb -% y_limb -% c) >> t_bits);
        }
        return c != 0;
    }

    // 以常量时间比较两个大整数;若 x >= y 则返回 true。
    fn limbsCmpGeq(x: anytype, y: @TypeOf(x)) bool {
        return !limbsCmpLt(x, y);
    }

    // 计算两个 limb 的乘积,并以双倍宽度的 limb 返回结果。
    fn mulWide(x: Limb, y: Limb) WideLimb {
        const half_bits = @typeInfo(Limb).int.bits / 2;
        const Half = @Int(.unsigned, half_bits);
        const x0 = @as(Half, @truncate(x));
        const x1 = @as(Half, @truncate(x >> half_bits));
        const y0 = @as(Half, @truncate(y));
        const y1 = @as(Half, @truncate(y >> half_bits));
        const w0 = math.mulWide(Half, x0, y0);
        const t = math.mulWide(Half, x1, y0) + (w0 >> half_bits);
        var w1: Limb = @as(Half, @truncate(t));
        const w2 = @as(Half, @truncate(t >> half_bits));
        w1 += math.mulWide(Half, x0, y1);
        const hi = math.mulWide(Half, x1, y1) + w2 + (w1 >> half_bits);
        const lo = x *% y;
        return .{ .hi = hi, .lo = lo };
    }
};

const ct_unprotected = struct {
    // 若 on 为 true,则返回 x,否则返回 y。
    fn select(on: bool, x: Limb, y: Limb) Limb {
        return if (on) x else y;
    }

    // 以恒定时间比较两个值。
    fn eql(x: anytype, y: @TypeOf(x)) bool {
        return x == y;
    }

    // 以常量时间比较两个大整数;若 x < y 则返回 true。
    fn limbsCmpLt(x: anytype, y: @TypeOf(x)) bool {
        const x_limbs = x.limbsConst();
        const y_limbs = y.limbsConst();
        assert(x_limbs.len == y_limbs.len);

        var i = x_limbs.len;
        while (i != 0) {
            i -= 1;
            if (x_limbs[i] != y_limbs[i]) {
                return x_limbs[i] < y_limbs[i];
            }
        }
        return false;
    }

    // 以常量时间比较两个大整数;若 x >= y 则返回 true。
    fn limbsCmpGeq(x: anytype, y: @TypeOf(x)) bool {
        return !limbsCmpLt(x, y);
    }

    // 计算两个 limb 的乘积,并以双倍宽度的 limb 返回结果。
    fn mulWide(x: Limb, y: Limb) WideLimb {
        const wide = math.mulWide(Limb, x, y);
        return .{
            .hi = @as(Limb, @truncate(wide >> @typeInfo(Limb).int.bits)),
            .lo = @as(Limb, @truncate(wide)),
        };
    }
};

test "finite field arithmetic" {
    const M = Modulus(256);
    const m = try M.fromPrimitive(u256, 3429938563481314093726330772853735541133072814650493833233);
    var x = try M.Fe.fromPrimitive(u256, m, 80169837251094269539116136208111827396136208141182357733);
    const y = try M.Fe.fromPrimitive(u256, m, 24620149608466364616251608466389896540098571);

    const x_ = try x.toPrimitive(u256);
    try testing.expect((try M.Fe.fromPrimitive(@TypeOf(x_), m, x_)).eql(x));
    try testing.expectError(error.Overflow, x.toPrimitive(u50));

    const bits = m.bits();
    try testing.expectEqual(bits, 192);

    var x_y = m.mul(x, y);
    try testing.expectEqual(x_y.toPrimitive(u256), 1666576607955767413750776202132407807424848069716933450241);

    try m.toMontgomery(&x);
    x_y = m.mul(x, y);
    try testing.expect(x_y.montgomery); // 结果保留第一个操作数的形式
    try m.fromMontgomery(&x_y);
    try testing.expectEqual(x_y.toPrimitive(u256), 1666576607955767413750776202132407807424848069716933450241);
    try m.fromMontgomery(&x);

    x = m.add(x, y);
    try testing.expectEqual(x.toPrimitive(u256), 80169837251118889688724602572728079004602598037722456304);
    x = m.sub(x, y);
    try testing.expectEqual(x.toPrimitive(u256), 80169837251094269539116136208111827396136208141182357733);

    const big = try Uint(512).fromPrimitive(u495, 77285373554113307281465049383342993856348131409372633077285373554113307281465049383323332333429938563481314093726330772853735541133072814650493833233);
    const reduced = m.reduce(big);
    try testing.expectEqual(reduced.toPrimitive(u495), 858047099884257670294681641776170038885500210968322054970);

    const x_pow_y = try m.powPublic(x, y);
    try testing.expectEqual(x_pow_y.toPrimitive(u256), 1631933139300737762906024873185789093007782131928298618473);
    try testing.expect(!x_pow_y.montgomery);
    try m.toMontgomery(&x);
    var x_pow_y2 = try m.powPublic(x, y);
    try testing.expect(x_pow_y2.montgomery);
    try m.fromMontgomery(&x_pow_y2);
    try m.fromMontgomery(&x);
    try testing.expect(x_pow_y2.eql(x_pow_y));
    try testing.expectError(error.NullExponent, m.powPublic(x, m.zero));

    try testing.expect(!x.isZero());
    try testing.expect(!y.isZero());
    try testing.expect(m.v.isOdd());

    const x_sq = m.sq(x);
    const x_sq2 = m.mul(x, x);
    try testing.expect(!x_sq.montgomery);
    try testing.expect(!x_sq2.montgomery);
    try testing.expect(x_sq.eql(x_sq2));
    try m.toMontgomery(&x);
    var x_sq3 = m.sq(x);
    var x_sq4 = m.mul(x, x);
    try testing.expect(x_sq3.montgomery);
    try testing.expect(x_sq4.montgomery);
    try m.fromMontgomery(&x_sq3);
    try m.fromMontgomery(&x_sq4);
    try testing.expect(x_sq.eql(x_sq3));
    try testing.expect(x_sq3.eql(x_sq4));
    try m.fromMontgomery(&x);

    var x_mont = x;
    try m.toMontgomery(&x_mont);

    // 非蒙哥马利形式 + 蒙哥马利形式
    const add_nm_m = m.add(x, x_mont);
    try testing.expect(!add_nm_m.montgomery);
    var add_m_nm = m.add(x_mont, x);
    try testing.expect(add_m_nm.montgomery);
    try m.fromMontgomery(&add_m_nm);
    try testing.expect(add_nm_m.eql(add_m_nm));

    // 非蒙哥马利形式 - 蒙哥马利形式
    var y_mont = y;
    try m.toMontgomery(&y_mont);
    const sub_nm_m = m.sub(x, y_mont);
    try testing.expect(!sub_nm_m.montgomery);
    var sub_m_nm = m.sub(x_mont, y);
    try testing.expect(sub_m_nm.montgomery);
    try m.fromMontgomery(&sub_m_nm);
    try testing.expect(sub_nm_m.eql(sub_m_nm));

    // mul:保留第一操作数的形式
    const mul_nm_m = m.mul(x, x_mont);
    try testing.expect(!mul_nm_m.montgomery);
    const mul_nm_nm = m.mul(x, x);
    try testing.expect(mul_nm_m.eql(mul_nm_nm));
    var mul_m_nm = m.mul(x_mont, x);
    try testing.expect(mul_m_nm.montgomery);
    try m.fromMontgomery(&mul_m_nm);
    try testing.expect(mul_m_nm.eql(mul_nm_nm));

    try testing.expectEqual(x.toPrimitive(u256), 80169837251094269539116136208111827396136208141182357733);
    try testing.expectError(error.UnexpectedRepresentation, x_mont.toPrimitive(u256));
}

fn testCt(ct_: anytype) !void {
    const l0: Limb = 0;
    const l1: Limb = 1;
    try testing.expectEqual(l1, ct_.select(true, l1, l0));
    try testing.expectEqual(l0, ct_.select(false, l1, l0));
    try testing.expectEqual(false, ct_.eql(l1, l0));
    try testing.expectEqual(true, ct_.eql(l1, l1));

    const M = Modulus(256);
    const m = try M.fromPrimitive(u256, 3429938563481314093726330772853735541133072814650493833233);
    const x = try M.Fe.fromPrimitive(u256, m, 80169837251094269539116136208111827396136208141182357733);
    const y = try M.Fe.fromPrimitive(u256, m, 24620149608466364616251608466389896540098571);
    try testing.expectEqual(false, ct_.limbsCmpLt(x.v, y.v));
    try testing.expectEqual(true, ct_.limbsCmpGeq(x.v, y.v));

    try testing.expectEqual(WideLimb{ .hi = 0, .lo = 0x88 }, ct_.mulWide(1 << 3, (1 << 4) + 1));
}

test ct {
    try testCt(ct_protected);
    try testCt(ct_unprotected);
}

fn expectWellFormedLimbs(x: anytype) !void {
    for (x.limbsConst()) |limb| {
        try testing.expect(limb <= math.maxInt(TLimb));
    }
    for (x.limbs_buffer[x.limbs_len..]) |limb| {
        try testing.expectEqual(0, limb);
    }
}

// `Uint` 可存储的最大值的大端编码。
fn maxUintBytes(comptime U: type) [@divCeil(U.capacity_bits, 8)]u8 {
    var buf: [@divCeil(U.capacity_bits, 8)]u8 = @splat(0xff);
    buf[0] = 0xff >> (8 * buf.len - U.capacity_bits);
    return buf;
}

test "modulus creation" {
    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;

    const M = Modulus(256);
    try testing.expectError(error.EvenModulus, M.fromPrimitive(u8, 0));
    try testing.expectError(error.ModulusTooSmall, M.fromPrimitive(u8, 1));
    try testing.expectError(error.EvenModulus, M.fromPrimitive(u8, 2));
    for ([_]u65{ 3, 255, (1 << 64) + 1 }) |v| {
        const m = try M.fromPrimitive(u65, v);
        try testing.expectEqual(v, try m.toUint().toPrimitive(u65));
        try testing.expectEqual(@divCeil(65 - @clz(v), 8), m.encodedLen());
        try testing.expect((try M.fromUint(m.toUint())).v.eql(m.v));
    }
    const cap = maxUintBytes(Uint(256));
    try testing.expectEqual(cap.len, (try M.fromBytes(&cap, .big)).encodedLen());
}

test "Uint serialization" {
    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;

    const U = Uint(256);
    const x = try U.fromPrimitive(u128, (1 << t_bits) + 5);
    try testing.expectError(error.Overflow, Uint(64).fromPrimitive(u256, 1 << 200));
    try testing.expectError(error.Overflow, x.toPrimitive(u8));
    try testing.expectError(error.Overflow, x.toPrimitive(@Int(.unsigned, t_bits)));
    try testing.expectEqual((1 << t_bits) + 5, try x.toPrimitive(@Int(.unsigned, t_bits + 1)));
    const max = try U.fromPrimitive(u128, (1 << t_bits) - 1);
    try testing.expectEqual((1 << t_bits) - 1, try max.toPrimitive(@Int(.unsigned, t_bits)));
    try testing.expectError(error.Overflow, max.toPrimitive(@Int(.unsigned, t_bits - 1)));
    const signed_max = try U.fromPrimitive(u128, math.maxInt(i128));
    try testing.expectEqual(math.maxInt(i128), try signed_max.toPrimitive(i128));
    try testing.expectError(error.Overflow, (try U.fromPrimitive(u128, 1 << 127)).toPrimitive(i128));

    inline for (.{ .big, .little }) |endian| {
        const zero = try U.fromBytes(&.{}, endian);
        var empty: [0]u8 = .{};
        try zero.toBytes(&empty, endian);
        try testing.expectError(error.Overflow, x.toBytes(&empty, endian));
        var tight: [16]u8 = undefined;
        try x.toBytes(&tight, endian);
        try testing.expectEqual((1 << t_bits) + 5, mem.readInt(u128, &tight, endian));
        try testing.expect(x.eql(try U.fromBytes(&tight, endian)));
        var normalized: [16]u8 = undefined;
        try x.normalize().toBytes(&normalized, endian);
        try testing.expectEqualSlices(u8, &tight, &normalized);

        var cap = maxUintBytes(U);
        if (endian == .little) mem.reverse(u8, &cap);
        const full = try U.fromBytes(&cap, endian);
        try expectWellFormedLimbs(full);
        var out: [cap.len]u8 = undefined;
        try full.toBytes(&out, endian);
        try testing.expectEqualSlices(u8, &cap, &out);
        out[if (endian == .big) 0 else out.len - 1] |= 1 << (U.capacity_bits % 8);
        try testing.expectError(error.Overflow, U.fromBytes(&out, endian));
        var padded = if (endian == .big) [_]u8{0} ++ cap else cap ++ [_]u8{0};
        try testing.expect(full.eql(try U.fromBytes(&padded, endian)));
        padded[if (endian == .big) 0 else padded.len - 1] = 1;
        try testing.expectError(error.Overflow, U.fromBytes(&padded, endian));
    }
}

test "field element decoding" {
    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;

    const M = Modulus(256);
    const mv: u256 = (1 << 190) + 33;
    const m = try M.fromPrimitive(u256, mv);
    try testing.expectError(error.NonCanonical, M.Fe.fromPrimitive(u256, m, mv));
    try testing.expectError(error.Overflow, M.Fe.fromPrimitive(u256, m, 1 << 255));

    inline for (.{ .big, .little }) |endian| {
        var buf: [32]u8 = undefined;
        try m.toBytes(&buf, endian);
        try testing.expectError(error.NonCanonical, M.Fe.fromBytes(m, &buf, endian));
        const x = try M.Fe.fromPrimitive(u256, m, mv - 1);
        try x.toBytes(&buf, endian);
        try testing.expect(x.eql(try M.Fe.fromBytes(m, &buf, endian)));
    }
}

test "Uint bit measurement and shifts" {
    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;

    const U = Uint(256);
    try testing.expectEqual(0, U.zero.bitLenPublic());
    try testing.expectEqual(U.max_limbs_count * t_bits, U.zero.trailingZeroBitsPublic());
    try testing.expectEqual(t_bits, U.zero.normalize().trailingZeroBitsPublic());
    for ([_]usize{ 0, t_bits - 1, t_bits, t_bits + 1, 255 }) |offset| {
        const x = try U.fromPrimitive(u256, math.shl(u256, 1, offset));
        try testing.expectEqual(offset + 1, x.bitLenPublic());
        try testing.expectEqual(offset, x.trailingZeroBitsPublic());
    }

    const v: u256 = (1 << 255) | (1 << t_bits) | 3;
    for ([_]usize{ 0, 1, t_bits - 1, t_bits, t_bits + 1, U.max_limbs_count * t_bits, 10_000 }) |shift| {
        var x = try U.fromPrimitive(u256, v);
        x.shiftRightPublic(shift);
        try testing.expectEqual(math.shr(u256, v, shift), try x.toPrimitive(u256));
        try testing.expectEqual(U.max_limbs_count, x.limbs_len);
        try expectWellFormedLimbs(x);
    }
    for ([_]usize{ 0, 1, t_bits - 1, t_bits, t_bits + 1 }) |shift| {
        var x = try U.fromPrimitive(u256, (1 << t_bits) + 3);
        x.shiftLeft(shift);
        try testing.expectEqual(math.shl(u256, (1 << t_bits) + 3, shift), try x.toPrimitive(u256));
    }

    var x = (try U.fromPrimitive(u8, 5)).normalize();
    try testing.expectEqual(1, x.shiftRightByOneWithCarry(1));
    try testing.expectEqual((1 << (t_bits - 1)) + 2, try x.toPrimitive(u64));
    try testing.expectEqual(0, x.shiftRightByOneWithCarry(0));
    x.shiftRightPublic(t_bits);
    try testing.expect(x.isZero());
    try testing.expectEqual(1, x.limbs_len);
}

test "Uint division and gcd" {
    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;

    const U = Uint(256);
    const v: u256 = (1 << 255) + (1 << t_bits) + 13;
    for ([_]usize{ 1, 7, math.maxInt(TLimb), (1 << t_bits) + 5, math.maxInt(usize) }) |divisor| {
        var x = try U.fromPrimitive(u256, v);
        try testing.expectEqual(v % divisor, try x.divRemPublic(divisor));
        try testing.expectEqual(v / divisor, try x.toPrimitive(u256));
        try expectWellFormedLimbs(x);
    }
    var x = (try U.fromPrimitive(u16, 1000)).normalize();
    try testing.expectError(error.DivisionByZero, x.divRemPublic(0));
    try testing.expectEqual(6, try x.divRemPublic(7));
    try testing.expectEqual(142, try x.toPrimitive(u16));
    try testing.expectEqual(1, x.limbs_len);
    try testing.expectEqual(142, try x.divRemPublic(1000));
    try testing.expectEqual(0, try x.divRemPublic(7));

    for ([_][3]u256{ .{ 0, 5, 5 }, .{ 6, 6, 6 }, .{ 17, 4, 1 }, .{ 15 << 200, 21 << 100, 3 << 100 } }) |c| {
        const a = (try U.fromPrimitive(u256, c[0])).normalize();
        const b = try U.fromPrimitive(u256, c[1]);
        try testing.expectEqual(c[2], try (try a.gcdPublic(b)).toPrimitive(u256));
        try testing.expectEqual(c[2], try (try b.gcdPublic(a)).toPrimitive(u256));
    }
    try testing.expectError(error.DivisionByZero, U.zero.gcdPublic(U.zero));
}

test "Uint addition and multiply-add" {
    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;

    const U = Uint(256);
    const full = try U.fromBytes(&maxUintBytes(U), .big);
    const one = try U.fromPrimitive(u8, 1);
    var carry = (try U.fromPrimitive(u64, math.maxInt(TLimb))).normalize();
    try testing.expectEqual(0, carry.addWithOverflow(one));
    try testing.expectEqual(one.limbs_len, carry.limbs_len);
    try testing.expectEqual(1 << t_bits, try carry.toPrimitive(u128));
    try testing.expectEqual(0, carry.subWithOverflow(one.normalize()));
    try testing.expectEqual(math.maxInt(TLimb), try carry.toPrimitive(u64));
    var wrapped = U.zero.normalize();
    try testing.expectEqual(1, wrapped.subWithOverflow(one));
    try testing.expect(wrapped.eql(full));
    try testing.expectEqual(1, wrapped.addWithOverflow(one));
    try testing.expect(wrapped.isZero());

    for ([_]struct { acc: U, x: U, y: U, overflow: u1, expected: U }{
        .{ .acc = U.zero, .x = full, .y = one, .overflow = 0, .expected = full },
        .{ .acc = full, .x = U.zero, .y = full, .overflow = 0, .expected = full },
        .{ .acc = full, .x = full, .y = U.zero, .overflow = 0, .expected = full },
        .{ .acc = U.zero, .x = full, .y = full, .overflow = 1, .expected = one },
        .{ .acc = full, .x = one, .y = one, .overflow = 1, .expected = U.zero },
    }) |c| {
        var acc = c.acc;
        try testing.expectEqual(c.overflow, acc.mulAddWithOverflow(c.x, c.y));
        try testing.expect(acc.eql(c.expected));
        try expectWellFormedLimbs(acc);
    }
    const a: u256 = (1 << 100) + 3;
    const b: u256 = (1 << 80) + 7;
    var acc = try U.fromPrimitive(u256, a);
    try testing.expectEqual(0, acc.mulAddWithOverflow(try U.fromPrimitive(u256, a), try U.fromPrimitive(u256, b)));
    try testing.expectEqual(a + a * b, try acc.toPrimitive(u256));

    var short = one.normalize();
    const high = (try U.fromPrimitive(u64, 1 << (t_bits - 1))).normalize();
    const two = (try U.fromPrimitive(u8, 2)).normalize();
    try testing.expectEqual(1, short.mulAddWithOverflow(high, two));
    try testing.expectEqual(1, short.limbs_len);
    try testing.expect(short.isOne());
}