How I Create a Colab Session That Improves Some Polynomials

[EdH]

(Note: I expect to keep the first post of each of these "How I..." threads up-to-date with the latest version. Please read the rest of each thread to see what may have led to the current set of instructions.)

I will take the liberty of expecting readers to already be somewhat familiar with Google's Colaboratory sessions. There are several threads already on Colab and these should be reviewed by interested readers:

Google Colaboratory Notebook?
GPU72 Notebook Integration...
Notebook Instance Reverse SSH and HTTP Tunnels.
Colab question

I do not, as of yet, have a github account, so I have not created an upload of this to github. Others may feel free to do so, if desired.

The following is a manner to use CADO-NFS size and root optimization to look for improved polynomials. It is based on this thread in the Factoring forum:

Improving Polynomials With CADO-NFS and Msieve Tools

Unfortunately, although I'm creating this thread to show how to create this Colab session, it may not be of much interest. In order for this to run, the first time it is invoked, it takes twenty minutes to build CADO-NFS. Then it takes a couple hours to do a full "spin" for a candidate polynomial. Benefits may be experienced, though, and here are some examples:

Using the Skew Optimizer at cownoise you can compare the Murphy_E scores for the sample polynomial and its spin:

original : 1.27260067e-15
best spin: 1.32925706e-15

To use Colab, you need a Gmail account and will be required to log into that account to run a session.

On to the specifics:

Open a Google Colaboratory session.
Sign in with your Google/Gmail account info.
Choose New Python3 notebook:

Menu->File->New notebook

Click Connect to start a session.
Edit title from Untitled... to whatever you like.
Paste the following into the Codeblock:

########################################################
### This Colaboratory session is designed to improve ###
### a polynomial through a process of repeated size  ###
### and root optimizations using CADO-NFS.           ###
###                                                  ###
### Although more than one polynomial can be entered ###
### initially, a single run of one polynomial may    ###
### use up the limited time for a Colab session.     ###
########################################################

# True runs a shortened session for testing.
test = True

# Relace the below polynomial with the one to spin.
# Be sure to match the formatting exactly:
# ( ' at beginning and ', at the end of each line).
# Make sure the lines immediately before and after are
# undisturbed.
polyinit = [
'n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711',
'skew: 15664544.853',
'c0: -626081313147184760199029071786307655596384808000',
'c1: 114155706290582003827015758825221679754150',
'c2: 9698330805779200485429519766575815',
'c3: -1612013188384034013354246592',
'c4: -71413365342160076609',
'c5: 2982285821808',
'c6: 45360',
'Y0: -66175507466676477845668491119429817',
'Y1: 284594098468775320577861',
]
polyinit.append('')
polyinit.append('')

import os
import shutil
import subprocess
import sys
import time

# This function changes all the signs for all the c# values
# in temp2neg, placing the output in tempneg.  Then it
# appends both temp2neg and tempneg to rawset.
def polynegate():
  inF = open("/content/cado-nfs/polyspin/temp2neg", "r")
  outF = open("/content/cado-nfs/polyspin/tempneg", "w")
  for line in inF:
    if line[:1] == "c":
      if line[4:5] == "-":
        line = line[:4] + line[5:]
      else:
        line = line[:4] + "-" + line[4:]
    outF.write(line)
  outF.close()
  inF.close()
  rawF = open("/content/cado-nfs/polyspin/rawset", "a")
  tnF = open("/content/cado-nfs/polyspin/tempneg", "r")
  inF = open("/content/cado-nfs/polyspin/temp2neg", "r")
  for line in inF:
    rawF.write(line)
  for line in tnF:
    rawF.write(line)
  inF.close()
  tnF.close()
  rawF.close()

# This function performs CADO-NFS size optimizations on
# the polynomials in rawset
def sizeopt(seff):
  sopttemp = open("/content/cado-nfs/polyspin/sopttemp", "w")
  for eff in seff:
