How I Run an SNFS Process with CADO-NFS on My Ubuntu Machines

EdH · 2019-10-13, 22:41

(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.)

This thread will explain the steps I use to factor using the Special Number Field Sieve (SNFS) with CADO-NFS. It can be run on a single machine or with clients from several computers which are already running Ubuntu and have CADO-NFS installed* and tested per:

How I Install CADO-NFS on my Ubuntu Machines

Additionally, to generate the files needed to run an SNFS process with CADO-NFS, I use YAFU. So, you should be sure you have YAFU installed. If not, you can do so per:

How I install YAFU onto my Ubuntu Machines

*In this instance "install" is referring to the acquiring and compilation of the CADO-NFS and YAFU packages only. The scripts and binary will have to be called using their respective paths.

I will be referencing the folder Math/cado-nfs as described in the installation routine above. Make any local changes for your computer.

Copy the YAFU binary and yafu.ini into your Math/cado-nfs directory.

In the example below, I will be providing steps I use and a commented bash script which I use to automate the individual steps. The basic process I use is to run YAFU to provide the suggested polynomial and sieving information. Using the produced YAFU files, I create a parameter file (parameters/factor/params.snfsTest) to instruct CADO-NFS and the polynomial (parameters/polynomials/snfsTest.poly) file which will be used for the factorization steps. Then I run CADO-NFS providing the params.snfsTest file referenced in the call. Additionally, when the params.snfsTest file is constructed, many parameters are harvested from appropriate params.cXX(X) files.

YAFU can be used with composites by themselves or cofactors of larger numbers of many forms for SNFS info generation. For the following example, I will be using an Homogeneous Cunningham Number (HCN) that has been factored to remove all the smaller factors and is left with a larger composite. More information for the use of YAFU for SNFS can be found in docfile.txt which is provided with the YAFU installation. For the way I use YAFU, I need to provide the full HCN and the cofactor to YAFU in the following manner:

Code:

./yafu "snfs(<HCN>,<cofactor>)" -v -np

YAFU will expand expressions, so I use the shortened version of the HCN. For this example, I will use HCN 3-2,621, whose expression is 3^621-2^621, and its cofactor which I want to factor:

Code:

./yafu "snfs(3^621-2^621,68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201)" -v -np

This will give lots of useful info:

Code:

$ ./yafu "snfs(3^621-2^621,68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201)" -v -np

10/13/19 16:59:07 v1.35-beta @ math79, System/Build Info: 
Using GMP-ECM 7.0.4, Powered by GMP 6.1.2
detected         Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes
measured cpu frequency ~= 3392.282880
using 1 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983

>> nfs: checking for job file - no job file found
nfs: checking for poly file - no poly file found
nfs: commencing nfs on c297: 196019456595217403424358869547043901268534422088371648839758497010903389071218128291079833917562981687314579002350353213091076130678792570923114297015849876092938837313606077797614692465895064744543480956541405738169857357996520018006681038099360876090542938296393476491929377823276234246964500051
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: input divides 3^621 - 2^621
nfs: degree 4 difficulty = 197.53, degree 6 difficulty = 197.53
nfs: choosing degree 6
nfs: guessing snfs difficulty 197 is roughly equal to gnfs difficulty 140
nfs: creating ggnfs job parameters for input of size 140

gen: ========================================================
gen: selected polynomial:
gen: ========================================================

n: 68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201
# 3^621-2^621, difficulty: 197.53, anorm: 3.00e+36, rnorm: 8.34e+38
# scaled difficulty: 197.53, suggest sieving algebraic side
# size = 8.910e-10, alpha = 1.996, combined = 1.545e-11, rroots = 0
type: snfs
size: 197
skew: 1.0000
c6: 1
c3: 1
c0: 1
Y1: -590295810358705651712
Y0: 834385168331080533771857328695283
m: 16100805496191306534598776482363127041445450199543934322527595715812520334262036265217595033789232856437047404305558262832570559299625366550040047609760171251306527270
nfs: job file is missing params, filling them

***factors found***

***co-factor***
C167 = 68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201

ans = 68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201

Note that I have highlighted three bits of info in the above output from YAFU:

"choosing degree 6" is important because if the degree chosen is 4, it could be problematic to factor vis SNFS.

"gnfs difficulty 140" is telling me to use the params.c140 file to complete the parameter file for the CADO-NFS run.

"suggest sieving algebraic side" tells me to set the sieving to the algebraic side with tasks.sieve.sqside = 1. If it suggested the rational side, that would be = 0.

