Feedback for new MPQS utility sought

[smh]

input to factor: factoring 1251113070752508635091254775733031861914621515967125028042245367160549153736903792446325387413597651
probable prime factor: 24948940438712878811224813097421187454482816577
probable prime factor: 50146942064568647740731181087923885752797750645042963

If you whish, you can submit this factor to: http://homepage2.nifty.com/m_kamada/...orizations.htm as it completes the factorization of (7*10^143-43)/9

This was the last composite < 101 digits left over.

If you don't want to submit this, let me know and i'll do it.

[jasonp]

Originally Posted by JHansen

No offence intended what so ever.

No offense taken

Originally Posted by JHansen

Let my last post be a warning to everyone trying to make a post while horribly intoxicated by (way too much!) alcohol

I think it can generally be regarded as good advice to avoid talking
about computational number theory when drunk. Most likely it will be
in a social situation, and others may ask for some of what you're having.

jasonp

[jasonp]

Originally Posted by error404

Jason,

For my second test using distributed SIQS, I used smh_c100.txt

[...]

Moving msieve.tgz to the fourth system, I started msieve085 and found the
correct factors.

[...]

found 121974 relations (16262 full + 105712 partial), need 69540
begin with 1823643 relations
reduce to 332448 relations in 11 passes
attempting to read 16262 full and 332448 partial relations

Outstanding.

Wow, *look* at all those partials from the three runs combined!
I bet you could have run your machines for half as long and still
gotten enough partials to finish the factorization. Unfortunately I
don't see a way to determine that while a factorization is running
unless you move to a client-server model that has a global view
of how you're doing.

Maybe a poor-man's substitute would be a perl script that ran
the separate processes, concatenated the output, tried to
restart from the combined file and would repeat the process if
more relations were needed.

jasonp

[smh]

I started 2 c101's last wednesday, and this morning (after 120 hours) , both screen output looked like the following

....
failed to read relation 1631597
failed to read relation 1631602
failed to read relation 1631621
failed to read relation 1631625
failed to read relation 1631626
failed to read relation 1631630
failed to read relation 1631630
recovered 1871 full and 30316 partial relations
recovered 206231 polynomials
attempting to build 58898 cycles

[xilman]

Originally Posted by jasonp

No offense taken

I think it can generally be regarded as good advice to avoid talking
about computational number theory when drunk. Most likely it will be
in a social situation, and others may ask for some of what you're having.

jasonp

Indeed.

Jes: what kind of schnapps was it? I may get some, as I'm a great believer in such things.

My recommendations: almost all versions of Oude Jenever, most single malt Scotch, Stroh 80 rum, La Fée absinthe and 151-proof (i.e. 75.5%) golden Bacardi.

