CTNT ECM Example.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Factor of F_7 is 59649589127497217\n",
      "Factor of F_8 is 1238926361552897\n",
      "Factor of F_9 is 2424833\n"
     ]
    }
   ],
   "source": [
    "# %load ECM.py\n",
    "# %load ec3.py\n",
    "from math import log\n",
    "import pickle\n",
    "import gmpy2\n",
    "\n",
    "with open('primes10000.pickle','rb') as f:\n",
    "    Primes10000=pickle.load(f)\n",
    "                                                                                                                                                                                                             \n",
    "def ecm(N,arange=100,krange=10000):\n",
    "    for a in range(-arange,arange):\n",
    "        x,y=0,1\n",
    "        for B in Primes10000:\n",
    "            k=B**(int(log(10000)/log(B)))\n",
    "            sx,sy,t=x,y,k\n",
    "            first=True\n",
    "            while t>0:\n",
    "                if t%2==1:\n",
    "                    if first:\n",
    "                        xm,ym=sx,sy\n",
    "                        first=False\n",
    "                    else:\n",
    "                        # x1=xm,y1=ym, x2=sx,y2=sy,a=a,b=1,N=N\n",
    "                        d,u,v=gmpy2.gcdext(sx-xm,N)\n",
    "                        if d>1:\n",
    "                            if d==N:\n",
    "                                break\n",
    "                            else:\n",
    "                                return d\n",
    "                        L=(u*(sy-ym)) % N\n",
    "                        x_sum=(L*L-xm-sx) % N\n",
    "                        ym=(L*(xm-x_sum)-ym) % N\n",
    "                        xm=x_sum\n",
    "                # sx=x,sy=y,a=a,b=1,N\n",
    "                d,u,v=gmpy2.gcdext(2*sy,N)\n",
    "                if d>1:\n",
    "                    if d==N:\n",
    "                        break\n",
    "                    else:\n",
    "                        return d\n",
    "                L=(u*(3*sx*sx+a)) % N\n",
    "                x2=(L*L-2*sx) % N\n",
    "                sy=(L*(sx-x2)-sy) %N\n",
    "                sx=x2\n",
    "                t=t//2\n",
    "            x,y=xm,ym\n",
    "    print('Failed')\n",
    "\n",
    "\n",
    "\n",
    "N=2**(128)+1\n",
    "print('Factor of F_7 is',ecm(N))\n",
    "N=2**(256)+1\n",
    "print('Factor of F_8 is',ecm(N))\n",
    "N=2**(512)+1\n",
    "print('Factor of F_9 is',ecm(N))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5529373746539492451469451709955220061537996975706118061624681552800446063738635599565773930892108210210778168305399196915314944498011438291393118209"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(2**512+1)//2424833"
   ]
  },
  {
   "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
}