The NaCL ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{130} - 5$ using the following modular multiplication function:

static void mulmod(unsigned int h[17],const unsigned int r[17])
{  
  unsigned int hr[17];
  unsigned int i, j, u;

  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  unsigned int horig[17];
  unsigned int j, negative;

  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?

The NaCl ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{130} - 5$ using the following modular multiplication function:

static void mulmod(unsigned int h[17],const unsigned int r[17])
{  
  unsigned int hr[17];
  unsigned int i, j, u;

  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  unsigned int horig[17];
  unsigned int j, negative;

  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?

The NaCL ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{30} - 5$ using the following modular multiplication function:

static void mulmod(unsigned int h[17],const unsigned int r[17])
{  
  unsigned int hr[17];
  unsigned int i, j, u;

  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  unsigned int horig[17];
  unsigned int j, negative;

  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?

The NaCL ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{130} - 5$ using the following modular multiplication function:

static void mulmod(unsigned int h[17],const unsigned int r[17])
{  
  unsigned int hr[17];
  unsigned int i, j, u;

  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  unsigned int horig[17];
  unsigned int j, negative;

  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?

The NaCL ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{30} - 5$ using the following modular multiplication function (variables ommitted for brevity):

static void mulmod(unsigned int h[17],const unsigned int r[17])
{  
  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?

The NaCL ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{30} - 5$ using the following modular multiplication function:

static void mulmod(unsigned int h[17],const unsigned int r[17])
{  
  unsigned int hr[17];
  unsigned int i, j, u;

  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  unsigned int horig[17];
  unsigned int j, negative;

  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?