Be very careful with the rums (and the absinthe if you drink it neat as I do - it's 68% alcohol). Unless you are accustomed to drinking booze in which water is a minority constituent, they can cause severe discomfort.

Another cautionary tale: some years ago I was with my then fiancee (now wife) and some friends who were feeding us fondue. Accompanying the bread and cheese was a bottle of Pflumli, which is a kind of plum schnapps. As well as sipping the booze, it's quite pleasant to dip the bread cube into the schnapps before putting it into the cheese sauce. Anyway, I was sipping some 50% alcohol when our host made me laugh. I inhaled several cc of it. This is a seriously bad idea.

The next couple of minutes were spent coughing violently. As soon as I'd recovered enough I had to go and lie down for half an hour because snorting alcohol is a very effective method of becoming very drunk very rapidly. I can't honestly recommend it.

I'll save the stories about drinking with other CNT people for another time, especially the one about how I was introduced to Oude Jenever.


Paul

[jasonp]

Originally Posted by smh

I started 2 c101's last wednesday, and this morning (after 120 hours) , both screen output looked like the following

....
failed to read relation 1631597
failed to read relation 1631602
failed to read relation 1631621
failed to read relation 1631625
failed to read relation 1631626
failed to read relation 1631630
failed to read relation 1631630
recovered 1871 full and 30316 partial relations
recovered 206231 polynomials
attempting to build 58898 cycles

I'm trying to get to the bottom of why this sometimes happens. I know
it will happen if you do two msieve runs simultaneously in the same directory.
The hanging behavior was fixed in version 0.85 but that uses a savefile
format that changed in version 0.84 and is not compatible with previous
versions. If your original run used 0.84 then a restart with 0.85 may salvage
some of your work, though not enough to complete the factorization.

smh, I'm really sorry my code keeps wasting your time. I can try and
build a custom version to recover some of the work you've done; we
can discuss it off-list if we're still on speaking terms

jasonp

[error404]

Jason,

May I suggest that you post the PM you send to me this morning.
From : jasonp
To : error404
Date : 2004-11-29 07:01
Title : Re: msieve.dat
This message answers a lot of questions.


I am getting inconsistent results when I concatenate msieve.dat files.
When I concatenate 3 or more, I normally get
failed to read relation 237919

When I only concatenate 2 files, it normally works. Thus, I am finding
it best to do a round robin instead of all 5 systems at once.

[quote]
>I've never done network programming, but do you
>think there would be an interest in a client-server
>version of the code? Obviously it would not be
>something you'd trust to work over the Internet,
>but it could greatly help jobs on a small LAN.

YES!!! I would be delighted to have an automated method of sneaker net.

Tom

/******************************************************************************/

Concatenate 5 different msieve.dat files.

p4-2535#
p4-2535# time ./qs085 < rsa110.txt

Msieve v. 0.85
random seeds: 00000bfa 41ab1177
input to factor: factoring 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
Mon Nov 29 06:09:27 2004
using multiplier of 3
Mon Nov 29 06:09:30 2004
using sieve block of 65536
using a sieve bound of 2016551 (74992 primes)
using large prime bound of 604965300
using double large prime bound of 6413791293514800
restarting with 3172 full and 470752 partial relations

found 176575 relations (3172 full + 173403 partial), need 75120
begin with 470752 relations
reduce to 272492 relations in 6 passes
attempting to read 3172 full and 272492 partial relations
failed to read relation 96004
failed to read relation 96018
|
|
failed to read relation 237919
failed to read relation 237946
recovered 3158 full and 272456 partial relations
recovered 259175 polynomials
freed 1158 duplicate relations
freed 173077 duplicate relations
rebuilding graph...
attempting to build 343 cycles
found 343 cycles in 3 passes
distribution of cycle lengths:
length 2 : 277
length 3 : 51
length 4 : 13
length 5 : 2
largest cycle: 5 relations
Mon Nov 29 06:10:05 2004
error: not enough relations to find linear dependencies
36.783u 0.914s 0:37.80 99.7% 87+110122k 0+0io 0pf+0w
p4-2535#

/******************************************************************************/

Concatenate 2 different msieve.dat files.

p4-2535#
p4-2535# time ./qs085 < rsa110.txt
Msieve v. 0.85
random seeds: 00000c1b 41ab12a4
input to factor: factoring 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
Mon Nov 29 06:14:28 2004
using multiplier of 3
Mon Nov 29 06:14:31 2004
using sieve block of 65536
using a sieve bound of 2016551 (74992 primes)
using large prime bound of 604965300
using double large prime bound of 6413791293514800
restarting with 860 full and 128011 partial relations

sieving in progress (press Ctrl-C to pause)
found 937 relations (865 full + 72 partial), need 75120
found 943 relations (870 full + 73 partial), need 75120
found 948 relations (875 full + 73 partial), need 75120
found 955 relations (880 full + 75 partial), need 75120
found 960 relations (885 full + 75 partial), need 75120
found 965 relations (890 full + 75 partial), need 75120
found 971 relations (895 full + 76 partial), need 75120
found 977 relations (898 full + 79 partial), need 75120
found 977 relations (898 full + 79 partial), need 75120

/******************************************************************************/

[jasonp]

Originally Posted by error404

May I suggest that you post the PM you send to me this morning.
From : jasonp
To : error404
Date : 2004-11-29 07:01
Title : Re: msieve.dat
This message answers a lot of questions.

See end of message.

Originally Posted by error404

I am getting inconsistent results when I concatenate msieve.dat files.
When I concatenate 3 or more, I normally get
failed to read relation 237919
restarting with 3172 full and 470752 partial relations

found 176575 relations (3172 full + 173403 partial), need 75120
begin with 470752 relations
reduce to 272492 relations in 6 passes
attempting to read 3172 full and 272492 partial relations
failed to read relation 96004
failed to read relation 96018
|
|

Aaargh! If this line is to be believed, you have more than enough relations
to finish the factorization right now, but the program isn't reading them!
Can you try 'cascading': concatenate two .dat files, restart, hit Ctrl-C,
concat another .dat file, restart, etc.? If that still doesn't work,
then it may be something with the relations themselves.

Note that a run needs to produce fresh relations to be useful; taking your
5 outputs, concatenating them, and giving the complete result back to
all 5 sieving machines will not introduce any new information, only a huge
number of duplicates (this may be what's happening).

You could concatenate all the files and try a single restart, and if that
doesn't produce enough relations then just restart every siever without
modifying its .dat file. Later, stop every siever and repeat the process.

Quoted message below.
jasonp

Originally Posted by error404

1: the rate that relations are found is progressive.
The more relations in the msieve.dat file, the faster
the rest of the relations can be found.

2: each time qs085 is started, it generates a different
seed. This generates a unique set of relations for each msieve.dat file.

3: which is more efficient, combining the msieve.dat
files early and often, or waiting until the summation
of all the msieve.dat files approaches about 50% and
then combine them?

Every time you restart the program it chooses new
random seeds. Those random numbers are used to
choose the parameters for new polynomials. For big
factorizations, the number of possible polynomials
is so large that duplicates are very unlikely. Of course
if you do choose duplicate polynomials you will get
duplicate relations that the code will filter out as
useless.

The relations found are divided into full relations
and partial relations. Full relations from different
runs just add together. Partial relations are different:
the program can combine many partial relations into
one to simulate a full relation. The number of full
relations that can be derived this way depends on
the size of the total pool of partial relations you
have available. It's nonlinear in that size: folks have
found that for P partial relations, when the pool is
large, you can get k^4 full relations for some k.
Double the size of the pool and you get 16x more
full relations out of it. As each run progresses, full
and partial relations accumulate at about a constant
rate.

It doesn't matter whether you do or do not
concatenate savefiles, and when running on dif-
ferent machines simultaneously it doesn't matter
how far each one gets. The only thing that matters
is the size of the combined pool of partials, and that
increases linearly as the machines keep running. When
the progress meter tells you there are (x full + y
partial) relations, it's half lying: you have many
more partials than that in your pool but only 'y'
full relations can be derived from them at the present.
If you stopped a run and added in the savefile from
another machine so that the pool of partials doubled,
then after a restart you'd have ~16*y partials, way
way more than before the restart.

The catch is that to get that kind of quartic be-
havior the size of the pool has to be sufficiently large,
say a few hundred thousand partials. You can
calculate the pool size on a unix machine by running

grep R msieve.dat | wc

while a run is in progress. And remember that the
size of the pool is linear in the number of machine-
hours you spend building it, no matter what you do
with savefiles.

Does this clear things up?

Originally Posted by error404

As to your suggestion to provide documentation,
remember the UNIX maximum:
"Real programmers don't document, if it was
hard to write, it should be hard to read!"

See the Guide to Real Programmers on my web page.
And most of the time I spend at work goes into
reverse engineering code that other people have
written

[xilman]

Originally Posted by jasonp

Aaargh! If this line is to be believed, you have more than enough relations
to finish the factorization right now, but the program isn't reading them!
Can you try 'cascading': concatenate two .dat files, restart, hit Ctrl-C,
concat another .dat file, restart, etc.? If that still doesn't work,
then it may be something with the relations themselves.

Note that a run needs to produce fresh relations to be useful; taking your
5 outputs, concatenating them, and giving the complete result back to
all 5 sieving machines will not introduce any new information, only a huge
number of duplicates (this may be what's happening).

I have a couple of observations, based on rescuing MPQS computations on various numbers over the last fifteen years or so.

First, if you have a Unix box, merging two or more sets of relations can usually be well done with a pipeline of the form "sort *.rels | uniq" though the precise details may differ depending on the precise format of the relations. This not only strips out duplicates, it also tends to put relations which form cycles relatively close to one another, though that's only an otherwise unintended benefit.

Secondly a "preening" program is invaluable for rescuing possibly corrupted relations files. It's a filter which repeatedly reads a relation and verifies that all the given primes do indeed divide the given quadratic residue. If a relation passes, it is written on stdout. If there is anything wrong with it, it's written to stderr. After concatenating all the relations (and possibly piping them through the merge-sort given above) and redirecting the output streams to files, you have a file of good relations and another one (preferably empty) of material that needs more attention.

Paul

[smh]

smh, I'm really sorry my code keeps wasting your time. I can try and
build a custom version to recover some of the work you've done; we
can discuss it off-list if we're still on speaking terms

Don't worry, it's just two boxes which would otherwise have been idle anyway.

I deleted the savefiles already. I might look for some more numbers, although most <= 100 digit factorizations wanted for various projects are already done. 105-110 digits probably takes to long and would be faster with GNFS (for which i wasted quite a few cpu cycles too, but things look better with every new version. Hope the same for msieve).

[error404]

Jason,

Using Paul's suggestion and filtering the 5 data files creates a
248 MB file as opposed to concatenating them and creating a 593 MB
file.

However, as seen below, when I restart with the cleaned up and
filtered msieve.dat, everything is rejected and qs085 starts all
over again. I tried this twice with the same results.


A bit of detective work shows that somehow, I got a few hundred
lines of C code dumped into the msieve5.dat file. Then of
course,
# sort *.dat | uniq
adds its own advertisement to the end of the file.

The problem is two fold. The 140 MB msieve5.dat exceeds the buffer
size for EMACS, KWrite, and KWord. Opening the 247 MB msieve.dat
file will cause KWrite and KWord to freeze.

The worse news is that my Titanium laptop, using BBEdit, which
can easily open a gigbyte text file, cratered the its hard drive
Sunday and that is not an option for the next few days.

Any ideas on how to remove the text from the ?.dat files?

Tom

/******************************************************************************/

Script started on Mon 29 Nov 2004 01:30:18 PM CST
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:# ls -l
total 578640
-rwxr--r-- 1 root root 87270174 2004-11-29 13:25 msieve1.dat
-rwxr--r-- 1 root root 105056412 2004-11-29 13:26 msieve2.dat
-rwxr--r-- 1 root root 137021825 2004-11-29 13:27 msieve3.dat
-rwxr--r-- 1 root root 123805743 2004-11-29 13:23 msieve4.dat
-rwxr--r-- 1 root root 139322861 2004-11-29 13:25 msieve5.dat
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:# sort *.dat | uniq > msieve.dat
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:# cat msieve1.dat msieve2.dat msieve3.dat msieve4.dat msieve5.dat >> all.txt
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:# ls -l
total 1398960
-rwxr--r-- 1 root root 592477015 2004-11-29 13:34 all.txt
-rwxr--r-- 1 root root 247525520 2004-11-29 13:32 msieve.dat
-rwxr--r-- 1 root root 87270174 2004-11-29 13:25 msieve1.dat
-rwxr--r-- 1 root root 105056412 2004-11-29 13:26 msieve2.dat
-rwxr--r-- 1 root root 137021825 2004-11-29 13:27 msieve3.dat
-rwxr--r-- 1 root root 123805743 2004-11-29 13:23 msieve4.dat
-rwxr--r-- 1 root root 139322861 2004-11-29 13:25 msieve5.dat
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:#
root@k8-2200:/mnt/D:# exit
Script done on Mon 29 Nov 2004 01:35:00 PM CST

/******************************************************************************/

Script started on Mon Nov 29 13:58:14 2004
gigabyte#
gigabyte# time ./qs085 < rsa110.txt

Msieve v. 0.85
random seeds: 00001094 41ab7f6c
input to factor: factoring 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
Mon Nov 29 13:58:36 2004
using multiplier of 3
Mon Nov 29 13:58:39 2004
using sieve block of 65536
using a sieve bound of 2016551 (74992 primes)
using large prime bound of 604965300
using double large prime bound of 6413791293514800

sieving in progress (press Ctrl-C to pause)
found 5 relations (5 full + 0 partial), need 75120
^C
received signal 2; shutting down
found 5 relations (5 full + 0 partial), need 75120
found 5 relations (5 full + 0 partial), need 75120
Mon Nov 29 14:13:36 2004
894.564u 3.195s 15:00.04 99.7% 76+61089k 0+4io 0pf+0w
gigabyte# exit
Script done on Mon Nov 29 14:13:44 2004

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

"probable prime" : "composite",
cache_size = 16384; break;
cache_size = 32768; break;
cache_size = 8192; break;
log(2.0) + .5);
mp_sprintf(&n, 10));
mp_sprintf(&n2, 10));
:"0"(code))
:"=a"(a), "=b"(b), "=c"(c), "=d"(d) \
|
|
|
while (((uint32)(1) << j) < prime_list[num_primes - 1])
while (isdigit(n_string[i]))
{128, 500, 40, 1 * 65536},
{183, 2000, 40, 1 * 65536},
{200, 3000, 50, 3 * 65536},
{212, 5400, 100, 3 * 65536},
{233, 11000, 80, 3 * 65536},
{249, 30000, 30, 40 * 65536},
{266, 50000, 30, 48 * 65536},
{283, 55000, 80, 56 * 65536},
{298, 60000, 80, 64 * 65536},
{315, 65000, 150, 72 * 65536},
{332, 70000, 300, 80 * 65536},
{347, 75000, 300, 88 * 65536},
{64, 100, 40, 1 * 65536},
}
} while(--i > 1);
--jasonp@boo.net 11/26/04
SIQS polynomials is not cheap anymore. */
if the factor base data does not fit in cache then switching
should be large when the factor base is large. This is because
#define SMALL_PRIME_BOUND 5000
#else
#endif
#if defined(__GNUC__)
#include "msieve.h"
#include <time.h>
--------------------------------------------------------------------*/
/* Note that contrary to popular wisdom, the SIQS sieve size
/*--------------------------------------------------------------------*/

/******************************************************************************/

This source distribution is placed in the public domain by its author,
benefit from your work.
errors.
fb_t * build_factor_base(mp_t *n, uint32 *fb_size, uint32 *multiplier) {
fb_t * build_one_factor_base(mp_t *n, uint32 *fb_size) {
int main(int argc, char **argv) {
please consider making those additions public too, so that others may
sieve_param_t prebuilt_params[] = {
uint32 *prime_list;
uint32 get_sieve_block_size(void) {
uint32 num_primes;
uint32 num_primes_alloc;
uint32 stop_sieving = 0;
useful. Again optionally, if you add to the functionality present here
void do_trial_factor(mp_t *n) {
void factor_integer(char *n_string) {
void fill_prime_list(uint32 fb_size) {
void get_sieve_params(uint32 bits, sieve_param_t *params) {
void handle_signal(int sig) {
without having to notify anyone. I disclaim any responsibility for any
}
};

/******************************************************************************/