Skip to content

Why does One require Mul? #364

@ZettaScript

Description

@ZettaScript

While this is algebraically correct, implementations may not be able to provide One and Mul for the same types.

For example, I implemented polynomial quotient rings $(\mathbb{Z}/q\mathbb{Z})/(x^n+1)$ as a type Poly that implements One, but not Mul because naive polynomial multiplication would be inefficient and require a lot of code (division and extended Euclidean algorithm on polynomials). Instead, multiplication is done efficiently in the Number Theoretic Transform (NTT) domain, which is represented as a different type PolyNtt to ensure mathematical soundness. In this case I have to create my own trait One without the requirement.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions