LL GPU error-detection side computation

[ewmayer]

Since we are talking about DWT-enabled 'implicit mod via convolution-based multiply', the issue at hand boils down to this: Let m = 2^p-1 be the modulus, and r = current LL-test residue. ('r' can also be thought of as standing for 'remainder', since that is precisely what it is.)

Q: Is there a number-theoretic checksum for r^2 (mod m) which does not rely on knowledge of the quotient q = floor(r^2/m)?

A: To the best of my knowledge, no. But anyone who thinks they have found such a thing can test it out easily enough using an arbitrary-precision app of their choice, such as linux bc or Pari/GP.

[science_man_88]

Originally Posted by ewmayer

Since we are talking about DWT-enabled 'implicit mod via convolution-based multiply', the issue at hand boils down to this: Let m = 2^p-1 be the modulus, and r = current LL-test residue. ('r' can also be thought of as standing for 'remainder', since that is precisely what it is.)

Q: Is there a number-theoretic checksum for r^2 (mod m) which does not rely on knowledge of the quotient q = floor(r^2/m)?

A: To the best of my knowledge, no. But anyone who thinks they have found such a thing can test it out easily enough using an arbitrary-precision app of their choice, such as linux bc or Pari/GP.

not to my limited knowledge either except that ( so we can turn it into a negative form for higher values and square a lower value.

edit:google results come to https://en.wikipedia.org/wiki/Checksum#Modular_sum as possible I think but I'm not advanced enough to understand. okay never mind that's more about integrity not authenticity apparently.

[LaurV]

Originally Posted by ewmayer

Since we are talking about DWT-enabled 'implicit mod via convolution-based multiply', the issue at hand boils down to this: Let m = 2^p-1 be the modulus, and r = current LL-test residue. ('r' can also be thought of as standing for 'remainder', since that is precisely what it is.)

Q: Is there a number-theoretic checksum for r^2 (mod m) which does not rely on knowledge of the quotient q = floor(r^2/m)?

A: To the best of my knowledge, no. But anyone who thinks they have found such a thing can test it out easily enough using an arbitrary-precision app of their choice, such as linux bc or Pari/GP.

No. If this would be possible to do, we would not need to do DC. I remember I wrote some question like that in a mail to George 13-15 years ago
We had some email exchange at the time, and I was trying to find one such relation, to eliminate the DC (you know, the $10k bonus, hehe). George never replied directly to that email, most probably considering me a crank (which I was, and I still am, but I learned a lot since, hehe).

[preda]

Originally Posted by ewmayer

Since we are talking about DWT-enabled 'implicit mod via convolution-based multiply', the issue at hand boils down to this: Let m = 2^p-1 be the modulus, and r = current LL-test residue. ('r' can also be thought of as standing for 'remainder', since that is precisely what it is.)

Q: Is there a number-theoretic checksum for r^2 (mod m) which does not rely on knowledge of the quotient q = floor(r^2/m)?

A: To the best of my knowledge, no. But anyone who thinks they have found such a thing can test it out easily enough using an arbitrary-precision app of their choice, such as linux bc or Pari/GP.

Choose integer k > 1,
let M such that M^k == m, and
function checksum(r) = r mod M,

then checksum(r^2 mod m) == checksum(r)^2 mod M.

But.. M would need to be an "infinite precision real number" for this to work. So this is not a practical solution.