# Inverse Square Roots

As in the internet-draft, the `decaf377`

functions are defined in terms of the
following function, which computes the square root of a ratio of field elements,
with the special behavior that if the input is nonsquare, it returns the square
root of a related field element, to allow reuse of the computation in the
hash-to-group setting.

Define $ζ$ as a non-square in the field and `sqrt_ratio_zeta(N,D)`

as:

- (True, $DN $) if $N$ and $D$ are nonzero, and $DN $ is square;
- (True, $0$) if $N$ is zero;
- (False, $0$) if $D$ is zero and $N$ is non-zero;
- (False, $ζDN $) if $N$ and $D$ are nonzero, and $DN $ is nonsquare.

Since $ζ$ is nonsquare, if $DN $ is nonsquare, $ζDN $ is
square. Note that **unlike** the similar function in the
`ristretto255`

/`decaf448`

internet-draft, this function does not make any
claims about the sign of its output.

To compute `sqrt_ratio_zeta`

we use a table-based method adapted from Sarkar 2020 and zcash-pasta, which is described in the remainder of this section.

## Constants

We set $n>1$ (the 2-adicity of the field) and $m$ odd such that $p−1=2_{n}m$. For the BLS12-377 scalar field, $n=47$ and $m=60001509534603559531609739528203892656505753216962260608619555$.

We define $g=ζ_{m}$ where $ζ$ is a non-square as described above. We fix $ζ$ as 2841681278031794617739547238867782961338435681360110683443920362658525667816.

We then define a $k≥1$ and $ℓ_{0},…,ℓ_{k−1}>0$ such that $ℓ_{0}+…+ℓ_{k−1}=n−1$. We also define a parameter $w$ where $1≤w≤max(ℓ_{0},ℓ_{1},…,ℓ_{k−1})$. For decaf377 we choose:

- $k=6$
- $ℓ_{0,1}=7$
- $ℓ_{2,3,4,5}=8$
- $w=8$

## Precomputation

Lookup tables are needed which can be precomputed as they depend only on the 2-adicity $n$ and the choice of $ℓ_{i}$ above.

### $g$ lookup table: $g_{ν2_{iw}}$

We compute $g_{ν2_{iw}}$ for $ν∈1,…,2_{w}−1$ and $i∈0,…,k−1$, indexed on $x$ and $ν$:

$ gg_{2_{8}}⋮g_{2_{40}} g_{2}g_{2_{9}}⋮g_{2_{41}} ……⋱… g_{2_{8}−1}(g_{2_{8}})_{2_{8}−1}⋮(g_{2_{40}})_{2_{8}−1} $

This table lets us look up powers of $g$.

### $s$ lookup table: $g_{−ν(2_{n−w})}$

We compute $g_{−ν(2_{n−w})}$ for $ν∈0,…,2_{w}−1$, indexed on $g_{−ν(2_{n−w})}$:

$(g_{0} g_{−2_{39}} (g_{−2_{39}})_{2} … (g_{−2_{39}})_{2_{8}−1} )$

We use this table in the procedure that follows to find $q_{i}$ (they are the $ν$ values) in order to compute $s_{i}$.

## Procedure

In the following procedure, let $u=N/D$. We use the following relations from Sarkar 2020:

- Equation 1: $α_{i}=x_{i}g_{t_{i}}$ and $t_{i}=(t_{i−1}+s_{i−1})/2_{ℓ_{i}}$ for $i∈0,…,k−1$ and $t_{k}=t_{k−1}+s_{k−1}$
- Lemma 3: $α_{i}g_{s_{i}}=1$ for $i∈0,…,k−1$
- Equation 2: $s_{i}=q_{i}2_{n−l_{i}}$

In these expressions, $x_{i}$ and $α_{i}$ are field elements. $q_{i}$ are unsigned $ℓ_{i}$-bit integers. At each $i$, the algorithm first computes $x_{i}$, then $t_{i}$ and $α_{i}$ (from the previous step’s $t_{i−1}$ and $s_{i−1}$), then finally $s_{i}$ and $q_{i}$, in each case such that they satisfy the above expressions. Note that in the algorithm $t_{0}=0$.

### Step 1: Compute $v=u_{2m−1}$

We compute $v=u_{2m−1}$. This corresponds to line 2 of the `findSqRoot`

Algorithm 1 in Sarkar 2020.

Substituting $u=N/D$:

$v=(DN )_{2m−1}=N_{2m−1}D_{−2m−1}$

Applying Fermat’s Little Theorem (i.e. $D_{p−1}=1modp$):

$v=N_{2m−1}D_{p−1−2m−1}$

Substituting $p−1=2_{n}m$ and rearranging:

$v=N_{2m−1}D_{2_{n}m−2m−1}$

$v=N_{2m−1}D_{21(2_{n+1}m−m−1)}$

$v=N_{2m−1}D_{21(2_{n+1}m−m−1−2_{n+1}+2_{n+1})}$

$v=N_{2m−1}D_{21(2_{n+1}−1)(m−1)+2_{n}}$

$v=N_{2m−1}D_{21(2_{n+1}−1)(m−1)}D_{2_{n}}$

We compute $v$ using a quantity $w$ we define as:

$w=(ND_{2_{n+1}−1})_{(m−1)/2}D_{2_{n}−1}$

We also define:

$s=D_{2_{n}−1}$

$t=D_{2_{n+1}−1}=Ds_{2}$

And substitute $s$ and $t$ into $w$ which gives us:

$w=s(Nt)_{2m−1}$

We now can use $w$ in the computation for $v$ and $uv$:

$v=wD$

$uv=wN$

### Step 2: Compute $x$

