Skip to content

Bug: M31::new() function performs incorrect modular reduction #8

@0x6980

Description

@0x6980

We have a function named new in the field, which tries to compute u32 values to a value mod P.

    #[inline]
    pub const fn new(val: u32) -> Self {
        let reduced = if val >= P { val - P } else { val };
        Self(reduced)
    }

Where P = 2^31 -1.

Here's the problem:

When val >= P, the code does val - P, which works only if val < 2*P (i.e., val < 2^32 - 2). For values ≥ 2*P (≥2^32 - 2 ), this will not properly reduce them modulo P:

  • Input val = 2*P = 2^32 - 2 → Should output 0, but the code outputs: 2p - p = p (which is P, not 0)

  • Input val = u32::MAX = 2^32 - 1 → Should output 1, but the code outputs: 2^32 - 1 - (2^31 - 1) = 2^31 (which is P+1, not 1)

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions