toMont

fn toMont(x: u32) u32

File

Code

fn toMont(x: u32) u32 {
    // R = 2^32, R mod q can be computed as:
    // 2^32 mod q = 2^32 mod (2^23 - 2^13 + 1)
    // Using the identity 2^23 = 2^13 - 1 (mod q), we can reduce 2^32
    // But it's easier to just do: return montReduce(x * R^2 mod q)
    // where R^2 mod q is precomputed

    // Computing R^2 mod q:
    // R = 2^32, so R^2 = 2^64
    // We can compute this by noting that R mod q first:
    // 2^32 = 2^32 mod q
    // But let's use a simpler approach: multiply x by R in the Montgomery domain
    // Actually, the simplest is: x * R mod q = montReduceLe2Q(x * R^2 mod q)

    // Precompute R^2 mod q at comptime
    const r_mod_q = comptime blk: {
        // 2^32 mod q - compute by successive squaring
        var r: u64 = 1;
        for (0..32) |_| {
            r = (r * 2) % Q;
        }
        break :blk @as(u32, @intCast(r));
    };

    const r2_mod_q = comptime blk: {
        const r = @as(u64, r_mod_q);
        break :blk @as(u32, @intCast((r * r) % Q));
    };

    return montReduceLe2Q(@as(u64, x) * @as(u64, r2_mod_q));
}