无需分配、尽力保持常数时间的大整数有限域算术。
与 std.math.big 不同,这些整数具有固定的最大长度,且仅用于模算术。
算术操作旨在对给定模数以常数时间运行,因此适用于密码学。
名称中包含 Public 的函数除外。
部分代码移植自 Go 语言中采用 BSD 许可证的 crypto/internal/bigmod/nat.go 文件;该文件本身受 BearSSL 启发。
stdbuiltincryptomathmemtestingassertEndianLimbcarry_bitst_bitsTLimbnative_endianWideLimbOverflowErrorInvalidModulusErrorNullExponentErrorFieldElementErrorRepresentationErrorDivisionByZeroErrorErrorUintFe_decodeBytesorLimbsmulAddLimbmulAddWideModulusctct_protectedct_unprotectedtestCtexpectWellFormedLimbsmaxUintBytes
std.crypto.ff.assert
别名
别名目标 std.debug.assert
std.crypto.ff.builtin
常量
std.crypto.ff.carry_bits
常量
std.crypto.ff.crypto
别名
别名目标 std.crypto
std.crypto.ff.ct
类型
std.crypto.ff.ct_protected
命名空间
std.crypto.ff.ct_protected.eql
函数
fn eql(x: anytype, y: @TypeOf(x)) bool
参数
y: @TypeOf(x)
std.crypto.ff.ct_protected.limbsCmpGeq
函数
fn limbsCmpGeq(x: anytype, y: @TypeOf(x)) bool
参数
y: @TypeOf(x)
std.crypto.ff.ct_protected.limbsCmpLt
函数
fn limbsCmpLt(x: anytype, y: @TypeOf(x)) bool
参数
y: @TypeOf(x)
std.crypto.ff.ct_protected.mulWide
函数
fn mulWide(x: Limb, y: Limb) WideLimb
参数
std.crypto.ff.ct_protected.select
函数
fn select(on: bool, x: Limb, y: Limb) Limb
参数
std.crypto.ff.ct_unprotected
命名空间
std.crypto.ff.ct_unprotected.eql
函数
fn eql(x: anytype, y: @TypeOf(x)) bool
参数
y: @TypeOf(x)
std.crypto.ff.ct_unprotected.limbsCmpGeq
函数
fn limbsCmpGeq(x: anytype, y: @TypeOf(x)) bool
参数
y: @TypeOf(x)
std.crypto.ff.ct_unprotected.limbsCmpLt
函数
fn limbsCmpLt(x: anytype, y: @TypeOf(x)) bool
参数
y: @TypeOf(x)
std.crypto.ff.ct_unprotected.mulWide
函数
fn mulWide(x: Limb, y: Limb) WideLimb
参数
std.crypto.ff.ct_unprotected.select
函数
fn select(on: bool, x: Limb, y: Limb) Limb
参数
std.crypto.ff.decodeBytes
函数
fn decodeBytes(limbs: []Limb, bytes: []const u8, comptime endian: Endian) Limb
参数
std.crypto.ff.DivisionByZeroError
错误集合
错误
- DivisionByZero
std.crypto.ff.Endian
别名
别名目标 std.lang.Endian
std.crypto.ff.Error
错误集合
std.crypto.ff 函数可能返回的全部错误集合。
错误
- DivisionByZero DivisionByZeroError
- EvenModulus InvalidModulusError
- ModulusTooSmall InvalidModulusError
- NonCanonical FieldElementError
- NullExponent NullExponentError
- Overflow OverflowError
- UnexpectedRepresentation RepresentationError
std.crypto.ff.expectWellFormedLimbs
函数
fn expectWellFormedLimbs(x: anytype) !void
std.crypto.ff.Fe_
类型函数
域元素。
fn Fe_(comptime bits: comptime_int) type
参数
bits: comptime_int
字段
std.crypto.ff.Fe_.compare
函数
以恒定时间比较两个域元素。
pub fn compare(x: Self, y: Self) math.Order
参数
std.crypto.ff.Fe_.encoded_bytes
常量
编码域元素所需的最大字节数。
std.crypto.ff.Fe_.eql
函数
以常量时间判断域元素是否相等,并返回 true。
不同表示形式的元素比较结果为不等;要比较数值,应先将其转换为相同形式。
pub fn eql(x: Self, y: Self) bool
参数
std.crypto.ff.Fe_.FeUint
类型
std.crypto.ff.Fe_.fromBytes
函数
从字节串创建域元素。
pub fn fromBytes(m: Modulus(bits), bytes: []const u8, comptime endian: Endian) (OverflowError || FieldElementError)!Self
参数
std.crypto.ff.Fe_.fromPrimitive
函数
从原始值创建域元素。 此函数可能不是常量时间。
pub fn fromPrimitive(comptime T: type, m: Modulus(bits), x: T) (OverflowError || FieldElementError)!Self
参数
std.crypto.ff.Fe_.isOdd
函数
若元素为奇数,则返回 true。
要求使用普通表示形式,因为蒙哥马利编码不保留奇偶性。
pub fn isOdd(self: Self) bool
参数
self: Self
std.crypto.ff.Fe_.isZero
函数
若元素为零,则返回 true。
pub fn isZero(self: Self) bool
参数
self: Self
std.crypto.ff.Fe_.limbs_count
函数
fn limbs_count(self: Self) usize
参数
self: Self
std.crypto.ff.Fe_.Self
别名
别名目标 std.crypto.ff.Fe_
std.crypto.ff.Fe_.toBytes
函数
将域元素转换为字节串。 如果元素采用蒙哥马利形式,则返回错误。
pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) (OverflowError || RepresentationError)!void
参数
std.crypto.ff.Fe_.toPrimitive
函数
将域元素转换为原始值。 此函数可能不是常量时间。 若元素采用 Montgomery 形式,则返回错误。
pub fn toPrimitive(self: Self, comptime T: type) (OverflowError || RepresentationError)!T
参数
self: Self
T: type
std.crypto.ff.FieldElementError
错误集合
对于给定模数,域元素无效。
错误
- NonCanonical
std.crypto.ff.InvalidModulusError
错误集合
模数无效。模数必须是奇数。
错误
- EvenModulus
- ModulusTooSmall
std.crypto.ff.Limb
类型
std.crypto.ff.math
别名
别名目标 std.math
std.crypto.ff.maxUintBytes
函数
fn maxUintBytes(comptime U: type) [@divCeil(U.capacity_bits, 8)]u8
参数
U: type
std.crypto.ff.mem
别名
别名目标 std.mem
std.crypto.ff.Modulus
类型函数
定义有限域的模数。
域内全部运算均对此模数取模,不进行堆分配。
max_bits 表示模数可设置的最大值的位数。
pub fn Modulus(comptime max_bits: comptime_int) type
参数
max_bits: comptime_int
字段
SelfFeFeUintlimbs_countbitsencodedLenonefromUintfromPrimitivefromBytestoBytestoUintrejectNonCanonicalshrinkcomputeRRshiftInaddsubtoMontgomeryfromMontgomeryreducemontgomeryLoopmontgomeryMulmontgomerySqpowWithEncodedExponentInternalmulsqmax_encoded_bytespowpowPublicpowWithEncodedExponentpowWithEncodedPublicExponent
std.crypto.ff.Modulus.add
函数
将两个域元素相加(对 m 取模)。
pub fn add(self: Self, x: Fe, y: Fe) Fe
参数
std.crypto.ff.Modulus.bits
函数
模数的实际大小,单位为位。
pub fn bits(self: Self) usize
参数
self: Self
std.crypto.ff.Modulus.computeRR
函数
fn computeRR(self: *Self) void
参数
self: *Self
std.crypto.ff.Modulus.encodedLen
函数
返回编码后的长度,单位为字节。
pub fn encodedLen(self: Self) usize
参数
self: Self
std.crypto.ff.Modulus.Fe
类型
一个域元素,表示由该模数定义的域中的值。 元素只能与创建它的模数一起使用,即使另一个模数大小相同也不例外。
std.crypto.ff.Modulus.FeUint
常量
std.crypto.ff.Modulus.fromBytes
函数
从字节串创建新的模数。
pub fn fromBytes(bytes: []const u8, comptime endian: Endian) (InvalidModulusError || OverflowError)!Self
参数
bytes: []const u8
endian: Endian
std.crypto.ff.Modulus.fromMontgomery
函数
将域元素从 Montgomery 形式转换出来。
pub fn fromMontgomery(self: Self, x: *Fe) RepresentationError!void
参数
错误
- UnexpectedRepresentation
std.crypto.ff.Modulus.fromPrimitive
函数
从原始值创建新模数。模数必须为奇数且大于 2。
pub fn fromPrimitive(comptime T: type, x: T) (InvalidModulusError || OverflowError)!Self
参数
T: type
x: T
std.crypto.ff.Modulus.fromUint
函数
由 Uint 值创建新的模数。
模数必须为大于 2 的奇数。
pub fn fromUint(v_: FeUint) InvalidModulusError!Self
参数
v_: FeUint
错误
- EvenModulus
- ModulusTooSmall
std.crypto.ff.Modulus.limbs_count
函数
fn limbs_count(self: Self) usize
参数
self: Self
std.crypto.ff.Modulus.max_encoded_bytes
常量
std.crypto.ff.Modulus.montgomeryLoop
函数
fn montgomeryLoop(self: Self, d: *Fe, x: Fe, y: Fe) u1
参数
std.crypto.ff.Modulus.montgomeryMul
函数
fn montgomeryMul(self: Self, x: Fe, y: Fe) Fe
参数
std.crypto.ff.Modulus.montgomerySq
函数
fn montgomerySq(self: Self, x: Fe) Fe
参数
std.crypto.ff.Modulus.mul
函数
计算两个域元素的乘积。 结果保留第一个操作数的表示形式。
pub fn mul(self: Self, x: Fe, y: Fe) Fe
参数
std.crypto.ff.Modulus.one
函数
返回元素 1。
pub fn one(self: Self) Fe
参数
self: Self
std.crypto.ff.Modulus.pow
函数
以常量时间返回 x^e (mod m)。
pub fn pow(self: Self, x: Fe, e: Fe) (NullExponentError || RepresentationError)!Fe
参数
std.crypto.ff.Modulus.powPublic
函数
返回 x^e (mod m),假定指数公开。
对于 x,此函数仍为常量时间。
pub fn powPublic(self: Self, x: Fe, e: Fe) (NullExponentError || RepresentationError)!Fe
参数
std.crypto.ff.Modulus.powWithEncodedExponent
函数
返回 x^e (mod m),指数以字节字符串提供。
指数通常较小,因此若已有序列化表示,此函数无需创建域元素,比 powPublic 更快。
若指数公开,可以改用 powWithEncodedPublicExponent(),略微提高速度。
pub fn powWithEncodedExponent(self: Self, x: Fe, e: []const u8, endian: Endian) NullExponentError!Fe
参数
错误
- NullExponent
std.crypto.ff.Modulus.powWithEncodedExponentInternal
函数
fn powWithEncodedExponentInternal(self: Self, x: Fe, e: []const u8, endian: Endian, comptime public: bool) NullExponentError!Fe
参数
错误
- NullExponent
std.crypto.ff.Modulus.powWithEncodedPublicExponent
函数
返回 x^e (mod m),指数为公开值,以字节串提供。
指数通常较小,因此当已有序列化表示时,无需创建域元素,
此函数比 powPublic 更快。
如果指数为秘密值,则必须改用 powWithEncodedExponent。
pub fn powWithEncodedPublicExponent(self: Self, x: Fe, e: []const u8, endian: Endian) NullExponentError!Fe
参数
错误
- NullExponent
std.crypto.ff.Modulus.reduce
函数
约减任意 Uint,将其转换为域元素。
pub fn reduce(self: Self, x: anytype) Fe
参数
self: Self
std.crypto.ff.Modulus.rejectNonCanonical
函数
拒绝非规范形式的域元素。
pub fn rejectNonCanonical(self: Self, fe: Fe) error{NonCanonical}!void
参数
错误
- NonCanonical
std.crypto.ff.Modulus.Self
别名
std.crypto.ff.Modulus.shiftIn
函数
计算 x << t_bits + y (mod m)
fn shiftIn(self: Self, x: *Fe, y: Limb) void
参数
std.crypto.ff.Modulus.shrink
函数
fn shrink(self: Self, fe: *Fe) OverflowError!void
参数
错误
- Overflow
std.crypto.ff.Modulus.sq
函数
将域元素平方。
pub fn sq(self: Self, x: Fe) Fe
参数
std.crypto.ff.Modulus.sub
函数
两域元素相减(模 m)。
pub fn sub(self: Self, x: Fe, y: Fe) Fe
参数
std.crypto.ff.Modulus.toBytes
函数
将模数序列化为字节串。
pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) OverflowError!void
参数
错误
- Overflow
std.crypto.ff.Modulus.toMontgomery
函数
将域元素转换为 Montgomery 形式。
pub fn toMontgomery(self: Self, x: *Fe) RepresentationError!void
参数
错误
- UnexpectedRepresentation
std.crypto.ff.Modulus.toUint
函数
将模数作为整数返回
pub fn toUint(self: Self) FeUint
参数
self: Self
std.crypto.ff.mulAddLimb
函数
fn mulAddLimb(z: []Limb, x: []const Limb, y: Limb) Limb
参数
std.crypto.ff.mulAddWide
函数
fn mulAddWide(z: []Limb, x: []const Limb, y: []const Limb) void
参数
std.crypto.ff.native_endian
常量
std.crypto.ff.NullExponentError
错误集合
使用零指数求幂。 密码协议中出现零指数求幂,几乎总是存在可能导致轻易被攻击的缺陷。 因此,此模块遇到零指数时返回错误,促使应用程序显式处理这种情况。
错误
- NullExponent
std.crypto.ff.orLimbs
函数
fn orLimbs(limbs: []const Limb) Limb
参数
limbs: []const Limb
std.crypto.ff.OverflowError
错误集合
值过大,无法写入目标位置。
错误
- Overflow
std.crypto.ff.RepresentationError
错误集合
表示形式无效(Montgomery 域与非 Montgomery 域不一致)。
错误
- UnexpectedRepresentation
std.crypto.ff.std
别名
别名目标 std
std.crypto.ff.t_bits
常量
usize
std.crypto.ff.testCt
函数
fn testCt(ct_: anytype) !void
std.crypto.ff.testing
别名
别名目标 std.testing
std.crypto.ff.TLimb
常量
std.crypto.ff.Uint
类型函数
最大大小固定为 max_bits 的无符号大整数,适用于密码学操作。
存储大小向上取整到完整的 limb,可容纳至多 capacity_bits 位。
除非明确禁用侧信道防护,否则各操作均按恒定时间设计。
pub fn Uint(comptime max_bits: comptime_int) type
参数
max_bits: comptime_int
字段
Selfmax_limbs_countcapacity_bitsencoded_byteslimbsConstlimbsnormalizezerofromPrimitivetoPrimitivetoBytesfromByteseqlcompareisZeroisOddisOneaddWithOverflowsubWithOverflowmulAddWithOverflowbitLenPublictrailingZeroBitsPublicshiftRightPublicdivRemPublicgcdPublicexpandTocmovconditionalAddWithOverflowconditionalSubWithOverflowshiftLeftshiftRightByOneWithCarry
std.crypto.ff.Uint.addWithOverflow
函数
将 y 加到 x 上,并在较大的活动位宽处回绕。溢出时返回 1。
pub fn addWithOverflow(x: *Self, y: Self) u1
参数
std.crypto.ff.Uint.bitLenPublic
函数
返回位长度;零则返回 0。
pub fn bitLenPublic(x: Self) usize
参数
x: Self
std.crypto.ff.Uint.capacity_bits
常量
std.crypto.ff.Uint.cmov
函数
fn cmov(x: *Self, on: bool, y: Self) void
参数
std.crypto.ff.Uint.compare
函数
比较两个整数。
pub fn compare(x: Self, y: Self) math.Order
参数
std.crypto.ff.Uint.conditionalAddWithOverflow
函数
fn conditionalAddWithOverflow(x: *Self, on: bool, y: Self) u1
参数
std.crypto.ff.Uint.conditionalSubWithOverflow
函数
fn conditionalSubWithOverflow(x: *Self, on: bool, y: Self) u1
参数
std.crypto.ff.Uint.divRemPublic
函数
原地除以 divisor 并返回余数。
若 divisor 为零,则返回 error.DivisionByZero,不修改整数。
pub fn divRemPublic(x: *Self, divisor: usize) DivisionByZeroError!usize
参数
x: *Self
divisor: usize
错误
- DivisionByZero
std.crypto.ff.Uint.encoded_bytes
常量
序列化整数所需的字节数。
std.crypto.ff.Uint.eql
函数
若两个整数相等则返回 true。
pub fn eql(x: Self, y: Self) bool
参数
std.crypto.ff.Uint.expandTo
函数
fn expandTo(x: *Self, new_len: usize) void
参数
x: *Self
new_len: usize
std.crypto.ff.Uint.fromBytes
函数
从字节数组创建新的大整数。
pub fn fromBytes(bytes: []const u8, comptime endian: Endian) OverflowError!Self
参数
bytes: []const u8
endian: Endian
错误
- Overflow
std.crypto.ff.Uint.fromPrimitive
函数
从原始类型创建新的大整数。 此函数可能不是常量时间运行。
pub fn fromPrimitive(comptime T: type, init_value: T) OverflowError!Self
参数
T: type
init_value: T
错误
- Overflow
std.crypto.ff.Uint.gcdPublic
函数
返回最大公约数,其中 gcd(x, 0) = x。
若两个操作数均为零,返回 error.DivisionByZero。
pub fn gcdPublic(x: Self, y: Self) DivisionByZeroError!Self
参数
错误
- DivisionByZero
std.crypto.ff.Uint.isOdd
函数
若整数为奇数则返回 true。
pub fn isOdd(x: Self) bool
参数
x: Self
std.crypto.ff.Uint.isOne
函数
pub fn isOne(x: Self) bool
参数
x: Self
std.crypto.ff.Uint.isZero
函数
若整数为零则返回 true。
pub fn isZero(x: Self) bool
参数
x: Self
std.crypto.ff.Uint.limbs
函数
活动 Limb 的可变切片。
fn limbs(self: *Self) []Limb
参数
self: *Self
std.crypto.ff.Uint.limbsConst
函数
活动 Limb 的常量切片。
fn limbsConst(self: *const Self) []const Limb
参数
self: *const Self
std.crypto.ff.Uint.max_limbs_count
常量
std.crypto.ff.Uint.mulAddWithOverflow
函数
将 x 与 y 的乘积加到 acc,按当前有效位宽回绕。
若结果有任何部分被丢弃,则返回 1。
pub fn mulAddWithOverflow(acc: *Self, x: Self, y: Self) u1
参数
std.crypto.ff.Uint.normalize
函数
fn normalize(self: Self) Self
参数
self: Self
std.crypto.ff.Uint.Self
别名
别名目标 std.crypto.ff.Uint
std.crypto.ff.Uint.shiftLeft
函数
fn shiftLeft(x: *Self, shift: usize) void
参数
x: *Self
shift: usize
std.crypto.ff.Uint.shiftRightByOneWithCarry
函数
fn shiftRightByOneWithCarry(x: *Self, carry: u1) u1
参数
x: *Self
carry: u1
std.crypto.ff.Uint.shiftRightPublic
函数
pub fn shiftRightPublic(x: *Self, shift: usize) void
参数
x: *Self
shift: usize
std.crypto.ff.Uint.subWithOverflow
函数
从 x 减去 y,按两者中较大的有效位宽回绕。下溢时返回 1。
pub fn subWithOverflow(x: *Self, y: Self) u1
参数
std.crypto.ff.Uint.toBytes
函数
将大整数编码为字节数组。
pub fn toBytes(self: Self, bytes: []u8, comptime endian: Endian) OverflowError!void
参数
错误
- Overflow
std.crypto.ff.Uint.toPrimitive
函数
将大整数转换为基本类型。 此函数可能不以常数时间运行。
pub fn toPrimitive(self: Self, comptime T: type) OverflowError!T
参数
self: Self
T: type
错误
- Overflow
std.crypto.ff.Uint.trailingZeroBitsPublic
函数
返回尾随零位的数量;输入为零时返回有效位宽。
pub fn trailingZeroBitsPublic(x: Self) usize
参数
x: Self
std.crypto.ff.Uint.zero
常量
整数零。
Self
std.crypto.ff.WideLimb
容器
字段
源码
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());
}