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

[Rene Struik <[e-mail]>]

Two sentences are all that is needed to describe taking a square root 
and any number of inversions ("Montgomery's trick"), in an easy to read 
format by humans.

On 2021-05-03 2:23 a.m., Daira Hopwood wrote:
> On 23/04/2021 21:47, Rene Struik wrote:
>> 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.
>
> But computing the inverse and the square root in parallel isn't what
> we're doing. The combined inverse-and-sqrt method we're referring to
> here isn't rocket science, it will be familiar to anyone who has
> implemented Ed25519.
>
>> I think this would be easier to read than any "div" verbiage and 
>> avoids having to deal with divisions by zero.
>
> Just to be clear, there are no divisions by zero in the specification
> I gave in my previous post:
>
> Let h be some fixed nonsquare in Fq. Define sqrt_ratio for
> u ∊ Fq and v ∊ Fq* as:
>
>   sqrt_ratio(u, v) = (true, sqrt(u/v)),    if u/v 
is square in Fq
>                    = (false, sqrt(h*u/v)), otherwise.
>
> Notice that sqrt_ratio is not defined for v = 0, and it is easily proven
> that it is never applied with v = 0.
>

-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]