Aliqueit Failing to Find Msieve Factors

[EdH]

I'm trying to update all my programs after a long spell and my latest trouble has been that Aliqueit will not find the msieve generated factors when doing ggnfs runs. This appears to be because msieve now labels them as prime (p) rather than probable prime (prp).

Example:

Aliqueit can't find the factors below

Sat Sep  3 11:58:22 2016  p43 factor: 1032645240290090810816003055340155848615831
Sat Sep  3 11:58:22 2016  p47 factor: 26647647369550909677517697388501083393863948447

until I change them to the following:

Sat Sep  3 11:58:22 2016  prp43 factor: 1032645240290090810816003055340155848615831
Sat Sep  3 11:58:22 2016  prp47 factor: 26647647369550909677517697388501083393863948447

Then it runs along happy.

I would change the Aliqueit source to use "factor:" instead of "prp," but then it wouldn't find the factors generated by other programs that use this format:

09/03/16 17:55:02 v1.35-beta @ math58, prp12 = 269899936147
09/03/16 17:55:02 v1.35-beta @ math58, prp25 = 2793457951223996505799291

Any thoughts? (Or, should I just go away...)

Although not a true fix, I seem to remember something about Aliqueit being able to use YAFU for the entire factorization. If someone could point me toward that thread, I could probably use that as a work-a-round.

Thanks for all...

[Dubslow]

Just read the documentation that aliqueit comes with. It mentions the -y option.

[EdH]

Originally Posted by Dubslow

Just read the documentation that aliqueit comes with. It mentions the -y option.

How odd!

This is the entire aliqueit.txt that came with my package:

//aliqueit, computes aliquot sequences
//Mikael Klasson 2009-2011
//mklasson at googles big mail thing
//http://mklasson.com
//
//Additional code by Greebley, bsquared, and bchaffin.

//Note that the program searches for 'libgmp.so.10' upon execution, and it
//should be a sym-link to libgmp.so.10.0.4 also provided.

A C++ program for computing and verifying aliquot sequences. Designed to be run 
autonomously.

The actual computations are mostly done with external programs. Trial division 
and Pollard rho are done internally, P-1/P+1/ECM are done with GMP-ECM, QS is 
done with Msieve or YAFU, and GNFS is done with ggnfs. Aliqueit tries to 
minimise the time spent factoring by running different methods to different 
depths depending on the composite size.

The config file is configured for my system so you'll need to set proper 
executable names and whatnot. Moreover, if you're not running windows you'll 
want to change null_device and ggnfs_clean_cmd.

The program is most simply started with "aliqueit 162126" if you want to work 
on sequence 162126.

The first thing it does in that case is verify correctness of the existing 
alq_162126.elf file (just takes a second or two), after which it resumes where 
the elf file ends.

Known factors can be specified with one or more "-f <factor>" arguments.

"-e" switch skips ecm on the current iteration and goes straight to qs/gnfs.

"-p" runs at idle priority.

"-q" quits after factoring the first number.

"-s <start>" submits the given sequence's elf file to Syd's DB, starting with 
iteration <start>. You'll need wget to use this.

"-d <max_digits>" quits after sequence reaches <max_digits> digits.

"-c <max_cofactor>" quits after sequence passes ecm with a cofactor of 
<max_cofactor> or more digits.

"-b" with -c and -d quits after a number meets both limits.

"-m <max_ecm_level>" ecm will only run to level <max_ecm_level> where 
'1'=20-digit factor, '2'=25, etc.

You can start working at an arbitrary offset using "-i <index> <start_value>" 
argument, e.g.: "aliqueit 162126 -i 10 13169790".

The ecm depth settings seem pretty optimal for <65 digits. For composites of 70 
digits or more the ecm depth is tuned to make the total ecm work take about 1/4 
of the time a qs/gnfs run would. I'd be happy to hear of better ideas.

I've included win32 and win64 executables. The latter isn't really faster as 
the time spent in the program itself is insignificant compared to the external 
factorisation programs. I just like to run native programs when possible.

I'm normally compiling the program with MSVC 2008. Solution/project files for 
that scenario are included. A simple Makefile is also included for linux. 
You'll need the gmp lib to compile on either platform. A consequence of the 
MSVC 2008 compilation is that the executable won't run on windows versions 
earlier than win2k. If you need to run on an older OS I can probably cook up 
another executable for you if you ask me.

Comments and suggestions are most welcome.

You may use the source and program however you see fit. I accept no 
responsibility for anything untoward that may happen to you, though I have no 
reason to suspect any such thing should happen. In the land of the free they 
are happy to try and sue you for anything though. You may not use this program 
unless you accept this agreement and take responsibility for your own actions. 
Otherwise, no soup for you!

Cheers,
Mikael


