src/zeromorph.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8f6d5984",
   "metadata": {},
   "outputs": [],
   "source": [
    "from group import DummyGroup\n",
    "from utils import log_2, pow_2\n",
    "from unipolynomial import UniPolynomial\n",
    "from mle2 import MLEPolynomial\n",
    "from kzg10 import Commitment, KZG10Commitment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ef41b6ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ProofTranscript:\n",
    "    def __init__(self, field):\n",
    "        self.field = field\n",
    "        self.state = 0  # Initial state\n",
    "    \n",
    "    def absorb(self, element):\n",
    "        \"\"\"\n",
    "        Absorb a field element into the transcript.\n",
    "        \n",
    "        Args:\n",
    "            element: A field element to be absorbed. \n",
    "        \"\"\"\n",
    "        if isinstance(element, int):\n",
    "            element = self.field(element)\n",
    "        elif isinstance(element, sage.rings.integer.Integer):\n",
    "            element = self.field(element)\n",
    "        elif isinstance(element, Commitment):\n",
    "            element = element.value\n",
    "        elif isinstance(element, list):\n",
    "            element = sum(element)\n",
    "        elif not element.parent() == self.field:\n",
    "            raise TypeError(\"Must absorb a field element\")\n",
    "        \n",
    "        # if not isinstance(element, self.field.Element):\n",
    "        #     raise TypeError(\"Must absorb a field element\")\n",
    "        \n",
    "        # Simple hash function: multiply by a prime and add the element\n",
    "        bs = str(element).encode('utf-8')\n",
    "        n = int.from_bytes(bs, 'big')\n",
    "        self.state = (self.state * int(31) + n) % self.field.order()\n",
    "    \n",
    "    def squeeze(self):\n",
    "        \"\"\"\n",
    "        Generate a random field element based on the current state.\n",
    "        \n",
    "        Returns:\n",
    "            A field element.\n",
    "        \"\"\"\n",
    "        # Use the current state to generate a \"random\" field element\n",
    "        self.state = (self.state * 31 + 17) % self.field.order()\n",
    "        return self.field(self.state)\n",
    "    \n",
    "    def clone(self):\n",
    "        new = ProofTranscript(self.field)\n",
    "        new.state = self.state\n",
    "        return new\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6af8b57e-4815-4f79-9d61-45800f04b328",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Finite Field of size 193, Finite Field in b of size 193^2)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F193.<a> = GF(193)\n",
    "R193.<X> = F193[]\n",
    "R193\n",
    "Fp=F193\n",
    "Fp2 = Fp.extension(2, 'b')\n",
    "Fp, Fp2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "07537939",
   "metadata": {},
   "outputs": [],
   "source": [
    "UniPolynomial.set_scalar(Fp(0), Fp)\n",
    "Commitment.set_scalar(Fp(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e61877fa-8efa-45de-aff8-328ec618cb91",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Multivariate Polynomial Ring in X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, A0, A1, A2, B0, B1, B2 over Finite Field of size 193"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R_2.<X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, A0, A1, A2, B0, B1, B2> = Fp[]; R_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4d32f85f-a043-4f6b-b072-096c798631be",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(125, True, True)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "omega = Fp.primitive_element()^3; omega, omega^64 == 1, omega^32 == -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "a8b0b738-1223-4f22-9fac-b3f2aebf94bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "H16 = [(omega^4)^i for i in range(16)]\n",
    "H8 = [(omega^8)^i for i in range(8)]\n",
    "H4 = [(omega^16)^i for i in range(4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2f14969b-635f-4e3c-87a9-7e38cbe59c6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "G1 = DummyGroup(Fp)\n",
    "G2 = DummyGroup(Fp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0dd5907a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "point= [3, 3]\n",
      "Number of quotients: 2\n",
      "q_0: num_var=0, evals=[6]\n",
      "q_1: num_var=1, evals=[1, 2]\n",
      "rem= 22\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mle = MLEPolynomial([1, 4, 2, 6], 2)\n",
    "point = [3, 3]  # Replace with actual Scalar values\n",
    "\n",
    "print(\"point=\", point)\n",
    "quo, rem = mle.decompose_by_div(point)\n",
    "\n",
    "print(f\"Number of quotients: {len(quo)}\")\n",
    "\n",
    "for i, q in enumerate(quo):\n",
    "    # q * MLEPolynomial.from_coeffs([-point[i], 1])\n",
    "    print(f\"q_{i}: num_var={q.num_var}, evals={q.evals}\")\n",
    "print(\"rem=\", rem)\n",
    "rem == mle.evaluate(point)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "caa602bb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X0*X1 + 3*X0 + X1 + 1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "6 * (X0-3) + (X0 + 1) * (X1-3) + 22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "7f1968a9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 1, 1]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MLEPolynomial.compute_coeffs_from_evals([1, 4, 2, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "a3a35f5e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q_1 = MLEPolynomial.compute_coeffs_from_evals([1, 2]); q_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "10922214",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6*X0*X1 + 4*X0 + 2*X1 + 1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Basis = [1, X0, X1, X0 * X1, X2, X0 * X2, X1 * X2, X0 * X1 * X2]\n",
    "def poly(coeffs):\n",
    "    return sum([coeff * basis for coeff, basis in zip(coeffs, Basis)])\n",
    "\n",
    "poly([1, 4, 2, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "797ac38a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X0*X1 + 3*X0 + X1 + 1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "6 * (X0-3) + (X0 + 1) * (X1-3) + 22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "0dae1548",
   "metadata": {},
   "outputs": [],
   "source": [
    "# def ntt_core(vs, twiddle):\n",
    "#     n = len(vs)\n",
    "#     k = log_2(n)\n",
    "#     half = 1\n",
    "#     for i in range(k):\n",
    "#         for j in range(0, n, 2*half):\n",
    "#             for l in range(j, j+half):\n",
    "#                 vs[l+half] = vs[l+half] + twiddle * vs[l]\n",
    "#         half <<= 1\n",
    "#     return vs\n",
    "\n",
    "# def compute_evals_from_coeffs(f_coeffs):\n",
    "#     \"\"\"\n",
    "#     Compute the evaluations of the polynomial from the coefficients.\n",
    "#         Time: O(n * log(n))\n",
    "#     \"\"\"\n",
    "#     return ntt_core(f_coeffs, 1)\n",
    "\n",
    "# def compute_coeffs_from_evals(f_evals):\n",
    "#     \"\"\"\n",
    "#     Compute the evaluations of the polynomial from the coefficients.\n",
    "#         Time: O(n * log(n))\n",
    "#     \"\"\"\n",
    "#     return ntt_core(f_evals, -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "155bc969",
   "metadata": {},
   "outputs": [],
   "source": [
    "def periodic_poly(dim, degree):\n",
    "    \"\"\"\n",
    "    Compute the periodic polynomial Phi(X^d)\n",
    "\n",
    "        Phi_k(X)   = 1 + X   + X^2  + X^3  + ... + X^(2^k-1)\n",
    "        Phi_k(X^d) = 1 + X^d + X^2d + X^3d + ... + X^(2^(k-1))d\n",
    "\n",
    "    Args:\n",
    "        dim: dimension of the space of size 2^k\n",
    "        degree: degree of X^d\n",
    "\n",
    "    Returns:\n",
    "        list: the coefficients of Phi(X^d)\n",
    "    \"\"\"\n",
    "    n = pow_2(dim)\n",
    "    coeffs = [0] * (n * degree)\n",
    "    for i in range(n):\n",
    "        coeffs[i * degree] = 1\n",
    "    return UniPolynomial(coeffs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "e4ad7a95",
   "metadata": {},
   "outputs": [],
   "source": [
    "kzg10 = KZG10Commitment(G1, G2, 24); "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "c99260f4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([1,\n",
       "  X0,\n",
       "  X0^2,\n",
       "  X0^3,\n",
       "  X0^4,\n",
       "  X0^5,\n",
       "  X0^6,\n",
       "  X0^7,\n",
       "  X0^8,\n",
       "  X0^9,\n",
       "  X0^10,\n",
       "  X0^11,\n",
       "  X0^12,\n",
       "  X0^13,\n",
       "  X0^14,\n",
       "  X0^15,\n",
       "  X0^16,\n",
       "  X0^17,\n",
       "  X0^18,\n",
       "  X0^19,\n",
       "  X0^20,\n",
       "  X0^21,\n",
       "  X0^22,\n",
       "  X0^23,\n",
       "  X0^24],\n",
       " [1,\n",
       "  X0,\n",
       "  X0^2,\n",
       "  X0^3,\n",
       "  X0^4,\n",
       "  X0^5,\n",
       "  X0^6,\n",
       "  X0^7,\n",
       "  X0^8,\n",
       "  X0^9,\n",
       "  X0^10,\n",
       "  X0^11,\n",
       "  X0^12,\n",
       "  X0^13,\n",
       "  X0^14,\n",
       "  X0^15,\n",
       "  X0^16,\n",
       "  X0^17,\n",
       "  X0^18,\n",
       "  X0^19,\n",
       "  X0^20,\n",
       "  X0^21,\n",
       "  X0^22,\n",
       "  X0^23,\n",
       "  X0^24])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kzg10.setup(secret_symbol=X0, g1_generator=1, g2_generator=1)\n",
    "kzg10.srs, kzg10.srs2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "c39c89f0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Commitment(6*X0^24 + 2*X0^23 + 4*X0^22 + X0^21), 21)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ff = [1, 4, 2, 6]\n",
    "ff_cm = kzg10.commit(ff)\n",
    "deg_arg = kzg10.prove_degree_bound(ff_cm, ff, 4)\n",
    "deg_arg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "911fce9e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kzg10.verify_degree_bound(ff_cm, deg_arg, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ae433018",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prove_zeromorph_naive(C, f, k, point, v, transcript, debug=0):  \n",
    "    \"\"\"\n",
    "\n",
    "        r(X) = ⟦f_mle⟧_n - v * 𝚽_n(z) - ∑_k(z^{2^k} * 𝚽_{n-k-1}(z^{2^{k+1}}) - uk * 𝚽_{n-k}(z^{2^k})) * ⟦q_k⟧_k\n",
    "             = f(X) - v * 𝚽_n(z) \n",
    "                - ∑_k (z^{2^k} * 𝚽_{n-k-1}(z^{2^{k+1}}) - uk * 𝚽_{n-k}(z^{2^k})) * q_k(X)\n",
    "    f: polynomial\n",
    "    k: number of variables\n",
    "    point: (u0, u1, ..., u_{k-1})\n",
    "    v: evaluation value\n",
    "    transcript: transcript\n",
    "    \"\"\"\n",
    "    n = len(f)\n",
    "    k = len(point)\n",
    "    evals = f.copy()\n",
    "    print(f\"P> f={f}, point={point}, v={v}\")\n",
    "\n",
    "    quotients, rem = MLEPolynomial(f, k).decompose_by_div(point)\n",
    "    print(f\"quotients={quotients}, rem={rem}\")\n",
    "    assert rem == v, \"Evaluation does not match\"\n",
    "    f_uni = UniPolynomial(f)\n",
    "\n",
    "    print(f\"P> ▶️▶️ C={C}\")\n",
    "    print(f\"P> ▶️▶️ point={point}\")\n",
    "    print(f\"P> ▶️▶️ v={v}\")\n",
    "    transcript.absorb(C)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    q_cm_vec = []\n",
    "    q_uni_vec = []\n",
    "    deg_arg_vec = []\n",
    "\n",
    "    for i in range(k):\n",
    "        qi = quotients[i]\n",
    "        qi_cm = kzg10.commit(qi.evals)\n",
    "        q_cm_vec.append(qi_cm)\n",
    "        q_uni_vec.append(UniPolynomial(qi.evals))\n",
    "        print(f\"P> ▶️▶️ q_cm={qi_cm}\")\n",
    "        transcript.absorb(qi_cm)\n",
    "    \n",
    "    print(f\"P> f_cm={C}, q_cm_vec={q_cm_vec}, q_uni_vec={q_uni_vec}\")\n",
    "\n",
    "    for i in range(k):\n",
    "        qi_deg_arg = kzg10.prove_degree_bound(q_cm_vec[i], q_uni_vec[i].coeffs, pow_2(i))\n",
    "        deg_arg_vec.append(qi_deg_arg)\n",
    "        print(f\"P> ▶️▶️ deg_arg={qi_deg_arg}\")\n",
    "        transcript.absorb(qi_deg_arg[0])\n",
    "        transcript.absorb(qi_deg_arg[1])\n",
    "\n",
    "    f_deg_arg = kzg10.prove_degree_bound(C, f_uni.coeffs, pow_2(k))\n",
    "    deg_arg_vec.append(f_deg_arg)\n",
    "    print(f\"P> ▶️▶️ deg_arg={f_deg_arg}\")\n",
    "    transcript.absorb(f_deg_arg[0])\n",
    "    transcript.absorb(f_deg_arg[1])\n",
    "\n",
    "    zeta = transcript.squeeze()\n",
    "    if debug > 0:\n",
    "        print(f\"P> zeta={zeta}\")\n",
    "\n",
    "    # compute r(X) = f(X) - v * phi_n(zeta) - ∑_i (c_i * qi(X))\n",
    "    phi_uni_at_zeta = periodic_poly(k, 1).evaluate(zeta)\n",
    "    if debug > 1:\n",
    "        print(f\"P> f_uni={f_uni}, v={v}, phi_uni_at_zeta={phi_uni_at_zeta}\")\n",
    "\n",
    "    r_uni = f_uni - UniPolynomial([phi_uni_at_zeta * v])\n",
    "    for i in range(k):\n",
    "        c_i = zeta^(pow_2(i)) * periodic_poly(k-i-1, pow_2(i+1)).evaluate(zeta) \\\n",
    "                   - point[i] * periodic_poly(k-i, pow_2(i)).evaluate(zeta)\n",
    "        r_uni -= Fp(c_i) * q_uni_vec[i]\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"P> r_uni=\", r_uni)\n",
    "    if debug > 0:\n",
    "        assert r_uni.evaluate(zeta) == 0, f\"Evaluation does not match, {r_uni.evaluate(zeta)}!=0\"\n",
    "        print(f\"P> 👀 r(zeta={zeta}) == 0 ✅\")\n",
    "    \n",
    "    r_at_0_arg = kzg10.prove_eval(r_uni.coeffs, zeta, 0)\n",
    "\n",
    "    if debug > 1:\n",
    "        v_cm = kzg10.commit(UniPolynomial([phi_uni_at_zeta * v]).coeffs)\n",
    "        r_cm = C - v_cm \n",
    "        print(\"P> C - v_cm=\", r_cm)\n",
    "        for i in range(k):\n",
    "            c_i = zeta^(pow_2(i)) * periodic_poly(k-i-1, pow_2(i+1)).evaluate(zeta) \\\n",
    "                       - point[i] * periodic_poly(k-i, pow_2(i)).evaluate(zeta)\n",
    "            r_cm = r_cm - q_cm_vec[i] * c_i\n",
    "\n",
    "        print(f\"P> r_cm={r_cm}, r({zeta})={r_uni.evaluate(zeta)}\")\n",
    "        checked = kzg10.verify_eval(r_cm, r_at_0_arg, zeta, 0)\n",
    "        print(\"P> r_at_0_arg=\", r_at_0_arg)\n",
    "        print(\"P> 👀  r(zeta) == 0 ✅\" if checked else \"👀  r(zeta) == 0 ❌\")\n",
    "\n",
    "    return (q_cm_vec, deg_arg_vec, r_at_0_arg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "f9ed88fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verify_zeromorph_naive(f_cm, num_var, point, v, prf, transcript):\n",
    "    \"\"\"\n",
    "    Verify an evaluation proof(argument) of the MLE polynomial in Zeromorph+KZG10.\n",
    "\n",
    "    Args:\n",
    "        f_cm: commitment to the MLE polynomial\n",
    "        num_var: number of variables\n",
    "        point: (u0, u1, ..., u_{k-1})\n",
    "        v: evaluation value\n",
    "        prf: proof\n",
    "    \n",
    "    Returns:\n",
    "        bool: True if the proof is valid, False otherwise.\n",
    "    \"\"\"\n",
    "    n = pow_2(num_var)\n",
    "    k = len(point)\n",
    "    assert k == num_var, \"Number of variables must match the point\"\n",
    "\n",
    "    print(f\"V> ▶️▶️ f_cm={f_cm}\")\n",
    "    print(f\"V> ▶️▶️ point={point}\")\n",
    "    print(f\"V> ▶️▶️ v={v}\")\n",
    "    transcript.absorb(f_cm)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "    \n",
    "    # decompose the proof\n",
    "    q_cm_vec, deg_arg_vec, r_at_0_arg = prf\n",
    "    \n",
    "    for q in q_cm_vec:\n",
    "        print(f\"V> ▶️▶️ q_cm={q}\")\n",
    "        transcript.absorb(q)\n",
    "\n",
    "    q_cm_vec.append(f_cm)\n",
    "    for i in range(k+1):\n",
    "        # TODO: add support for degree_bound proofs\n",
    "        p = deg_arg_vec[i]\n",
    "        assert kzg10.verify_degree_bound(q_cm_vec[i], p, pow_2(i))\n",
    "        print(f\"V> ▶️▶️ deg_arg={p}\")\n",
    "        transcript.absorb(p[0])\n",
    "        transcript.absorb(p[1])\n",
    "\n",
    "    zeta = transcript.squeeze()\n",
    "    print(f\"V> zeta={zeta}\")\n",
    "    \n",
    "    phi_uni_at_zeta = periodic_poly(k, 1).evaluate(zeta)\n",
    "    v_cm = kzg10.commit(UniPolynomial([phi_uni_at_zeta * v]).coeffs)\n",
    "    r_cm = f_cm - v_cm \n",
    "    for i in range(k):\n",
    "        c_i = zeta^(pow_2(i)) * periodic_poly(k-i-1, pow_2(i+1)).evaluate(zeta) \\\n",
    "                   - point[i] * periodic_poly(k-i, pow_2(i)).evaluate(zeta)\n",
    "        r_cm = r_cm - q_cm_vec[i] * c_i\n",
    "    print(f\"V> r_cm={r_cm}\")\n",
    "    checked = kzg10.verify_eval(r_cm, r_at_0_arg, zeta, 0)\n",
    "    print(\"V> r_at_0_arg=\", r_at_0_arg)\n",
    "    print(\"V> 👀  r(zeta) == 0 ✅\" if checked else \"👀  r(zeta) == 0 ❌\")\n",
    "\n",
    "    return checked"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "fefc23fd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P> f=[1, 4], point=[3], v=10\n",
      "quotients=[MLEPolynomial([3], 0)], rem=10\n",
      "P> ▶️▶️ C=Commitment(4*X0 + 1)\n",
      "P> ▶️▶️ point=[3]\n",
      "P> ▶️▶️ v=10\n",
      "P> ▶️▶️ q_cm=Commitment(3)\n",
      "P> f_cm=Commitment(4*X0 + 1), q_cm_vec=[Commitment(3)], q_uni_vec=[3]\n",
      "P> ▶️▶️ deg_arg=(Commitment(3*X0^24), 24)\n",
      "P> ▶️▶️ deg_arg=(Commitment(4*X0^24 + X0^23), 23)\n",
      "P> zeta=47\n",
      "P> f_uni=1 + 4x, v=10, phi_uni_at_zeta=48\n",
      "P> r_uni= 5 + 4x\n",
      "P> 👀 r(zeta=47) == 0 ✅\n",
      "P> C - v_cm= Commitment(4*X0 - 93)\n",
      "P> r_cm=Commitment(4*X0 + 5), r(47)=0\n",
      "P> r_at_0_arg= Commitment(4)\n",
      "P> 👀  r(zeta) == 0 ✅\n",
      "V> ▶️▶️ f_cm=Commitment(4*X0 + 1)\n",
      "V> ▶️▶️ point=[3]\n",
      "V> ▶️▶️ v=10\n",
      "V> ▶️▶️ q_cm=Commitment(3)\n",
      "V> ▶️▶️ deg_arg=(Commitment(3*X0^24), 24)\n",
      "V> ▶️▶️ deg_arg=(Commitment(4*X0^24 + X0^23), 23)\n",
      "V> zeta=47\n",
      "V> r_cm=Commitment(4*X0 + 5)\n",
      "V> r_at_0_arg= Commitment(4)\n",
      "V> 👀  r(zeta) == 0 ✅\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transcript = ProofTranscript(Fp)\n",
    "\n",
    "f_uni = UniPolynomial([1, 4])\n",
    "f_cm = kzg10.commit(f_uni.coeffs)\n",
    "\n",
    "prf = prove_zeromorph_naive(f_cm, [1, 4], 1, [3], 10, transcript.clone(), debug=2)\n",
    "verify_zeromorph_naive(f_cm, 1, [3], 10, prf, transcript.clone())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "d30c6e2a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isinstance(Fp(3), (type(Fp(2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "039eec79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P> f=[1, 4, 2, 6], point=[3, 3], v=22\n",
      "quotients=[MLEPolynomial([6], 0), MLEPolynomial([1, 2], 1)], rem=22\n",
      "P> ▶️▶️ C=Commitment(6*X0^3 + 2*X0^2 + 4*X0 + 1)\n",
      "P> ▶️▶️ point=[3, 3]\n",
      "P> ▶️▶️ v=22\n",
      "P> ▶️▶️ q_cm=Commitment(6)\n",
      "P> ▶️▶️ q_cm=Commitment(2*X0 + 1)\n",
      "P> f_cm=Commitment(6*X0^3 + 2*X0^2 + 4*X0 + 1), q_cm_vec=[Commitment(6), Commitment(2*X0 + 1)], q_uni_vec=[6, 1 + 2x]\n",
      "P> ▶️▶️ deg_arg=(Commitment(6*X0^24), 24)\n",
      "P> ▶️▶️ deg_arg=(Commitment(2*X0^24 + X0^23), 23)\n",
      "P> ▶️▶️ deg_arg=(Commitment(6*X0^24 + 2*X0^23 + 4*X0^22 + X0^21), 21)\n",
      "P> zeta=70\n",
      "P> f_uni=1 + 4x + 2x^2 + 6x^3, v=22, phi_uni_at_zeta=185\n",
      "P> r_uni= 111 + 117x + 2x^2 + 6x^3\n",
      "P> 👀 r(zeta=70) == 0 ✅\n",
      "P> C - v_cm= Commitment(6*X0^3 + 2*X0^2 + 4*X0 - 16)\n",
      "P> r_cm=Commitment(6*X0^3 + 2*X0^2 - 76*X0 - 82), r(70)=0\n",
      "P> r_at_0_arg= Commitment(6*X0^2 + 36*X0 - 65)\n",
      "P> 👀  r(zeta) == 0 ✅\n",
      "V> ▶️▶️ f_cm=Commitment(6*X0^3 + 2*X0^2 + 4*X0 + 1)\n",
      "V> ▶️▶️ point=[3, 3]\n",
      "V> ▶️▶️ v=22\n",
      "V> ▶️▶️ q_cm=Commitment(6)\n",
      "V> ▶️▶️ q_cm=Commitment(2*X0 + 1)\n",
      "V> ▶️▶️ deg_arg=(Commitment(6*X0^24), 24)\n",
      "V> ▶️▶️ deg_arg=(Commitment(2*X0^24 + X0^23), 23)\n",
      "V> ▶️▶️ deg_arg=(Commitment(6*X0^24 + 2*X0^23 + 4*X0^22 + X0^21), 21)\n",
      "V> zeta=70\n",
      "V> r_cm=Commitment(6*X0^3 + 2*X0^2 - 76*X0 - 82)\n",
      "V> r_at_0_arg= Commitment(6*X0^2 + 36*X0 - 65)\n",
      "V> 👀  r(zeta) == 0 ✅\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transcript = ProofTranscript(Fp)\n",
    "\n",
    "f_uni = UniPolynomial([1, 4, 2, 6])\n",
    "f_cm = kzg10.commit(f_uni.coeffs)\n",
    "\n",
    "prf = prove_zeromorph_naive(f_cm, [1, 4, 2, 6], 2, [3, 3], 22, transcript.clone(), debug=2)\n",
    "verify_zeromorph_naive(f_cm, 2, [3, 3], 22, prf, transcript.clone())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "f3be10cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prove_zeromorph_opt(f_cm, f, k, point, v, transcript, debug=0):  \n",
    "    \"\"\"\n",
    "    Optimized version of prove_zeromorph_naive\n",
    "\n",
    "        - Degree bound arguments are aggregated and merged into the evaluation proof\n",
    "\n",
    "        r(X) = ⟦f_mle⟧_n - v * 𝚽_n(z) - ∑_k(z^{2^k} * 𝚽_{n-k-1}(z^{2^{k+1}}) - uk * 𝚽_{n-k}(z^{2^k})) * ⟦q_k⟧_k\n",
    "             = f(X) - v * 𝚽_n(z) \n",
    "                - ∑_k (z^{2^k} * 𝚽_{n-k-1}(z^{2^{k+1}}) - uk * 𝚽_{n-k}(z^{2^k})) * q_k(X)\n",
    "\n",
    "    f: polynomial\n",
    "    k: number of variables\n",
    "    point: (u0, u1, ..., u_{k-1})\n",
    "    v: evaluation value\n",
    "    transcript: transcript\n",
    "    \"\"\"\n",
    "    n = len(f)\n",
    "    k = len(point)\n",
    "    evals = f.copy()\n",
    "    print(f\"P> f={f}, point={point}, v={v}\")\n",
    "\n",
    "    # Round 1.\n",
    "\n",
    "    quotients, rem = MLEPolynomial(f, k).decompose_by_div(point)\n",
    "    print(f\"quotients={quotients}, rem={rem}\")\n",
    "    assert rem == v, \"Evaluation does not match\"\n",
    "    f_uni = UniPolynomial(f)\n",
    "\n",
    "    print(f\"P> ▶️▶️ f_cm={f_cm}\")\n",
    "    print(f\"P> ▶️▶️ point={point}\")\n",
    "    print(f\"P> ▶️▶️ v={v}\")\n",
    "    transcript.absorb(f_cm)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    q_cm_vec = []\n",
    "    q_uni_vec = []\n",
    "    deg_arg_vec = []\n",
    "\n",
    "    for i in range(k):\n",
    "        qi = quotients[i]\n",
    "        qi_cm = kzg10.commit(qi.evals)\n",
    "        q_cm_vec.append(qi_cm)\n",
    "        q_uni_vec.append(UniPolynomial(qi.evals))\n",
    "        print(f\"P> ▶️▶️ q_cm={qi_cm}\")\n",
    "        transcript.absorb(qi_cm)\n",
    "    \n",
    "    print(f\"P> f_cm={f_cm}, q_cm_vec={q_cm_vec}, q_uni_vec={q_uni_vec}\")\n",
    "\n",
    "    # Round 2.\n",
    "\n",
    "    beta = transcript.squeeze()\n",
    "    print(f\"P> ◀️◀️ beta={beta}\")\n",
    "\n",
    "    q_hat_uni = UniPolynomial([0])\n",
    "    coeffs = [0] * n\n",
    "    coeffs.append(1)\n",
    "    beta_power = 1\n",
    "    for i in range(k):\n",
    "        print(f\"P> coeffs={coeffs}, coeffs[pow_2(i)]={coeffs[pow_2(i)]}\")\n",
    "        x_deg_2_to_i_uni = UniPolynomial(coeffs[pow_2(i):])\n",
    "        print(f\"P> x_deg_2_to_i_uni[{i}]={x_deg_2_to_i_uni}\")\n",
    "        q_hat_uni += x_deg_2_to_i_uni * q_uni_vec[i] * Fp(beta_power)\n",
    "        beta_power *= beta\n",
    "    print(f\"P> q_hat_uni={q_hat_uni}\")\n",
    "    \n",
    "    q_hat_cm = kzg10.commit(q_hat_uni.coeffs)\n",
    "    print(f\"P> ▶️▶️ q_hat_cm={q_hat_cm}\")\n",
    "    transcript.absorb(q_hat_cm)\n",
    "\n",
    "    # Round 3.\n",
    "\n",
    "    zeta = transcript.squeeze()\n",
    "    print(f\"P> ◀️◀️ zeta={zeta}\")\n",
    "\n",
    "    # compute r(X) = f(X) - v * phi_n(zeta) - ∑_i (c_i * qi(X))\n",
    "    #\n",
    "    #   r_ζ(X) = f(X) - v * 𝚽_k(ζ) \n",
    "    #            - ∑_i ( ζ^{2^i} * 𝚽_{k-i-1}(ζ^{2^{i+1}}) - u_i * 𝚽_{k-i}(ζ^{2^i}) ) * q_i(X)\n",
    "    #          = f(X) - v_𝚽 - ∑_i c_i * q_i(X)\n",
    "    \n",
    "    phi_uni_at_zeta = periodic_poly(k, 1).evaluate(zeta)\n",
    "    if debug > 1:\n",
    "        print(f\"P> f_uni={f_uni}, v={v}, phi_uni_at_zeta={phi_uni_at_zeta}\")\n",
    "\n",
    "    r_uni = f_uni - UniPolynomial([phi_uni_at_zeta * v])\n",
    "    for i in range(k):\n",
    "        c_i = zeta^(pow_2(i)) * periodic_poly(k-i-1, pow_2(i+1)).evaluate(zeta) \\\n",
    "                   - point[i] * periodic_poly(k-i, pow_2(i)).evaluate(zeta)\n",
    "        r_uni -= c_i * q_uni_vec[i]\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"P> r_uni=\", r_uni)\n",
    "    if debug > 0:\n",
    "        assert r_uni.evaluate(zeta) == 0, f\"Evaluation does not match, {r_uni.evaluate(zeta)}!=0\"\n",
    "        print(f\"P> 👀 r(zeta={zeta}) == 0 ✅\")\n",
    "\n",
    "    # compute h(X) = q_hat(X) - ∑_i ( beta^{i} * X^{2^k - 2^i} * q_i(X) ) \n",
    "    #\n",
    "    #    h_ζ(X) = q_hat(X) - ∑_i ( beta^{i} * ζ^{2^k - 2^i} * q_i(X) )\n",
    "\n",
    "    h_uni = q_hat_uni\n",
    "    for i in range(k):\n",
    "        e_i = (beta**i) * (zeta**(pow_2(k) - pow_2(i)))\n",
    "        h_uni -= e_i * q_uni_vec[i]\n",
    "\n",
    "    if debug > 1:\n",
    "        print(f\"P> h_uni={h_uni}\")\n",
    "    if debug > 0:\n",
    "        assert h_uni.evaluate(zeta) == 0, f\"Evaluation does not match, {h_uni.evaluate(zeta)}!=0\"\n",
    "        print(f\"P> 👀 h(zeta={zeta}) == 0 ✅\")\n",
    "    \n",
    "    alpha = transcript.squeeze()\n",
    "    print(f\"P> ◀️◀️ alpha={alpha}\")\n",
    "\n",
    "    a_uni = h_uni + r_uni * alpha\n",
    "\n",
    "    if debug > 0:\n",
    "        assert a_uni.evaluate(zeta) == 0, f\"Evaluation does not match, {a_uni.evaluate(zeta)}!=0\"\n",
    "        print(f\"P> 👀 a(zeta={zeta}) == 0 ✅\")\n",
    "\n",
    "    a_uni_cm = kzg10.commit(a_uni.coeffs)\n",
    "\n",
    "    arg = kzg10.prove_eval_and_degree(a_uni_cm, a_uni.coeffs, zeta, 0, kzg10.max_degree - pow_2(k))\n",
    "\n",
    "    # r_at_0_arg = kzg10.prove_eval(r_uni.coeffs, zeta, 0)\n",
    "\n",
    "    # if debug > 1:\n",
    "    #     v_cm = kzg10.commit(UniPolynomial([phi_uni_at_zeta * v]).coeffs)\n",
    "    #     r_cm = C - v_cm \n",
    "    #     print(\"P> C - v_cm=\", r_cm)\n",
    "    #     for i in range(k):\n",
    "    #         c_i = zeta^(pow_2(i)) * periodic_poly(k-i-1, pow_2(i+1)).evaluate(zeta) \\\n",
    "    #                    - point[i] * periodic_poly(k-i, pow_2(i)).evaluate(zeta)\n",
    "    #         r_cm = r_cm - q_cm_vec[i] * c_i\n",
    "\n",
    "    #     print(f\"P> r_cm={r_cm}, r({zeta})={r_uni.evaluate(zeta)}\")\n",
    "    #     checked = kzg10.verify_eval(r_cm, r_at_0_arg, zeta, 0)\n",
    "    #     print(\"P> r_at_0_arg=\", r_at_0_arg)\n",
    "    #     print(\"P> 👀  r(zeta) == 0 ✅\" if checked else \"👀  r(zeta) == 0 ❌\")\n",
    "\n",
    "    return (q_cm_vec, q_hat_cm, a_uni_cm, arg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "11be86a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verify_zeromorph_opt(f_cm, prf, k, point, v, transcript, debug=0):\n",
    "    \"\"\"\n",
    "    Optimized version of verify_zeromorph\n",
    "\n",
    "        - Degree bound arguments are aggregated and merged into the evaluation proof\n",
    "    \"\"\"\n",
    "    k = len(point)\n",
    "    n = pow_2(k)\n",
    "\n",
    "    # Round 1.\n",
    "\n",
    "    print(f\"V> ⏬ f_cm={f_cm}\")\n",
    "    print(f\"V> ⏬ point={point}\")\n",
    "    print(f\"V> ⏬ v={v}\")\n",
    "    transcript.absorb(f_cm)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    q_cm_vec, q_hat_cm, a_uni_cm, eval_deg_arg = prf\n",
    "\n",
    "    for i in range(k):\n",
    "        qi_cm = q_cm_vec[i]\n",
    "        print(f\"V> ▶️▶️ q_cm={qi_cm}\")\n",
    "        transcript.absorb(qi_cm)\n",
    "\n",
    "    # Round 2.\n",
    "\n",
    "    beta = transcript.squeeze()\n",
    "    print(f\"V> ◀️◀️ beta={beta}\")\n",
    "\n",
    "    print(f\"V> ▶️▶️ q_hat_cm={q_hat_cm}\")\n",
    "    transcript.absorb(q_hat_cm)\n",
    "\n",
    "    # Round 3.\n",
    "\n",
    "    zeta = transcript.squeeze()\n",
    "    print(f\"V> ◀️◀️ zeta={zeta}\")\n",
    "\n",
    "    # compute r(X) = f(X) - v * phi_n(zeta) - ∑_i (c_i * qi(X))\n",
    "    #\n",
    "    #   r_ζ(X) = f(X) - v * 𝚽_k(ζ) \n",
    "    #            - ∑_i ( ζ^{2^i} * 𝚽_{k-i-1}(ζ^{2^{i+1}}) - u_i * 𝚽_{k-i}(ζ^{2^i}) ) * q_i(X)\n",
    "    #          = f(X) - v_𝚽 - ∑_i c_i * q_i(X)\n",
    "    \n",
    "    phi_uni_at_zeta_mul_v = periodic_poly(k, 1).evaluate(zeta) * v\n",
    "    if debug > 1:\n",
    "        print(f\"V> phi_uni_at_zeta_mul_v={phi_uni_at_zeta_mul_v}\")\n",
    "\n",
    "    r_cm = f_cm - kzg10.commit([phi_uni_at_zeta_mul_v])\n",
    "    for i in range(k):\n",
    "        c_i = zeta^(pow_2(i)) * periodic_poly(k-i-1, pow_2(i+1)).evaluate(zeta) \\\n",
    "                   - point[i] * periodic_poly(k-i, pow_2(i)).evaluate(zeta)\n",
    "        r_cm -= c_i * q_cm_vec[i]\n",
    "\n",
    "    # if debug > 1:\n",
    "    #     print(\"P> r_uni=\", r_uni)\n",
    "    # if debug > 0:\n",
    "    #     assert r_uni.evaluate(zeta) == 0, f\"Evaluation does not match, {r_uni.evaluate(zeta)}!=0\"\n",
    "    #     print(f\"P> 👀 r(zeta={zeta}) == 0 ✅\")\n",
    "\n",
    "    # compute h(X) = q_hat(X) - ∑_i ( beta^{i} * X^{2^k - 2^i} * q_i(X) ) \n",
    "    #\n",
    "    #    h_ζ(X) = q_hat(X) - ∑_i ( beta^{i} * ζ^{2^k - 2^i} * q_i(X) )\n",
    "\n",
    "    h_cm = q_hat_cm\n",
    "    for i in range(k):\n",
    "        e_i = (beta**i) * (zeta**(pow_2(k) - pow_2(i)))\n",
    "        h_cm -= e_i * q_cm_vec[i]\n",
    "\n",
    "    if debug > 1:\n",
    "        print(f\"V> h_cm={h_cm}\")\n",
    "    # if debug > 0:\n",
    "    #     assert h_uni.evaluate(zeta) == 0, f\"Evaluation does not match, {h_uni.evaluate(zeta)}!=0\"\n",
    "    #     print(f\"V> 👀 h(zeta={zeta}) == 0 ✅\")\n",
    "    \n",
    "    alpha = transcript.squeeze()\n",
    "    print(f\"V> ◀️◀️ alpha={alpha}\")\n",
    "\n",
    "    a_cm = h_cm + r_cm * alpha\n",
    "\n",
    "    # if debug > 0:\n",
    "    #     assert a_uni.evaluate(zeta) == 0, f\"Evaluation does not match, {a_uni.evaluate(zeta)}!=0\"\n",
    "    #     print(f\"V> 👀 a(zeta={zeta}) == 0 ✅\")\n",
    "\n",
    "    checked = kzg10.verify_eval_and_degree(a_cm, eval_deg_arg, zeta, 0, kzg10.max_degree - pow_2(k))\n",
    "    print(\"V> 👀  a(zeta) == 0 ✅\" if checked else \"👀  a(zeta) == 0 ❌\")\n",
    "    \n",
    "    return checked\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "4a62c4c4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P> f=[1, 4, 2, 6], point=[3, 3], v=22\n",
      "quotients=[MLEPolynomial([6], 0), MLEPolynomial([1, 2], 1)], rem=22\n",
      "P> ▶️▶️ C=Commitment(6*X0^3 + 2*X0^2 + 4*X0 + 1)\n",
      "P> ▶️▶️ point=[3, 3]\n",
      "P> ▶️▶️ v=22\n",
      "P> ▶️▶️ q_cm=Commitment(6)\n",
      "P> ▶️▶️ q_cm=Commitment(2*X0 + 1)\n",
      "P> f_cm=Commitment(6*X0^3 + 2*X0^2 + 4*X0 + 1), q_cm_vec=[Commitment(6), Commitment(2*X0 + 1)], q_uni_vec=[6, 1 + 2x]\n",
      "P> ◀️◀️ beta=51\n",
      "P> coeffs=[0, 0, 0, 0, 1], coeffs[pow_2(i)]=0\n",
      "P> x_deg_2_to_i_uni[0]=x^3\n",
      "P> coeffs=[0, 0, 0, 0, 1], coeffs[pow_2(i)]=0\n",
      "P> x_deg_2_to_i_uni[1]=x^2\n",
      "P> q_hat_uni=51x^2 + 108x^3\n",
      "P> ▶️▶️ q_hat_cm=Commitment(-85*X0^3 + 51*X0^2)\n",
      "P> ◀️◀️ zeta=36\n",
      "P> f_uni=1 + 4x + 2x^2 + 6x^3, v=22, phi_uni_at_zeta=125\n",
      "P> r_uni= 57 + 176x + 2x^2 + 6x^3\n",
      "P> 👀 r(zeta=36) == 0 ✅\n",
      "P> h_uni= 17 + 13x + 51x^2 + 108x^3\n",
      "P> 👀 h(zeta=36) == 0 ✅\n",
      "P> ◀️◀️ alpha=168\n",
      "P> 👀 a(zeta=36) == 0 ✅\n",
      "V> ⏬ f_cm=Commitment(6*X0^3 + 2*X0^2 + 4*X0 + 1)\n",
      "V> ⏬ point=[3, 3]\n",
      "V> ⏬ v=22\n",
      "V> ▶️▶️ q_cm=Commitment(6)\n",
      "V> ▶️▶️ q_cm=Commitment(2*X0 + 1)\n",
      "V> ◀️◀️ beta=51\n",
      "V> ▶️▶️ q_hat_cm=Commitment(-85*X0^3 + 51*X0^2)\n",
      "V> ◀️◀️ zeta=36\n",
      "V> phi_uni_at_zeta_mul_v=48\n",
      "V> h_cm=Commitment(-85*X0^3 + 51*X0^2 + 13*X0 + 17)\n",
      "V> ◀️◀️ alpha=168\n",
      "V> 👀  a(zeta) == 0 ✅\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transcript = ProofTranscript(Fp)\n",
    "\n",
    "f_uni = UniPolynomial([1, 4, 2, 6])\n",
    "f_cm = kzg10.commit(f_uni.coeffs)\n",
    "\n",
    "prf = prove_zeromorph_opt(f_cm, [1, 4, 2, 6], 2, [3, 3], 22, transcript.clone(), debug=2)\n",
    "verify_zeromorph_opt(f_cm, prf, 2, [3, 3], 22, transcript.clone(), debug=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "360c0bf4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kzg10.h * Fp(3) * Fp(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9fccbffd",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.4",
   "language": "sage",
   "name": "sagemath-10.4"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}