#    print("Running sopt at " + str(eff))
    p = subprocess.Popen([sopt, "-inputpolys", "/content/cado-nfs/polyspin/rawset", "-sopteffort", str(eff), "-v"], stdout=subprocess.PIPE, stderr=subprocess.STDOUT)
    for line in iter(p.stdout.readline, b''):
      linet = line.decode("utf=8")
      sopttemp.write(linet)
  sopttemp.close()
  addnewopt("/content/cado-nfs/polyspin/sopttemp")
  print("Current exp_E list:")
  print(*expElist, sep = ", ")
  polynegate()

# This function performs CADO-NFS root optimizations on
# the polynomials in rawset
def rootopt(reff):
  ropttemp = open("/content/cado-nfs/polyspin/ropttemp", "w")
  for eff in reff:
#    print("Running ropt at" + str(eff))
    p = subprocess.Popen([ropt, "-t", "2", "-inputpolys", "/content/cado-nfs/polyspin/rawset", "-area", "1.00e+16", "-Bf", "10000000", "-Bg", "5000000", "-v", "-ropteffort", str(eff)], stdout=subprocess.PIPE, stderr=subprocess.STDOUT)
    for line in iter(p.stdout.readline, b''):
      linet = line.decode("utf=8")
      ropttemp.write(linet)
  ropttemp.close()
  addnewopt("/content/cado-nfs/polyspin/ropttemp")
  print("Current MurphyE list:")
  print(*MurphyElist, sep = ", ")
  polynegate()

# This function searches for new polynomials from either
# the size optimization or root optimization steps.
def addnewopt(opt):
  c5 = ""
  c6 = ""
  t2n = open("/content/cado-nfs/polyspin/temp2neg", "w")
  sF = open(opt, "r")
  for line in sF:
    if line[:3] == "n: ":
      n = line.rstrip()
    if line[:6] == "skew: ":
      skew = line.rstrip()
    if line[:4] == "c0: ":
      c0 = line.rstrip()
    if line[:4] == "c1: ":
      c1 = line.rstrip()
    if line[:4] == "c2: ":
      c2 = line.rstrip()
    if line[:4] == "c3: ":
      c3 = line.rstrip()
    if line[:4] == "c4: ":
      c4 = line.rstrip()
    if line[:4] == "c5: ":
      c5 = line.rstrip()
    if line[:4] == "c6: ":
      c6 = line.rstrip()
    if line[:4] == "Y0: ":
      Y0 = line.rstrip()
    if line[:4] == "Y1: ":
      Y1 = line.rstrip()
    if line[:10] == "# lognorm " and opt[-8:] == "sopttemp":
      expE = line.rstrip()[23:28]
      if not expE in expElist:
        expElist.append(expE)
        t2n.write(n + "\n")
        t2n.write(skew + "\n")
        t2n.write(c0 + "\n")
        t2n.write(c1 + "\n")
        t2n.write(c2 + "\n")
        t2n.write(c3 + "\n")
        t2n.write(c4 + "\n")
        if len(c5) > 0:
          t2n.write(c5 + "\n")
        if len(c6) > 0:
          t2n.write(c6 + "\n")
        t2n.write(Y0 + "\n")
        t2n.write(Y1 + "\n")
        t2n.write("\n")
    if line[:10] == "# MurphyE(" and opt[-8:] == "ropttemp":
      MurphyE = line.rstrip()[-9:]
      if not MurphyE in MurphyElist:
        MurphyElist.append(MurphyE)
        t2n.write(n + "\n")
        t2n.write(skew + "\n")
        t2n.write(c0 + "\n")
        t2n.write(c1 + "\n")
        t2n.write(c2 + "\n")
        t2n.write(c3 + "\n")
        t2n.write(c4 + "\n")
        if len(c5) > 0:
          t2n.write(c5 + "\n")
        if len(c6) > 0:
          t2n.write(c6 + "\n")
        t2n.write(Y0 + "\n")
        t2n.write(Y1 + "\n")
        t2n.write("\n")
  sF.close()
  t2n.close()

