有限域之美与力量 (以及 Zig)

有限域（和 Zig）之美与力量

数学是一个非常优美的研究领域，并且有很多分支。 但是，对我来说，数论是最有趣（且有用）的，它是密码学的核心。 为此，我们喜欢通过限制整数值的范围（在有限域内）来简化事情。 这使我们能够在计算限制内执行复杂的操作。

有限域 (FF) 涉及（或伽罗瓦域）有限数量的元素，并且我们可以在这些元素上执行乘法、加法、减法和除法。 一个常见的域由一个素数定义，我们对运算取 (mod p)。 总的来说，我们可以定义一个模数 ($N$) 来定义有限空间，并且我们有从 0 到 $N-1$ 的值。 模数可以是素数，也可以是合数（由多个素数相乘组成）。

示例

假设我们的模数为 $N = 13$，值为 $x = 10$ 和 $y = 8$，那么我们得到：

$x + y = 10+8=5 \pmod{13}$

$x - y = 10-8=2 \pmod{13}$

$x \times y = 10 \times 8=2 \pmod{13}$

$x^y = 10^8=9 \pmod{13}$

$x^2 = 10^2=2 \pmod{13}$

如果使用素数作为模数，我们可以反转运算并恢复原始值。 我们还可以使用合数作为模数，例如 $N = 21$：

$x + y = 10+8=18 \pmod{21}$

$x - y = 10-8=2 \pmod{21}$

$x \times y = 10 \times 8=17 \pmod{21}$

$x^y = 10^8=16 \pmod{21}$

$x^2 = 10^2=16 \pmod{21}$

如果使用合数模数，我们不保证可以反转运算。

编码

在 Zig 中，我们可以使用以下代码定义模数中的位数：

const crypto = @import("std").crypto;
const N = crypto.ff.Modulus(256);

这将定义一个具有 256 位的有限域。 然后我们可以使用以下代码定义 997 的模数：

const n = try N.fromPrimitive(u256, 997);

然后我们可以按照模数限制我们的值：

const x = try N.Fe.fromPrimitive(u256, n, 10);
    const y = try N.Fe.fromPrimitive(u256, n, 8);

然后我们可以应用有限域运算：

const res1 = n.add(x, y);
    const res2 = n.sub(x, y);
    const res3 = n.mul(x, y);
    const res4 = try n.pow(x, y);
    const res5 = n.sq(x);

源代码

以下代码使用 Zig 0.15.1 版本编译 [ here]。 通过 Zig，我们可以使用以下代码实现有限域计算 [ here]：

const std = @import("std");
const crypto = @import("std").crypto;

pub fn main() !void {
    var stdout_buffer: [4096]u8 = undefined;
    var stdout_writer = std.fs.File.stdout().writer(&stdout_buffer);
    const stdout = &stdout_writer.interface;
    var xstring: []u8 = undefined;
    var ystring: []u8 = undefined;
    var nstring: []u8 = undefined;
    const args = try std.process.argsAlloc(std.heap.page_allocator);
    defer std.process.argsFree(std.heap.page_allocator, args);
    // 检查是否有任何参数
    if (args.len > 1) {
        xstring = args[1];
    }
    if (args.len > 2) {
        ystring = args[2];
    }
    if (args.len > 3) {
        nstring = args[3];
    }
    const xval = try std.fmt.parseInt(u256, xstring, 10);
    const yval = try std.fmt.parseInt(u256, ystring, 10);
    const nval = try std.fmt.parseInt(u256, nstring, 10);

    const N = crypto.ff.Modulus(256);
    const n = try N.fromPrimitive(u256, nval);
    const x = try N.Fe.fromPrimitive(u256, n, xval);
    const y = try N.Fe.fromPrimitive(u256, n, yval);

    const res1 = n.add(x, y);
    const res2 = n.sub(x, y);
    const res3 = n.mul(x, y);
    const res4 = try n.pow(x, y);
    const res5 = n.sq(x);

    try stdout.print("Modulus: {s}\n\n", .{nstring});
    try stdout.print("{!}+{!} = {!}\n\n", .{ x.toPrimitive(u256), y.toPrimitive(u256), res1.toPrimitive(u256) });
    try stdout.print("{!}-{!} = {!}\n\n", .{ x.toPrimitive(u256), y.toPrimitive(u256), res2.toPrimitive(u256) });
    try stdout.print("{!}*{!} = {!}\n\n", .{ x.toPrimitive(u256), y.toPrimitive(u256), res3.toPrimitive(u256) });
    try stdout.print("{!}^{!} = {!}\n\n", .{ x.toPrimitive(u256), y.toPrimitive(u256), res4.toPrimitive(u256) });
    try stdout.print("{!}^2 = {!}\n\n", .{ x.toPrimitive(u256), res5.toPrimitive(u256) });
    try stdout.flush();
}

一个示例运行结果是 [ here]：

Modulus: 170141183460469231731687303715884105727

95949300215433201057985465432109991011+88650495309403022129594326612354105412 = 14458612064366991455892488328579990696
95949300215433201057985465432109991011-88650495309403022129594326612354105412 = 7298804906030178928391138819755885599
95949300215433201057985465432109991011*88650495309403022129594326612354105412 = 49991524536430291837590218100257596173
95949300215433201057985465432109991011^88650495309403022129594326612354105412 = 63681285772373855177490411131157177347
95949300215433201057985465432109991011^2 = 85048520307126761386043878741772214002

如果使用 Python 尝试，我们会得到：

>>> N=170141183460469231731687303715884105727
>>> x=95949300215433201057985465432109991011
>>> y=88650495309403022129594326612354105412
>>> (x+y)%N
14458612064366991455892488328579990696
>>> (x-y)%N
7298804906030178928391138819755885599
>>> (x*y)%N
49991524536430291837590218100257596173
>>> pow(x,y,N)
63681285772373855177490411131157177347
>>> pow(x,2,N)
85048520307126761386043878741772214002

演示在这里：

https://asecuritysite.com/zig/zig_ff

结论

因此，感谢有限域为互联网提供安全、信任和隐私的核心。

• 原文链接： medium.com/asecuritysite...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～