Mathematical_Formulation

Mathematical Formulation

This page explains the underlying math behind LAI.

---

1. Hash-Based Seed Function

For $$(x, y, s \in \mathbb{Z}_p)$$, define:

$$ H(x, y, s) ;=; \mathrm{SHA256}\bigl(\text{bytes}(x),|,\text{bytes}(y),|,\text{bytes}(s)\bigr);\bmod;p, $$

where $$“(|)”$$ denotes concatenation of the big-endian byte representations.

---

2. Modular Square Root (Tonelli–Shanks)

Solve $$(z^2 \equiv a \pmod p) for prime (p)$$:

1. Case $$(p \equiv 3 \pmod 4)$$:

   $$z = a^{\frac{p+1}{4}} \bmod p.$$

2. General Tonelli–Shanks (any odd prime):
   Runs in $$(O(\log^2 p))$$.

---

3. LAI Transformation $$(T)$$

Given:

• $$((x,y)\in \mathbb{F}_p^2)$$,
• parameter $$(a)$$,
• seed index $$(s)$$,

Define:

$$ \begin{cases} h = H(x,,y,,s),[6pt] x' = \dfrac{x + a + h}{2} \bmod p,[6pt] y' = \sqrt{x,y + h} ;\bmod p. \end{cases} $$

Thus,

$$ T\bigl((x,y),,s;,a,,p\bigr) ;=; \bigl(x',,y'\bigr). $$

---

4. Binary Exponentiation of $$(T)$$

To compute $$(T^k(P_0))$$ efficiently (exponentiation by squaring):

function pow_T(P, k):
   result ← P
   base   ← P
   s      ← 1
   while k > 0:
      if (k mod 2) == 1:
         result ← T(result, s)
      base ← T(base, s)
      k    ← k >> 1
      s    ← s + 1
   return result

---

Back to Home | Footer