# This section determines whether CADO-NFS is already installed.
# If CADO-NFS does not yet exist, it is built. The initial
# building of CADO-NFS takes about twenty minutes.
exists = os.path.isfile('/content/cado-nfs/README.msieve')
if exists < 1:
  fstart = time.time()
  print("Updating and installing system files (libgmp-dev, cmake, git). . .")
  subprocess.call(["apt", "update"])
  subprocess.call(["apt", "install", "libgmp-dev", "cmake", "git"])
  print("Retrieving CADO-NFS. . .")
  subprocess.call(["git", "clone", "https://gitlab.inria.fr/cado-nfs/cado-nfs.git"])
  os.chdir("/content/cado-nfs")
  print("Building CADO-NFS. This will take about twenty minutes. . .")
  p = subprocess.Popen(["make"], stdout=subprocess.PIPE, stderr=subprocess.STDOUT)
  for line in iter(p.stdout.readline, b''):
    print(line.rstrip().decode("utf=8"))
  os.mkdir("/content/cado-nfs/polyspin")
  os.chdir("/content/cado-nfs/polyspin")
  runtime = time.time() - fstart
  print("Elapsed time was", int(runtime / 60), "minutes and", int(runtime % 60), "seconds.\n")

# This removes the old rawset file for subsequent runs.
exists = os.path.isfile('/content/cado-nfs/polyspin/rawset')
if exists > 0:
  os.remove("/content/cado-nfs/polyspin/rawset")

# This iniatizes temp2neg with the polynomial from the top
# of the page which will eventually create the rawset file.
with open("/content/cado-nfs/polyspin/temp2neg", mode="wt", encoding="utf-8") as t2n:
  t2n.write("\n".join(polyinit))
polynegate()

# This constructs the pathnames to use for the CADO-NFS
# size and root optimization calls.
bpath = os.listdir("/content/cado-nfs/build")
sopt = "/content/cado-nfs/build/" + bpath[0] + "/polyselect/sopt"
ropt = "/content/cado-nfs/build/" + bpath[0] + "/polyselect/polyselect_ropt"

# This inializes some variables. c5 and c6 are initialized
# empty here so that degrees 4 and 5 polynomials can be run.
c5 = ""
c6 = ""
expElist = []
MurphyElist = []

# This first run is used to establish the exp_E for the original
# polynomial and its negated version, to minimize duplication.
seff = [0]
sizeopt(seff)
outF = open("/content/cado-nfs/polyspin/rawset", "w")
with open("/content/cado-nfs/polyspin/temp2neg", "r") as inT2n:
  for line in inT2n:
    outF.write(line)
with open("/content/cado-nfs/polyspin/tempneg", "r") as inTn:
  for line in inTn:
    outF.write(line)
outF.close()

# This runs various size and root optimizations,
# adding all new polynomials to rawset.
if test == True:
  seff = [0, 1, 10]
  sizeopt(seff)
  reff = [0, 0.01]
  rootopt(reff)
  seff = [0, 1, 10]
  sizeopt(seff)
  reff = [0, 0.01]
  rootopt(reff)
else:
  seff = [0, 1, 10, 100]
  sizeopt(seff)
  reff = [0, 0.01, 1]
  rootopt(reff)
  seff = [0, 1, 10, 100]
  sizeopt(seff)
  reff = [0, 0.01, 2]
  rootopt(reff)
  seff = [0, 1, 10, 100]
  sizeopt(seff)
  reff = [0, 0.01, 10]
  rootopt(reff)