When YAFU runs the above operation, it produces the file nfs.job which holds the polynomial values and some other sieving values. These are used in the construction of the params.snfsTest parameters file. The nfs.job file for the above run:

Code:

n: 68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201
# 3^621-2^621, difficulty: 197.53, anorm: 3.00e+36, rnorm: 8.34e+38
# scaled difficulty: 197.53, suggest sieving algebraic side
# size = 8.910e-10, alpha = 0.000, combined = 1.545e-11, rroots = 0
type: snfs
size: 197
skew: 1.0000
c6: 1
c3: 1
c0: 1
Y1: -590295810358705651712
Y0: 834385168331080533771857328695283
m: 16100805496191306534598776482363127041445450199543934322527595715812520334262036265217595033789232856437047404305558262832570559299625366550040047609760171251306527270

rlim: 14000000
alim: 14000000
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56
rlambda: 2.6
alambda: 2.6

The param.snfsTest file is constructed using the preceding values and filled in from the params.c140 file. The finished params.snfsTest file:

Code:

# SNFS Test File

name = snfsTest
N = 68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201

###########################################################################
# Polynomial selection
###########################################################################

tasks.polyselect.admin = 0
tasks.polyselect.admax = 0
tasks.polyselect.adrange = 0
tasks.polyselect.import = parameters/polynomials/snfsTest.poly

###########################################################################
# Sieve
###########################################################################

tasks.lim0 = 14000000
tasks.lim1 = 14000000
tasks.lpb0 = 28
tasks.lpb1 = 28
tasks.sieve.mfb0 = 56
tasks.sieve.mfb1 = 56
tasks.sieve.lambda0 = 2.6
tasks.sieve.lambda1 = 2.6
tasks.sieve.ncurves0 = 19
tasks.sieve.ncurves1 = 22
tasks.I = 14
tasks.qmin = 100000
tasks.sieve.qrange = 10000
tasks.sieve.rels_wanted = 82000000
tasks.sieve.sqside = 1

###########################################################################
# Filtering
###########################################################################

tasks.filter.purge.keep = 175
tasks.filter.target_density = 135.0

###########################################################################
# Linear algebra
###########################################################################

tasks.linalg.bwc.interval = 2000
tasks.linalg.bwc.interleaving = 0
tasks.linalg.m = 64
tasks.linalg.n = 64

###########################################################################
# Characters
###########################################################################

tasks.linalg.characters.nchar = 50

Notice that the names have been converted between the files, e.g. rlambda = lambda0.

(Note: The params.c140 file in this example is from the Improved params files for CADO thread, rather than the default c140 file.)

A polynomial file (snfsTest.poly) stills needs to be constructed and its values can be found in the nfs.job file as well. (Although the nfs.fb file also contains the values needed, it does not contain skew. Therefore I use the nfs.job file.) The snfsTest.poly file, once constructed:

Code:

n: 68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201
skew: 1.0000
c6: 1
c3: 1
c0: 1
Y1: -590295810358705651712
Y0: 834385168331080533771857328695283

Once the two files, params.snfsTest and snfsTest.poly, are constructed, CADO-NFS can be run with the following command:

Code:

./cado-nfs.py parameters/factor/params.snfsTest <all other options, etc.>

This is the script I use to generate both the poly file and the params file to use for the CADO-NFS run. I know it could use some tidying up, but for now I went with function:

Code:

#!/bin/bash/

#######################################################################################
# The three lines following this comment block are edited into the file for each run.
# (hcn) This is the expanded expression for the Homogenous Cunningham Number.
# (comp) This is the composite cofactor that is to be factored via SNFS.
# (pfile) This is the params.cXX(X) file to use for completing the SNFS params file.
#######################################################################################
hcn="3^621-2^621"
comp=68355486282114622663635894106854390569608547272637176702107797852793161878380701560397186525449704752263144020132918740789147994798351576463952148092839382243189128201 
pfile=c140
 
sqside=0 #Initialization of sqside. This will be changed if YAFU suggests algebraic.

# Clear out previous YAFU generated files.
rm factor.log
rm nfs.fb
rm nfs.job
rm session.log
rm YAFU_get_poly_score.out

# Run YAFU with screen output to review. Although all the files are created,
# I check this output anyway.
./yafu "snfs($hcn,$comp)" -v -np

