PminusOneMethod.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import factorial\n",
    "import numpy as np\n",
    "\n",
    "# Quick sieve of Eratosthenes\n",
    "P=np.zeros(10000)\n",
    "P[0]=1\n",
    "P[1]=1\n",
    "for i in range(2,10000):\n",
    "    if P[i]==0:\n",
    "        j=2\n",
    "        while i*j<1000:\n",
    "            P[i*j]=1\n",
    "            j=j+1\n",
    "\n",
    "Primes10000=[i for i,x in enumerate(P) if x==0]\n",
    "\n",
    "def mexp(a,x,N):\n",
    "    m,s=1,a\n",
    "    while x>0:\n",
    "        if x % 2 ==1:\n",
    "            m=((m*s) % N)\n",
    "        s=((s*s) % N)\n",
    "        x=x//2\n",
    "    return m\n",
    "\n",
    "def euclid(u,v):\n",
    "    if v==0:\n",
    "        raise ArithmeticError('Division by Zero')\n",
    "    x0,x1=u,v\n",
    "    a0,a1=1,0\n",
    "    b0,b1=0,1\n",
    "    while x1!=0:\n",
    "        q=x0//x1\n",
    "        x2=x0-q*x1\n",
    "        a2=a0-q*a1\n",
    "        b2=b0-q*b1\n",
    "        x0,a0,b0=x1,a1,b1\n",
    "        x1,a1,b1=x2,a2,b2\n",
    "    if x0<0:\n",
    "        return -x0,-a0,-b0\n",
    "    else:\n",
    "        return x0,a0,b0\n",
    "\n",
    "def show_factors(N):\n",
    "    for x in Primes10000:\n",
    "        while N % x ==0:\n",
    "            print(x)\n",
    "            N=N//x\n",
    "            if N==1:\n",
    "                break\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1869036133\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(641, -1415069, 615794)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N=2**32+1\n",
    "T=mexp(5,factorial(10),N)-1\n",
    "print(T)\n",
    "euclid(T,N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "3\n",
      "3\n",
      "5\n",
      "7\n",
      "--\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "show_factors(factorial(8))\n",
    "print('--')\n",
    "show_factors(640)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "189001559038533300097388655917426122707\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1,\n",
       " 3112174408228168112550962732800696651,\n",
       " -1728581532088651726610480563918521808)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N=2**128+1\n",
    "T=mexp(3,factorial(500),N)-1\n",
    "print(T)\n",
    "euclid(T,N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}