Compute $x=(uv)v$ using $v$ and $uv$ as calculated in the prior step. This corresponds to line 4 of the `findSqRoot`

Algorithm 1 in Sarkar 2020.

### Step 3: Compute $x_{i}$

We next compute $x_{i}=x_{2_{n−1−(ℓ+…+ℓ)}}$ for $i=0,..,k−1$. This corresponds to line 5 of the `findSqRoot`

Algorithm 1 in Sarkar 2020. This gives us the following components:

$x_{0}=x_{2_{n−1−ℓ}}=x_{2_{39}}=x_{1}$

$x_{1}=x_{2_{n−1−(ℓ+ℓ)}}=x_{2_{32}}=x_{2}$

$x_{2}=x_{2_{24}}=x_{3}$

$x_{3}=x_{2_{16}}=x_{4}$

$x_{4}=x_{2_{8}}=x_{5}$

$x_{5}=x_{2_{0}}=x$

### Step 4: Compute $s_{i}$ and $t_{i}$

Next, we loop over $k$. This corresponds to lines 6-9 of the `findSqRoot`

Algorithm 1 in Sarkar 2020.

#### For $i=0$

Using Lemma 3:

$α_{0}g_{s_{0}}=1$

Substituting the definition of $α_{0}$ from equation 1:

$x_{0}g_{t_{0}}g_{s_{0}}=1$

Rearranging and substituting in $t_{0}=0$ (initial condition):

$x_{0}=g_{−s_{0}}$

Substituting in equation 2:

$x_{0}=g_{−q_{0}2_{n−ℓ}}=g_{−q_{0}2_{40}}$

This is almost in a form where we can look up $q_{0}$ in our s lookup table to get $q_{0}$ and thus $s_{0}$. If we define $q_{0}=2q_{0}$ we get:

$x_{0}=g_{−q_{0}2_{39}}$

Which we can use with our s lookup table to get $q_{0}$. Expressing $s_{0}$ in terms of $q_{0}$, we get $s_{0}=q_{0}2_{39}$.

#### For $i=1$

First we compute $t_{1}$ using equation 1:

$t_{1}=(t_{0}+s_{0})/2_{ℓ_{1}}=(t_{0}+s_{0})/2_{7}=q_{0}2_{32}$

Next, similar to the first iteration, we use lemma 3 and substitute in $t_{1}$ and $s_{1}$ to yield:

$α_{1}g_{s_{1}}=1$

$x_{1}g_{q_{0}2_{32}}=g_{−q_{1}2_{39}}$

In this expression we can compute the quantities on the left hand side, and the right hand side is in the form we expect for the s lookup table, yielding us $q_{1}$. Note that here too we define $q_{1}=2q_{1}$ such that the s lookup table can be used. Expressing $s_{1}$ in terms of $q_{1}$, we get $s_{1}=q_{1}2_{39}$.

#### For $i=2,…,5$

The remaining iterations proceed similarly, yielding the following expressions:

$t_{2}=q_{0}2_{24}+q_{1}2_{31}$

$s_{2}=q_{2}2_{39}$

Note for $q_{2}$ and the remaining iterations we do not require a trick (i.e. where $q_{i}=2q_{i}$) to get $s_{2}$ in a form where it can be used with the s lookup table. In the following expressions for $t_{i}$, $q_{1}$ is always even, and so the high bit of each value is unchanged when adding $q_{1}$.

$t_{3}=q_{0}2_{16}+q_{1}2_{23}+q_{2}2_{31}$

$s_{3}=q_{3}2_{39}$

$t_{4}=q_{0}2_{8}+q_{1}2_{15}+q_{2}2_{23}+q_{3}2_{31}$

$s_{4}=q_{4}2_{39}$

$t_{5}=q_{0}+q_{1}2_{7}+q_{2}2_{15}+q_{3}2_{23}+q_{4}2_{31}$

$s_{5}=q_{5}2_{39}$

At the end of this step, we have found $s_{i}$ and $t_{i}$ for $i∈0,…,k−1$.

### Step 5: Return result $y$

Next, we can use equation 1 to compute $t=t_{5}+s_{5}$ using $t_{5}$ and $s_{5}$ from the previous step:

$t=q_{0}+q_{1}2_{7}+q_{2}2_{15}+q_{3}2_{23}+q_{4}2_{31}+q_{5}2_{39}$

This matches the expression from Lemma 4 in Sarkar 2020.

Next, to compute $g_{t/2}$, we lookup entries in the g lookup table. To do so, we can decompose $t/2$ into:

$t/2=q_{0}2_{0}+q_{1}2_{8}+q_{2}2_{16}+q_{3}2_{24}+q_{4}2_{32}+q_{5}2_{40}$

then $g_{t/2}$ is computed as:

$g_{t/2}=g_{q_{0}2_{0}}g_{q_{1}2_{8}}g_{q_{2}2_{16}}g_{q_{3}2_{24}}g_{q_{4}2_{32}}g_{q_{5}2_{40}}$

Multiplying in $uv$ from step 1, we compute:

$y=uvg_{t/2}$

This corresponds to line 10 of the `findSqRoot`

Algorithm 1 in Sarkar 2020.

In the non-square case, $q_{0}$ will be odd, and $t$ will be odd. We will have computed $y=(N/D)g $ and multiply $y$ by a correction $ζ/g $ to get our desired output.

We can use the result of this computation $y$ to determine whether or not the square exists, recalling from Step 1 that $u=N/D$:

- If $u$ is square, then $y=N/D $, and $y_{2}D−N=0$
- If $u$ is non-square, then $y=ζN/D $ and $y_{2}D−ζN=0$.