# Extract polynomial data from nfs.job and use it to create the poly file
# and start the params file.
exec <"nfs.job"
while read line
  do
    case $line in
      *"algebraic side"*) let sqside=${sqside}+1
      ;;
    esac
    case $line in
      "n: "*) echo $line >parameters/polynomials/snfsTest.poly
      echo "# SNFS Test File" >parameters/factor/params.snfsTest
      echo "" >>parameters/factor/params.snfsTest
      echo "name = snfsTest" >>parameters/factor/params.snfsTest
      echo "N = ${line:3}" >>parameters/factor/params.snfsTest
      echo "" >>parameters/factor/params.snfsTest
      echo "###########################################################################" >>parameters/factor/params.snfsTest
      echo "# Polynomial selection" >>parameters/factor/params.snfsTest
      echo "###########################################################################" >>parameters/factor/params.snfsTest
      echo "" >>parameters/factor/params.snfsTest
      echo "tasks.polyselect.admin = 0" >>parameters/factor/params.snfsTest
      echo "tasks.polyselect.admax = 0" >>parameters/factor/params.snfsTest
      echo "tasks.polyselect.adrange = 0" >>parameters/factor/params.snfsTest
      echo "tasks.polyselect.import = parameters/polynomials/snfsTest.poly" >>parameters/factor/params.snfsTest
      echo "" >>parameters/factor/params.snfsTest
      echo "###########################################################################" >>parameters/factor/params.snfsTest
      echo "# Sieve" >>parameters/factor/params.snfsTest
      echo "###########################################################################" >>parameters/factor/params.snfsTest
      echo "" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "skew: "*) echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c8: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c7: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c6: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c5: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c4: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c3: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c2: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c1: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "c0: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "Y1: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "Y0: "*)  echo $line >>parameters/polynomials/snfsTest.poly
      ;;
    esac
    case $line in
      "rlim: "*) echo "tasks.lim0 = ${line:6}" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "alim: "*) echo "tasks.lim1 = ${line:6}" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "lpbr: "*) echo "tasks.lpb0 = ${line:6}" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "lpba: "*) echo "tasks.lpb1 = ${line:6}" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "mfbr: "*) echo "tasks.sieve.mfb0 = ${line:6}" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "mfba: "*) echo "tasks.sieve.mfb1 = ${line:6}" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "rlambda: "*) echo "tasks.sieve.lambda0 = ${line:9}" >>parameters/factor/params.snfsTest
      ;;
    esac
    case $line in
      "alambda: "*) echo "tasks.sieve.lambda1 = ${line:9}" >>parameters/factor/params.snfsTest
      ;;
    esac
  done

# Use the appropriate params.cXX(X) file to complete the SNFS params file.
exec <"parameters/factor/params.${pfile}"
  while read line
    do
      case $line in
        "tasks.sieve.ncurves"*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.I ="*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.qmin"*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.sieve.qrange"*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.sieve.rels_wanted"*) echo $line >>parameters/factor/params.snfsTest
        echo "tasks.sieve.sqside = $sqside" >>parameters/factor/params.snfsTest
        echo "" >>parameters/factor/params.snfsTest
        echo "###########################################################################" >>parameters/factor/params.snfsTest
        echo "# Filtering" >>parameters/factor/params.snfsTest

        echo "###########################################################################" >>parameters/factor/params.snfsTest
        echo "" >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.filter.purge"*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.filter.target"*) echo $line >>parameters/factor/params.snfsTest   
        echo "" >>parameters/factor/params.snfsTest
        echo "###########################################################################" >>parameters/factor/params.snfsTest
        echo "# Linear algebra" >>parameters/factor/params.snfsTest

        echo "###########################################################################" >>parameters/factor/params.snfsTest
        echo "" >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.linalg.bwc"*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.linalg.m"*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.linalg.n"*) echo $line >>parameters/factor/params.snfsTest
        echo "" >>parameters/factor/params.snfsTest
        echo "###########################################################################" >>parameters/factor/params.snfsTest
        echo "# Characters" >>parameters/factor/params.snfsTest

        echo "###########################################################################" >>parameters/factor/params.snfsTest
        echo "" >>parameters/factor/params.snfsTest
        ;;
      esac
      case $line in
        "tasks.linalg.characters"*) echo $line >>parameters/factor/params.snfsTest
        ;;
      esac
    done

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How I Install CADO-NFS onto my Ubuntu Machines	EdH	EdH	3	2019-06-24 03:42
How I Install GMP-ECM onto my Ubuntu Machines	EdH	EdH	12	2019-04-16 09:28
How I Run a Larger Factorization Via CADO-NFS on Several Ubuntu Machines	EdH	EdH	0	2018-02-25 18:00
How I Install msieve onto my Ubuntu Machines	EdH	EdH	0	2018-02-23 14:43
How I Install GMP onto my Ubuntu Machines	EdH	EdH	0	2018-02-21 23:48