Improving Polynomials With CADO-NFS and Msieve Tools

EdH · 2020-12-03, 18:33

Forum member Max0526 has been "spinning" polynomials for various projects for a while now with noted success. With his permission, this thread will be an attempt to bring that procedure and a script based on it to light. It will discuss the steps Max uses and the script that is being developed.

Steps used to "spin" polynomials, to find better ones:

Step 1a: Compile a list of polynomials to "spin" in the CADO-NFS format, with one empty line in between each.

Example of CADO-NFS polynomials (step 1a):

Code:

# norm 3.955008e-15 alpha -10.525549 e 1.263e-15 rroots 4
skew: 20719118.62
c0: 762197820414584056355396858170301594531724356640
c1: 282438427720261099877094537227345105837822
c2: 10694897894745705918703999452376463
c3: -1550660754332995251622323056
c4: -74517626418497602049
c5: 2925078878448
c6: 45360
Y0: -66175567287217599588365775303500573
Y1: 284594098468775320577861

# norm 3.905700e-15 alpha -10.006285 e 1.255e-15 rroots 6
skew: 14837476.76
c0: -48435262418969769514610791143274851397285135584
c1: 33010637664063929475758747878463381423956
c2: 10301020259326875457171150530613793
c3: -1575557113665696390916906444
c4: -73281005399858760929
c5: 2948001010128
c6: 45360
Y0: -66175543317848844252701950274313570
Y1: 284594098468775320577861

Step 1b: Replace all the "# norm..." lines with "n: <composite>.

Example with changes (step 1b):

Code:

n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 20719118.62
c0: 762197820414584056355396858170301594531724356640
c1: 282438427720261099877094537227345105837822
c2: 10694897894745705918703999452376463
c3: -1550660754332995251622323056
c4: -74517626418497602049
c5: 2925078878448
c6: 45360
Y0: -66175567287217599588365775303500573
Y1: 284594098468775320577861

n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 14837476.76
c0: -48435262418969769514610791143274851397285135584
c1: 33010637664063929475758747878463381423956
c2: 10301020259326875457171150530613793
c3: -1575557113665696390916906444
c4: -73281005399858760929
c5: 2948001010128
c6: 45360
Y0: -66175543317848844252701950274313570
Y1: 284594098468775320577861

Step 2a: Duplicate the entire list of polynomials into a new file.
Step 2b: Change the signs for all the c#'s in the new file. Do NOT alter the Y#'s.
Step 2c: Append the new file to the original remembering the empty lines.

Example of polynomial file with all changes (step 2c):

Code:

n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 20719118.62
c0: 762197820414584056355396858170301594531724356640
c1: 282438427720261099877094537227345105837822
c2: 10694897894745705918703999452376463
c3: -1550660754332995251622323056
c4: -74517626418497602049
c5: 2925078878448
c6: 45360
Y0: -66175567287217599588365775303500573
Y1: 284594098468775320577861

n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 14837476.76
c0: -48435262418969769514610791143274851397285135584
c1: 33010637664063929475758747878463381423956
c2: 10301020259326875457171150530613793
c3: -1575557113665696390916906444
c4: -73281005399858760929
c5: 2948001010128
c6: 45360
Y0: -66175543317848844252701950274313570
Y1: 284594098468775320577861

n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 20719118.62
c0: -762197820414584056355396858170301594531724356640
c1: -282438427720261099877094537227345105837822
c2: -10694897894745705918703999452376463
c3: 1550660754332995251622323056
c4: 74517626418497602049
c5: -2925078878448
c6: -45360
Y0: -66175567287217599588365775303500573
Y1: 284594098468775320577861

n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
skew: 14837476.76
c0: 48435262418969769514610791143274851397285135584
c1: -33010637664063929475758747878463381423956
c2: -10301020259326875457171150530613793
c3: 1575557113665696390916906444
c4: 73281005399858760929
c5: -2948001010128
c6: -45360
Y0: -66175543317848844252701950274313570
Y1: 284594098468775320577861

Step 3a: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 0, and save the results into a size-opts file.
Step 3b: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 1, and append the results to the size-opts file.
Step 3c: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 10, and append the results to the size-opts file.
Step 3d: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 100, and append the results to the size-opts file.
Step 3e: Examine the size-opts file and extract all the unique polynomials based on the exp_E value in the "# lognorm..." line.
Step 3f: Create a duplicate list with swapped signs, as before.
Step 3g: Append both lists to the previous list of polynomials remembering the empty line spacing between polynomials.

