sppark icon indicating copy to clipboard operation
sppark copied to clipboard

A question about Montgomery mult (form ff/mont_t.cuh)

Open Kui2ei opened this issue 3 months ago • 0 comments

When i observed the implementation of Montgomery multiplication over finite fields, I'm very confused about

static inline void mad_n_redc(uint32_t even[], uint32_t odd[],
                                    const uint32_t a[], uint32_t bi, bool first=false)
        {
            if (first) {
                mul_n(odd, a+1, bi);
                mul_n(even, a,  bi);
            } else {
                asm("add.cc.u32 %0, %0, %1;" : "+r"(even[0]) : "r"(odd[1]));
                madc_n_rshift(odd, a+1, bi);
                cmad_n(even, a, bi);
                asm("addc.u32 %0, %0, 0;" : "+r"(odd[n-1]));
            }

            uint32_t mi = even[0] * M0;

            cmad_n(odd, MOD+1, mi);
            cmad_n(even, MOD,  mi);
            asm("addc.u32 %0, %0, 0;" : "+r"(odd[n-1]));
        }

third to last row cmad_n(odd, MOD+1, mi);

As you commented on the last line in the function cmad_n “”// return carry flag“” But obviously the carry in the first “cmad_n” function will not be received by the second “cmad_n” function Why is the overflow not considered?

If you think overflow must not happen here, please tell me why as well,THANKs

Kui2ei avatar Mar 18 '24 07:03 Kui2ei