Work on a BASH Scipt to Find Polynomials Using the Best of Msieve and CADO-NFS

[EdH]

Max0526 helped me build a script for his polynomial spinning technique, but I was not able to fully realize all he did when spinning polynomials. My version of that script has never been effective with polynomials found by Gimarel who has consistently posted record scoring polynomials.

This thread is intended to use Gimarel's process, which he has been so kind as to share with us in the Polynomial Request thread, in building a script to implement his process. I have been stumped at the first step and hope to find a way through his process of using both Msieve and CADO-NFS to find the best polynomials we can, using the best portions from both packages.

If possible, I would like to incorporate the use of a GPU in the first stage eventually, but I'm confused from the start with the following from the Polynomial Request thread:

Originally Posted by Gimarel

My "secret" is, that I don't use the sizeopt of msieve but the sopt of cado and sort the result by "exp_E".
For productive hits I run the rootsieve of msieve multiple (upt to 100) times with different stage2_norms.

I'd like to approach this one step at a time, building a BASH script to add to for each step.

At the start, I'm already confused by the above. If I run Msieve with -np1, it will find the initial values and place them into msieve.dat.m. This file is not readable by CADO-NFS sopt (unless I'm missing some sopt switch(es)). My question at this point is whether to perform Msieve -nps/npr to get to the polynomial format that sopt would use, or perhaps start with CADO-NFS (which would rule out a GPU) first?

In trying to keep with one step at a time, I'd like to start with setting up the initial directory structure and work from there. My first step is to create a working directory at the same level as the Msieve and CADO-NFS directories and build the script to work within that directory: mkdir polyWork. In my case, the parent directory for the other three is Math and the following script will use that path.

And, now for the script:

#!/bin/bash
#####################################
## This script is designed to use  ##
## portions of Msieve and CADO-NFS ##
## to find polynomials.            ##
#####################################

# set path to polyWork directory:
cd $HOME/Math/polyWork

# Set values for Msieve and CADO-NFS
# operations:

minc=1000000
maxc=1200000