Step 4a: Run CADO-NFS root optimization (polyselect_ropt) against the polynomials using an effort of 0, and save the results into a root-opts file.
Step 4b: Run CADO-NFS root optimization (polyselect_ropt) against the polynomials using an effort of 0.01, and append the results to the root-opts file.
Step 4c: Examine the root-opts file and extract all the unique polynomials based on the MurphyE value at the end of the "# MurphyE(..." line.
Step 4d: Create a duplicate list with swapped signs, as before.
Step 4e: Append both lists to the previous list of polynomials remembering the empty line spacing between polynomials.

Note: The preceding steps can be rerun multiple times, and/or the values of 1 and 2 can be used for the effort. After the runs, duplicate, change signs and append as before.

Step 5a: Run CADO-NFS root optimization (polyselect_ropt) against the polynomials using an effort of 10, and save the results into a root-opts file.
Step 5b: Examine the end of the root-opts file to find the "# Best polynomial found..." section.

The process used by Max0526 continues with further steps, some which include Msieve and other programs. These additional steps will be added at a later time.

EdH · 2020-12-03, 18:34

In the previous post, a method of finding better polynomials from already good ones was described. With help from Max0526 and swellman, I have written a bash script following the above steps. The script itself is provided below this description of use.

This Bash script, written for linux, uses external programs from the CADO-NFS package, specifically sopt and polyselect_ropt, both from within the polyselect folder within the specific build directory for the machine on which CADO-NFS was compiled. The script has been written in a manner to work from a subdirectory of cado-nfs, e.g. polyspin (this will be used for the examples below). In its present form, the script will search the build directory to find the name to use in its program calls. Presently, this search will fail if there are multiple directories within cado-nfs/build. Failure is displayed as no values being returned for the steps and a nearly immediate return to the calling prompt. In this case, the variable "bfolder" in the script should be changed to reflect the directory (from the build directory) to be used when running the script.

Note: If the CADO-NFS default build was used, the value shown by "echo $HOSTNAME" should be the name of the folder to use, but if the default was changed during the build, it could be different. That's why the current method is in place.

The script will need a file containing a list of the polynomials to "spin." This should be formatted in the following way:

Code:

# norm 3.979386e-15 alpha -10.165470 e 1.273e-15 rroots 6
skew: 17426583.98
c0: -424107143151389852394750951199674677445544423680
c1: 88091499630191140625983913523351724991412
c2: 17615204059869713970942209146992473
c3: -901787453125978278572433036
c4: -99339672027298490849
c5: 2419474999248
c6: 45360
Y0: -66176095990481059463373702221884018
Y1: 284594098468775320577861

This is the typical way CADO-NFS polynomials are expressed in posts in the forum threads.

Note: Multiple polynomials can be supplied in the list, but make sure a single blank line separates all polynomials:

Code:

. . .
Y0: -66176095990481059463373702221884018
Y1: 284594098468775320577861

# norm 3.979386e-15 alpha -10.165470 e 1.273e-15 rroots 6
skew: 17426583.98
c0: -424107143151389852394750951199674677445544423680
. . .

To run the script, once the polynomials file is created, from within the polyspin directory, use either:

Code:

$ bash <scriptname> <polynomials filename> <composite>

or, simply:

Code:

$ bash <scriptname>

The latter of these invocations, will cause the script to prompt for the file and composite.

An example of calling the script with the above single polynomial, and its subsequent output:

Code:

~/Math/cado-nfs/polyspin$ bash polyspin.sh polys 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
Full exp_E list from sopteffort 0, 1, 10, 100:
49.90 49.74 
As of ropteffort=1, Murphy_E scores:
1.269e-15 1.618e-16 1.270e-15 1.120e-15 1.243e-15
Full exp_E list from sopteffort 0, 1, 10, 100:
49.90 49.74 49.89 49.97 
As of ropteffort=2, Murphy_E scores:
1.269e-15 1.618e-16 1.270e-15 1.120e-15 1.243e-15 1.327e-15 1.143e-15 1.107e-15 1.191e-15 1.123e-15
Full exp_E list from sopteffort 0, 1, 10, 100:
49.90 49.74 49.89 49.97 50.04 49.86 49.99 50.14 49.83 
As of ropteffort=10, Murphy_E scores:
1.269e-15 1.618e-16 1.270e-15 1.120e-15 1.243e-15 1.327e-15 1.143e-15 1.107e-15 1.191e-15 1.123e-15 1.146e-15 1.140e-15 1.117e-15 1.224e-15 1.250e-15 1.109e-15 1.129e-15 1.157e-15 1.110e-15 1.136e-15 1.159e-15
# Best polynomial found:
n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711
Y0: -66175507466676477845668491119429817
Y1: 284594098468775320577861
c0: -626081313147184760199029071786307655596384808000
c1: 114155706290582003827015758825221679754150
c2: 9698330805779200485429519766575815
c3: -1612013188384034013354246592
c4: -71413365342160076609
c5: 2982285821808
c6: 45360
skew: 15664544.853
# 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
Full run time: 1:03:10