# This harvests the best polinomial from the latest
# root optimization and writes it to the screen.
bp = open("/content/cado-nfs/polyspin/ropttemp", "r")
for line in bp:
  if line[:5] == "# n: ":
    n = line.rstrip()[2:]
  if line[:8] == "# skew: ":
    skew = line.rstrip()[2:]
  if line[:6] == "# c0: ":
    c0 = line.rstrip()[2:]
  if line[:6] == "# c1: ":
    c1 = line.rstrip()[2:]
  if line[:6] == "# c2: ":
    c2 = line.rstrip()[2:]
  if line[:6] == "# c3: ":
    c3 = line.rstrip()[2:]
  if line[:6] == "# c4: ":
    c4 = line.rstrip()[2:]
  if line[:6] == "# c5: ":
    c5 = line.rstrip()[2:]
  if line[:6] == "# c6: ":
    c6 = line.rstrip()[2:]
  if line[:6] == "# Y0: ":
    Y0 = line.rstrip()[2:]
  if line[:6] == "# Y1: ":
    Y1 = line.rstrip()[2:]
  if line[:12] == "# # lognorm ":
    lnorm = line.rstrip()[2:]
  if line[:12] == "# # MurphyE(":
    ME = line.rstrip()[2:]
bp.close()
print("Best polynomial found:")
print(n)
print(skew)
print(c0)
print(c1)
print(c2)
print(c3)
print(c4)
if len(c5) > 0:
  print(c5)
if len(c6) > 0:
  print(c6)
print(Y0)
print(Y1)
print(lnorm)
print(ME)

# This prints a verification of which run was made.
if test == True:
  print("Finished shortened test run!")
else:
  print("Finished polynomial run!")

Click on the Run cell icon or use CTRL-Enter.

The first time this is run, CADO-NFS will be built prior to running the "spin" cycles. Subsequent runs within the same session will just do the "spin.".

Here's an example spin with the sample polynomial with test = True:

Current exp_E list:
50.04
Current exp_E list:
50.04, 49.74
Current MurphyE list:
1.327e-15, 1.973e-16
Current exp_E list:
50.04, 49.74
Current MurphyE list:
1.327e-15, 1.973e-16
Best polynomial found:
n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 15664544.853
c0: -626081313147184760199029071786307655596384808000
c1: 114155706290582003827015758825221679754150
c2: 9698330805779200485429519766575815
c3: -1612013188384034013354246592
c4: -71413365342160076609
c5: 2982285821808
c6: 45360
Y0: -66175507466676477845668491119429817
Y1: 284594098468775320577861
# lognorm 59.63, E 49.29, alpha -10.34 (proj -2.10), 4 real roots
# MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.327e-15
Finished shortened test run!

Here's an example spin with the sample polynomial with test = False:

Current exp_E list:
50.04
Current exp_E list:
50.04, 49.74
Current MurphyE list:
1.327e-15, 1.973e-16, 1.243e-15, 1.123e-15
Current exp_E list:
50.04, 49.74, 49.90, 49.83
Current MurphyE list:
1.327e-15, 1.973e-16, 1.243e-15, 1.123e-15, 1.188e-15, 1.134e-15, 1.136e-15
Current exp_E list:
50.04, 49.74, 49.90, 49.83, 49.86
Current MurphyE list:
1.327e-15, 1.973e-16, 1.243e-15, 1.123e-15, 1.188e-15, 1.134e-15, 1.136e-15, 1.224e-15, 1.078e-15, 1.129e-15, 1.110e-15, 1.207e-15, 1.222e-15
Best polynomial found:
n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 15664544.853
c0: -626081313147184760199029071786307655596384808000
c1: 114155706290582003827015758825221679754150
c2: 9698330805779200485429519766575815
c3: -1612013188384034013354246592
c4: -71413365342160076609
c5: 2982285821808
c6: 45360
Y0: -66175507466676477845668491119429817
Y1: 284594098468775320577861
# lognorm 59.63, E 49.29, alpha -10.34 (proj -2.10), 4 real roots
# MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.327e-15
Finished polynomial run!

In this case, the first, shorter version actually produced a better scoring polynomial than the original, which wasn't improved by the longer run.