{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shanks(p,g,h):      # Solves g^x=h in F_p using the Shanks algorithm.  \n",
    "    n=floor(p**0.5)+1\n",
    "    list_a=[]\n",
    "    i=0\n",
    "    temp=1\n",
    "    print 'Producing the list of powers of g...',\n",
    "    while i<=n-1:\n",
    "        list_a.append( [temp,i] )\n",
    "        temp=(temp*g)%p\n",
    "        i=i+1\n",
    "    print 'done.'                # list_a now contains [g^0,0],[g^1,1],..,[g^{n-1},n-1]\n",
    "                                 # We are keeping track of both the power AND the exponent to make our life\n",
    "                                 # easier later\n",
    "    print 'Producing the list of h*g^{-jn}...',\n",
    "    list_b=[]\n",
    "    ginv=fastpower(g,p-2,p)\n",
    "    u=fastpower(ginv,n,p)\n",
    "    i=0\n",
    "    temp=h\n",
    "    while i<=n-1:\n",
    "        list_b.append( temp)\n",
    "        temp=(temp*u)%p\n",
    "        i=i+1\n",
    "    print 'done.'               # list_b now contains hg^0,h*g^{-n},h*g^{-2n},...,h*g^{-(n-1)n}\n",
    "    print 'Starting collision algorithm for two lists of length', len(list_a)\n",
    "    \n",
    "    l=collision(list_a,list_b)  # Do the collision algorithm.  l[0]=i will be the index in the first list\n",
    "                                # and l[1]=j will be the index in the second list\n",
    "    if l=='F':\n",
    "        print \"\\n There is no solution\"\n",
    "        return\n",
    "    return l[0]+n*l[1]          # The solution is x=i+n*j.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fastpower(x,e,p):           # Compute x^e in Z/p using the fast powering algorithm\n",
    "    if e==0:\n",
    "        return 1\n",
    "    if e==1:\n",
    "        return x%p\n",
    "    if e%2==0:\n",
    "        output=fastpower(x,e/2,p)\n",
    "        output=(output*output)%p\n",
    "        return output\n",
    "    output=fastpower(x,(e-1)/2,p)\n",
    "    output=(output*output*x)%p\n",
    "    return output\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def collision(l,m):          #Given two lists l=[(a0,b0),(a1,b1),...] and m=[x0,x1,x2,...]\n",
    "                             #having the same length, see if some ai matches an xj.\n",
    "                             #If no, return 'F' for 'Fail'.\n",
    "    i=0                      #If yes, return the pair [i,j] giving the indices for the matching elements\n",
    "    print 'Sorting the first list...',\n",
    "\n",
    "    l.sort(key=sortFirst)  #First sort the list l so that a0<=a1<=a2<=...\n",
    "    print 'done.'               #This can take a while for very long lists.\n",
    "    print 'Testing elements of the second list...', \n",
    "    i=0                         #Now test elements of m one by one to see if they match one of the ai terms.\n",
    "    n=len(m)\n",
    "    while i<=n-1:\n",
    "        if i%100==0:\n",
    "           print '.',\n",
    "        x=m[i]\n",
    "        u=is_in(l,x)      #The function is_in decides if x matches one of the ai\n",
    "        if u=='F':\n",
    "            i=i+1\n",
    "            continue\n",
    "        print 'done'\n",
    "        return [u,i]\n",
    "    print 'done.'\n",
    "    return 'F'\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_in(l,x):          #Given l=[[a0,b0],[a1,b1],...] and x, decide if x equals one of the ai.\n",
    "                         #Use the method of \"compare to middle term\" and divide the problem in half.\n",
    "    if len(l)==0:        #If no, return 'F'.  If yes, return the bi.  \n",
    "        return 'F'       #Assumes that a0<=a1<=a2<=... from the beginning.\n",
    "    first=0           \n",
    "    last=len(l)-1        #Set up pointers \"first\" and \"last\", originally at the start and end of the list l.\n",
    "    while first<last:\n",
    "        middle=first+((last-first)//2)  #Go to roughly the middle term\n",
    "        u=l[middle][0]                  #and pull out the a-value\n",
    "        if u==x:                        #If it matches our x, return the corresponding b-value.\n",
    "            return l[middle][1]\n",
    "        if u<x:                         #If x is bigger, reset the pointers to look at the last half of the list\n",
    "            first=middle+1              #and repeat\n",
    "            continue\n",
    "        last=middle-1                   #If x is smaller, reset the pointers to look at the first half of the list.\n",
    "                                        #If we come out of the loop, we never found our x.\n",
    "    if first>last:                      #Either we exhausted all elements, or we narrowed it down to exactly one.\n",
    "        return 'F'\n",
    "    u=l[first]\n",
    "    if u[0]==x:                         #Do one last check to see if we have the x.\n",
    "        return u[1]\n",
    "    return 'F'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findprime(lower,upper,tries):\n",
    "    i=1\n",
    "    while i<=tries:\n",
    "        a=randint(lower,upper)\n",
    "        if is_prime(a):\n",
    "            return a\n",
    "        i=i+1\n",
    "    print 'None found'\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=findprime(10^7,10^8,15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "98981269"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Producing the list of powers of g... done.\n",
      "Producing the list of h*g^{-jn}... done.\n",
      "Starting collision algorithm for two lists of length 8533\n",
      "Sorting the first list... done.\n",
      "Testing elements of the second list... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . done\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "57398245"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shanks(a,3,55)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortFirst(a):\n",
    "    return a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(12^69)%71"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "def order(x,p):\n",
    "    i=1\n",
    "    temp=x\n",
    "    while i<=p:\n",
    "#        if i%100==0:\n",
    "#          print '\\r testing ',i,\n",
    "        if temp==1:\n",
    "            return i\n",
    "        temp=(temp*x)%p\n",
    "        i=i+1\n",
    "    print 'Error'\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "35295289"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_prim_gen(p):     # Find a primitive generator for F_p\n",
    "    x=2                   # Warning: For big primes (9 or more digits) this can take a while.\n",
    "    while x<=p-1:\n",
    "        print 'Testing ',x,'...',\n",
    "        u=order(x,p)\n",
    "        print 'Order is ',u,'...',\n",
    "        if u==p-1:\n",
    "            print 'So found a generator'\n",
    "            return x\n",
    "        print 'So not a generator'\n",
    "        x=x+1\n",
    "    print 'Error'\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing  2 ... Order is  18198982 ... So not a generator\n",
      "Testing  3 ... Order is  72795928 ... So found a generator\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_prim_gen(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dlp_naive(p,g,h):   # Solve g^x=h in Z/p, given g and h.  Uses the brute force algorithm.  \n",
    "    i=0                 # i keeps track of the exponent we are trying\n",
    "    temp=1              #Start with g^0\n",
    "    while i<=p:\n",
    "        if temp==h:     #if we found it, return the exponent\n",
    "            return i\n",
    "        temp=(temp*g)%p # Otherwise multiply by one more copy of g and increase i.\n",
    "        i=i+1\n",
    "    print 'Error: no solution found'\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "83562159"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dlp_naive(a,2,55)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dlp_naive(23,5,19)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ph_estimate(n):\n",
    "    i=1\n",
    "    save=0\n",
    "    while i<=n:\n",
    "        b=findprime(10^20,10^21,35)\n",
    "        if b==0:\n",
    "            continue\n",
    "        l=factor(b-1)\n",
    "        count=0\n",
    "        for a in l:\n",
    "            count=count+a[1]*a[0]\n",
    "        save=save+(b+0.0)/count\n",
    "        i=i+1\n",
    "    return (save+0.0)/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "def miller_rabin_test(n,a):\n",
    "    k=0\n",
    "    temp=n-1\n",
    "    while (temp%2)==0:\n",
    "        k=k+1\n",
    "        temp=temp/2\n",
    "    q=(n-1)/(2^k)\n",
    "    A=fastpower(a,q,n)\n",
    "    if A==1:\n",
    "        return False\n",
    "    i=0\n",
    "    while i<=k-1:\n",
    "        if A==n-1:\n",
    "            return False\n",
    "        A=(A**2)%n\n",
    "        i=i+1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "miller_rabin_test(5,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.7",
   "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.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}