{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# General Number Field Sieve - Interactive Notebook\n",
    "\n",
    "This notebook lets you run the GNFS algorithm on your own hardware.\n",
    "\n",
    "## Setup\n",
    "\n",
    "First, install the required packages:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this cell first to install dependencies\n",
    "!pip install sympy numpy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GNFS Implementation\n",
    "\n",
    "Clone the repository and import the GNFS module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Clone the repository (run once)\n",
    "!git clone https://github.com/toddsmithie/General-Number-Field-Sieve.git\n",
    "\n",
    "# Add to path\n",
    "import sys\n",
    "sys.path.insert(0, './General-Number-Field-Sieve')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Run GNFS Factorization\n",
    "\n",
    "Configure parameters and factor your number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import sympy as sp\n",
    "from gnfs import select_polynomial, find_relations, find_factors\n",
    "\n",
    "# ===== CONFIGURATION =====\n",
    "n = 91                # Integer to factor\n",
    "degree = 1            # Polynomial degree (1 for small numbers, higher for large)\n",
    "bound = 20            # Smoothness bound (max prime in factor base)\n",
    "interval = 50         # Sieve interval (search range)\n",
    "# =========================\n",
    "\n",
    "start = time.time()\n",
    "\n",
    "print(f\"GNFS Factorization of n = {n}\")\n",
    "print(\"=\" * 60)\n",
    "\n",
    "# Step 0: Primality check (polynomial time using Miller-Rabin)\n",
    "print(\"\\nSTEP 0: PRIMALITY CHECK\")\n",
    "print(\"-\" * 60)\n",
    "if sp.isprime(n):\n",
    "    elapsed = time.time() - start\n",
    "    print(\"Number is PRIME - cannot be factored!\")\n",
    "    print(f\"\\n{'='*60}\")\n",
    "    print(f\"RESULT: {n} is prime\")\n",
    "    print(f\"{'='*60}\")\n",
    "    print(f\"Time: {elapsed:.3f}s\")\n",
    "else:\n",
    "    print(f\"{n} is composite - proceeding with factorization...\")\n",
    "    \n",
    "    # Step 1: Polynomial selection\n",
    "    print(\"\\nSTEP 1: POLYNOMIAL SELECTION\")\n",
    "    print(\"-\" * 60)\n",
    "    selection = select_polynomial(n, degree=degree)\n",
    "    print(f\"Choose m = floor(n^(1/d)) = {selection.m}\")\n",
    "    print(f\"Algebraic polynomial f(x) = {selection.algebraic}\")\n",
    "    print(f\"Rational polynomial g(x) = {selection.rational}\")\n",
    "    print(f\"These share root m = {selection.m} modulo n = {n}\")\n",
    "    \n",
    "    # Step 2: Build factor base and sieve\n",
    "    print(\"\\nSTEP 2: SIEVING FOR SMOOTH RELATIONS\")\n",
    "    print(\"-\" * 60)\n",
    "    primes = list(sp.primerange(2, bound + 1))\n",
    "    print(f\"Factor base (primes <= {bound}): {primes}\")\n",
    "    print(f\"Searching for relations in interval [-{interval}, {interval}]...\")\n",
    "    \n",
    "    relations = list(find_relations(selection, primes=primes, interval=interval))\n",
    "    print(f\"Found {len(relations)} smooth relations\")\n",
    "    \n",
    "    if relations:\n",
    "        print(f\"\\nRelations (a, b) where a - {selection.m}*b factors over the base:\")\n",
    "        shown = min(6, len(relations))\n",
    "        for i, rel in enumerate(relations[:shown]):\n",
    "            val = rel.a - selection.m * rel.b\n",
    "            factors_str = \" * \".join(\n",
    "                f\"{p}^{e}\" if e > 1 else str(p) \n",
    "                for p, e in rel.rational_factors.items()\n",
    "            ) if rel.rational_factors else \"1\"\n",
    "            print(f\"  ({rel.a:4}, {rel.b:2}): {rel.a:4} - {selection.m}*{rel.b:2} = {val:5} = {factors_str}\")\n",
    "        if len(relations) > shown:\n",
    "            print(f\"  ... ({len(relations) - shown} more relations)\")\n",
    "    \n",
    "    # Step 3: Linear algebra\n",
    "    print(\"\\nSTEP 3: LINEAR ALGEBRA OVER GF(2)\")\n",
    "    print(\"-\" * 60)\n",
    "    print(f\"Building exponent matrix ({len(relations)} relations x {len(primes)} primes)...\")\n",
    "    print(\"Finding vectors in nullspace (dependencies with even exponents)...\")\n",
    "    \n",
    "    # Step 4: Extract factors\n",
    "    print(\"\\nSTEP 4: SQUARE ROOT AND FACTOR EXTRACTION\")\n",
    "    print(\"-\" * 60)\n",
    "    \n",
    "    factors = list(find_factors(n, relations, primes))\n",
    "    elapsed = time.time() - start\n",
    "    \n",
    "    if factors and len(factors) >= 2:\n",
    "        p, q = factors[0], factors[1]\n",
    "        print(\"Combining relations to form congruence of squares...\")\n",
    "        print(\"Found: x^2 = y^2 (mod n) where x != +/-y\")\n",
    "        print(\"gcd(x - y, n) gives non-trivial factor!\")\n",
    "        print()\n",
    "        print(\"=\" * 60)\n",
    "        print(f\"RESULT: {n} = {p} x {q}\")\n",
    "        print(\"=\" * 60)\n",
    "        print(f\"Verification: {p} x {q} = {p * q}\")\n",
    "        print(f\"Time: {elapsed:.3f}s\")\n",
    "    else:\n",
    "        print(\"No factors found with current parameters.\")\n",
    "        print()\n",
    "        print(\"Tips:\")\n",
    "        print(\"  - Try a smaller semiprime (91, 143 work well)\")\n",
    "        print(\"  - Increase smoothness bound\")\n",
    "        print(\"  - Increase sieve interval\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment with Different Numbers\n",
    "\n",
    "Try these examples or your own:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example: Small semiprimes that work well\n",
    "test_numbers = [\n",
    "    (91, \"7 × 13\"),\n",
    "    (143, \"11 × 13\"),\n",
    "    (221, \"13 × 17\"),\n",
    "    (323, \"17 × 19\"),\n",
    "]\n",
    "\n",
    "for num, note in test_numbers:\n",
    "    print(f\"\\n{'='*60}\")\n",
    "    print(f\"Testing n = {num} ({note})\")\n",
    "    print(f\"{'='*60}\")\n",
    "    # Copy the factorization code from above with n = num"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learn More\n",
    "\n",
    "- **Repository:** https://github.com/toddsmithie/General-Number-Field-Sieve\n",
    "- **Documentation:** See the `book/` directory in the repository\n",
    "- **Algorithm Details:** https://en.wikipedia.org/wiki/General_number_field_sieve"
   ]
  }
 ],
 "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}