The "Best polynomial found" is the CADO-NFS assessment of all the previous polynomials starting from the original set that was given when the script was invoked. It is output to both file (BestPoly) and screen.

There are several intermediate files that can be reviewed during and after the run, depending on the variable "keepintfiles" setting. These files include the outputs of size and root optimizations as well as the temporary files used for negating the c# values. The rawset file contains the initial and all subsequent polynomials that were added. The original polynomial file is not changed.

The script for polyspin.sh:

Code:

#/bin/bash/###############################################################
# This script is based on work developed by Max0526 on mersenneforum.org.
# It is designed to refine polynomials in a manner to increase their
# MurphyE score by running them through sizeopt and rootopt procedures.
#
# To use this script, create a directory within your cado-nfs folder,
# e.g. "polyspin" and place this script and your file containing the
# polynomials within that folder.  You can then use:
#     bash polyspin.sh <polysfilename> <composite>
# Or, you can simply use:
#     bash polyspin.sh
# and enter the filename and composite when prompted.
#
# This script searches the cado-nfs/build directory for the folder where
# the programs are compiled.  If there are more than one folder within
# the build directory, unexpected behaviour may me be witnessed.  In such
# case, the script should be edited in this manner:                       
#     bfolder=<folder in build directory to use>
#
# Discussion of this process and script can be found in this thread:
#     <add thread address here>
###########################################################################

# filename for original polys
inpolys=$1
# composite for polys
composite=$2
# finds build directory to use for programs
# change this if more than one folder in build directory
bfolder=$(ls ../build)
# keep final intermediate files
# no means remove all intermediate files at end
keepintfiles=yes
# Initialize several variables
MurphyEs=""
expEs=""
c5=""
c6=""
SECONDS=0

# Create tempneg file with negated c values
function negatecs {
  rm tempneg 2>/dev/null
  exec <"temp2neg"
    while read line
      do
        case $line in
          "n: "*) echo $line >> tempneg
            ;;
          "skew: "*) echo $line >> tempneg
            ;;
          "Y0: "*) echo $line >> tempneg
            ;;
          "Y1: "*) echo $line >> tempneg
            echo ""  >> tempneg
            ;;
          "c"*) test=${line:4}
          if [[ $test = -* ]]
            then
              echo ${line:0:4}${line:5} >> tempneg
            else
              echo ${line:0:4}-${line:4} >> tempneg
          fi
          ;;
        esac
      done
}

