Post-Quantum Polynomial Mod Operations in C

Post-quantum algortithms like Kyber for example move away from integer factorisation and discerete logarithms and use lattice based methods for generating private/public key pairings.

Kyber key generation is based on mod p operations using polynomial add and subtract methods. As a toy exercise, the code below is a simple mod P polynomial add operation in C# and would allow mod P additions of two polynomials.

For a deeper explaination of this head over to the great resources at https://asecuritysite.com/kyber/ and watch the video below.

[embed]

namespace QuantCrypt.Core.Math;

public record PolynomialTerm(int Coefficient, int Order);

public static class PolynomialOperations
{
    public static PolynomialTerm[] AddMod(PolynomialTerm[] polynomialA, PolynomialTerm[] polynomialB, int mod)
    {
        List<PolynomialTerm> result = new();

        foreach (PolynomialTerm poly in polynomialA)
        {
            PolynomialTerm? orderMatchPoly = polynomialB.FirstOrDefault(p => p.Order == poly.Order);
            result.Add(orderMatchPoly is null ? 
                poly with { Coefficient = poly.Coefficient % mod } : 
                poly with { Coefficient = (poly.Coefficient + orderMatchPoly.Coefficient) % mod});
        }

        result.AddRange(polynomialB
            .Where(p => result.All(r => r.Order != p.Order))
            .Select(p => p with { Coefficient = p.Coefficient % mod }));

        return result
            .Where(p => p.Coefficient != 0)
            .OrderByDescending(p => p.Order).ToArray();
    }
}

using QuantCrypt.Core.Math;

namespace QuantCrypt.Core.Tests;

public class MathTests
{
    [Fact]
    public void ModPolynomial_Add_Successful_Test()
    {
        // Arrange
        PolynomialTerm[] polynomialA = new[]
        {
            new PolynomialTerm(2, 4),
            new PolynomialTerm(3, 3),
            new PolynomialTerm(10, 1),
            new PolynomialTerm(3, 0)
        };

        PolynomialTerm[] polynomialB = new[]
        {
            new PolynomialTerm(3, 5),
            new PolynomialTerm(14, 3),
            new PolynomialTerm(10, 1),
            new PolynomialTerm(4, 0)
        };

        // Act
        PolynomialTerm[] actualResult = PolynomialOperations.AddMod(polynomialA, polynomialB, 17);

        // Assert
        PolynomialTerm[] expectedResult = new[]
        {
            new PolynomialTerm(3, 5),
            new PolynomialTerm(2, 4),
            new PolynomialTerm(3, 1),
            new PolynomialTerm(7, 0)
        };
        expectedResult.OrderByDescending(p => p.Order);

        Assert.True(expectedResult.SequenceEqual(actualResult));
    }
}

You can see the full code at https://github.com/leedale1981/infosec/tree/master/Cryptography