crypto/Galois_Degree_Two.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "62ab24b9",
   "metadata": {},
   "source": [
    "### Galois Fields of Degree 2\n",
    "\n",
    "Burton Rosenberg\n",
    "\n",
    "November 5, 2021\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "fdac90eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class QuadInt:\n",
    "    \n",
    "    def __init__(self,p,d):\n",
    "        assert d%p!=0\n",
    "        assert not self.qr(d,p)\n",
    "\n",
    "        # p should be a prime but we only hope so\n",
    "        assert p>2\n",
    "\n",
    "        self.p = p\n",
    "        self.d = d%p\n",
    "\n",
    "    def qr(self,a,p):\n",
    "        \"\"\"\n",
    "        check if a is quadradic residue mod p\n",
    "        \"\"\"\n",
    "        return a**((p-1)//2)%p==1\n",
    "        \n",
    "    def get_mod(self):\n",
    "        return self.p\n",
    "    \n",
    "    def get_des(self):\n",
    "        return self.d\n",
    "\n",
    "    def canonical(self,a):\n",
    "        return (a[0]%self.p,a[1]%self.p)\n",
    "\n",
    "    def zero(self):\n",
    "        return (0,0)\n",
    "    \n",
    "    def one(self):\n",
    "        return (1,0)\n",
    "\n",
    "    def zero_p(self,a):\n",
    "        return self.canonical(a)==self.zero()\n",
    "    \n",
    "    def one_p(self,a):\n",
    "        return self.canonical(a)==self.one()\n",
    "    \n",
    "    def equal_p(self,a,b):\n",
    "        return self.canonical(a)==self.canonical(b)\n",
    "\n",
    "    def conj(self,a):\n",
    "        return (a[0],-a[1]%self.p)\n",
    "\n",
    "    def minus(self,a):\n",
    "        return (-a[0]%self.p,-a[1]%self.p)\n",
    "\n",
    "    def add(self,a,b):\n",
    "        c = (a[0]+b[0]) %self.p\n",
    "        d = (a[1]+b[1]) %self.p\n",
    "        return (c,d)\n",
    "    \n",
    "    def mult(self,a,b):\n",
    "        c = (a[0]*b[0]+self.d*a[1]*b[1]) %self.p\n",
    "        d = (a[0]*b[1]+a[1]*b[0]) %self.p\n",
    "        return (c,d)\n",
    "    \n",
    "    def exp(self,a,n):\n",
    "        if n==0:\n",
    "            return (1,0)\n",
    "        if n==1:\n",
    "            return a\n",
    "        if n%2==0:\n",
    "            c = self.exp(a,n//2)\n",
    "            return self.mult(c,c)\n",
    "        c = self.exp(a,n-1)\n",
    "        return self.mult(a,c)\n",
    " \n",
    "    def extended_gcd(self,a,b):\n",
    "        \"\"\"\n",
    "        extended GCD algorithm. recursive. returns (d,s,t) \n",
    "        where d = s*a+t*b and d = gcd(a,b)\n",
    "        \"\"\"\n",
    "        assert(\n",
    "            a>=0 and b>=0 )\n",
    "        if b==0:\n",
    "            return (a,1,0)\n",
    "        (q,r) = divmod(a,b)\n",
    "        (d,s,t) = self.extended_gcd(b,r)\n",
    "        # gcd(a, b) == gcd(b, r) == s*b + t*r == s*b + t*(a - q*b)\n",
    "        return (d,t,s-q*t)\n",
    "\n",
    "    def invert_base(self,c):\n",
    "        assert c[1]==0\n",
    "        a = c[0]\n",
    "        (d,t,s) = self.extended_gcd(a,self.p)\n",
    "        assert 1==d\n",
    "        return (t%self.p,0)\n",
    "    \n",
    "    def invert(self,a):\n",
    "        if self.zero_p(a):\n",
    "            return (0,0)\n",
    "\n",
    "        c = (a[0],-a[1])\n",
    "        d = self.mult(a,c)\n",
    "        d_inv = self.invert_base(d)\n",
    "        return self.mult(c,d_inv)\n",
    "    \n",
    "    def orbit_length(self,g):\n",
    "        if self.zero_p(g):\n",
    "            return 0\n",
    "        gg = g\n",
    "        i  = 1\n",
    "        while not self.one_p(gg):\n",
    "            gg = self.mult(gg,g)\n",
    "            i += 1\n",
    "        return i\n",
    "\n",
    "    def gen_p(self,g):\n",
    "        pp = self.p*self.p-1\n",
    "        return self.orbit_length(g)==pp\n",
    "\n",
    "    def next(self,a):\n",
    "        if a[1]==(self.p-1):\n",
    "            return ((a[0]+1)%self.p,0)\n",
    "        return (a[0],(a[1]+1)%self.p)\n",
    "        \n",
    "    def str(self,c):\n",
    "        return f'{c[0]} + {c[1]}\\u221A{self.d}'\n",
    "    \n",
    "    def __str__(self):\n",
    "        return f'Z/{self.p}Z[\\u221A{self.d}]'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "873cce25",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "field is: Z/11Z[√7]\n",
      "*** passed test_inv\n",
      "*** passesd test_fermat\n",
      "*** passesd test_squares\n"
     ]
    }
   ],
   "source": [
    "qi = QuadInt(11,7)\n",
    "print(f'field is: {qi}')\n",
    "\n",
    "def test_inv(qi):\n",
    "    p = qi.get_mod()\n",
    "    a = (0,1)\n",
    "    while not qi.zero_p(a):\n",
    "        b = qi.invert(a)\n",
    "        c = qi.mult(a,b)\n",
    "        assert qi.one_p(c), f'{a}'\n",
    "        a = qi.next(a)\n",
    "    return True\n",
    "\n",
    "def test_fermat(qi):\n",
    "    p = qi.get_mod()\n",
    "    p_x = p*p-1\n",
    "    a = (0,1)\n",
    "    while not qi.zero_p(a):\n",
    "        assert qi.one_p(qi.exp(a,p_x))\n",
    "        a = qi.next(a)\n",
    "    return True\n",
    "\n",
    "def test_squares(qi):\n",
    "    p = qi.get_mod()\n",
    "    a = (0,1)\n",
    "    sqs = []\n",
    "    i = 0\n",
    "    while not qi.zero_p(a):\n",
    "        b1 = qi.mult(a,a)\n",
    "        a_minus = qi.minus(a)\n",
    "        b2 = qi.mult(a_minus,a_minus)\n",
    "        assert qi.equal_p(b1,b2)\n",
    "        if  b1 not in sqs:\n",
    "            sqs += [b1]\n",
    "        i += 1\n",
    "        a = qi.next(a)\n",
    "    assert len(sqs)==((p*p-1)//2)\n",
    "    return True\n",
    "        \n",
    "if test_inv(qi):\n",
    "    print(f'*** passed test_inv')\n",
    "if test_fermat(qi):\n",
    "    print(f'*** passesd test_fermat')\n",
    "if test_squares(qi):\n",
    "    print(f'*** passesd test_squares')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "7f39bc30",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 + 2√7\n",
      "1 + 9√7\n",
      "2 + 3√7\n",
      "2 + 4√7\n",
      "2 + 7√7\n",
      "2 + 8√7\n",
      "3 + 1√7\n",
      "3 + 10√7\n",
      "4 + 3√7\n",
      "4 + 5√7\n",
      "4 + 6√7\n",
      "4 + 8√7\n",
      "5 + 1√7\n",
      "5 + 2√7\n",
      "5 + 9√7\n",
      "5 + 10√7\n",
      "6 + 1√7\n",
      "6 + 2√7\n",
      "6 + 9√7\n",
      "6 + 10√7\n",
      "7 + 3√7\n",
      "7 + 5√7\n",
      "7 + 6√7\n",
      "7 + 8√7\n",
      "8 + 1√7\n",
      "8 + 10√7\n",
      "9 + 3√7\n",
      "9 + 4√7\n",
      "9 + 7√7\n",
      "9 + 8√7\n",
      "10 + 2√7\n",
      "10 + 9√7\n",
      "are the 32 generators of Z/11Z[√7]\n"
     ]
    }
   ],
   "source": [
    "\n",
    "def find_gen(qi):\n",
    "    a = (0,1)\n",
    "    gens = []\n",
    "    while not qi.zero_p(a):\n",
    "        if qi.gen_p(a):\n",
    "            gens += [a]\n",
    "        a = qi.next(a)\n",
    "    return gens\n",
    "\n",
    "i = 0 \n",
    "for g in find_gen(qi):\n",
    "    i += 1\n",
    "    print(qi.str(g))\n",
    "print(f'are the {i} generators of {qi}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f1c3e911",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4cdf93a6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}