if [ ${#1} -gt 9 ]
  then
    composite=$1
  elif [ -e worktodo.ini ]
    then
      read composite <worktodo.ini
  else
    echo -n "Enter composite: "
    read composite in
fi
echo "$composite" >worktodo.ini

echo "Finding polynomials for: $composite"

# Since this location should be relative
# to the working directory and static, it
# is only set in the command lines.
../msieve/msieve -v -t 20 -np1 "${minc}, ${maxc}"

echo "Msieve stage 1 complete!"

Two problems arise at this point, for me:

1. The min and max coeff range is not observed when I run only -np1

2. The resulting msieve.dat.m file is not readable by CADO-NFS sopt, unless there's an option I'm unaware of.

[RichD]

Originally Posted by EdH

1. The min and max coeff range is not observed when I run only -np1

min and max coeff must immediately follow -np1.

[EdH]

Originally Posted by RichD

min and max coeff must immediately follow -np1.

Excellent - thanks! Change made.

[Gimarel]

Originally Posted by EdH

2. The resulting msieve.dat.m file is not readable by CADO-NFS sopt, unless there's an option I'm unaware of.

You have two options.
1. Run msieve -nps with a really high stage2_norm and convert the output with something like that for degree six:

cat msieve.dat.ms |
while read l; do 
  line=($l)
  echo "n: $composite"
  echo "c6: ${line[0]}"
  echo "c5: ${line[1]}"
  echo "c4: ${line[2]}"
  echo "c3: ${line[3]}"
  echo "c2: ${line[4]}"
  echo "c1: ${line[5]}"
  echo "c0: ${line[6]}"
  echo "Y1: ${line[7]}"
  echo "Y0: ${line[8]}"
  echo
 done

2. You can modify msieve to output the CADO format when run with -nps:

Index: gnfs/poly/stage2/stage2.c
===================================================================
--- gnfs/poly/stage2/stage2.c    (revision 1035)
+++ gnfs/poly/stage2/stage2.c    (working copy)
@@ -219,10 +219,12 @@
 void
 poly_sizeopt_run(poly_sizeopt_t *data, mpz_t ad, mpz_t p, mpz_t d)
 {
+    int32 i;
     double pol_norm;
     double alpha_proj;
     int status;
     curr_poly_t *c = (curr_poly_t *)(data->internal);
+    FILE *mfile = (FILE *)data->callback_data;
 
     mpz_set(c->gmp_d, d);
     mpz_set(c->gmp_p, p);
@@ -237,6 +239,13 @@
         return;
     }
 
+        gmp_fprintf(mfile, "n: %Zd\n", data->gmp_N);
+        for (i = data->degree; i >= 0; i--)
+                 gmp_fprintf(mfile, "c%d: %Zd\n", i, c->gmp_a[i]);
+        gmp_fprintf(mfile, "Y1: %Zd\nY0: %Zd\n\n", c->gmp_lina[1], c->gmp_lina[0]);
+        fflush(mfile);
+        return;
+
     optimize_initial(c, data->degree, &pol_norm, 0);
 
     stage2_root_score(data->degree, c->gmp_a, 100, &alpha_proj, 1);

[EdH]

Thanks! The conversion wasn't my block. I commonly convert* for versions of my spin script. There are also some programs for that. My confusion was how to get to that point without running Msieve size option. Now I understand that I do run the size option with a high enough stage2_norm to only save the top scoring polynomials for the CADO-NFS sopt run.

I'll work some more and add another step to see where I get. There is some mention elsewhere about adjusting the stage1 and stage2 norms from Msieve's original calculations. I'll add that as well. And, then you can let me know if I'm getting way off course.

Of note: To get the GPU portion to work, I'm going to move everything from the "polyWork" directory into an Msieve directory called "msievePoly"

* My normal conversion accepts all coefficients up through degree 8, just in case.

[Gimarel]

Originally Posted by EdH

Thanks! The conversion wasn't my block. I commonly convert* for versions of my spin script. There are also some programs for that. My confusion was how to get to that point without running Msieve size option. Now I understand that I do run the size option with a high enough stage2_norm to only save the top scoring polynomials for the CADO-NFS sopt run.

No, you want to run all stage 1 hits through sopt. This is the reason to use a very high stage2_norm so msieve doesn't omit some hits.

[EdH]

Originally Posted by Gimarel

No, you want to run all stage 1 hits through sopt. This is the reason to use a very high stage2_norm so msieve doesn't omit some hits.

Ah!, thanks! I had actually tried that in my earlier experiments. I was thinking backwards (not uncommon these days).

Would there be a suggestion for the stage1 and stage2 starting values, either static or based on the original Msieve ones?

[Gimarel]

Originally Posted by EdH

Would there be a suggestion for the stage1 and stage2 starting values, either static or based on the original Msieve ones?

Stage 1 depends on different parameters (cpu/gpu, size of the composite, leading coefficient searched). I'm sorry, I can't give a generic suggestion.
As I don't use msieve's sizeopt any more, I don't have a suggestion for stage 2 as well. If you just want all hits use something like 1e40.

[EdH]

Thanks! I've gotten quite a ways past the single next step.

Here's where I am ATM:

- I run Msieve -np1 for 5 seconds to get initial values for degree and stage2_norm.

- I run Msieve with -np1 and -nps using a stage2_norm based on a multiplier times the original.
- - This seems to only run single threaded. Should I be able to get multi-threaded?

- I convert the msieve.dat.ms file into a poly file for CADO-NFS sopt.
- - I've made this portion work across varying degrees by incorporating the degree value found earlier.
- - This file is tens for thousands of polynomials.
- - - Should I use the scores to trim this yet?

- I run CADO-NFS sopt on the new file.
- - You mention using exp_E to determine value.
- - - IIRC, the lower exp_E, the better (or am I backwards again?).
- - - - I'm thinking at this point I should cull somewhat.
- - - - Would it be of value to only keep the polynomials with the lowest exp_E?
- - Should I make more than one pass with varying values for sopt or is there a particular value I should use?

[RichD]

You might find this post helpful - by VBCurtis.

Only -np1 is multi-thread.

[VBCurtis]

If I were going this route, I think I'd want to feed CADO sopt thousands of hits but not tens of thousands. The stage1 norm is still a useful filter to keep only the best GPU stage 1 hits.

The advice I gave in that linked post was intended to feed the CPU a stream of GPU hits such that size-opt on CPU took about the same time as stage 1 on GPU. You might want more hits than that, but I'd still reduce the default stage1 norm by a factor of 5 to start, and then tune as desired to balance the GPU time spent vs the CADO-sopt time spent on CPU. I personally lean toward making the GPU work "harder" by setting the stage1 norm lower.