mpn_sec_add_1_itch

Niels Möller nisse at lysator.liu.se
Wed Jul 2 20:17:50 UTC 2014


Can we document that mpn_sec_add_1_itch(n) <= n? I see no reason any
implementation would need more scartch space, and this makes it possibly
to skip the function call to the itch function if one is willing to
always pass n limbs of scratch. E.g., if one has a dead area around
anyway.

E.g, I'm looking into implementing arithmetic mod p = 2^{255} - 19. For
a 64-bit machine, I could do a reduction from 512 to 256 bits using

void
curve_25519_modp(mp_limb_t *rp)
{
  mp_limb_t hi, cy;

  cy = mpn_addmul_1 (rp, rp + 4, (mp_limb_t) 19 << 1);
  hi = rp[3];
  
  cy = (cy << 1) + (hi >> 63);
  rp[3] = (hi & (GMP_NUMB_MASK >> 1))
    + mpn_sec_add_1(rp, rp, 3, cy * 19, rp+4);
}

(Untested, and generalizable to any limb size which isn't a divisor of
255).

/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.



More information about the gmp-devel mailing list