[QUOTE=R.D. Silverman;140265]Actually, I meant Franke, Aoki, CWI, et. al., rather than you.[/QUOTE]

Uhm, so when you wrote

[QUOTE] It's been a long time since we heard an update from Bruce.......
[/QUOTE]

you were thinking that I

(1) had info on the current Franke, Aoki, CWI, et. al project, presuming
that there is one; and
(2) am authorized to circulate updates?

I'm flattered, but neither is the case. Meanwhile, my post above
reports the factorization of 10,257+ C208 snfs Childers/Dodson,
c208 = p61*p148. This is the one for which there was a matrix
miss in msieve, perhaps due to the number having been under-sieved
to begin with. -Bruce

tiny factoring failed
 

I'm using version 1.30 on the v5 server to crack incoming factors. I'm getting the error "tiny factoring failed" most of the time on the composite 131264085676711234219725791

Has this been fixed? Any ideas on how to make msieve always return the factors for small numbers?

This is a mysterious long-standing bug in the tiny factoring code, and is still present for the latest version. A user noticed this a while ago and was making the changes to run ECM when the tiny QS code failed, but that has its own problems. When the factors are much smaller than ECM expects, the algorithm succeeds but finds a 'factor' of the input, so that ECM has to work harder than would be prudent for general inputs.

I've been meaning to ask: the one thing I don't like about the current library's fire-and-forget-ness is that on an internal error, the code calls exit(-1) from many different places. Can the v5 server framework handle this happening?

[QUOTE=jasonp;140350]This is a mysterious long-standing bug in the tiny factoring code, and is still present for the latest version.[/quote]

Let me know if this ever gets fixed. In the meantime, I'll loop 100 times before giving up.

[quote]I've been meaning to ask: the one thing I don't like about the current library's fire-and-forget-ness is that on an internal error, the code calls exit(-1) from many different places. Can the v5 server framework handle this happening?[/QUOTE]

I think so. Msieve is a DLL on the v5 server, so each PHP call basically re-inits the msieve code.

[QUOTE=bdodson;140325]Uhm, so when you wrote

you were thinking that I <snip>

[/QUOTE]


Actually, I was referring to a different thread entirely: "The dog that
didn't bark in the night". Sorry for the confusion. Mea Culpa.

[QUOTE=bdodson;140263] So that's c208 = p61*p148 with p61 =

6621650829759394867011952029659651154933062041670057842400167
[/QUOTE]
Great, this had me worried.
[QUOTE]
On the clusters, 6,392+ c262 finished sieving and was shipped off
to Cal State, Fullerton (and Greg). We made a last minute addition
of 5,389+ at difficulty 272 (a 2/3 ratio would sugest c. c180 gnfs,
perhaps comparable to the current 5, 421- project).[/QUOTE]
You guys are going to give me an ulcer with these huge jobs :) On the one hand, Tom and friends have a big head start, but on the other hand the two of you have enormous resources.

[quote=jasonp;140350]This is a mysterious long-standing bug in the tiny factoring code, and is still present for the latest version. [/quote]

I think I've fixed the bug. It occured because the matrix building code did not prevent duplicate partial relations from being added to the matrix, specifically this loop:

[code]
for (i = 0; i < ncols; i++) {
tiny_relation *r = params->relation_list + i;
for (j = 0; j < r->num_factors; j++) {
row = r->fb_offsets[j];
params->matrix[row][i / 64] ^= bitmask[i & 63];
}
if (r->large_prime > 1) {
r = params->partial_list +
LARGE_PRIME_HASH(r->large_prime);
for (j = 0; j < r->num_factors; j++) {
row = r->fb_offsets[j];
params->matrix[row][i / 64] ^= bitmask[i & 63];
}
}
}
[/code]

blindly looks up the entry into params->partial_list that matches the large prime of 'r' and adds that relation to the matrix, regardless of whether or not it has already added it. So if 3 or more relations share a large prime, multiples of the first relation are added to the matrix.

I hacked a fix, adding an extra vector into params to track whether or not the partial_list entry has already been added for a given large prime. Repeated tests of 131264085676711234219725791 always yielded the correct factorization, but trials with different small inputs that have caused problems would probably be necessary.

- ben.

[QUOTE=bsquared;140732]I think I've fixed the bug. It occured because the matrix building code did not prevent duplicate partial relations from being added to the matrix[/QUOTE]
I don't doubt that making the change causes the factorization to work, but isn't it expected that a given relation could appear in the matrix multiple times? NFS relations sometimes appear in dozens of different NFS matrix columns. In fact, NFS filtering sometimes makes a relation appear multiple times in the *same* matrix column, though in that case the code reduces the number of times a relation appears to 0 or 1 times.

The list of relations that go into each matrix column is the 'cycle basis' for the matrix, and my understanding was always that it didn't matter how often relations appear, as long as all the relations appear at least once and no columns are empty or duplicates of each other.

[quote=jasonp;140756]
The list of relations that go into each matrix column is the 'cycle basis' for the matrix, and my understanding was always that it didn't matter how often relations appear, as long as all the relations appear at least once and no columns are empty or duplicates of each other.[/quote]

I'm confused by this last part, or I'm misunderstanding your code. Relations are columns in the matrix, so "at least once" conflicts with "no duplicate columns".

Duplication of columns appears to be exactly what's happening. There aren't many duplicates, but there also aren't many total relations. In the example I found 3 duplicates, or about 5% duplication.

[edit]
Ok, I see what I was missing. The column index is not incremented before adding the partial relation, so the partial is not duplicated but is instead XOR'ed with the initial relation. Is it possible that two different relations in relation_list XOR'ed with different partial relations produce a duplication or a null? Maybe the fix is just adding a basic level of filtering - duplication/null checking in the columns.

[QUOTE=bsquared;140760]
Ok, I see what I was missing. The column index is not incremented before adding the partial relation, so the partial is not duplicated but is instead XOR'ed with the initial relation. Is it possible that two different relations in relation_list XOR'ed with different partial relations produce a duplication or a null? Maybe the fix is just adding a basic level of filtering - duplication/null checking in the columns.[/QUOTE]
I guess that's necessary; when there are only a few relations, it's entirely possible to get matrix columns that look the same.

Basically the code maintains a hashtable of partial relations and an array of full relations. A given hash bucket only contains one partial relation, and aliases in the hashtable are thrown away. Thus, when another partial relation with the same large prime appears, you need only check the hashtable once and if the large prime matches then you have a cycle. That second partial relation is stored in the full array with the understanding that all partial relations with that large prime will be XOR-ed with the relation out of the hashtable.

[quote=jasonp;140773]I guess that's necessary; when there are only a few relations, it's entirely possible to get matrix columns that look the same.

Basically the code maintains a hashtable of partial relations and an array of full relations. A given hash bucket only contains one partial relation, and aliases in the hashtable are thrown away. Thus, when another partial relation with the same large prime appears, you need only check the hashtable once and if the large prime matches then you have a cycle. That second partial relation is stored in the full array with the understanding that all partial relations with that large prime will be XOR-ed with the relation out of the hashtable.[/quote]

Yeah, I followed all that in the code - it is a very clever way of counting/tracking full from partial relations. Much better than my code, which sorts a list and iterates to count pairs. If the bug is indeed duplication due to XOR'ing, then my code should have the same bug because it builds the matrix pretty much the same way as yours. But it doesn't (at least, I haven't seen it fail yet in the same way). My Guassian elimination is quite a bit different, which is maybe how it avoids the problem.

By the way, how did you design the hash function for doing the partial relation storing? Does that particular function minimize collisions in the interval you are mapping to somehow?