Chapter_31_Number-Theoretic_Algorithms/exercises_31.9.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 31.9 Integer factorization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.9-1\n",
    "\n",
    "> Referring to the execution history shown in Figure 31.7(a), when does POLLARDRHO print the factor 73 of 1387?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$x = 84, y = 814$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.9-2\n",
    "\n",
    "> Suppose that we are given a function $f : \\mathbb{Z}_n \\rightarrow \\mathbb{Z}_n$ and an initial value $x_0 \\in \\mathbb{Z}_n$. Define $x_i = f(x_{i - 1})$ for $i = 1,2,\\dots$. Let $t$ and $u > 0$ be the smallest values such that $x_{t+i} = x_{t+u+i}$ for $i = 0, 1, \\dots$. In the terminology of Pollard's rho algorithm, $t$ is the length of the tail and $u$ is the length of the cycle of the rho. Give an efficient algorithm to determine $t$ and $u$ exactly, and analyze its running time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.9-3\n",
    "\n",
    "> How many steps would you expect POLLARD-RHO to require to discover a factor of the form $p^e$, where $p$ is prime and $e > 1$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Theta(\\sqrt{p})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.9-4 $\\star$\n",
    "\n",
    "> One disadvantage of POLLARD-RHO as written is that it requires one gcd computation for each step of the recurrence. Instead, we could batch the gcd computations by accumulating the product of several $x_i$ values in a row and then using this product instead of $x_i$ in the gcd computation. Describe carefully how you would implement this idea, why it works, and what batch size you would pick as the most effective when working on a $\\beta$-bit number $n$."
   ]
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}