# Run size optimization at effort 0, 1, 10, 100
function sizeopt {
  rm soptset 2>/dev/null
  for s in 0 1 10 100
    do
      ../build/$bfolder/polyselect/sopt -inputpolys rawset -sopteffort $s -v >> soptset
    done
# Filter size optimized polys and add to rawset with negations
  rm temp2neg 2>/dev/null
  exec <"soptset"
    while read line
      do
        check=0
        case $line in
          "n: "*) n=$line
            ;;
          "Y0: "*) Y0=$line
            ;;
          "Y1: "*) Y1=$line
            ;;
          "c0: "*) c0=$line
            ;;
          "c1: "*) c1=$line
            ;;
          "c2: "*) c2=$line
            ;;
          "c3: "*) c3=$line
            ;;
          "c4: "*) c4=$line
            ;;
          "c5: "*) c5=$line
            ;;
          "c6: "*) c6=$line
            ;;
          "skew: "*) skew=$line
            ;;
          "# lognorm "*) expE=${line:23:5}
            case $expEs in
              *"$expE"*) check=1
                ;;
            esac
            if [ $check -eq 0 ]
              then
                expEs="${expEs}${expE} "
                echo "$n" >>temp2neg
                echo "$skew" >>temp2neg
                echo "$c0" >>temp2neg
                echo "$c1" >>temp2neg
                echo "$c2" >>temp2neg
                echo "$c3" >>temp2neg
                echo "$c4" >>temp2neg
                if [ ${#c5} -gt 0 ]
                  then
                    echo "$c5" >>temp2neg
                fi
                if [ ${#c6} -gt 0 ]
                  then
                    echo "$c6" >>temp2neg
                fi
                echo "$Y0" >>temp2neg
                echo "$Y1" >>temp2neg
                echo "" >>temp2neg
            fi
            ;;
        esac
      done
      echo "Full exp_E list from sopteffort 0, 1, 10, 100:"
      echo "$expEs"
  if [ -e temp2neg ]
    then
      negatecs          
      cat temp2neg >>rawset
      cat tempneg >>rawset
  fi
}

# Accept input for polyfile and/or composite,
# if not provided on command line
if [ ${#inpolys} -lt 1 ]
  then
    printf "polys file: "
    read inpolys in
fi
if [ ${#composite} -lt 1 ]
  then
    printf "composite: "
    read composite in
fi

# Create rawset file from polyfile
rm rawset 2>/dev/null
rm temp2neg 2>/dev/null
exec <"$inpolys"
  while read line
    do
      case $line in
        "skew:"*) echo "n: $composite" >> rawset
          echo $line >> rawset
          ;;
        "c0:"*) echo $line >> rawset
          ;;
        "c1:"*) echo $line >> rawset
          ;;
        "c2:"*) echo $line >> rawset
          ;;
        "c3:"*) echo $line >> rawset
          ;;
        "c4:"*) echo $line >> rawset
          ;;
        "c5:"*) echo $line >> rawset
          ;;
        "c6:"*) echo $line >> rawset
          ;;
        "Y0:"*) echo $line >> rawset
          ;;
        "Y1:"*) echo $line >> rawset
          echo "" >> rawset
          ;;
      esac
    done

# Create set of polys to negate c values
cp rawset temp2neg

# negate polys
negatecs

# Append tempneg to rawset
cat tempneg >> rawset

# Run initial size optimization
sizeopt

# Run root optimization on rawset at effort 0, 0.01, 1, 2, 10
for r in 1 2 10
  do
    rm roptset 2>/dev/null
    ../build/$bfolder/polyselect/polyselect_ropt -t $(nproc) -inputpolys rawset -area 1.00e+16 -Bf 10000000 -Bg 5000000 -v -ropteffort 0 >> roptset 2>/dev/null
    ../build/$bfolder/polyselect/polyselect_ropt -t $(nproc) -inputpolys rawset -area 1.00e+16 -Bf 10000000 -Bg 5000000 -v -ropteffort 0.01 >> roptset 2>/dev/null
    ../build/$bfolder/polyselect/polyselect_ropt -t $(nproc) -inputpolys rawset -area 1.00e+16 -Bf 10000000 -Bg 5000000 -v -ropteffort $r >> roptset 2>/dev/null
          
# Filter root optimized polys and add uniques to rawset with negations
    rm temp2neg 2>/dev/null
    exec <"roptset"
      while read line
        do
          check=0
          case $line in
            "n: "*) n=$line
              ;;
            "Y0: "*) Y0=$line
              ;;
            "Y1: "*) Y1=$line
              ;;
            "c0: "*) c0=$line
              ;;
            "c1: "*) c1=$line
              ;;
            "c2: "*) c2=$line
              ;;
            "c3: "*) c3=$line
              ;;
            "c4: "*) c4=$line
              ;;
            "c5: "*) c5=$line
              ;;
            "c6: "*) c6=$line
              ;;
            "skew: "*) skew=$line
              ;;
            "# MurphyE("*) MurphyE=${line##*=}
              case $MurphyEs in
                *"$MurphyE"*) check=1
                  ;;
              esac
              if [ $check -eq 0 ]
                then
                  MurphyEs="${MurphyEs} ${MurphyE}"
                  echo "$n" >>temp2neg
                  echo "$skew" >>temp2neg
                  echo "$c0" >>temp2neg
                  echo "$c1" >>temp2neg
                  echo "$c2" >>temp2neg
                  echo "$c3" >>temp2neg
                  echo "$c4" >>temp2neg
                  if [ ${#c5} -gt 0 ]
                    then
                      echo "$c5" >>temp2neg
                  fi
                  if [ ${#c6} -gt 0 ]
                    then
                      echo "$c6" >>temp2neg
                  fi
                  echo "$Y0" >>temp2neg
                  echo "$Y1" >>temp2neg
                  echo "" >>temp2neg
              fi
              ;;
          esac
        done
              echo "As of ropteffort=${r}, Murphy_E scores:"
              echo $MurphyEs
    if [ -e temp2neg ]
      then
        negatecs          
        cat temp2neg >>rawset
        cat tempneg >>rawset
        if [ $r -lt 10 ]
          then
            sizeopt
        fi
    fi
  done

# Extract best polynomial
c5=""
c6=""
rm BestPoly 2>/dev/null
exec <"roptset"
  while read line
    do
      case $line in
        "# n: "*) n=$line
          ;;
        "# Y0: "*) Y0=$line
          ;;
        "# Y1: "*) Y1=$line
          ;;
        "# c0: "*) c0=$line
          ;;
        "# c1: "*) c1=$line
          ;;
        "# c2: "*) c2=$line
          ;;
        "# c3: "*) c3=$line
          ;;
        "# c4: "*) c4=$line
          ;;
        "# c5: "*) c5=$line
          ;;
        "# c6: "*) c6=$line
          ;;
        "# skew: "*) skew=$line
          ;;
        "# # lognorm "*) lognorm=$line
          ;;
        "# # MurphyE("*) MurphyE=$line
          ;;
      esac
    done
