cryptopals_set6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib, base64\n",
    "def sha256(msg):\n",
    "    hasher = hashlib.sha256()\n",
    "    hasher.update(msg.encode())\n",
    "    return hasher.hexdigest()\n",
    "def sha1(msg):\n",
    "    hasher = hashlib.sha1()\n",
    "    hasher.update(msg.encode())\n",
    "    return hasher.hexdigest()\n",
    "def sha1i(msg):\n",
    "    \"\"\"SHA1 but it returns an integer\"\"\"\n",
    "    return int(sha1(msg), 16)\n",
    "def bytes_to_int(b):\n",
    "    return int.from_bytes(b, 'big')\n",
    "def int_to_bytes(i, pad_to_length=None):\n",
    "    s = hex(i)[2:].upper()\n",
    "    if len(s) % 2 == 1:\n",
    "        s = '0' + s\n",
    "    b = base64.b16decode(s)\n",
    "    if pad_to_length and len(b) < pad_to_length:\n",
    "        b = b'\\x00' * (pad_to_length - len(b)) + b\n",
    "    return b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Crypto"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First, get some primitives down :\n",
    "\n",
    "import gensafeprime\n",
    "\n",
    "def primegen(small=True, big=False, size_n=None):\n",
    "    \"\"\"Generate a random prime.\"\"\"\n",
    "    if size_n:\n",
    "        return gensafeprime.generate(size_n//2)\n",
    "    if small:\n",
    "        return gensafeprime.generate(32)\n",
    "    if big:\n",
    "        return gensafeprime.generate(1024)\n",
    "    return gensafeprime.generate(128)\n",
    "\n",
    "def egcd(r, u, v, rp, up, vp):\n",
    "    \"\"\"Extended Euclid algorithm for GCD\n",
    "    Given a, b, find GCD(a,b) and x,y such that :\n",
    "        a.x b+ b.y = GCD(a,b)     (Bézout coefficients)\n",
    "    \"\"\"\n",
    "    if r == 0:\n",
    "        return up, vp\n",
    "    else:\n",
    "        return egcd(rp - (rp // r)*r, up - (rp // r)*u, vp - (rp // r)*v, r, u, v)\n",
    "    \n",
    "    \n",
    "def invmod(a, N):\n",
    "    \"\"\"Calculate the inverse modulo\"\"\"\n",
    "    x, _ = egcd(a, 1, 0, N, 0, 1)\n",
    "    return x % N\n",
    "\n",
    "assert (invmod(15, 37) * 15) % 37 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unsafe encryption.\n"
     ]
    }
   ],
   "source": [
    "import base64\n",
    "\n",
    "def str_to_int(s):\n",
    "    return int(base64.b16encode(s), 16)\n",
    "def int_to_str(i):\n",
    "    s = hex(i)[2:].upper()\n",
    "    if len(s) % 2 == 1:\n",
    "        s = '0' + s # base16 wants even length strings, adding a 0 in front does not change the value. Perfect.\n",
    "    return base64.b16decode(s)\n",
    "assert int_to_str(str_to_int((b\"Hello, world !\"))) == b'Hello, world !'\n",
    "\n",
    "class RSA:\n",
    "    def __init__(self, small=True, big=False, block_length=None, p=None, q=None, size_n=None):\n",
    "        if p is None:\n",
    "            self.p = primegen(small=small, big=big, size_n=size_n)\n",
    "        else:\n",
    "            self.p = p\n",
    "        if q is None:\n",
    "            self.q = primegen(small=small, big=big, size_n=size_n)\n",
    "        else:\n",
    "            self.q = q\n",
    "        self.n = self.p * self.q\n",
    "        self.et = (self.p - 1) * (self.q - 1)\n",
    "        self.e = 3\n",
    "        self.d = invmod(self.e, self.et)\n",
    "        if block_length is None:\n",
    "            self.block_length = 3 + (not small)*9\n",
    "        else:\n",
    "            self.block_length = block_length\n",
    "    \n",
    "    @property\n",
    "    def public(self):\n",
    "        return self.e, self.n\n",
    "    \n",
    "    @property\n",
    "    def private(self):\n",
    "        return self.d, self.n\n",
    "    \n",
    "    def encrypt_block(self, s, i2s = True):\n",
    "        # Encrypt one block\n",
    "        if isinstance(s, bytes):\n",
    "            m = str_to_int(s)\n",
    "            if m ** 3 < self.n:\n",
    "                print('Unsafe encryption.') # If the cubed message does not wrap around, it's not much use...\n",
    "            if m > self.n:\n",
    "                raise Exception(\"Message not encryptable. Please use blocks.\")\n",
    "            if i2s:\n",
    "                return int_to_str(pow(m, self.e, self.n))\n",
    "            else:\n",
    "                return pow(m, self.e, self.n)\n",
    "        else:\n",
    "            m = s\n",
    "            return pow(m, self.e, self.n)\n",
    "    \n",
    "    def decrypt_block(self, s, i2s = True, pad_to_block_length=False):\n",
    "        if isinstance(s, bytes):\n",
    "            c = str_to_int(s)\n",
    "            if c > self.n:\n",
    "                raise Exception(\"Message not encryptable. Please use blocks.\")\n",
    "            if i2s:\n",
    "                s = int_to_str(pow(c, self.d, self.n))\n",
    "                if len(s) < self.block_length and pad_to_block_length:\n",
    "                    # If the highest bytes are 0, the resulting string gets truncated.\n",
    "                    # Let's pad it back to the actual length of a block\n",
    "                    s = b'\\x00' * (self.block_length - len(s)) + s\n",
    "                return s\n",
    "            else:\n",
    "                return pow(c, self.d, self.n)\n",
    "        else:\n",
    "            c = s\n",
    "            return pow(c, self.d, self.n)\n",
    "    \n",
    "    def encrypt(self, s):\n",
    "        acc = []\n",
    "        for i in range(0, len(s), self.block_length):\n",
    "            acc.append(self.encrypt_block(s[i:i+self.block_length]))\n",
    "        return acc\n",
    "        \n",
    "    \n",
    "    def decrypt(self, s):\n",
    "        return b\"\".join(self.decrypt_block(b) for b in s)\n",
    "        \n",
    "    \n",
    "r = RSA(small=False)\n",
    "assert r.decrypt(r.encrypt(b\"Vanilla Ice Baby\")) == b'Vanilla Ice Baby'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cryptopals Notebook\n",
    "\n",
    "## Set 6\n",
    "\n",
    "### Exercice 41\n",
    "\n",
    "Implement unpadded message recovery oracle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Setting up legitimate side of things\n",
    "class Server:\n",
    "    def __init__(self):\n",
    "        self.rsa = RSA(small=False)\n",
    "        self.memory = set()\n",
    "    \n",
    "    def encrypt(self, s):\n",
    "        return self.rsa.encrypt(s)\n",
    "    \n",
    "    def decrypt(self, s):\n",
    "        if b\"\".join(s) in self.memory:\n",
    "            raise Exception(\"Message already decrypted\") # Why bother with hashes\n",
    "        else:\n",
    "            self.memory.add(b\"\".join(s))\n",
    "            return self.rsa.decrypt(s)\n",
    "\n",
    "# Alice is the server\n",
    "alice = Server()\n",
    "\n",
    "# Bob is the JS client\n",
    "original_message = b'{ \"time\": 62365314455, \"social\": \"555-555-555\" }'\n",
    "bob = {'message': alice.encrypt(original_message) }\n",
    "\n",
    "# Bob asks for the decrypted message\n",
    "bob['clear'] = alice.decrypt(bob['message'])\n",
    "assert bob['clear'] == original_message"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Eve gets a hold of the ciphertext !\n",
    "eve = {'message': bob['message']}\n",
    "\n",
    "# Ensure that the server won't decrypt it again...\n",
    "try:\n",
    "    alice.decrypt(eve['message'])\n",
    "    assert False\n",
    "except:\n",
    "    assert True\n",
    "    \n",
    "# Now modify message so that is different but still the same.\n",
    "(e, n), s = alice.rsa.public, 4 # Totally random, I swear.\n",
    "c = [str_to_int(block) for block in eve['message']] # Go back to ints for math\n",
    "cp = [(pow(s, e, n) * block) % n for block in c]\n",
    "assert c != cp\n",
    "new_message = alice.decrypt([int_to_str(block) for block in cp])\n",
    "assert new_message != original_message # We got a jumbled mess here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now Eve will want to recover original_message from new_message :\n",
    "blocks = [str_to_int(new_message[i:i+12]) for i in range(0, len(new_message), 12)]\n",
    "new_blocks = [(block * invmod(s, n)) % n for block in blocks]\n",
    "decrypted_message = b\"\".join(int_to_str(block) for block in new_blocks)\n",
    "\n",
    "# This is due to the fact that we add 0's to ensure int_to_str. Not that important.\n",
    "# We could just make a smarter way to convert str to ints. Meh.\n",
    "decrypted_message = b\"\".join(bytes([b]) for b in decrypted_message if b != 0)\n",
    "assert decrypted_message == original_message"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 42\n",
    "\n",
    "Bleichenbacher's e=3 RSA Attack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "sender = RSA(small=False, big=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sign(sender, text):\n",
    "    \"\"\"Simple implementation of RSA signing\"\"\"\n",
    "    d, n = sender.private\n",
    "    _hash = base64.b16decode(sha1(text).upper())\n",
    "    asn1 = b'\\x30\\x21\\x30\\x09\\x06\\x05\\x2b\\x0e\\x03\\x02\\x1a\\x05\\x00\\x04\\x14' # ASN.1 encoding for SHA1\n",
    "    block = b'\\x00\\x01' + b'\\xff' * (128 - len(_hash) - len(asn1) - 3) + b'\\x00' + asn1 + _hash # Pad out to 128 bytes\n",
    "    assert len(block) == 128 # 1024 bit blocks\n",
    "    return pow(bytes_to_int(block), d, n)\n",
    "\n",
    "def check_signature(sender, text, signature):\n",
    "    \"\"\"Flawed implementation of RSA signature verification\"\"\"\n",
    "    e, n = sender.public\n",
    "    _hash = base64.b16decode(sha1(text).upper())\n",
    "    asn1 = b'\\x30\\x21\\x30\\x09\\x06\\x05\\x2b\\x0e\\x03\\x02\\x1a\\x05\\x00\\x04\\x14' # ASN.1 encoding for SHA1\n",
    "    clearint = pow(signature, e, n)\n",
    "    clearblock = b'\\x00' + int_to_bytes(clearint) # Initial null byte is lost during integer conversion\n",
    "    if not (clearblock[0:3] == b'\\x00\\x01\\xff'):\n",
    "        print('Starting bytes not ok')\n",
    "        return False # Check only the \"important\" bytes\n",
    "    clearblock = clearblock[3:]\n",
    "    while clearblock[0] == 255:\n",
    "        clearblock = clearblock[1:] # Consume 0xFF bytes\n",
    "    return clearblock.startswith(b'\\x00' + asn1 + _hash) # Check important bytes\n",
    "    # So we did NOT check that the padding was the entire length\n",
    "    # and we did NOT check the remaining block was equal to the ans1 + hash part.\n",
    "    \n",
    "# Check base case\n",
    "assert check_signature(sender, \"Hello, world !\", sign(sender, \"Hello, world !\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "This is all inspired from this submission : https://www.ietf.org/mail-archive/web/openpgp/current/msg00999.html\n",
    "\n",
    "Let's define D and N :\n",
    "$$\\begin{align*}\n",
    "D\n",
    "&= 0x00\\ ASN.1\\ HASH \\\\\n",
    "&= 2^{288} - N\n",
    "\\end{align*}$$\n",
    "\n",
    "And now build the signature, using the least amount of padding possible (to have the largest possible margin) :\n",
    "$$\\begin{align*}\n",
    "signature\n",
    "&= 0x00\\ 0x01\\ 0xFF\\ 0x00\\ ASN.1\\ HASH\\ GARBAGE\\ (1024\\ bit\\ key)\\\\\n",
    "&= 2^{1009} - 2^{1000} + D.2^{712} + garbage\\\\\n",
    "&= 2^{1009} - 2^{1000} + 2^{1000} - N.2^{712} + garbage\\\\\n",
    "&= 2^{1009} - N.2^{712} + garbage\\\\\n",
    "\\end{align*}$$\n",
    "\n",
    "Sadly, given that 2^1009 is not a perfect cube, we cannot make a nice formula like in the Hal Finney writeup. We still have a good base. Let's crunch some numbers to find a perfect cube that would fit our description. WolframAlpha reveals that the cube root of our baseline (2^1009 - N\\*2^712) is around 1.7\\*10^101. Let's use that as a starting value (note: we could have found this value by using the same binary search used to find the perfect root)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now, we want to forge a signature\n",
    "e, n = sender.public\n",
    "_hash = base64.b16decode(sha1('Hello, world !').upper())\n",
    "asn1 = b'\\x30\\x21\\x30\\x09\\x06\\x05\\x2b\\x0e\\x03\\x02\\x1a\\x05\\x00\\x04\\x14' # ASN.1 encoding for SHA1\n",
    "D = bytes_to_int(b'\\x00' + asn1 + _hash)\n",
    "N = 2**288 - D\n",
    "target = 2**1009 - N * (2**712)\n",
    "base = 176254032823638680266052181223788664320230109282117832543013801901130780612858290399771331518246797307"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found a good root. (root^3 - target) is 16127599852352072733114186255968266580760613075092633068618640212423478497054982267802592076314564076913940744080994100546246971644854173908828995096951797527509070032754050928806580131027491716868344335397286586176 and (2^712 - (root^3 - target)) is 5417916800390065152544908304308740433333578757271087059886318366546048406945860779574986056278438219311781496353911879206280622851898686714542534203638306433907526124188058145386474621266694133074872823712473929920\n"
     ]
    }
   ],
   "source": [
    "# We need a perfect cube that is slightly larger than our target (less than 2^712 difference, should be doable)\n",
    "def is_good_root(n):\n",
    "    if (n**3 - target) < 0:\n",
    "        return -1 # Too small\n",
    "    if (n**3 - target) > 2**712:\n",
    "        return 1  # Too big\n",
    "    return 0 # Perfect.\n",
    "\n",
    "low = base\n",
    "high = base*2\n",
    "mid = (high - low) // 2 + low\n",
    "is_ok = is_good_root(mid)\n",
    "while is_ok != 0:\n",
    "    if is_ok < 0:\n",
    "        low = mid\n",
    "    elif is_ok > 0:\n",
    "        high = mid\n",
    "    mid = (high - low) // 2 + low\n",
    "    is_ok = is_good_root(mid)\n",
    "root = mid\n",
    "    \n",
    "print('Found a good root. (root^3 - target) is %s and (2^712 - (root^3 - target)) is %s' % (mid**3 - target, 2**712 - (mid**3 - target)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now for the test !\n",
    "assert check_signature(sender, \"Hello, world !\", root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Interlude : Cyclic Groups Math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CyclicInteger:\n",
    "    def __init__(self, value, n):\n",
    "        self.value = int(value)\n",
    "        self.n = int(n)\n",
    "    def __int__(self):\n",
    "        return int(self.value) % int(self.n)\n",
    "    def __add__(self, i):\n",
    "        return CyclicInteger((int(self) + int(i)) % self.n, self.n)\n",
    "    def __sub__(self, i):\n",
    "        return CyclicInteger((int(self) - int(i)) % self.n, self.n)\n",
    "    def __eq__(self, i):\n",
    "        return int(self) == int(i) % self.n\n",
    "    def __lt__(self, i):\n",
    "        return int(self) < int(i) % self.n\n",
    "    def __gt__(self, i):\n",
    "        return int(self) > int(i) % self.n\n",
    "    def __mul__(self, i):\n",
    "        return CyclicInteger((int(self)*int(i)) % self.n, self.n)\n",
    "    def __truediv__(self, i):\n",
    "        return CyclicInteger((int(self) * invmod(int(i), self.n)) % self.n, self.n)\n",
    "    def __pow__(self, i, m=None):\n",
    "        if m is None:\n",
    "            return CyclicInteger(pow(int(self), int(i), self.n), self.n)\n",
    "        else:\n",
    "            return CyclicInteger(pow(int(self), int(i), self.n) % int(m), self.n)\n",
    "    def __mod__(self, i):\n",
    "        return CyclicInteger((int(self) % int(i)) % self.n, self.n)\n",
    "    @property\n",
    "    def inverse(self):\n",
    "        return CyclicInteger(invmod(int(self), self.n), self.n)\n",
    "    \n",
    "a, b, c = CyclicInteger(1, 13), CyclicInteger(10, 13), CyclicInteger(11, 13)\n",
    "assert int(a - b) == 4  \n",
    "assert int(b + c) == 8\n",
    "assert int(c + 5) == 3\n",
    "assert int(c * c.inverse) == a == 1\n",
    "assert c.inverse.inverse == c\n",
    "assert int(c / c.inverse.inverse) == a == 1\n",
    "assert int(b ** 2) == 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 43\n",
    "\n",
    "DSA key recovery from nonce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Parameters\n",
    "p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1\n",
    "q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b\n",
    "g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def dsa_sign(text, p, q, g, return_private_key=False, nonce=None, force_private_key=None,\n",
    "            check_r_non_zero=True):\n",
    "    \"\"\"Sign a given text using DSA\n",
    "    \n",
    "    Note : some arguments are useful for later exercices.\n",
    "    \"\"\"\n",
    "    # Generate public and private keys\n",
    "    if force_private_key:\n",
    "        x = CyclicInteger(force_private_key, q)\n",
    "    else:\n",
    "        x = CyclicInteger(random.randint(1, q-1), q)\n",
    "    y = CyclicInteger(pow(g, int(x), p), p)\n",
    "    \n",
    "    # Random per message key (with r != 0)\n",
    "    if nonce is None:\n",
    "        k = CyclicInteger(random.randint(1, q-1), q)\n",
    "    else:\n",
    "        k = CyclicInteger(nonce, q)\n",
    "    r = CyclicInteger(pow(g, int(k), p), q)\n",
    "    while r == 0 and check_r_non_zero:\n",
    "        k = CyclicInteger(random.randint(1, q-1), q)\n",
    "        r = CyclicInteger(pow(g, int(k), p), q)\n",
    "    \n",
    "    # Calculate signature\n",
    "    H = CyclicInteger(sha1i(text), q)\n",
    "    s = k.inverse * (H + x*r) # These are all CyclicIntegers\n",
    "    \n",
    "    if s == 0:\n",
    "        return dsa_sign(text, p, q, g) # Start again\n",
    "    if return_private_key:\n",
    "        return int(y), int(r), int(s), int(x), int(k)\n",
    "    else:\n",
    "        return int(y), int(r), int(s)\n",
    "\n",
    "def dsa_verify(text, r, s, y, p, q, g):\n",
    "    \"\"\"Verify the signature of a given text with DSA\n",
    "    \"\"\"\n",
    "    w = CyclicInteger(s, q).inverse\n",
    "    H = CyclicInteger(sha1i(text), q)\n",
    "    u1 = H * w\n",
    "    u2 = CyclicInteger(r, q) * w\n",
    "    v =((pow(g, int(u1), p) * pow(int(y), int(u2), p)) % p) % q\n",
    "    return int(v) == int(r)\n",
    "\n",
    "text = \"Hello, world !\"\n",
    "y, r, s = dsa_sign(text, p, q, g)\n",
    "assert dsa_verify(text, r, s, y, p, q, g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's first try to recover the private key from a test message\n",
    "text = \"What's wrong with the world mama ?\"\n",
    "\n",
    "def dsa_recover_private_key_from_nonce(text, r, s, y, p, q, g, k):\n",
    "    \"\"\"k is the nonce. The rest is simply a text with it's signature.\"\"\"\n",
    "    H = CyclicInteger(sha1i(text), q)\n",
    "    r, s, k = CyclicInteger(r, q), CyclicInteger(s, q), CyclicInteger(k, q)\n",
    "    return int(((s * k) - H) / r) # Cyclic Group Math ensured by the class\n",
    "\n",
    "def dsa_check_private_key(text, r, s, y, p, q, g, k, x):\n",
    "    \"\"\"Let's see if a given recovered private key matches with the\n",
    "    one that was actually used to generate a given signature.\n",
    "    \"\"\"\n",
    "    y_test, r_test, s_test = dsa_sign(text, p, q, g, force_private_key=x, nonce=k)\n",
    "    return y_test == y and r_test == r and s_test == s\n",
    "\n",
    "y, r, s, x, k = dsa_sign(text, p, q, g, return_private_key=True)\n",
    "x_recovered = dsa_recover_private_key_from_nonce(text, r, s, y, p, q, g, k)\n",
    "assert x == x_recovered # Yay \\o/\n",
    "assert dsa_check_private_key(text, r, s, y, p, q, g, k, x_recovered)\n",
    "assert not dsa_check_private_key(text, r, s, y, p, q, g, k, x_recovered + 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How this works (this is really trivial) :\n",
    "\n",
    "$$\\begin{align*}\n",
    "((s.k) - H(msg)).r^{-1}\n",
    "&= ((k^{-1}.(H(msg)+r.x).k)-H(msg)).r^{-1}\\\\\n",
    "&= x\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 25%|██▌       | 16572/65536 [00:18<00:53, 923.46it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found private key : 0x15fb2873d16b3e129ff76d0918fd7ada54659e49  (nonce : 16575)\n"
     ]
    }
   ],
   "source": [
    "# Now, the actual challenge.\n",
    "# The author has used a nonce <2**16. This is really low and can easily be bruteforced.\n",
    "y = 0x84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07bbb283e6633451e535c45513b2d33c99ea17\n",
    "r = 548099063082341131477253921760299949438196259240\n",
    "s = 857042759984254168557880549501802188789837994940\n",
    "text = \"\"\"For those that envy a MC it can be hazardous to your health\n",
    "So be friendly, a matter of life and death, just like a etch-a-sketch\n",
    "\"\"\"\n",
    "assert sha1i(text) == 0xd2d0714f014a9784047eaeccf956520045c45265\n",
    "\n",
    "import tqdm\n",
    "for k in tqdm.tqdm(range(2**16)):\n",
    "    x_recovered = dsa_recover_private_key_from_nonce(text, r, s, y, p, q, g, k)\n",
    "    if dsa_check_private_key(text, r, s, y, p, q, g, k, x_recovered):\n",
    "        print('Found private key :', hex(x_recovered), ' (nonce : %s)' % k)\n",
    "        break\n",
    "\n",
    "assert sha1(hex(x_recovered)[2:]) == '0954edd5e0afe5542a4adf012611a91912a3ec16'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 44\n",
    "\n",
    "\n",
    "DSA nonce recovery from repeated nonce\n",
    "\n",
    "##### How it works\n",
    "\n",
    "If k stays constant for two messages m1 and m2, then r stays constant too. This gives us (everything is mod q) :\n",
    "$$\\begin{align*}\n",
    "\\dfrac{m2-m1}{s2-s1}\n",
    "&= (m2-m1).[k^{-1}.(m2+x.r)-k^{-1}.(m1+x.r)]^{-1}\\\\\n",
    "&= k\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = 0x2d026f4bf30195ede3a088da85e398ef869611d0f68f0713d51c9c1a3a26c95105d915e2d8cdf26d056b86b8a7b85519b1c23cc3ecdc6062650462e3063bd179c2a6581519f674a61f1d89a1fff27171ebc1b93d4dc57bceb7ae2430f98a6a4d83d8279ee65d71c1203d2c96d65ebbf7cce9d32971c3de5084cce04a2e147821"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load into an object\n",
    "messages = []\n",
    "with open('44.txt') as _in:\n",
    "    message = {}\n",
    "    for l in _in:\n",
    "        key = l.split(':')[0]\n",
    "        value = l.split(':')[1].strip()\n",
    "        if key == 'msg':\n",
    "            value += ' ' # Apparently each message has a trailing space\n",
    "        elif key == 'm':\n",
    "            value = CyclicInteger(int(value, 16), q)\n",
    "        else:\n",
    "            value = CyclicInteger(int(value), q)\n",
    "        message[key] = value\n",
    "        if 's' in message and 'r' in message and 'msg' in message and 'm' in message:\n",
    "            messages.append(message)\n",
    "            message = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found the two messages : Listen for me, you better listen for me now.  and Pure black people mon is all I mon know. \n"
     ]
    }
   ],
   "source": [
    "# Try to find messages with the same k.\n",
    "# There is a neat trick here : if k is constant...\n",
    "# ... r is constant too. Soooooo.... easy enough to\n",
    "# identify the messages.\n",
    "from itertools import combinations\n",
    "\n",
    "m0, m1 = None, None\n",
    "for m0, m1 in combinations(messages, 2):\n",
    "    if m0['r'] == m1['r']:\n",
    "        print('Found the two messages : {} and {}'.format(m0['msg'], m1['msg']))\n",
    "        break\n",
    "\n",
    "realfingerprint = 'ca8f6f7c66fa362d40760d135b763eb8527d3d52'\n",
    "k = (m1['m'] - m0['m']) / (m1['s'] - m0['s'])\n",
    "x_recovered = dsa_recover_private_key_from_nonce(m0['msg'], m0['r'], m0['s'], y, p, q, g, k)\n",
    "x_recovered_2 = dsa_recover_private_key_from_nonce(m1['msg'], m1['r'], m1['s'], y, p, q, g, k)\n",
    "\n",
    "assert dsa_check_private_key(m0['msg'], m0['r'], m0['s'], y, p, q, g, k, x_recovered)\n",
    "assert dsa_check_private_key(m1['msg'], m1['r'], m1['s'], y, p, q, g, k, x_recovered)\n",
    "assert sha1(hex(x_recovered)[2:]) == realfingerprint\n",
    "assert sha1(hex(x_recovered_2)[2:]) == realfingerprint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 45\n",
    "\n",
    "DSA parameter tampering\n",
    "\n",
    "If we can force g = 0:\n",
    "$$\\begin{align*}\n",
    "g=0\n",
    "&=> r = 0\\\\\n",
    "&=> s = k^{-1}.H(msg)\\\\\n",
    "&=> y = 0\n",
    "\\end{align*}$$\n",
    "\n",
    "This means the signature does no longer depend on the private key... Also, the nonce can be trivially extracted which is bad as we already know. Also the signature can be trivially forged (take the hash). In a word : completely broken."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "text1, text2 = \"Hello, world !\", \"How are you today ?\"\n",
    "y1, r1, s1 = dsa_sign(text1, p, q, g=0, check_r_non_zero=False)\n",
    "assert y1 == r1 == 0\n",
    "y2, r2, s2 = dsa_sign(text2, p, q, g=0, check_r_non_zero=False)\n",
    "assert y2 == r2 == 0\n",
    "h1 = sha1i(text1)\n",
    "assert dsa_verify(text1, 0, h1, 0, p, q, g=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we can force g = (p+1):\n",
    "$$\\begin{align*}\n",
    "g=p+1\n",
    "&=> r = g^{k}\\ mod\\ p\\ =\\ 1^{k}\\ mod\\ p\\ =\\ 1\\\\\n",
    "&=> s = k^{-1}.(H(msg)+x)\\\\\n",
    "&=> y = g^{x}\\ mod\\ p\\ =\\ 1^{k}\\ mod\\ p\\ =\\ 1\\\\\n",
    "\\end{align*}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 915537087426811535594528344905753090244691238521\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text1 = \"Hello, world !\"\n",
    "y1, r1, s1 = dsa_sign(text1, p, q, g=p+1)\n",
    "print(y1, r1, s1)\n",
    "\n",
    "z = sha1i(\"Goodbye\")\n",
    "r = ((y1 * z) % p) % q\n",
    "s = (r * invmod(z, q)) % q\n",
    "dsa_verify(\"text1\", 1, 1, 1, p, q, g=p+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, apparently, this is actually slightly more complicated and allows to generate a magic signature. However, I don't quite see where my math is wrong... So this is most definitely not as easy as that, but I can't seem to find the mistake."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 46\n",
    "\n",
    "RSA parity Oracle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use small primes for simplicity\n",
    "p = 0xC2B0C8D9BFE064019955C4A3819E31BFA6679B32BC5A2021D1EDC5EA83BCCFD79946200A6D5C7D349B69B1BE3EE01AF3C48811D9B95BD8740BB5EA5B3BD1CAB5\n",
    "q = 0xFC932034EA8B970B000C6C1CBBB7ACAB0ECC6D7C86840B75C9A2EAFC84536D04DF4F63B49B7852D65CC9FA313EB2E095C5A1B3E47BF9550447E65907741A43F9\n",
    "r = RSA(p=p, q=q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import base64\n",
    "def oracle(encrypter, cypher):\n",
    "    \"\"\"Returns True if the plaintext is odd and False if it is even\"\"\"\n",
    "    return bool(encrypter.decrypt_block(cypher, i2s=False) % 2)\n",
    "\n",
    "message = \"VGhhdCdzIHdoeSBJIGZvdW5kIHlvdSBkb24ndCBwbGF5IGFyb3VuZCB3aXRoIHRoZSBGdW5reSBDb2xkIE1lZGluYQ==\"\n",
    "message = base64.b64decode(message)\n",
    "cypher = r.encrypt_block(message, i2s=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "encrypt() got an unexpected keyword argument 'i2s'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-25-5e273853407f>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mtqdm\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mlo\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mhi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mr\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcypher\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mcypher_2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mr\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mencrypt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mi2s\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mFalse\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m \u001b[0mpbar\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtqdm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtqdm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mr\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m20\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpbar\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: encrypt() got an unexpected keyword argument 'i2s'"
     ]
    }
   ],
   "source": [
    "import tqdm, math\n",
    "lo, hi, c = 0, r.n, cypher\n",
    "cypher_2 = r.encrypt(2, i2s=False)\n",
    "pbar = tqdm.tqdm(range(int(math.log(r.n, 2))+20))\n",
    "for i in pbar:\n",
    "    pbar.set_description(str(int_to_str(hi)))\n",
    "    if oracle(r, c*cypher_2):\n",
    "        lo, hi, c = (hi+lo)//2, hi, c*cypher_2 - r.n\n",
    "    else:\n",
    "        lo, hi, c = lo, (hi+lo)//2, c*cypher_2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 47\n",
    "\n",
    "Bleichenbacher's PKCS 1.5 padding Oracle (Simple Case)\n",
    "\n",
    "(moving directly to complete case)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 48\n",
    "\n",
    "Bleichenbacher's PKCS 1.5 padding Oracle (Complete Case)\n",
    "\n",
    "(see PDF for explanation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Helpers\n",
    "import os\n",
    "def nzrb(n):\n",
    "    \"\"\"N non-zero, random, bytes\"\"\"\n",
    "    b = os.urandom(n)\n",
    "    while b'\\x00' in b:\n",
    "        b = os.urandom(n)\n",
    "    return b\n",
    "\n",
    "# PKCS 1.5 padding and unpadding, given 512 bit block size\n",
    "_BS = 512 // 8\n",
    "def pkcs1(msg):\n",
    "    \"\"\"Given a bytes message, return padded message.\"\"\"\n",
    "    if len(msg) > _BS - 3 - 10: # min 10 bytes padding\n",
    "        raise ValueError('Message to long. Max size is {}'.format(_BS -13 ))\n",
    "    return b'\\x00\\x02' + nzrb(_BS - 3 - len(msg)) + b'\\x00' + msg\n",
    "    \n",
    "def unpkcs1(msg):\n",
    "    \"\"\"Given a padded bytes message, return unpadded message\n",
    "    or raise ValueError if the padding is invalid.\"\"\"\n",
    "    if isinstance(msg, int):\n",
    "        msg = int_to_bytes(msg, pad_to_length=_BS)\n",
    "    if msg[:2] != b'\\x00\\x02':\n",
    "        raise ValueError('Invalid padding : non-conformant lowest bytes {}'.format(msg[:2]))\n",
    "    msg = msg[2:]\n",
    "    i = 0\n",
    "    if not msg:\n",
    "        raise ValueError('Not enough padding (min 10 bytes)')\n",
    "    while i < len(msg) and msg[i] != 0:\n",
    "        i += 1\n",
    "    #if i == len(msg):\n",
    "    #    raise ValueError('Invalid padding : no null byte after padding')\n",
    "    #if i < 10:\n",
    "    #    raise ValueError('Invalid padding : only {} padding bytes instead of min 10'.format(i))\n",
    "    return msg[i+1:]\n",
    "\n",
    "msg = b'Short test'\n",
    "assert unpkcs1(pkcs1(msg)) == msg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Start with a legitimate RSA user, encrypting a message. This gives us `m` and `c`.\n",
    "alice = RSA(size_n=_BS*8, block_length=_BS)\n",
    "m = pkcs1(b'I\\'m not a 90s kid')\n",
    "c = alice.encrypt_block(m)\n",
    "\n",
    "def oracle(a, c, verbose=False):\n",
    "    \"\"\"PKCS validity oracle for alice.\"\"\"\n",
    "    try:\n",
    "        unpkcs1(a.decrypt_block(c, pad_to_block_length=True))\n",
    "        return True\n",
    "    except ValueError as err:\n",
    "        # Message was not PKCS compliant\n",
    "        if verbose:\n",
    "            print(err)\n",
    "        return False\n",
    "    \n",
    "c_i = bytes_to_int(c)\n",
    "assert oracle(alice, c, verbose=True)\n",
    "assert oracle(alice, c_i, verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Actual Bleichenbacher search ###\n",
    "#\n",
    "# Step 1 : blinding.\n",
    "# This step is not required as we start with an encrypted message (which is already PKCS conforming)\n",
    "import tqdm, math, copy\n",
    "B = pow(2, 8*(_BS - 2))\n",
    "\n",
    "def bleichenbacher(B, message, alice):\n",
    "    \"\"\"Bleichenbacher '98 attach\n",
    "    \"\"\"\n",
    "    e, n = alice.public\n",
    "    c0 = message\n",
    "    s, M, i = [], [], 0\n",
    "    \n",
    "    # Helper functions\n",
    "    def homomorphic_oracle(si):\n",
    "        return oracle(alice, (message * pow(si, e, n)) % n)\n",
    "    def insert_interval(intervals, new_interval):\n",
    "        new_a, new_b = new_interval\n",
    "        for i, (a, b) in enumerate(intervals):\n",
    "            if a <= new_a <= new_b <= b:\n",
    "                # New interval included in existing one. Skip.\n",
    "                return intervals\n",
    "            \n",
    "            elif (new_a <= a <= new_b <= b) or (a <= new_a <= b <= new_b) or (new_a <= a <= b <= new_b):\n",
    "                # New interval larger than existing one. Replace\n",
    "                return intervals[:i] + [(min(a, new_a), max(b, new_b))] + intervals[i+1:]\n",
    "            \n",
    "        # If we arrived at the end, there is no overlap. Add the new interval.\n",
    "        return intervals + [new_interval]\n",
    "    def total_length(intervals):\n",
    "        return sum(i[1] - i[0] for i in intervals)\n",
    "    \n",
    "    \n",
    "    # Step 1 : not necessary, we assume \"message\" is already an encrypted, PKCS valid message.\n",
    "    print(\"Step 1\")\n",
    "    s.append(1)\n",
    "    M.append([(2*B,3*B-1)])\n",
    "    i = 1\n",
    "    \n",
    "    # For faster replay, store and allow for an offset\n",
    "    # WARNING : dont use these if you change any of the random parameters!\n",
    "    cheat = {}\n",
    "    \n",
    "    while True:\n",
    "        \n",
    "        # Step 2a\n",
    "        if i == 1:\n",
    "            \n",
    "            print(\"Step 2a\")\n",
    "            ctr = cheat.get(i, 0)\n",
    "            s.append(n // (3*B) + ctr)\n",
    "            while not homomorphic_oracle(s[i]):\n",
    "                s[i] += 1\n",
    "                ctr += 1\n",
    "            print(\"Step 2a took {} iterations (s1 = {})\".format(ctr, s[i]))\n",
    "\n",
    "                \n",
    "        # Step 2b\n",
    "        elif i > 1 and len(M[i-1]) > 1:\n",
    "            \n",
    "            print(\"Step 2b\")\n",
    "            ctr = cheat.get(i, 0)\n",
    "            s.append(s[i-1] + 1 + ctr)\n",
    "            while not homomorphic_oracle(s[i]):\n",
    "                s[i] += 1 \n",
    "                ctr += 1\n",
    "            print(\"Step 2b took {} iterations\".format(ctr))\n",
    "             \n",
    "        # Step 2c\n",
    "        elif len(M[i-1]) == 1:\n",
    "            \n",
    "            print(\"Step 2c\")\n",
    "            ctr_r, ctr_s = 0, 0\n",
    "            a, b = M[i-1][0]\n",
    "            r = (2*(b*s[i-1] - 2*B) // n) - 1\n",
    "            s.append((2*B + r*n) // b)\n",
    "            while not homomorphic_oracle(s[i]):\n",
    "                if s[i] >= (3*B + r*n) // a:\n",
    "                    r += 1\n",
    "                    s[i] = (2*B + r*n) // b\n",
    "                    ctr_r += 1\n",
    "                    ctr_s += 1\n",
    "                else:\n",
    "                    s[i] += 1\n",
    "                    ctr_s += 1\n",
    "            print(\"Step 2c took {} r-iterations and {} s-iterations\".format(ctr_r, ctr_s))\n",
    "            \n",
    "        else:\n",
    "            raise(\"wut\")\n",
    "                    \n",
    "            \n",
    "        \n",
    "        # Step 3\n",
    "        if i == 1:\n",
    "            print(\"Skipping first iteration of step 3.\")\n",
    "            M.append(copy.deepcopy(M[0]))\n",
    "            i += 1\n",
    "            continue\n",
    "        print(\"Step 3 - starting with {} interval{}\".format(len(M[i-1]), \"s\"*(len(M[i-1]) > 1)))\n",
    "        if len(M[i-1]) == 1:\n",
    "            print(\"         of length {}\".format(M[i-1][0][1] - M[i-1][0][0]))\n",
    "        before_len = total_length(M[i-1])\n",
    "        M.append([]) # Ensure at best that the base interval is the same\n",
    "        for a,b in M[i-1]:\n",
    "            for r in range((a*s[i] - 3*B + 1) // n, (b*s[i] - 2*B) // n + 1):\n",
    "                lo = max(a, math.ceil((2*B + r*n) // s[i]))\n",
    "                hi = min(b, math.floor((3*B - 1 + r*n) // s[i]))\n",
    "                if lo < hi and hi <= 3*B - 1 and lo >= 2*B :\n",
    "\n",
    "                    M[i] = insert_interval(copy.deepcopy(M[i]), [lo, hi])\n",
    "        after_len = total_length(M[i])\n",
    "        print(\"Step 3 - ending with {} interval{}\".format(len(M[i]), \"s\"*(len(M[i]) > 1)))\n",
    "        if len(M[i]) == 1:\n",
    "            print(\"         of length {}\".format(M[i][0][1] - M[i][0][0]))\n",
    "        print(\"         Size shrunk by {}%\".format(round((before_len - after_len) / before_len * 100, 4)))\n",
    "\n",
    "        # Step 4\n",
    "        if len(M[i]) == 1 and M[i][0][1] - M[i][0][0] == 1:\n",
    "            m = M[i][0][1] # s0 is 1, so its inverse is also 1.\n",
    "            print(\"Found solution :\")\n",
    "            print(unpkcs1(m))\n",
    "            return unpkcs1(m)\n",
    "        \n",
    "        # And rollover to next iteration\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1\n",
      "Step 2a\n",
      "Step 2a took 47808 iterations (s1 = 62541)\n",
      "Skipping first iteration of step 3.\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1096 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 204586912993508866875824356051724947013540127877691549342705710506008362275292159680204380770369009821930417757972504438076078534117837065833032974335\n",
      "Step 3 - ending with 3 intervals\n",
      "         Size shrunk by 99.9971%\n",
      "Step 2b\n",
      "Step 2b took 41692 iterations\n",
      "Step 3 - starting with 3 intervals\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1300743003413436951108762615217811364344525186770866346798169584726774678483695971834915706655691307350267236884404490681048739063944462584060187\n",
      "         Size shrunk by 77.9097%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1300743003413436951108762615217811364344525186770866346798169584726774678483695971834915706655691307350267236884404490681048739063944462584060187\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 700993010157541182978500670035000315273579945649664554905057376508065232412523289739027458242228141639559702171889630869225529749969460878706174\n",
      "         Size shrunk by 46.1083%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 700993010157541182978500670035000315273579945649664554905057376508065232412523289739027458242228141639559702171889630869225529749969460878706174\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 350497105547337896498786811919933779929142508420677481506421412367563002330444590469851004823273759556506142243038014815833475015834774527943110\n",
      "         Size shrunk by 49.9999%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 350497105547337896498786811919933779929142508420677481506421412367563002330444590469851004823273759556506142243038014815833475015834774527943110\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 167642674345612076187303349988995965036114116662673336547526513227872827084394513970551098984953543696903405933922833434730501565169253396363005\n",
      "         Size shrunk by 52.17%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 167642674345612076187303349988995965036114116662673336547526513227872827084394513970551098984953543696903405933922833434730501565169253396363005\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 89217592337397020079526635096209382145458454639237210277296817704941410589528847637132583280691445605809377760361090285203226575337579827088661\n",
      "         Size shrunk by 46.7811%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 89217592337397020079526635096209382145458454639237210277296817704941410589528847637132583280691445605809377760361090285203226575337579827088661\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 44608805895347690076702041877772545298722621202681398255589422393702988452490470892899175855273542914068135862338907851210757064683163909872463\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 44608805895347690076702041877772545298722621202681398255589422393702988452490470892899175855273542914068135862338907851210757064683163909872463\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 21246674825762168118789524343138706970039026985861085412519061299952762202008997859412021209920081852447788454050461263254971561281957497067561\n",
      "         Size shrunk by 52.3711%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 21246674825762168118789524343138706970039026985861085412519061299952762202008997859412021209920081852447788454050461263254971561281957497067561\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9525648502220682492709225855494416256729981018581771466066058186537623607771402465399396682589141486891359299913031576994422749729025939730845\n",
      "         Size shrunk by 55.1664%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9525648502220682492709225855494416256729981018581771466066058186537623607771402465399396682589141486891359299913031576994422749729025939730845\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5595176665425918414311494659771258238912975458813776461640072803921784990716695258687071007863504012414823445103156645570445976251846671791432\n",
      "         Size shrunk by 41.262%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5595176665425918414311494659771258238912975458813776461640072803921784990716695258687071007863504012414823445103156645570445976251846671791432\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2797588370968097191480882669223797018692300959710653827458594588841882569709800554061915531334495083497293088429952246625296793190035187815488\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2797588370968097191480882669223797018692300959710653827458594588841882569709800554061915531334495083497293088429952246625296793190035187815488\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1398794195047833287989202943033313149891049646741817368699029572694903534323987924449180704875939015686309031535347130338005770266050903502338\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1398794195047833287989202943033313149891049646741817368699029572694903534323987924449180704875939015686309031535347130338005770266050903502338\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 665258386708415031031997313127560421913629179125150536326501531006261408526371731601317061555883900781304284674704289823322550091831910794660\n",
      "         Size shrunk by 52.4406%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 665258386708415031031997313127560421913629179125150536326501531006261408526371731601317061555883900781304284674704289823322550091831910794660\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 349723474359277990481508449201886813217925468564930674916482342553652678986068331822257001959038292775058218893388699476306329295552596898771\n",
      "         Size shrunk by 47.4304%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 349723474359277990481508449201886813217925468564930674916482342553652678986068331822257001959038292775058218893388699476306329295552596898771\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 174861737329094435514127505275219879570915597929665918402899057423243363669194676147372021356422381830466745547436881148904366936218038208007\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 174861737329094435514127505275219879570915597929665918402899057423243363669194676147372021356422381830466745547436881148904366936218038208007\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 87430868701911077873309766522500258185870702391429123062101851680965592500389296178047089056059107279553334451092326357582241982077160906229\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 87430868701911077873309766522500258185870702391429123062101851680965592500389296178047089056059107279553334451092326357582241982077160906229\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 41581080482082092338320148493485552613499685471150827383922474560991764063793022418282042775650986132139438582430687408435340718656706590882\n",
      "         Size shrunk by 52.4412%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 41581080482082092338320148493485552613499685471150827383922474560991764063793022418282042775650986132139438582430687408435340718656706590882\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 21857814548466296011743840473047960932718830877969132457034137519194862086456128083588757399568171532283751996423615744818425466296384636954\n",
      "         Size shrunk by 47.4333%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 21857814548466296011743840473047960932718830877969132457034137519194862086456128083588757399568171532283751996423615744818425466296384636954\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 10395300734723891749798152059208497528952081604471946886523502697025773981447696727765165445775276950241477368551236410687694862070274308626\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 10395300734723891749798152059208497528952081604471946886523502697025773981447696727765165445775276950241477368551236410687694862070274308626\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5464459722962246220657982992717991054303005328568494439317464625044790479600211863609617105131260801681289485754474930036510940550845076092\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5464459722962246220657982992717991054303005328568494439317464625044790479600211863609617105131260801681289485754474930036510940550845076092\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2598827097077972598314615093473001249389662696468748364907176834003973698081527016035391918601837584724804318775458337758759702878627573310\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2598827097077972598314615093473001249389662696468748364907176834003973698081527016035391918601837584724804318775458337758759702878627573310\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1366115311106445592317583483003635910929881797053987541542993846447691375388013923391047854973633335316478611224699074233313156309589583963\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1366115311106445592317583483003635910929881797053987541542993846447691375388013923391047854973633335316478611224699074233313156309589583963\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 649706893856950771689064727987007103355053977971770095212150523290462527165783229840560146612839584008332414285974009236933803891751322606\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 649706893856950771689064727987007103355053977971770095212150523290462527165783229840560146612839584008332414285974009236933803891751322606\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 291502647832694345971367888576049777695692383817602152601240011874876871141983306931267825010994961339550389950194860596557965292413845685\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 291502647832694345971367888576049777695692383817602152601240011874876871141983306931267825010994961339550389950194860596557965292413845685\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32764201295112681216462578215979826741558381844602263818036595821804121454854770922650678780717351277837428865552910212894931976786820951\n",
      "         Size shrunk by 88.7602%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32764201295112681216462578215979826741558381844602263818036595821804121454854770922650678780717351277837428865552910212894931976786820951\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32764201295112681216462578215979826741558381844602263818036595821804121454854770922650678780717351277837428865552910212894931976786820951\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32764201295112681216462578215979826741558381844602263818036595821804121454854770922650678780717351277837428865552910212894931976786820951\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32764201295112681216462578215979826741558381844602263818036595821804121454854770922650678780717351277837428865552910212894931976786820951\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32764201295112681216462578215979826741558381844602263818036595821804121454854770922650678780717351277837428865552910212894931976786820951\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 20240789670438925634686963048036654847420787382048825839696147649615234967883628810628344974768729388147224128949525184125279183477491849\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 20240789670438925634686963048036654847420787382048825839696147649615234967883628810628344974768729388147224128949525184125279183477491849\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 10151670831737608077167996376117282349635138473688496638770856543356566927718490293962987410888748843241209868122302519204001020326640035\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 10151670831737608077167996376117282349635138473688496638770856543356566927718490293962987410888748843241209868122302519204001020326640035\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5336388473771236919880116550786632048016803750225092168320148796243871191381710537948550633025766153501274957930204635403066553552903514\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5336388473771236919880116550786632048016803750225092168320148796243871191381710537948550633025766153501274957930204635403066553552903514\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2537917709759162547470197468862272522692472299519381682885386186601750541782683797575243396595450205245543081479277640705303998351423547\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2537917709759162547470197468862272522692472299519381682885386186601750541782683797575243396595450205245543081479277640705303998351423547\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 255970324432794332830328084968125886831339697480282395377655520847356244302191163830267907735104895579535965252302172038041599731472725\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 255970324432794332830328084968125886831339697480282395377655520847356244302191163830267907735104895579535965252302172038041599731472725\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 255970324432794332830328084968125886831339697480282395377655520847356244302191163830267907735104895579535965252302172038041599731472725\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 255970324432794332830328084968125886831339697480282395377655520847356244302191163830267907735104895579535965252302172038041599731472725\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 255970324432794332830328084968125886831339697480282395377655520847356244302191163830267907735104895579535965252302172038041599731472725\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 255970324432794332830328084968125886831339697480282395377655520847356244302191163830267907735104895579535965252302172038041599731472725\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 158131169050261444096461700734738795745918692916410202378207073714764884564074400653261286199071840431589485101788683490901699552754932\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 158131169050261444096461700734738795745918692916410202378207073714764884564074400653261286199071840431589485101788683490901699552754932\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 83381069922513926777016853713096907642023919335898047837736838890015275173736660686783863321785927881577962746691876434972893960145193\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 83381069922513926777016853713096907642023919335898047837736838890015275173736660686783863321785927881577962746691876434972893960145193\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 41690534961256971884167704001690007033891561463763314484558361579557149289074223662315782169500909387525532300747883110130413608522725\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 41690534961256971884167704001690007033891561463763314484558361579557149289074223662315782169500909387525532300747883110130413608522725\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 20845267480628488065998671287131041034309434814507922080054749810178540051149955734997701049346825605481270323913330383327645755229401\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 20845267480628488065998671287131041034309434814507922080054749810178540051149955734997701049346825605481270323913330383327645755229401\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 10422633740314244563978040465137111048263600132148553582519388949048302804502724293659259997662058001388925527356369861686366740521574\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 10422633740314244563978040465137111048263600132148553582519388949048302804502724293659259997662058001388925527356369861686366740521574\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5211316870157122414733696437961463300880016897829486956545212356875740256444325057166536879575954927071284748034147756910707886806485\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5211316870157122414733696437961463300880016897829486956545212356875740256444325057166536879575954927071284748034147756910707886806485\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2605658435078561240553017270328959862623437175670104319428768642202245988848227227966992363249565405122061621584788535596842673310780\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2605658435078561240553017270328959862623437175670104319428768642202245988848227227966992363249565405122061621584788535596842673310780\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1239217632011522722981554057809640589797852408953244156868027389945600127847846395261140409183795209292965761282264938414283662380865\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1239217632011522722981554057809640589797852408953244156868027389945600127847846395261140409183795209292965761282264938414283662380865\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 651414608769726795368937708257560913233073729205816683516544318700906232756439124252583247076101011132345827795874153844822019126800\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 651414608769726795368937708257560913233073729205816683516544318700906232756439124252583247076101011132345827795874153844822019126800\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 325707304384863398203002745556234216436642949639359799916612580690076894216736377553437261149195426537706556451102868634141993173074\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 325707304384863398203002745556234216436642949639359799916612580690076894216736377553437261149195426537706556451102868634141993173074\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 162853652192431699231134845634980548482917423451674030502265952187178083543076260656861839700193169124276352001223214801096657200302\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 162853652192431699231134845634980548482917423451674030502265952187178083543076260656861839700193169124276352001223214801096657200302\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 77451102000728606176677376910128529914024177437645524627744126986245257439444424856765644107429585668691821797921442679322180652815\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 77451102000728606176677376910128529914024177437645524627744126986245257439444424856765644107429585668691821797921442679322180652815\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 40713413048108262640716068451227980437566460504529420719241766326092577291151967965845235658503493871348764441634078327501461666557\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 40713413048108262640716068451227980437566460504529420719241766326092577291151967965845235658503493871348764441634078327501461666557\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 20356706524054131322383557239002515089617917936045448003420774687457858296927251218852993021707644084294105192017819857280385687705\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 20356706524054131322383557239002515089617917936045448003420774687457858296927251218852993021707644084294105192017819857280385687705\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9681387750091137412041348545254565241576511960249253414504675327276964677242128568054617627446376485910857150905988777760824834918\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9681387750091137412041348545254565241576511960249253414504675327276964677242128568054617627446376485910857150905988777760824834918\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4343728363109632152509923703438691783976863342243883104634598133306851031694268028648274713957395949679209503483564627449414566822\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4343728363109632152509923703438691783976863342243883104634598133306851031694268028648274713957395949679209503483564627449414566822\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2544588315506770374214323119837529881102452515805649430758176926707040489102446609747757288329050507302809553482905958591139244492\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2544588315506770374214323119837529881102452515805649430758176926707040489102446609747757288329050507302809553482905958591139244492\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1272294157753385187115073759189813890448645292125035146749936040876387914132709801733625985381172490196122771120327100150640149647\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1272294157753385187115073759189813890448645292125035146749936040876387914132709801733625985381172490196122771120327100150640149647\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 636147078876692593559514929412669182698695856393822063438082317820610102441363920546469999270439141432946048181127798711874754974\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 636147078876692593559514929412669182698695856393822063438082317820610102441363920546469999270439141432946048181127798711874754974\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 302543367190348313640890704985602506230198274774395636773991102696542555585618629273428049641754401056652402240978198042091917376\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 302543367190348313640890704985602506230198274774395636773991102696542555585618629273428049641754401056652402240978198042091917376\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 159036769719173153544800185555168460837936557589501916376827230013992999760866888638128330206864559423958258048591247892249735425\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 159036769719173153544800185555168460837936557589501916376827230013992999760866888638128330206864559423958258048591247892249735425\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15257020262312816006204023302938657618288928928461294808900520996050565993596378504357462899463987390126166709938026684384869551\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15257020262312816006204023302938657618288928928461294808900520996050565993596378504357462899463987390126166709938026684384869551\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15257020262312816006204023302938657618288928928461294808900520996050565993596378504357462899463987390126166709938026684384869551\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15257020262312816006204023302938657618288928928461294808900520996050565993596378504357462899463987390126166709938026684384869551\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15257020262312816006204023302938657618288928928461294808900520996050565993596378504357462899463987390126166709938026684384869551\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15257020262312816006204023302938657618288928928461294808900520996050565993596378504357462899463987390126166709938026684384869551\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9425352159133635575643846081508292018026742988025654639390214537736788475437920318986526924779352705695486124467887123261796585\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9425352159133635575643846081508292018026742988025654639390214537736788475437920318986526924779352705695486124467887123261796585\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4727240112349192532219806114833423869994728783750067960529454107541030740357457613224329287852457615490585776738163940494999141\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4727240112349192532219806114833423869994728783750067960529454107541030740357457613224329287852457615490585776738163940494999141\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2120961114799627758138649248107369136266740613793782205655862453059600858347827779719632510517714195219894773594978985180912377\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2120961114799627758138649248107369136266740613793782205655862453059600858347827779719632510517714195219894773594978985180912377\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1242474763431040260496665751781261976154191044335134230536173124421018593326583239353415548803813545511418486664148682784886010\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1242474763431040260496665751781261976154191044335134230536173124421018593326583239353415548803813545511418486664148682784886010\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 621237381715520130248334762305938759986425512922412185227861421342697917814444341024825648063584550406745754407894362375573266\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 621237381715520130248334762305938759986425512922412185227861421342697917814444341024825648063584550406745754407894362375573266\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 59597735399659437691541393929897742022778698030373319003477215114933189555286256601409167347438606925423855063651649980765248\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 59597735399659437691541393929897742022778698030373319003477215114933189555286256601409167347438606925423855063651649980765248\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 59597735399659437691541393929897742022778698030373319003477215114933189555286256601409167347438606925423855063651649980765248\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 59597735399659437691541393929897742022778698030373319003477215114933189555286256601409167347438606925423855063651649980765248\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 59597735399659437691541393929897742022778698030373319003477215114933189555286256601409167347438606925423855063651649980765248\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 59597735399659437691541393929897742022778698030373319003477215114933189555286256601409167347438606925423855063651649980765248\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 36817781871615763935485313068451090699562494821446906273168712498385509984763429978693060479274916536724748693610829511724870\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 36817781871615763935485313068451090699562494821446906273168712498385509984763429978693060479274916536724748693610829511724870\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 18465781688864033337229584769769754965051648030270404774047404901062686939578505572577250786151949504977365048408459976203782\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 18465781688864033337229584769769754965051648030270404774047404901062686939578505572577250786151949504977365048408459976203782\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9706834089305002035072653084037535231105106650094736467152034650115971290657872899425203447668475160703459429597875908696356\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9706834089305002035072653084037535231105106650094736467152034650115971290657872899425203447668475160703459429597875908696356\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4616445422216008334313433818577708513997575242462216920575969668801113815332829706874671827246219697492350328350602479425207\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4616445422216008334313433818577708513997575242462216920575969668801113815332829706874671827246219697492350328350602479425207\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2426708522326250508769363494689317970729946866756562581400047141699164355461882273786096341904053197574340059858400551827673\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2426708522326250508769363494689317970729946866756562581400047141699164355461882273786096341904053197574340059858400551827673\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1213354261163125254384681754540762301755618765601210144057515108522055084936132671754834806976727016687387371470127461774804\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1213354261163125254384681754540762301755618765601210144057515108522055084936132671754834806976727016687387371470127461774804\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 606677130581562627192340879069406979975470715856337301372494723803991577778974539016353536477385718944148380642175986184119\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 606677130581562627192340879069406979975470715856337301372494723803991577778974539016353536477385718944148380642175986184119\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 288527838888500520894706686544858760057689731787787028540903812586222925725262882769240732146974677367548608983219980921274\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 288527838888500520894706686544858760057689731787787028540903812586222925725262882769240732146974677367548608983219980921274\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 129453193041969467745882214528958572459405210142304450095276246882973986138746215454054901901097461021335835512573678503798\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 129453193041969467745882214528958572459405210142304450095276246882973986138746215454054901901097461021335835512573678503798\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 75834641322695328399046126107768622455660255402727387072677052026080393244606829266460748058487619333947410967276490970284\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 75834641322695328399046126107768622455660255402727387072677052026080393244606829266460748058487619333947410967276490970284\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 37917320661347664199523063060911755872742867283613299262271942753969071592291784699201978159510224811654558675368778186704\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 37917320661347664199523063060911755872742867283613299262271942753969071592291784699201978159510224811654558675368778186704\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3637557092264369976336403404445085151769152885835140305634801871517371569549854502689539400843683922854065680795304740140\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3637557092264369976336403404445085151769152885835140305634801871517371569549854502689539400843683922854065680795304740140\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3637557092264369976336403404445085151769152885835140305634801871517371569549854502689539400843683922854065680795304740140\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3637557092264369976336403404445085151769152885835140305634801871517371569549854502689539400843683922854065680795304740140\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3637557092264369976336403404445085151769152885835140305634801871517371569549854502689539400843683922854065680795304740140\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3637557092264369976336403404445085151769152885835140305634801871517371569549854502689539400843683922854065680795304740140\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2247179069312485591758755825394307023915405501508976681159453115426459802809458327646832255254655194238600459287529654861\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2247179069312485591758755825394307023915405501508976681159453115426459802809458327646832255254655194238600459287529654861\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1184916270667114506235095148596164962828650776851097440433419354936737013427229335344239326883220953686815860756119484809\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1184916270667114506235095148596164962828650776851097440433419354936737013427229335344239326883220953686815860756119484809\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 592458135333557253117547574299798166142087287737621376208359049851180771938825927525994179940452947958801739930483484331\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 592458135333557253117547574299798166142087287737621376208359049851180771938825927525994179940452947958801739930483484331\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 296229067666778626558773787150328004252984118696828852102093731174512340586176212068675851795683957787028841439254022223\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 296229067666778626558773787150328004252984118696828852102093731174512340586176212068675851795683957787028841439254022223\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 140882733832275644968122351764846958626578181675315503862896510404215296395767602143048651762638276010032475627017455535\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 140882733832275644968122351764846958626578181675315503862896510404215296395767602143048651762638276010032475627017455535\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 74057266916694656639693447905377408773994711166293743713059910712191286436798937769267970754758595703512577007859503290\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 74057266916694656639693447905377408773994711166293743713059910712191286436798937769267970754758595703512577007859503290\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 35220683458068911242030588292647834460716176624590678449987684612572797373328570469485990901487541883943870918288113079\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 35220683458068911242030588292647834460716176624590678449987684612572797373328570469485990901487541883943870918288113079\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3552301847914423805016023534655934188207222198353524733509705534274655199166225705423354472101864916629083649009117656\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3552301847914423805016023534655934188207222198353524733509705534274655199166225705423354472101864916629083649009117656\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3552301847914423805016023534655934188207222198353524733509705534274655199166225705423354472101864916629083649009117656\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3552301847914423805016023534655934188207222198353524733509705534274655199166225705423354472101864916629083649009117656\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3552301847914423805016023534655934188207222198353524733509705534274655199166225705423354472101864916629083649009117656\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3552301847914423805016023534655934188207222198353524733509705534274655199166225705423354472101864916629083649009117656\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2194510809875474210701909870544886191368014874447492856500491928412141955986365620970592499027917499862890489329590477\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2194510809875474210701909870544886191368014874447492856500491928412141955986365620970592499027917499862890489329590477\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1100646358064653476313455887650431454791505754462306508381456061119963865722401759097288457942408991783278354433391843\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1100646358064653476313455887650431454791505754462306508381456061119963865722401759097288457942408991783278354433391843\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 493824741523626204474973704026073159775948652328486813389735174110957368171929495656971321965244163848951408266843483\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 493824741523626204474973704026073159775948652328486813389735174110957368171929495656971321965244163848951408266843483\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 289286198893338502498802531886728465146465730001692100151307071836357555738295728738634044486794531697265934328311043\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 289286198893338502498802531886728465146465730001692100151307071836357555738295728738634044486794531697265934328311043\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 137580794758081684539181985968945176290851035610108441888124335288671808193084578630632595332120882434816063078035293\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 137580794758081684539181985968945176290851035610108441888124335288671808193084578630632595332120882434816063078035293\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 72321549723334625624700632972748129057947026259475384194771664281418839527701126645057536980452040362642613155836032\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 72321549723334625624700632972748129057947026259475384194771664281418839527701126645057536980452040362642613155836032\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 34395198689520421134795496492571449650185513982946423721715668033325354903615610944846255765240129778023117289808739\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 34395198689520421134795496492571449650185513982946423721715668033325354903615610944846255765240129778023117289808739\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 18080387430833656406175158243253658062694918674809618496003199662919270014800219294740557301626114476899596813148797\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 18080387430833656406175158243253658062694918674809618496003199662919270014800219294740557301626114476899596813148797\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9040193715416828203087579121626829430811438809321913240929432232646231119737797737816793006250924290399646819982820\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9040193715416828203087579121626829430811438809321913240929432232646231119737797737816793006250924290399646819982820\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4299399836190052641849437061583587544278577798993616908389799278458622185272265878657995864770042872446585362541296\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4299399836190052641849437061583587544278577798993616908389799278458622185272265878657995864770042872446585362541296\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2260048428854207050771894780407748385799862235298302879721585555071665426284085930650272262734110071512603267588822\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2260048428854207050771894780407748385799862235298302879721585555071665426284085930650272262734110071512603267588822\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 216815298334620593567872530316998641969945216892241375818511985971554190561082997916610240088093677241548721962002\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 216815298334620593567872530316998641969945216892241375818511985971554190561082997916610240088093677241548721962002\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 216815298334620593567872530316998641969945216892241375818511985971554190561082997916610240088093677241548721962002\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 216815298334620593567872530316998641969945216892241375818511985971554190561082997916610240088093677241548721962002\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 216815298334620593567872530316998641969945216892241375818511985971554190561082997916610240088093677241548721962002\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 216815298334620593567872530316998641969945216892241375818511985971554190561082997916610240088093677241548721962002\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 133942310173063611493036491092454194536156844528922218833667309395578268870007181893410821153490978723618592550080\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 133942310173063611493036491092454194536156844528922218833667309395578268870007181893410821153490978723618592550080\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 67178122440469572528897454087270127928239190745870250477062775722656841852361894838141384497041544592315008493216\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 67178122440469572528897454087270127928239190745870250477062775722656841852361894838141384497041544592315008493216\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 35313256700846985168310855943870306495236348409134491836398690788487690058425457401090892497753920536263074578215\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 35313256700846985168310855943870306495236348409134491836398690788487690058425457401090892497753920536263074578215\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 17656628350423492584155427971935153249142008354774449226277835965843947939700552993281824033184179042804060259624\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 17656628350423492584155427971935153249142008354774449226277835965843947939700552993281824033184179042804060259624\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8828314175211746292077713985967576624951962714939025440158540625821999697521549824893172155432997798745974603992\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8828314175211746292077713985967576624951962714939025440158540625821999697521549824893172155432997798745974603992\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4414157087605873146038856992983788312571220991857462926834175973636006280684757901393171824022238916668450136986\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4414157087605873146038856992983788312571220991857462926834175973636006280684757901393171824022238916668450136986\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2099316326264674141528045440227204294524387564304302539232883765526889865954583891007755925496980846908007110552\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2099316326264674141528045440227204294524387564304302539232883765526889865954583891007755925496980846908007110552\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1103539271901468286509714248245947326343244940111851422914877446571131894951822749011515752020189259545236587853\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1103539271901468286509714248245947326343244940111851422914877446571131894951822749011515752020189259545236587853\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 551769635950734143254857124122973663173110589343237433437984124234394173644154776807399926731521023790801450094\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 551769635950734143254857124122973663173110589343237433437984124234394173644154776807399926731521023790801450094\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 275884817975367071627428562061486831586927324493446647214128412354404143364139744022294929344846483678256933209\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 275884817975367071627428562061486831586927324493446647214128412354404143364139744022294929344846483678256933209\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 131207270391542133845502840014200292617879146596645756213483153161585302396687433494134234935299604494076738005\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 131207270391542133845502840014200292617879146596645756213483153161585302396687433494134234935299604494076738005\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 68971204493841767906857140515371708866264798670812777784806843140015839119511626838569702155728218996885210485\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 68971204493841767906857140515371708866264798670812777784806843140015839119511626838569702155728218996885210485\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 34485602246920883953428570257685854433138212301372450306389927042464279818388973069599653194831126441887609908\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 34485602246920883953428570257685854433138212301372450306389927042464279818388973069599653194831126441887609908\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 16400908798942766730687855001775036754132893466369097263408781866710612185995398744873173134538504486462512850\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 16400908798942766730687855001775036754132893466369097263408781866710612185995398744873173134538504486462512850\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8621400561730220988357142564421463623433505693272036263804899573919426495397151675974281112196760058052215385\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8621400561730220988357142564421463623433505693272036263804899573919426495397151675974281112196760058052215385\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4100227199735691682671963750443759193296070585047226307033573652573273191381063388568878379994709127826411290\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4100227199735691682671963750443759193296070585047226307033573652573273191381063388568878379994709127826411290\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2155350140432555247089285641105365906805185961938566796401688506811316409728870762545071548253794259682766430\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2155350140432555247089285641105365906805185961938566796401688506811316409728870762545071548253794259682766430\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1077675070216277623544642820552682953402598657693859630050440450156103869179531764139076150960065684899158872\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1077675070216277623544642820552682953402598657693859630050440450156103869179531764139076150960065684899158872\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 512528399966961460333995468805469899334760776394368501012715639893448653211181343446305120365407132187778537\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 512528399966961460333995468805469899334760776394368501012715639893448653211181343446305120365407132187778537\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 269418767554069405886160705138170738365443563464411122050898606497330026456562632380370766747884353510236343\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 269418767554069405886160705138170738365443563464411122050898606497330026456562632380370766747884353510236343\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 134709383777034702943080352569085369182721870431027064648099243822890726733204706913980686170325538660675082\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 134709383777034702943080352569085369182721870431027064648099243822890726733204706913980686170325538660675082\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 67354691888517351471540176284542684591360957390218908229712107055001791742833201137961070045093805505172857\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 67354691888517351471540176284542684591360957390218908229712107055001791742833201137961070045093805505172857\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32033024997935091270874716800341868709865583228607712517107769413872300135143294084558725651600062798314882\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32033024997935091270874716800341868709865583228607712517107769413872300135143294084558725651600062798314882\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 16838672972129337867885044071135671147898028015683423207968216193275073166811983218311347901602767352056707\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 16838672972129337867885044071135671147898028015683423207968216193275073166811983218311347901602767352056707\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8008256249483772817718679200085467177484564627412757871674942605947230078940223517909739610376814761179278\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8008256249483772817718679200085467177484564627412757871674942605947230078940223517909739610376814761179278\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3593047888160990292635496764560365192272150859369070939038257242415133742773801451490507597155356900629465\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3593047888160990292635496764560365192272150859369070939038257242415133742773801451490507597155356900629465\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2104834121516167233485630508891958893489962302468989095736851362372342304387169947693467940205547999590601\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2104834121516167233485630508891958893489962302468989095736851362372342304387169947693467940205547999590601\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1001032031185471602214834900010683397186239800335131949950458315597982748690103100852792694624981014146368\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1001032031185471602214834900010683397186239800335131949950458315597982748690103100852792694624981014146368\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 526208530379041808371407627222989723372547009863466703768724744332855717924042522272864892004523030847217\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 526208530379041808371407627222989723372547009863466703768724744332855717924042522272864892004523030847217\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 250258007796367900553708725002670849296577693072318954032925126021057362021309455455821907999792466965047\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 250258007796367900553708725002670849296577693072318954032925126021057362021309455455821907999792466965047\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25240622732627740312352838264430181706060418271558961862995419084945489520058359332834747698001854508699\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25240622732627740312352838264430181706060418271558961862995419084945489520058359332834747698001854508699\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25240622732627740312352838264430181706060418271558961862995419084945489520058359332834747698001854508699\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25240622732627740312352838264430181706060418271558961862995419084945489520058359332834747698001854508699\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25240622732627740312352838264430181706060418271558961862995419084945489520058359332834747698001854508699\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25240622732627740312352838264430181706060418271558961862995419084945489520058359332834747698001854508699\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15592937145040325295766407052573394240611030203615204961108135503340173601778410625753848235748830738497\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15592937145040325295766407052573394240611030203615204961108135503340173601778410625753848235748830738497\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8222008287172528255803244175359214427696239926545681107084963204470227931821181855215064427754118589335\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8222008287172528255803244175359214427696239926545681107084963204470227931821181855215064427754118589335\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4111004143586264127901622087679607213848119963355447768350594217899206999985702938324536948178006017289\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4111004143586264127901622087679607213848119963355447768350594217899206999985702938324536948178006017289\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1955140685909124223075849414083366010129558512741504280863501824566510421509385048647257014619718962422\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1955140685909124223075849414083366010129558512741504280863501824566510421509385048647257014619718962422\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 877208957070554270662963077285245408270277448756535642148555721707748076518934987428432835209165850138\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 877208957070554270662963077285245408270277448756535642148555721707748076518934987428432835209165850138\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 513875517948283015987702760959950901731015156876523051231308352326987428462061438843824240943207209228\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 513875517948283015987702760959950901731015156876523051231308352326987428462061438843824240943207209228\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 49298091274663555297564137235215198644649661436281951421456567443030526913675453066035693917186260571\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 49298091274663555297564137235215198644649661436281951421456567443030526913675453066035693917186260571\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 49298091274663555297564137235215198644649661436281951421456567443030526913675453066035693917186260571\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 49298091274663555297564137235215198644649661436281951421456567443030526913675453066035693917186260571\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 49298091274663555297564137235215198644649661436281951421456567443030526913675453066035693917186260571\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 49298091274663555297564137235215198644649661436281951421456567443030526913675453066035693917186260571\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 21140193290704330903532494305386569208789818380317953605819004995334954179756403666289173165061505007\n",
      "         Size shrunk by 57.1176%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 21140193290704330903532494305386569208789818380317953605819004995334954179756403666289173165061505007\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3081130704666472206097758577200949915290603859240676853103786881644117356799532170681824209918306325\n",
      "         Size shrunk by 85.4252%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3081130704666472206097758577200949915290603859240676853103786881644117356799532170681824209918306325\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3081130704666472206097758577200949915290603859240676853103786881644117356799532170681824209918306325\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3081130704666472206097758577200949915290603859240676853103786881644117356799532170681824209918306325\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3081130704666472206097758577200949915290603859240676853103786881644117356799532170681824209918306325\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3081130704666472206097758577200949915290603859240676853103786881644117356799532170681824209918306325\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1903434710087930333955860235909838164137087620914193063646909466529821792665532915336132630316566165\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1903434710087930333955860235909838164137087620914193063646909466529821792665532915336132630316566165\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1003663120992740265600981954999904104943388974581722365244889526407633201310530204682616376101961777\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1003663120992740265600981954999904104943388974581722365244889526407633201310530204682616376101961777\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 477329269020782281024377298360196779816786834739369147809439723684179603363423614940577612989373351\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 477329269020782281024377298360196779816786834739369147809439723684179603363423614940577612989373351\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 214162343034803288736074970040343117253485764798005757393549202954722639024189131300433465643114299\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 214162343034803288736074970040343117253485764798005757393549202954722639024189131300433465643114299\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 125457890124092533200122744374988013117923621832338888275518300781244657632603936694986319842976638\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 125457890124092533200122744374988013117923621832338888275518300781244657632603936694986319842976638\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 59666158627597785128047162295024597477098354344798697304793110443839143884912271467902486116915778\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 59666158627597785128047162295024597477098354344798697304793110443839143884912271467902486116915778\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 31364472531023133300030686093747003279480905458285216787376139024289018820772217408328289133430959\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 31364472531023133300030686093747003279480905458285216787376139024289018820772217408328289133430959\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14916539656899446282011790573756149369274588586262710084272806430247560842419110831741843396317586\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14916539656899446282011790573756149369274588586262710084272806430247560842419110831741843396317586\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7841118132755783325007671523436750819870226364583835116750069995383370605981881429243429106650765\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7841118132755783325007671523436750819870226364583835116750069995383370605981881429243429106650765\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3920559066377891662503835761718375409935113182291917633505859193888290041436756893406022545248202\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3920559066377891662503835761718375409935113182291917633505859193888290041436756893406022545248202\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 376114587971981470470917795068475331456372541723065091420340878259924462270258259759901484676525\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 376114587971981470470917795068475331456372541723065091420340878259924462270258259759901484676525\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 376114587971981470470917795068475331456372541723065091420340878259924462270258259759901484676525\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 376114587971981470470917795068475331456372541723065091420340878259924462270258259759901484676525\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 376114587971981470470917795068475331456372541723065091420340878259924462270258259759901484676525\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 376114587971981470470917795068475331456372541723065091420340878259924462270258259759901484676525\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 232352869883780558344221220203837666520640578699173717875801881159980220824663680841707929278614\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 232352869883780558344221220203837666520640578699173717875801881159980220824663680841707929278614\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 3 - ending with 1 interval\n",
      "         of length 116535466069526924078217113857469916947457723330338725098030341779083944119952216796779493442122\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 116535466069526924078217113857469916947457723330338725098030341779083944119952216796779493442122\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 61258735412154557226622433776849615780236143473308919864224805689824894261342672300435693529506\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 61258735412154557226622433776849615780236143473308919864224805689824894261342672300435693529506\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 29133866517381731019554278464367479236864430832584921736841548948872883364549177257379558960304\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 29133866517381731019554278464367479236864430832584921736841548948872883364549177257379558960304\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15314683853038639306655608444212403945059035868327277767722102740965558571671074672540721771137\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15314683853038639306655608444212403945059035868327277767722102740965558571671074672540721771137\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7283466629345432754888569616091869809216107708146245463106259956224589424547364505481432590062\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7283466629345432754888569616091869809216107708146245463106259956224589424547364505481432590062\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3828670963259659826663902111053100986264758967081822429534644517648223080813731580474667842082\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3828670963259659826663902111053100986264758967081822429534644517648223080813731580474667842082\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1820866657336358188722142404022967452304026927036562305082557033994045392599970513316392075640\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1820866657336358188722142404022967452304026927036562305082557033994045392599970513316392075640\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 957167740814914956665975527763275246566189741770455794108918556437482860071930577139884922977\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 957167740814914956665975527763275246566189741770455794108918556437482860071930577139884922977\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 455216664334089547180535601005741863076006731759140634977263761307129975428938215013225139418\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 455216664334089547180535601005741863076006731759140634977263761307129975428938215013225139418\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 239291935203728739166493881940818811641547435442613960197558228298459908134763749411297353398\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 239291935203728739166493881940818811641547435442613960197558228298459908134763749411297353398\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 119645967601864369583246940970409405820773717721306980098849085181853338778470902579986916417\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 119645967601864369583246940970409405820773717721306980098849085181853338778470902579986916417\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 59822983800932184791623470485204702910386858860653490049442035349082515567007708258578018138\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 59822983800932184791623470485204702910386858860653490049442035349082515567007708258578018138\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 29911491900466092395811735242602351455193429430326745024725390864080219327946918371435149051\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 29911491900466092395811735242602351455193429430326745024725390864080219327946918371435149051\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14225520760440298349391737531429433221125210367473145430638211870880949729341416352546076317\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14225520760440298349391737531429433221125210367473145430638211870880949729341416352546076317\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7477872975116523098952933810650587863798357357581686267578152978900024747139836140833715117\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7477872975116523098952933810650587863798357357581686267578152978900024747139836140833715117\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3738936487558261549476466905325293931899178678790843133789144820536558647701840949200390996\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3738936487558261549476466905325293931899178678790843133789144820536558647701840949200390996\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1778190095055037293673967191428679152640651295934143180909202482244443242431962019359241902\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1778190095055037293673967191428679152640651295934143180909202482244443242431962019359241902\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 797816898803425165772717334480371763011387604505793204189083440168570692347189364896505395\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 797816898803425165772717334480371763011387604505793204189083440168570692347189364896505395\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 467367060944782693684558363165661741487397334848855391857197278894989907339307996047144641\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 467367060944782693684558363165661741487397334848855391857197278894989907339307996047144641\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 233683530472391346842279181582830870743698667424427695928598906365801775052981821768820498\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 233683530472391346842279181582830870743698667424427695928598906365801775052981821768820498\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 116841765236195673421139590791415435371849333712213847964299519912477592872322866820722294\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 116841765236195673421139590791415435371849333712213847964299519912477592872322866820722294\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 55568440470469915427311474732146223520020352997941974412504661559389722105659990236565092\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 55568440470469915427311474732146223520020352997941974412504661559389722105659990236565092\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 29210441309048918355284897697853858842962333428053461991248781425612073540272383980387710\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 29210441309048918355284897697853858842962333428053461991248781425612073540272383980387710\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 13892110117617478856827868683036555880005088249485493603180840194526370385450682235597243\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 13892110117617478856827868683036555880005088249485493603180840194526370385450682235597243\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 6232944521901759107599354175627904398526465660201509409129770709786142413542160880441869\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 6232944521901759107599354175627904398526465660201509409129770709786142413542160880441869\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3651305163631114794410612212231732355370291678506682748914249178221523845633204362135689\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3651305163631114794410612212231732355370291678506682748914249178221523845633204362135689\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1736513764702184857103483585379569485000636031185686700399618890742502236044261795241358\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1736513764702184857103483585379569485000636031185686700399618890742502236044261795241358\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 912826290907778698602653053057933088842572919626670687228732120187698027152628890607367\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 912826290907778698602653053057933088842572919626670687228732120187698027152628890607367\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 456413145453889349301326526528966544421286459813335343614366061112061548753100211232888\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 456413145453889349301326526528966544421286459813335343614366061112061548753100211232888\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 217064220587773107137935448172446185625079503898210837549983347204805381921306954840293\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 217064220587773107137935448172446185625079503898210837549983347204805381921306954840293\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 114103286363472337325331631632241636105321614953333835903594168803520341340530174684370\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 114103286363472337325331631632241636105321614953333835903594168803520341340530174684370\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 57051643181736168662665815816120818052660807476666917951797084417669741532402364934828\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 57051643181736168662665815816120818052660807476666917951797084417669741532402364934828\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 27133027573471638392241931021555773203134937987276354693748402554694307152909841705585\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 27133027573471638392241931021555773203134937987276354693748402554694307152909841705585\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14262910795434042165666453954030204513165201869166729487949312565753450291729577513022\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14262910795434042165666453954030204513165201869166729487949312565753450291729577513022\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7131455397717021082833226977015102256582600934583364743974656283125312190585683718896\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7131455397717021082833226977015102256582600934583364743974656283125312190585683718896\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 684148450040050139197624585119183996460146848627289856723401613855329579127843776761\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 684148450040050139197624585119183996460146848627289856723401613855329579127843776761\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 684148450040050139197624585119183996460146848627289856723401613855329579127843776761\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 684148450040050139197624585119183996460146848627289856723401613855329579127843776761\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 684148450040050139197624585119183996460146848627289856723401613855329579127843776761\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 684148450040050139197624585119183996460146848627289856723401613855329579127843776761\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 422647408202065995909326775661316180995782958596772329926073152718902283778080332355\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 422647408202065995909326775661316180995782958596772329926073152718902283778080332355\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 222857981178656908838538343031721945518206279205730148249207988611855179003027831517\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 222857981178656908838538343031721945518206279205730148249207988611855179003027831517\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 105988388958873587469695043052952239074745851512798260522454965354603308842908756071\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 105988388958873587469695043052952239074745851512798260522454965354603308842908756071\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 55714495294664227209634585757930486379551569801432537062301997785613575251682082792\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 55714495294664227209634585757930486379551569801432537062301997785613575251682082792\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 27857247647332113604817292878965243189775784900716268531150998892810580763120107787\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 27857247647332113604817292878965243189775784900716268531150998892810580763120107787\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 13928623823666056802408646439482621594887892450358134265575499446406238665879820491\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 13928623823666056802408646439482621594887892450358134265575499446406238665879820491\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 6624274309929599216855940190809514942171615719549891282653435396372982517590192476\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 6624274309929599216855940190809514942171615719549891282653435396372982517590192476\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2972099553061370424079587066472961615813477354145769791192403367468521708114840284\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2972099553061370424079587066472961615813477354145769791192403367468521708114840284\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1741077977958257100301080804935327699360986556294766783196937432654216353161288932\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1741077977958257100301080804935327699360986556294766783196937432654216353161288932\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 870538988979128550150540402467663849680493278147383391598468716327111880816268555\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 870538988979128550150540402467663849680493278147383391598468716327111880816268555\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 435269494489564275075270201233831924840246639073691695799234358163556866467040299\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 435269494489564275075270201233831924840246639073691695799234358163556866467040299\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 217634747244782137537635100616915962420123319536845847899617179081778664748246655\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 217634747244782137537635100616915962420123319536845847899617179081778664748246655\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 108817373622391068768817550308457981210061659768422923949808589540889390252804954\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 108817373622391068768817550308457981210061659768422923949808589540889390252804954\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 54408686811195534384408775154228990605030829884211461974904294770444709596072883\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 54408686811195534384408775154228990605030829884211461974904294770444709596072883\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25876071523162496940843516370349667742857873904491762822864982033280884899870143\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25876071523162496940843516370349667742857873904491762822864982033280884899870143\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 13602171702798883596102193788557247651257707471052865493726073692648886264452208\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 13602171702798883596102193788557247651257707471052865493726073692648886264452208\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 6469017880790624235210879092587416935714468476122940705716245508332076933370161\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 6469017880790624235210879092587416935714468476122940705716245508332076933370161\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3400542925699720899025548447139311912814426867763216373431518423164578370202676\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3400542925699720899025548447139311912814426867763216373431518423164578370202676\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1700271462849860449512774223569655956407213433881608186715759211582289199231875\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1700271462849860449512774223569655956407213433881608186715759211582289199231875\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 850135731424930224756387111784827978203606716940804093357879605791144603148572\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 850135731424930224756387111784827978203606716940804093357879605791144603148572\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 404313617549414014700679943286713558482154279757683794107265344270984697027071\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 404313617549414014700679943286713558482154279757683794107265344270984697027071\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 212533932856232556189096777946206994550901679235201023339469901447795357053118\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 212533932856232556189096777946206994550901679235201023339469901447795357053118\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 101078404387353503675169985821678389620538569939420948526816336067749068716827\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 101078404387353503675169985821678389620538569939420948526816336067749068716827\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 45350640152913977418206589759414087155357015291530911120489553377725019342084\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 45350640152913977418206589759414087155357015291530911120489553377725019342084\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 26566741607029069523637097243275874318862709904400127917433737680974851168458\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 26566741607029069523637097243275874318862709904400127917433737680974851168458\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2548651583641954284897538219091236578152130725336409571481502639382378879008\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2548651583641954284897538219091236578152130725336409571481502639382378879008\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2548651583641954284897538219091236578152130725336409571481502639382378879008\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2548651583641954284897538219091236578152130725336409571481502639382378879008\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2548651583641954284897538219091236578152130725336409571481502639382378879008\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2548651583641954284897538219091236578152130725336409571481502639382378879008\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1574484289445228859444434850146309215559746915835039056562159750298019043381\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1574484289445228859444434850146309215559746915835039056562159750298019043381\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 830210675219658422613659288852371072464459684512503997419804302530463818186\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 830210675219658422613659288852371072464459684512503997419804302530463818186\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 415105337609829211306829644426185536232229842256251998709902151265231909094\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 415105337609829211306829644426185536232229842256251998709902151265231909094\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 39822680994405535701524034673300571533627042583381399554398478740349708219\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 39822680994405535701524034673300571533627042583381399554398478740349708219\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 39822680994405535701524034673300571533627042583381399554398478740349708219\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 39822680994405535701524034673300571533627042583381399554398478740349708219\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 39822680994405535701524034673300571533627042583381399554398478740349708219\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 39822680994405535701524034673300571533627042583381399554398478740349708219\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 24601317022581700928819294533536081493121045559922485258783746098406547085\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 24601317022581700928819294533536081493121045559922485258783746098406547085\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 12972041800307162853338426388318298007257182570507874959684442227038497091\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 12972041800307162853338426388318298007257182570507874959684442227038497091\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 6169336205282806620798949329936425147737949825404110627857442386947634094\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 6169336205282806620798949329936425147737949825404110627857442386947634094\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 622229390537586495336313041770321430212922540365334368037476230317964198\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 622229390537586495336313041770321430212922540365334368037476230317964198\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 622229390537586495336313041770321430212922540365334368037476230317964198\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 622229390537586495336313041770321430212922540365334368037476230317964198\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 622229390537586495336313041770321430212922540365334368037476230317964198\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 622229390537586495336313041770321430212922540365334368037476230317964198\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 384395578477839077012801477086501273330016336873788832168496032787602297\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 384395578477839077012801477086501273330016336873788832168496032787602297\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 202688153129799419583412912317473406363393477664185546245069409797476517\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 202688153129799419583412912317473406363393477664185546245069409797476517\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 96395878207543853449983583280256642933405466021939228560272537296056783\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 96395878207543853449983583280256642933405466021939228560272537296056783\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 43249740746416070383268918761648261218411460200816069717874101045346915\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 43249740746416070383268918761648261218411460200816069717874101045346915\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25336019141224927447926614039684175795424184708023193280633676224684564\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25336019141224927447926614039684175795424184708023193280633676224684564\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 12049484775942981681247947910032080366675683252742403570034067162007097\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 12049484775942981681247947910032080366675683252742403570034067162007097\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5406217593302008797908614845206032652301432525102008714734262630668364\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5406217593302008797908614845206032652301432525102008714734262630668364\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 607645889196861811851868204853829521692307168325521843786597881169887\n",
      "         Size shrunk by 88.7602%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 607645889196861811851868204853829521692307168325521843786597881169887\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 607645889196861811851868204853829521692307168325521843786597881169887\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 607645889196861811851868204853829521692307168325521843786597881169887\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 607645889196861811851868204853829521692307168325521843786597881169887\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 607645889196861811851868204853829521692307168325521843786597881169887\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 375386307107264723645313942467286399736344078978309406414546907019143\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 375386307107264723645313942467286399736344078978309406414546907019143\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 197937649540819745686926672185032623401751443031431197504950595505348\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 197937649540819745686926672185032623401751443031431197504950595505348\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 98968824770409872843463336092516311700875721515715598752475297752675\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 98968824770409872843463336092516311700875721515715598752475297752675\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 49484412385204936421731668046258155850437860757857799376237648876337\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 49484412385204936421731668046258155850437860757857799376237648876337\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 23534149953013636096187398261781406966163443853012506972722787425795\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 23534149953013636096187398261781406966163443853012506972722787425795\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 12371103096301234105432917011564538962609465189464449844059412219084\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 12371103096301234105432917011564538962609465189464449844059412219084\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5883537488253409024046849565445351741540860963253126743180696856449\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5883537488253409024046849565445351741540860963253126743180696856449\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 593404188668810363136590043802567892277643719067892425572849493330\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 593404188668810363136590043802567892277643719067892425572849493330\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 593404188668810363136590043802567892277643719067892425572849493330\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 593404188668810363136590043802567892277643719067892425572849493330\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 593404188668810363136590043802567892277643719067892425572849493330\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 593404188668810363136590043802567892277643719067892425572849493330\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 366588190534438206684876896940709374742523514627255279701705963886\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 366588190534438206684876896940709374742523514627255279701705963886\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 193298485879706782897389328305695921290772893585382028813428315923\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 193298485879706782897389328305695921290772893585382028813428315923\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 91930273253959516000732024460083620961575952550830105362198388382\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 91930273253959516000732024460083620961575952550830105362198388382\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 41246166941085882552403372537277470796977482033554143636583424611\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 41246166941085882552403372537277470796977482033554143636583424611\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 24162310734963347862173666038211990161346611698172753601678539491\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 24162310734963347862173666038211990161346611698172753601678539491\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 11491284156744939500091503057510452620196994068853763170274798548\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 11491284156744939500091503057510452620196994068853763170274798548\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5155770867635735319050421567159683849622185254194267954572928077\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5155770867635735319050421567159683849622185254194267954572928077\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 579496277996885120250576214650945207302386444402238696848485834\n",
      "         Size shrunk by 88.7602%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 579496277996885120250576214650945207302386444402238696848485834\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 579496277996885120250576214650945207302386444402238696848485834\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 579496277996885120250576214650945207302386444402238696848485834\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 579496277996885120250576214650945207302386444402238696848485834\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 579496277996885120250576214650945207302386444402238696848485834\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 357996279818787311215700094668661498771995619753178984083697231\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 357996279818787311215700094668661498771995619753178984083697231\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 188768052616901155173231765923531173135520403891974637513113590\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 188768052616901155173231765923531173135520403891974637513113590\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 94384026308450577586615882961765586567760201945987318756556794\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 94384026308450577586615882961765586567760201945987318756556794\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 44887828737284919922232433818400205547644508081460012383885931\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 44887828737284919922232433818400205547644508081460012383885931\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 23596006577112644396653970740441396641940050486496829689139199\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 23596006577112644396653970740441396641940050486496829689139199\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2263657335925332500978813338480254716024947048446244909564398\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2263657335925332500978813338480254716024947048446244909564398\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2263657335925332500978813338480254716024947048446244909564398\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2263657335925332500978813338480254716024947048446244909564398\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2263657335925332500978813338480254716024947048446244909564398\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2263657335925332500978813338480254716024947048446244909564398\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1398422968042137934436328494799458979578107889660855406576942\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1398422968042137934436328494799458979578107889660855406576942\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 701372324020076873784881778412503211681945438772812693498218\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 701372324020076873784881778412503211681945438772812693498218\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 314683280495345173281886081979961172462291580456193112461726\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 314683280495345173281886081979961172462291580456193112461726\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 184343801383692534348859146409698411265156644425756481946400\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 184343801383692534348859146409698411265156644425756481946400\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 87671540502509609223110222301562901460243179846601586687277\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 87671540502509609223110222301562901460243179846601586687277\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 39335410061918146660235760247495146557786447557024139057716\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 39335410061918146660235760247495146557786447557024139057716\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 23042975172961566793607393301212301408144580553219560243300\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 23042975172961566793607393301212301408144580553219560243300\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 11521487586480783396803696650606150704072290276609780121650\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 11521487586480783396803696650606150704072290276609780121650\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5760743793240391698401848325303075352036145138304890060825\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5760743793240391698401848325303075352036145138304890060825\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2880371896620195849200924162651537676018072569152445030413\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2880371896620195849200924162651537676018072569152445030413\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1369867820351712644111097223461920335316299685103149791989\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1369867820351712644111097223461920335316299685103149791989\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 614615782217471041566183753867111664965413243078502172777\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 614615782217471041566183753867111664965413243078502172777\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 360046487077524481150115520331442209502259071144055628801\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 360046487077524481150115520331442209502259071144055628801\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 180023243538762240575057760165721104751129535572027814401\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 180023243538762240575057760165721104751129535572027814401\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 85616738771982040256943576466370020957268730318946861999\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 85616738771982040256943576466370020957268730318946861999\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8635167449666337970652821878357905258273876374993304861\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8635167449666337970652821878357905258273876374993304861\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8635167449666337970652821878357905258273876374993304861\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8635167449666337970652821878357905258273876374993304861\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8635167449666337970652821878357905258273876374993304861\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8635167449666337970652821878357905258273876374993304861\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5334560272377540338273347834775768202125960882800504328\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5334560272377540338273347834775768202125960882800504328\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2675523086624438758029486764574063154914647822467089438\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2675523086624438758029486764574063154914647822467089438\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1406431590146580004492638751294696130868199496656467300\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1406431590146580004492638751294696130868199496656467300\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 703215795073290002246319375647348065434099748328233650\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 703215795073290002246319375647348065434099748328233650\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 351607897536645001123159687823674032717049874164116825\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 351607897536645001123159687823674032717049874164116825\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 175803948768322500561579843911837016358524937082058412\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 175803948768322500561579843911837016358524937082058412\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 87901974384161250280789921955918508179262468541029206\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 87901974384161250280789921955918508179262468541029206\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 41805048228506855594210730696469736795541372226048273\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 41805048228506855594210730696469736795541372226048273\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 18756585150679658250921135066745351103680824068557806\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 18756585150679658250921135066745351103680824068557806\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 10987746798020156285098740244489813522407808567628650\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 10987746798020156285098740244489813522407808567628650\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5225631028563356949276341337058717099442671528256034\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5225631028563356949276341337058717099442671528256034\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2746936699505039071274685061122453380601952141907163\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2746936699505039071274685061122453380601952141907163\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1373468349752519535637342530561226690300976070953582\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1373468349752519535637342530561226690300976070953582\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 653203878570419618659542667132339637430333941032004\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 653203878570419618659542667132339637430333941032004\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 343367087438129883909335632640306672575244017738396\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 343367087438129883909335632640306672575244017738396\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32940549658456184275256431115562077553840165615057\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32940549658456184275256431115562077553840165615057\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32940549658456184275256431115562077553840165615057\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32940549658456184275256431115562077553840165615057\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32940549658456184275256431115562077553840165615057\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32940549658456184275256431115562077553840165615057\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 20349732484350358346074477519133637245658725291445\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 20349732484350358346074477519133637245658725291445\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 10730221482441558872166738520009583517976375554325\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 10730221482441558872166738520009583517976375554325\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5103155301331403270777677086971403417424483914313\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5103155301331403270777677086971403417424483914313\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 514696088413377879300881736180657461778752587735\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 514696088413377879300881736180657461778752587735\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 514696088413377879300881736180657461778752587735\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 514696088413377879300881736180657461778752587735\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 514696088413377879300881736180657461778752587735\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 514696088413377879300881736180657461778752587735\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 317964570067974349157413711236463081963417582679\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 317964570067974349157413711236463081963417582679\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 159473603166606352211802408967856356794515122322\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 159473603166606352211802408967856356794515122322\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 83829855331574678688802644687574871234190434018\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 83829855331574678688802644687574871234190434018\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 39868400791651588052950602241964089198628780581\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 39868400791651588052950602241964089198628780581\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 20957463832893669672200661171893717808547608505\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 20957463832893669672200661171893717808547608505\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9967100197912897013237650560491022299657195145\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9967100197912897013237650560491022299657195145\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 5239365958223417418050165292973429452136902126\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 5239365958223417418050165292973429452136902126\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2491775049478224253309412640122755574914298786\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2491775049478224253309412640122755574914298786\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1309841489555854354512541323243357363034225531\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1309841489555854354512541323243357363034225531\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 622943762369556063327353160030688893728574696\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 622943762369556063327353160030688893728574696\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 327460372388963588628135330810839340758556383\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 327460372388963588628135330810839340758556383\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 155735940592389015831838290007672223432143674\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 155735940592389015831838290007672223432143674\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 69873724694101729433689769606088664768937320\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 69873724694101729433689769606088664768937320\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 40932546548620448578516916351354917594819548\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 40932546548620448578516916351354917594819548\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 20466273274310224289258458175677458797409774\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 20466273274310224289258458175677458797409774\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9733496287024313489489893125479513964508980\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9733496287024313489489893125479513964508980\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4367107793381358089605610600380541548058583\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4367107793381358089605610600380541548058583\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2558284159288778036157307271959682349676221\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2558284159288778036157307271959682349676221\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 245426220137299480104866855707482081307770\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 245426220137299480104866855707482081307770\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 245426220137299480104866855707482081307770\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 245426220137299480104866855707482081307770\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 245426220137299480104866855707482081307770\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 245426220137299480104866855707482081307770\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 151617322000491308764178138368827382070263\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 151617322000491308764178138368827382070263\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 76042939742377449136639790042808702847726\n",
      "         Size shrunk by 49.8455%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 76042939742377449136639790042808702847726\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 34118029635791860075043832815472980844207\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 34118029635791860075043832815472980844207\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 19986594994443578407478963062185018356846\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 19986594994443578407478963062185018356846\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9505367467797181142079973755351087855966\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9505367467797181142079973755351087855966\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4264753704473982509380479101934122605526\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4264753704473982509380479101934122605526\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2498324374305447300934870382773127294606\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2498324374305447300934870382773127294606\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1249162187152723650467435191386563647303\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1249162187152723650467435191386563647303\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 624581093576361825233717595693281823651\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 624581093576361825233717595693281823651\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 312290546788180912616858797846640911825\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 312290546788180912616858797846640911825\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 148521366684330955344999589927360747749\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 148521366684330955344999589927360747749\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14979627693926970221244314923552373127\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14979627693926970221244314923552373127\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14979627693926970221244314923552373127\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14979627693926970221244314923552373127\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14979627693926970221244314923552373127\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14979627693926970221244314923552373127\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9253986938506549607188607078175499394\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9253986938506549607188607078175499394\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4879539793565326759638418716353764247\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4879539793565326759638418716353764247\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2439769896782663379819209358176882123\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2439769896782663379819209358176882123\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1160323177221335588632809296307505841\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1160323177221335588632809296307505841\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 520599817440671693039609265372817700\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 520599817440671693039609265372817700\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 200738137550339745243009249905473630\n",
      "         Size shrunk by 61.441%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 200738137550339745243009249905473630\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 152485618548916461238700584886055132\n",
      "         Size shrunk by 24.0375%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 152485618548916461238700584886055132\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14628542669850556856683901292531614\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14628542669850556856683901292531614\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14628542669850556856683901292531614\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14628542669850556856683901292531614\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 14628542669850556856683901292531614\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 14628542669850556856683901292531614\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9037096619635302350770124099780761\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9037096619635302350770124099780761\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4765175579653639413709393277689223\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4765175579653639413709393277689223\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2266256205510421071548455656850597\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2266256205510421071548455656850597\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1191293894913409853427348319422306\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1191293894913409853427348319422306\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 595646947456704926713674159711153\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 595646947456704926713674159711153\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 297823473728352463356837079855577\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 297823473728352463356837079855577\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 141641012844401316971778478553163\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 141641012844401316971778478553163\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 74455868432088115839209269963894\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 74455868432088115839209269963894\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 35410253211100329242944619638291\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 35410253211100329242944619638291\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15887445600606435944812294475489\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15887445600606435944812294475489\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9306983554011014479901158745487\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9306983554011014479901158745487\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4653491777005507239950579372743\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4653491777005507239950579372743\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2326745888502753619975289686372\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2326745888502753619975289686372\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1106570412846885288842019363697\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1106570412846885288842019363697\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 111606923445515112737151346531\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 111606923445515112737151346531\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 111606923445515112737151346531\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 111606923445515112737151346531\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 111606923445515112737151346531\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 111606923445515112737151346531\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 68947575528223437124405854033\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 68947575528223437124405854033\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 36355404507855525312113901350\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 36355404507855525312113901350\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 17290162700732582638156552558\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 17290162700732582638156552558\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 9088851126963881328028475337\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 9088851126963881328028475337\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4544425563481940664014237669\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4544425563481940664014237669\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2272212781740970332007118834\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2272212781740970332007118834\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1080635168795786414884784535\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1080635168795786414884784535\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 568053195435242583001779708\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 568053195435242583001779708\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 270158792198946603721196133\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 270158792198946603721196133\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 121211590580798614080904346\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 121211590580798614080904346\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 71006649429405322875222463\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 71006649429405322875222463\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 35503324714702661437611232\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 35503324714702661437611232\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 17751662357351330718805616\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 17751662357351330718805616\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8442462256217081366287379\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8442462256217081366287379\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4437915589337832679701404\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4437915589337832679701404\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2218957794668916339850702\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2218957794668916339850702\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1055307782027135170785922\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1055307782027135170785922\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 106436656423106301057006\n",
      "         Size shrunk by 89.9142%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 106436656423106301057006\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 106436656423106301057006\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 106436656423106301057006\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 106436656423106301057006\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 106436656423106301057006\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 65753531959746777653127\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 65753531959746777653127\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 34671215541701817810167\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 34671215541701817810167\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 17335607770850908905084\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 17335607770850908905084\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1663072756611035954016\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1663072756611035954016\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1663072756611035954016\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1663072756611035954016\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1663072756611035954016\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1663072756611035954016\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1027398936871043400831\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1027398936871043400831\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 541737742839090903283\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 541737742839090903283\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 270868871419545451642\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 270868871419545451642\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25985511822047436782\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25985511822047436782\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25985511822047436782\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25985511822047436782\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 25985511822047436782\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 25985511822047436782\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 16053108388610053138\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 16053108388610053138\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 8464652231860795363\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 8464652231860795363\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4232326115930397682\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4232326115930397682\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2012839855245848027\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2012839855245848027\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1058081528982599420\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1058081528982599420\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 503209963811462007\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 503209963811462007\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 225774181225893300\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 225774181225893300\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 132260191122824928\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 132260191122824928\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 12688238194359100\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 12688238194359100\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 12688238194359100\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 12688238194359100\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 12688238194359100\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 12688238194359100\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7838431830376003\n",
      "         Size shrunk by 38.2229%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7838431830376003\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4133130972588279\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4133130972588279\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1965663921138523\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1965663921138523\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1033282743147070\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1033282743147070\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 516641371573535\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 516641371573535\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 258320685786768\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 258320685786768\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 129160342893384\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 129160342893384\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 64580171446692\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 64580171446692\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 32290085723346\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 32290085723346\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15356749383895\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15356749383895\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 6890081214169\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 6890081214169\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 4036260715418\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 4036260715418\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1919593672987\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1919593672987\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1009065178855\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1009065178855\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 504532589427\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 504532589427\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 252266294714\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 252266294714\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 126133147357\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 126133147357\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 59987302281\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 59987302281\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 26914379743\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 26914379743\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15766643419\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15766643419\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7498412785\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7498412785\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3364297468\n",
      "         Size shrunk by 55.1332%\n",
      "Step 2c\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3364297468\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1970830428\n",
      "         Size shrunk by 41.4193%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1970830428\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 985415213\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 985415213\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 492707607\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 492707607\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 246353804\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 246353804\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 123176902\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 123176902\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 58581350\n",
      "         Size shrunk by 52.4413%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 58581350\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 30794225\n",
      "         Size shrunk by 47.4334%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 30794225\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15397112\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15397112\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7698557\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 6 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7698557\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 738553\n",
      "         Size shrunk by 90.4066%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 738553\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 738553\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 738553\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 738553\n",
      "         Size shrunk by 0.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 738553\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 456257\n",
      "         Size shrunk by 38.2228%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 456257\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 240580\n",
      "         Size shrunk by 47.2709%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 240580\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 120290\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 120290\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 60145\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 60145\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 30073\n",
      "         Size shrunk by 49.9992%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 30073\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15036\n",
      "         Size shrunk by 50.0017%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15036\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7519\n",
      "         Size shrunk by 49.9933%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7519\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3759\n",
      "         Size shrunk by 50.0066%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3759\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1880\n",
      "         Size shrunk by 49.9867%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 1880\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 940\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 940\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 470\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 470\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 235\n",
      "         Size shrunk by 50.0%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 235\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 112\n",
      "         Size shrunk by 52.3404%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 112\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 59\n",
      "         Size shrunk by 47.3214%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 59\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 28\n",
      "         Size shrunk by 52.5424%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 28\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 15\n",
      "         Size shrunk by 46.4286%\n",
      "Step 2c\n",
      "Step 2c took 1 r-iterations and 3 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 15\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 7\n",
      "         Size shrunk by 53.3333%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 7\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 3\n",
      "         Size shrunk by 57.1429%\n",
      "Step 2c\n",
      "Step 2c took 0 r-iterations and 1 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 3\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 2\n",
      "         Size shrunk by 33.3333%\n",
      "Step 2c\n",
      "Step 2c took 2 r-iterations and 7 s-iterations\n",
      "Step 3 - starting with 1 interval\n",
      "         of length 2\n",
      "Step 3 - ending with 1 interval\n",
      "         of length 1\n",
      "         Size shrunk by 50.0%\n",
      "Found solution :\n",
      "b\"I'm not a 90s kid\"\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "b\"I'm not a 90s kid\""
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bleichenbacher(B, c_i, alice)"
   ]
  }
 ],
 "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
}