Links to various excellent factoring programs:
aliqueit would be worthless without these, so cheers for them!
Precompiled versions of most everything, incl. x64 versions: 
http://gilchrist.ca/jeff/factoring/
GGNFS: http://tech.groups.yahoo.com/group/ggnfs/
GMP-ECM: http://gforge.inria.fr/projects/ecm/
Msieve: http://www.boo.net/~jasonp/qs.html
YAFU: http://bbuhrow.googlepages.com/home

If you have problems getting ggnfs up and running, check out 
http://www.mersenneforum.org/showpost.php?p=176126&postcount=11

CTRL-F turns red when I search for -y.

I will have to look further.

Edit: Found it in "whatsnew.txt."

Thanks for all the help...

[jasonp]

Code to prove primality was added to Msieve maybe 18 months ago.

[EdH]

Originally Posted by jasonp

Code to prove primality was added to Msieve maybe 18 months ago.

For the past couple years I was focusing on cycle searching. I've just started back in with making sure my Aliqueit (Ubuntu) page was up-to-date and I'm having lots of "little" things impeding my progress. My fault for not staying on top of all the advancements. However, this still means that Aliqueit is also not up-to-date. I don't think I am cable of making the changes needed without a strenuous effort.

For now the -y option appears to be the solution.

[schickel]

Originally Posted by EdH

For the past couple years I was focusing on cycle searching. I've just started back in with making sure my Aliqueit (Ubuntu) page was up-to-date and I'm having lots of "little" things impeding my progress. My fault for not staying on top of all the advancements. However, this still means that Aliqueit is also not up-to-date. I don't think I am cable of making the changes needed without a strenuous effort.

For now the -y option appears to be the solution.

One option would be to use an older version of Msieve in the Aliqueit folder that does print the factors as "prp". I've done that (unintentionally) on my biggest box (haven't bothered to update the msieve on there yet).

[Dubslow]

Try also looking at ./aliqueit -h, I think that mentions -y?

[EdH]

Originally Posted by schickel

One option would be to use an older version of Msieve in the Aliqueit folder that does print the factors as "prp". I've done that (unintentionally) on my biggest box (haven't bothered to update the msieve on there yet).

I had thought of that, but since I'm making sure my page works and trying to stay with the latest updates, I'd rather try to get all packages working at their latest versions. I might just enter some code in Aliqueit to work with the latest msieve, even though it won't be "pretty." But, I feel "funny" about offering other author's packages on the web, if I've chopped them up. Maybe I'll just note my changes within the code and docs.

Originally Posted by Dubslow

Try also looking at ./aliqueit -h, I think that mentions -y?

I use -h and --help all the time! I don't know why I was so focused (with blinders) on the aliqueit.txt file. Somehow I guess I believed it should contain all.

Thanks everyone!

[chris2be8]

Originally Posted by EdH

I would change the Aliqueit source to use "factor" instead of "prp," but then it wouldn't find the factors generated by other programs that use this format:

Also note that msieve says pnn if the factor is proven prime and found factor: nnn if there's more than 2 factors.

I updated my copy of factMsieve.pl as follows:

if (/p\d+ factor: (\d+)/) {
  if (($1 > 1) && ($1 < $N)) {
    push(@DIVISORS, $1);
  }
}

To make sure we get all factors once and once only.

Chris

[EdH]

Hi All,

Thanks for all the help.

I am now even more confused.

Note: I'm using the python script (factmsieve.py).

All three of my recent new installs and my one updated system failed to find the factors in a ggnfs run on the 89 digit composite in index 2133. They all failed several times. They all succeeded when I changed the two pXX lines to prpXX in test.log. In my study of the Aliqueit source code, I could find no reference to checking test.log. Now all four machines are succeeding fine through that same area of 4788, with no hiccup at all. I've tried several times. I made no changes (other than the removal of the B2scale sections at an earlier time) to the original source.

I am going to have to initialize another machine and see what happens...

(I don't think anyone sneaked in and fixed it during the night...)

[EdH]

Originally Posted by EdH

...
I am now even more confused.
...

Some of my confusion is lifted. But, my wits are in jeopardy!

The reason the machines succeeded is apparently because aliqueit.log held the factors from when I had edited the pXX to be prpXX. I had forgotten to delete it.

But, I think I have pieced together what is happening and it's actually factmsieve.py that is causing the issue. I think I can fix that more easily. (Of course, I've thought a lot of things that weren't quite right, recently...)

Anyway, basically Aliqueit never looks in test.log for the factors. It looks in ggnfs.log. The factors are supposed to be placed in ggnfs.log by factmsieve.py. But, factmsieve.py isn't finding the factors in test.log because they are labeled pXX instead of prpXX.

Questions as I experiment:

Does msieve output lines with prpXX anymore? If so, is "factor:" shown in lines with "prpXX" as well as "pXX" in the msieve log? If that is the case, perhaps factmsieve can simply look for that instead of "prp." Right now I'm testing whether a combination look can succeed.