echo "# Best polynomial found:"
echo "${n:2}" >>BestPoly
echo "${Y0:2}">>BestPoly
echo "${Y1:2}" >>BestPoly
echo "${c0:2}" >>BestPoly
echo "${c1:2}" >>BestPoly
echo "${c2:2}" >>BestPoly
echo "${c3:2}" >>BestPoly
echo "${c4:2}" >>BestPoly
if [ ${#c5} -gt 0 ]
  then
    echo "${c5:2}" >>BestPoly
fi
if [ ${#c6} -gt 0 ]
  then
    echo "${c6:2}" >>BestPoly
fi
echo "${skew:2}" >>BestPoly
echo "${lognorm:2}" >>BestPoly
echo "${MurphyE:2}" >>BestPoly
cat BestPoly

# Remove intermediate files if "keep" setting is (n)o
case $keepintfiles in
  "n"*)
    rm rawset
    rm roptset
    rm soptset
    rm tempneg
    rm temp2neg
    ;;
esac

# print time taken to run entire process
let hr=${SECONDS}/3600
let SECONDS=${SECONDS}%3600
let mn=${SECONDS}/60
let se=${SECONDS}%60
printf "Full run time: %d:%02d:%02d\n" $hr $mn $se

Branger · 2020-12-07, 21:36

Quote:

Originally Posted by EdH

Step 2b: Change the signs for all the c#'s in the new file. Do NOT alter the Y#'s.

At some point I played around with a similar scheme, but instead of multiplying all c# coefficients with -1, I tried a small positive multiplier such as 2-5, before feeding the polynomials to msieve to optimize them. At least for the multiplier of 2 I did find some polynomials that were better than the original one, though never one that ended up at the top. Perhaps this idea may be worth a try?

EdH · 2020-12-07, 22:30

Quote:

Originally Posted by Branger

At some point I played around with a similar scheme, but instead of multiplying all c# coefficients with -1, I tried a small positive multiplier such as 2-5, before feeding the polynomials to msieve to optimize them. At least for the multiplier of 2 I did find some polynomials that were better than the original one, though never one that ended up at the top. Perhaps this idea may be worth a try?

There are some more steps that Max uses, including, I think, some scaling. That may fit in with your multiplication. I don't think Bash can handle that math on its own*, but I'm working on a Python script, that I already am having success with in a Colab session. I'm sure I could get Python to perform the activity. Thanks for bringing it to the discussion!

*I actually could create a Bash function that would step through a string from end to beginning, doing doubling along the way, but that might be involved and probably a bit messy.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
use msieve linear algebra after CADO-NFS filtering	aein	Msieve	2	2017-10-05 01:52
Combining Msieve with CADO NFS	mfeltz	Msieve	10	2016-03-16 21:12
Murphy's Law and other tools	Uncwilly	Lounge	5	2014-07-07 22:36
how to run msieve or cado-nfs on mpi-cluster?	ravlyuchenko	Msieve	1	2011-08-16 12:12
Improving Sieving by 18%.	cipher	Prime Sierpinski Project	10	2009-07-01 13:34