mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-09-24, 22:33   #1
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

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

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:
Quote:
Originally Posted by Gimarel View Post
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:
Code:
#!/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.

Last fiddled with by EdH on 2022-09-24 at 23:08
EdH is offline   Reply With Quote
Old 2022-09-24, 22:48   #2
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

2×1,879 Posts
Default

Quote:
Originally Posted by EdH View Post
1. The min and max coeff range is not observed when I run only -np1
min and max coeff must immediately follow -np1.
RichD is offline   Reply With Quote
Old 2022-09-24, 23:09   #3
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

Quote:
Originally Posted by RichD View Post
min and max coeff must immediately follow -np1.
Excellent - thanks! Change made.
EdH is offline   Reply With Quote
Old 2022-09-25, 06:30   #4
Gimarel
 
Apr 2010

22·61 Posts
Default

Quote:
Originally Posted by EdH View Post
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:
Code:
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:
Code:
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);
Gimarel is offline   Reply With Quote
Old 2022-09-25, 12:26   #5
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

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.
EdH is offline   Reply With Quote
Old 2022-09-25, 12:59   #6
Gimarel
 
Apr 2010

24410 Posts
Default

Quote:
Originally Posted by EdH View Post
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.
Gimarel is offline   Reply With Quote
Old 2022-09-25, 13:05   #7
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

Quote:
Originally Posted by Gimarel View Post
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?
EdH is offline   Reply With Quote
Old 2022-09-26, 05:23   #8
Gimarel
 
Apr 2010

F416 Posts
Default

Quote:
Originally Posted by EdH View Post
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.
Gimarel is offline   Reply With Quote
Old 2022-09-26, 12:14   #9
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

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?
EdH is offline   Reply With Quote
Old 2022-09-26, 13:53   #10
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

2×1,879 Posts
Default

You might find this post helpful - by VBCurtis.

Only -np1 is multi-thread.
RichD is offline   Reply With Quote
Old 2022-09-26, 15:30   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

24·347 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Calculator that can factor and find exact roots of polynomials alpertron Programming 39 2022-06-02 12:21
Improving Polynomials With CADO-NFS and Msieve Tools EdH Factoring 4 2021-10-18 14:29
Combining Msieve with CADO NFS mfeltz Msieve 10 2016-03-16 21:12
How to find values of polynomials with nice factorization? Drdmitry Computer Science & Computational Number Theory 18 2015-09-10 12:23
how to run msieve or cado-nfs on mpi-cluster? ravlyuchenko Msieve 1 2011-08-16 12:12

All times are UTC. The time now is 12:23.


Sun Dec 4 12:23:07 UTC 2022 up 108 days, 9:51, 0 users, load averages: 0.80, 0.95, 0.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