2-adic roots (Was a message by Niels Möller, July 2012)

[Marco Bodrato]

Ciao Niels!

I'm sorry I did not remember about your proposals for a better implementation of bsqrtinv.
I've seen the FIXME in the code, and with that suggestions in mind I wrote a code that is almost equivalent to yours.
But I kept the meaning of the bitcount variable in line with the already existing code by Martin Boij.

Looking at your code I realized that I was using one more bit than needed in the initial table. I trimmed it.

Moreover, I did not take care about "canonicalization" of the returned value.
Given that in Z/2^k there are four solutions (if any) to the equation x^2=d (mod 2^k), if ones want to have a canonicalized value, I'd suggest the smallest. I used this criteria for my initial table, that way, every value in the table fits in 8 bits.

My bsqrt seems faster than yours, but this depends only on the use of a Karp–Markstein step in my code. This allows to just compute a half size inverse square root.

The two functions are internal only currently, but if we want to expose them in the API we should carefully chose the interface.

Ĝis,
m