A demonstration of Lemma 1.1

Frobenius.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "q = 3\n",
    "K = GF(q)\n",
    "l = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R.<x> = K[]\n",
    "P1 = R.irreducible_element(l-1)\n",
    "P1.is_primitive()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "P2 = P1(x^l)\n",
    "P3 = P2(x^l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 20, 100)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d1, d2, d3 = map(lambda P: P.degree(), [P1, P2, P3])\n",
    "d1, d2, d3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sigma = q^d2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Precomputation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(139471376, 1)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u, r = divmod(sigma, l^2)\n",
    "u,r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2*x^2 + x + 2, x)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = (pow(x, u, P1), x^r)\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a = R.random_element(99)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(x^3 + 2*x^2 + 2*x, x^99)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "monomials = [(m*pow(y[0],i,P1), y[1]^i) for (i,m) in enumerate(a)]\n",
    "monomials[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "174"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res = sum(m(x^(l^2)) * X for (m, X) in monomials)\n",
    "res.degree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, True)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expected = pow(a, sigma, P3)\n",
    "res == expected, (res % P3) == expected"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.1.beta2",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}

Q1.<xx>=R.quo(P1)
R1.<z>=PolynomialRing(Q1)
Q2.<zz>=R1.quo(z^(l^2)-xx)
xx = Q2(R1(xx))

def to_Q2(aa):
    return add([aa[i]*xx^(i//25)*zz^(i%25) for i in range(100)])

def from_Q1(b):
    return b.lift()(x^25)

def from_Q2(bb):
    return add([from_Q1(bb[i])*x^i for i in range(25)])

A = to_Q2(a)
check = from_Q2(A^sigma)
check == expected

YY = xx^u*zz^r
YY == zz^sigma

monomials = [Q2(1)]
for i in range(25):
    monomials.append(monomials[i]*YY)
## here, we should be a bit careful; these guys can all be computed in O(25) ops in F1.

res = add([monomials[i] * Q2(R1(A[i])) for i in range(25)])
## same, this sum takes O(25) ops in F1.

from_Q2(res) == expected