[CFRG] (suggested language re mixing square roots and inversions) Re: Comment on draft-irtf-cfrg-hash-to-curve-10

Hi Riad:

Text along the following lines would avoid implementation detail, but 
would illustrate how one could "mix" inversions and square roots:

The inverses of two nonzero elements y1 and y2 of GF(q) can be computed 
by first computing the inverse z of y1*y2 and by subsequently computing 
y2*z=:1/y1 and y1*z=:1/y2.

This method can be used to compute the inverse and a square root, 
respectively, of two nonzero elements x and y of GF(q) (where y is a 
square in GF(q)) by first computing a square root z of 1/(y*x^2) and by 
subsequently computing a square root of y as x*y*z and the inverse of x 
as x*y*z^2.

I think this would be easier to read than any "div" verbiage and avoids 
having to deal with divisions by zero.

(In the case q = 3 (mod 4), if y is a nonzero element of GF(q) and 
z:=y^{(q-3)/4}, then y is a square in GF(q) only if y*z^2=1. One can 
generalize this to q = 5 (mod 8), q = 9 (mod 16), etc., where the 
general procedure is to compute z:=y^{(q-2^s-1)/2^{s+1}} in GF(q) where 

q:=2^s+1 (mod 2^{s+1}) and where y is a square in GF(q) only if 
(y*z^2)=w, where w^{2^{s-1}}=1. For s large, one gets Daira Hopwood's 

case with higher s, but the principle remains the same (and one could 
refer to a paper for computational tricks or simply declare this out of 
scope).)

Rene

On 2021-04-23 3:30 p.m., Riad S. Wahby wrote:
> Hello Daira,
>
> Thanks for clarifying your feedback.
>
> I remain concerned about mixing implementation detail with high-level
> description. Here I am referring to using divsqrt in place of natural
> field arithmetic operations (sqrt, inversion, etc.) in the body text.
> Describing the algorithm independent of the implementation details is
> a way of specifying the mathematical properties of the algorithm, and
> having this specification explicit in the document has value, from my
> perspective.
>
> But as I said in my prior email, it seems like refactoring Appx. G to
> use divsqrt and adding a few implementations of that function for the
> relevant cases (3 mod 4, 5 mod 8, 9 mod 16, and general, perhaps?) is
> a nice way of cleaning things up. And it seems like the same refactor
> applied to SvdW and Elligator in Appx. G would help, too.
>
> This isn't something I can do in the near term, but I'm very happy to
> spend time on this once I've got some! I'm hopeful that's about three
> weeks from now, but I've been called an optimist before.
>
> Thanks again for the feedback and best regards,
>
> -=rsw
>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867