<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Oct 26, 2014, at 11:57 PM, Mike Hamburg <<a href="mailto:mike@shiftleft.org" class="">mike@shiftleft.org</a>> wrote:</div></blockquote><br class=""><blockquote type="cite" class=""><div class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">Right. In my try, I had calculated it by multiplication not requiring internal carry propagation, which depends on c as well as nail length. This can be computed by expanding the prime into polynomial P in the radix, and comparing the largest coefficient of ((x^limbs - 1) / (x-1))^2 mod P to 2^(2*wordsize - 2*radix - extra). Here extra is some small amount (0.1) to account for not having reduced perfectly the first time; + 1 if the polynomial is signed;</span></div></blockquote><br class=""><blockquote type="cite" class=""><div class=""></div></blockquote></div><div>+1 if the polynomial is signed isn’t quite right actually. It should be something more like, always treat the non-leading coefficients of the polynomial as negative, so that when computing the reduction they always add to each other rather than canceling.</div><div><br class=""></div><div>— Mike</div></body></html>