<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 Jan 22, 2016, at 4:20 AM, Michael Scott <<a href="mailto:mike.scott@miracl.com" class="">mike.scott@miracl.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><span style="font-size:12.8px" class="">Have a look at the references in </span><a href="http://www.google.com/patents/US9148282" target="_blank" style="font-size:12.8px" class="">http://www.google.com/patents/US9148282</a><div style="font-size:12.8px" class=""><br class=""></div><div style="font-size:12.8px" class="">Particularly Siguna Mueller's Lucas-function based method..</div></div></div></blockquote><div><br class=""></div><div>Thanks! To your knowledge, is the Mueller method itself patented? I’ll check it out when I can get the right login.</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div style="font-size:12.8px" class="">Not sure about the cost..</div></div></div></blockquote><div><br class=""></div><div>The abstract claims “expected cost = 1.33 * the number of multiplications for a square and multiply”, which would be 468 in this case.</div><div><br class=""></div><div>I’ve also improved the splitting in my code, pasted below, which improves its worst-case time to 718 multiplies, with 7 elements in RAM and 2 in ROM plus still that pesky dlog table. A little tuning can save another few multiplies, but I went with simplicity instead. So it’s still presumably worse than the Mueller method, except perhaps in that it is deterministic.</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div style="font-size:12.8px" class="">Mike</div></div></div></blockquote><div><br class=""></div><div>Thanks again,</div><div>— also Mike</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div style="font-size:12.8px" class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Thu, Jan 21, 2016 at 11:30 PM, Mike Hamburg <span dir="ltr" class=""><<a href="mailto:mike@shiftleft.org" target="_blank" class="">mike@shiftleft.org</a>></span> wrote:<br class=""><blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex" class="gmail_quote"><div style="word-wrap:break-word" class="">Hello Curves,<div class=""><br class=""></div><div class="">I was porting an embedded EC library to work with other curves, and I was wondering if anyone knew a compact, fast, deterministic algorithm for square roots mod NIST p224 (or other annoying primes)? I’m not worried about constant-time operation, since I probably have to blind anyway to reduce other side channels, but a deterministic algorithm is preferable because of possible real-time constraints.</div><div class=""><br class=""></div><div class="">OpenSSL’s implementation takes something like 4700 multiplications on average, which is more than a point*scalar multiply.</div><div class=""><br class=""></div><div class="">Dan’s paper [1] gives a variant of the Tonelli-Shanks algorithm which is fast and deterministic, requiring only 364 multiplies. But it’s very heavy, with 1024 precomputed elements. Reducing the table size makes the algorithm considerably slower.</div><div class=""><br class=""></div><div class="">I’ve tried to combine Dan’s Tonelli-Shanks variant with Sutherland’s algorithm, below. A variant with 4 precomputed points, a 64-element discrete log table (not as big as it sounds) and 10 or so field elements in memory takes 900 multiplies worst-case (~760 average-case).</div><div class=""><br class=""></div><div class="">Cipolla’s algorithm is nondeterministic.</div><div class=""><br class=""></div><div class="">Is Pocklington the way to go? It’s technically nondeterministic as well, but if I read [1] correctly the failure probability is 2^-96. A straightforward implementation probably takes more than 900 multiplies, but hopefully it’s simpler and uses less memory, right?</div><div class=""><br class=""></div><div class="">Is there some other algorithm I’m missing?</div><div class=""><br class=""></div><div class="">Thanks,</div><div class="">— Mike</div><div class=""><br class=""></div><div class="">[1] <a href="http://cr.yp.to/papers/sqroot.pdf" target="_blank" class="">http://cr.yp.to/papers/sqroot.pdf</a></div><div class=""><br class=""></div></div></blockquote></div></div></div></blockquote><div><br class=""></div><div><div>p = 2^224 - 2^96 + 1</div><div>F = GF(p)</div></div><div>qnr = 11^(2^128-1)</div><div>dlog_table = dict((</div><div> (qnr^(2^90*i),2^6-i) for i in xrange(2^6)</div><div>))</div>precmp = [qnr^2^66,qnr^2^84]<br class=""><br class="">def isqrt(x):<br class=""> s = x^3<br class=""> s = s^2 * x # 2^3 - 1<br class=""> u = s^2^3 * s # 2^6 - 1<br class=""> s = u^2^6 * u # 2^12 - 1<br class=""> t = s^2^12 * s # 2^24 - 1<br class=""> s = t^2^24 * t # 2^48 - 1<br class=""> s = s^2^48 * s # 2^96 - 1<br class=""> s = s^2^24 * t # 2^120 - 1<br class=""> s = s^2^6 * u # 2^126 - 1<br class=""> s = s^2 * x<br class=""> # here s == x^(2^127-1)<br class=""> <br class=""> ret = [s]<br class=""> rou = [qnr]<br class=""> <br class=""> def leaf(r,n=6):<br class=""> dlog = dlog_table[r]>>(tbits-n)<br class=""> for i in xrange(len(ret)):<br class=""> for j in xrange(n):<br class=""> if dlog & (1<<j): ret[i] = ret[i] * rou[i]<br class=""> rou[i] = rou[i]^2<br class=""> <br class=""> def stage(m):<br class=""> if len(ret) > 1:<br class=""> return ret[-1]^2^(6*m)<br class=""> else:<br class=""> return (ret[-1]^2*x)^2^(6*m-1)<br class=""> <br class=""> def descent(n):<br class=""> for i in xrange(n-1,0,-1):<br class=""> leaf(stage(i),6)<br class=""> <br class=""> if len(ret) > 1:<br class=""> rou.pop()<br class=""> leaf(ret.pop(),6)<br class=""> else:<br class=""> leaf(ret[0]^2*x,5)<br class=""> </div><div> # Have to apply leaf() 96/6 = 16 times</div><div> # Split it as 11+5, 11=6+5, 6=4+2, 5=3+2</div><div> # Precomputed roots of unity for 2^(6*5) and 2^(6*2)</div><div> ret.append(stage(11)); rou.append(precmp[0])<br class=""> ret.append(stage(3)); rou.append(precmp[1])<br class=""> descent(2)<br class=""> descent(3)<br class=""> <br class=""> ret.append(stage(6)); rou.append(precmp[0])<br class=""> ret.append(stage(3)); rou.append(precmp[1])<br class=""> descent(2)<br class=""> descent(3)<br class=""> <br class=""> ret.append(stage(4)); rou.append(precmp[1])<br class=""> descent(2)<br class=""> descent(4)<br class=""> <br class=""> return ret[0]</div><br class=""></body></html>