[QUOTE=chalsall;381055]Conversely, perhaps with the new server hardware this will no longer be an issue.[/QUOTE]

You've probably hit the main point right there... the new server doesn't seem to have a problem. At least not now. I guess when we get qbit computers doing TF work and submitting HUGE numbers, then maybe we'll worry about how well the server is able to check them. :)

Checking if a submitted q is a factor of Mp is trivial, and fast. Even with perl, for example, without any external tool. Also, checking if a submitted factor is prime, is trivial and fast, but a bit slower than the above. Factoring q is a bit slower, but this is still fast for 30-50 digits numbers, and it has to be done only for few "candidates", that pass (or say "escape"?) the two tests above. I can't believe this was a problem, even for the old server. If it occasionally crashed, other might have been its reasons... :wink:

[QUOTE=LaurV;381052]...[edit you make the "queued check" and I promise I will feed your queues with fake factors :razz: ...[/QUOTE]

Punk kid. :) This is why we can't have nice things. :yucky:

It wouldn't *really* be necessary at the moment, but think back to the days of yore, like a week ago, when people might submit a big set of results and it would take several minutes to come back to them with a thumbs up.

Just not a good user experience. If you have a better idea of what would work better besides queuing them up to check at a more convenient time.. ? I admittedly haven't put that much thought into it, and checking them later rather than having the website do it at the "point of sale" seemed like the most obvious approach, but maybe there's something better that makes everyone happy.

[QUOTE=Madpoo;381059]I'm guessing that normal factoring is likely to find the smallest prime factor, and it's the ECM and P-1 methods that might find a factor that could be composite... would that be generally true?[/QUOTE]Generally true, but not always. If someone does trial factoring beyond finding the first factor then there's a chance they could find a composite factor. For example, if someone should decide to TF [url=http://www.mersenne.ca/exponent/7508981]M7,508,981[/url] up to 2[sup]64[/sup] (about 0.25GHz-days of effort) they would find 10 prime factors, and they would also find another 10 composite factors). An extreme example for sure, but it can happen to a lesser degree in many cases.

It's not uncommon to find composite factors via P-1, I forget the statistical average but I would hazard a wild guess it's somewhere around 5% of P-1 factors are found as composites. Probably similar with ECM but I have little experience there.

[QUOTE=James Heinrich;381067]For example, if someone should decide to TF [url=]http://www.mersenne.ca/exponent/7508981[/url] up to 2[sup]64[/sup] (about 0.25GHz-days of effort) they would find 10 prime factors, and they would also find another 10 composite factors). An extreme example for sure, but it can happen to a lesser degree in many cases.[/QUOTE]

Care to correct your URL? :wink: :smile:

[QUOTE=LaurV;381052]...I will feed your queues with fake factors :razz:[/QUOTE]The thought occurred to me that a quick way to check for and/or screen out composite factors would be to create a lookup table of all possible composite factors. If a factor is submitted it would be relatively quick to see if that factor is in the known-composite-factors table and if so we would already have the prime-factor breakdown of said factor with a simple query.

[code]if (is_known_composite(factor)) {
process result for each of prime factors (but since we know about
this composite factor we already know about the prime factors so
probably will reject the "new" result as unneeded.
} else if (is_known_prime_factor(factor)) {
most likely ignore result as not-needed
} else {
confirm if submitted factor is prime or not, either by immediate
factoring or by adding to the factor-queue as discussed elsewhere
}[/code]In the first two cases we can get away with an indexed SQL query which should be fast to confirm a factor is prime and/or break a known composite into prime factors. Hopefully in most cases these would come back negative because people are only submitting new factors, but this kind of check should easily shut down LaurV's proposed attack vector of generating composite factors from known smaller factors without any expensive server-side factoring (especially where many factors are known and can generate composites of hundred of bits).

edit: [QUOTE=chalsall;381068]Care to correct your URL? :wink: :smile:[/QUOTE]Did, thanks :blush: Now you can edit your quote of my failed URL :wink:

[QUOTE=James Heinrich;381070]edit: Did, thanks :blush: Now you can edit your quote of my failed URL :wink:[/QUOTE]

Done.

Gosh, it almost seems like we might pull off a "flash mob" some day! :wink:

[QUOTE=James Heinrich;381070]The thought occurred to me that a quick way to check for and/or screen out composite factors would be to create a lookup table of all possible composite factors.[/QUOTE]

Could work. I was trying to imagine how big the table would be.

There are 1,065,769 exponents that have 3 or more factors, and counting the ones with 2 or more adds an additional 4.8 million exponents to the tally.

10 factors = 2 exponents
9 factors = 10 exponents
8 factors = 72 exponents
7 factors = 276 exponents
6 factors = 1,567 exponents
5 factors = 15,251 exponents
4 factors = 131,593 exponents
3 factors = 916,998 exponents
2 factors = ~4.8 million
1 factor = ~29.5 million

Someone else could do the permutations to see how many composites could be made for each exponent. The total table wouldn't be too bad and if it had an index, lookups in real time seems like it would be able to check and see if someone's just submitting the product of two existing factors.

The highly factored exponents (10 factors each) for those playing along at home are:
7508981 and 566448359

[QUOTE=Madpoo;381073]10 factors = 2 exponents [b]@ 1013 = 2026[/b]
9 factors = 10 exponents [b]@ 502 = 5,020[/b]
8 factors = 72 exponents [b]@ 247 = 17,784[/b]
7 factors = 276 exponents [b]@ 120 = 33,120[/b]
6 factors = 1,567 exponents [b]@ 57 = 89,319[/b]
5 factors = 15,251 exponents [b]@ 26 = 396,526[/b]
4 factors = 131,593 exponents [b]@ 11 = 1,447,523[/b]
3 factors = 916,998 exponents [b]@ 4 = 3,667,992[/b]
2 factors = ~4.8 million [b]@ 1 = ~4,800,000[/b]
1 factor = ~29.5 million [b]@ 0 = 0[/b][/quote]So that gives roughly 10.5-million records, not too bad.

[QUOTE=Madpoo;381073]The highly factored exponents (10 factors each) for those playing along at home are: 7508981 and 566448359[/QUOTE]And the rest of them are listed here: [url]http://www.mersenne.ca/manyfactors.php[/url] :smile:

Does the system try to divide submitted factors by any already known factors? For example, trying to factor 1500446411622255674968292288073771581046353 might seem a bit daunting but if it was known that 285341279 and 18694135089678809 were already factors for M7508981, then you could divide the gargantuan number by the two smaller ones (in this case they would both be divisors) and you would end up with 281287549065522023 which could have been a previously unknown factor, and a lot easier to check.

[QUOTE=TheMawn;381081]Does the system try to divide submitted factors by any already known factors?[/QUOTE]

No.

IMO, we don't need to worry about the user experience of someone trying to spam the server with known composite factors.

If I understand correctly, the only "good" users that might suffer a problem now are those using the manual results page to submit a big batch of factors.

YAFU is spawned for two reasons: 1) Verify a factor is prime, and 2) factor a composite factor.

We can eliminate 95% of the overhead from forking YAFU if we can move the "verify a factor is prime" code to PHP. We could do a few PRP tests using "bc" which is automatically included in PHP. Or we could link GMP into PHP which might allow us write better (true primality test rather than PRP) and faster code to verify a factor is prime.