sppark
sppark copied to clipboard
A question about Montgomery mult (form ff/mont_t.cuh)
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