Reference material discussion thread

[nomead]

About the manual assignment progress reports. Different programs have wildly different progress logs. Example from Mlucas:

[May 20 03:38:41] M50346019 Iter# = 24280000 [48.23% complete] clocks = 00:26:42.587 [160.2587 msec/iter] Res64: 54912F2731A45A41. AvgMaxErr = 0.042192089. MaxErr = 0.062500000. Residue shift count = 12144693.

But minimum common requirements should be current iteration count and Res64/shift so that interim residues could be stored, if needed.

I propose that instead of having the manual results submission form decipher many different log formats, there should be a simple common format, and let the client submission script do the conversion to that.

[kriesel]

Originally Posted by nomead

About the manual assignment progress reports. Different programs have wildly different progress logs. Example from Mlucas:

[May 20 03:38:41] M50346019 Iter# = 24280000 [48.23% complete] clocks = 00:26:42.587 [160.2587 msec/iter] Res64: 54912F2731A45A41. AvgMaxErr = 0.042192089. MaxErr = 0.062500000. Residue shift count = 12144693.

But minimum common requirements should be current iteration count and Res64/shift so that interim residues could be stored, if needed.

I propose that instead of having the manual results submission form decipher many different log formats, there should be a simple common format, and let the client submission script do the conversion to that.

I'm not concerned about Mlucas format, because the word is Madpoo and EWMayer were working together on implementation of the Primenet API in Mlucas v19, in development now. Mlucas is a cpu application, which is what the Primenet API was designed for and implemented for on the server and in prime95 & mprime.

I requested only CUDALucas progress reporting support, initially.

But what client submission script? Some gpu applications lack any client submission script, so all work reservation and submission is manual. Manual progress updates will be done only as needed in that use case. CUDALucas, for example, and CUDAPm1, have no client submission scripts. (Also many earlier versions of gpuowl, but there are so many log styles in gpuowl versus version, and many different gpuowl versions are fastest depending on the exponent / fft length, so I think supporting all the older useful versions of gpuowl progress reporting by the manual submission page is too much to ask.)

[nomead]

Originally Posted by kriesel

I'm not concerned about Mlucas format, because the word is Madpoo and EWMayer were working together on implementation of the Primenet API in Mlucas v19, in development now.

And it currently uses a Python script adapted from mfloop.py, works well enough but of course doesn't handle progress reports.

But what client submission script?

For CUDALucas / clLucas, there's llloop.py included in primetools - haven't tested it though, since I put about 99% of GPU effort into factoring now. But it shouldn't be that hard to adapt to other GPU LL / PRP applications.

(Also many earlier versions of gpuowl, but there are so many log styles in gpuowl versus version, and many different gpuowl versions are fastest depending on the exponent / fft length, so I think supporting all the older useful versions of gpuowl progress reporting by the manual submission page is too much to ask.)

Pretty much what my point was, choose some simple common format and then stick to it. So if the client output format changes, adapt the script, not the submission page. Like worktodo.txt - easy to parse and it's been around long enough that pretty much everything should support it directly. mfaktc seems to be pretty flexible with its output even now, but I see that as less of a problem anyway. I mean, how many people do GPU trial factoring work that takes so long, that expiration without progress reports could be a problem?

[kriesel]

Originally Posted by nomead

For CUDALucas / clLucas, there's llloop.py included in primetools - haven't tested it though, since I put about 99% of GPU effort into factoring now. But it shouldn't be that hard to adapt to other GPU LL / PRP applications.

I contacted the author some time ago; essentially no one used lloop.py and it was abandoned years ago. And it does not do progress reports.

how many people do GPU trial factoring work that takes so long, that expiration without progress reports could be a problem?

Agreed. And why I emphasized gpu primality test progress reporting, not P-1 or TF. Weeks-long TF or P-1 assignments are possible but not common.

A possible benefit of CUDALucas or cllucas progress reporting, that is not very relevant to the other gpu applications, is early detection of pathological runs that are producing all 0x0 or 0x02 or 0xfffffff800000000 interim res64, with potential savings of days or weeks of wasted run time. Some users don't recognize those as an issue, but if they could be persuaded to do interim progress reports, the server might educate them!
Mainly though, manual progress reporting is about preventing expiration of computations that are progressing, and reducing the chafing of other users who see no indicated progress at server reports and imagine wrongly that means no progress is occurring.

[kriesel]

The purpose of this post is to describe a shared foundation. Posting claims counter to what's here may indicate someone is an unaware novice, or is a troll. (Once I'm done weeding out my errors, with some help from others, that is.) This necessarily covers some points and leaves out much other material; whole books have been written about individual aspects, such as factorization. It's probably a good idea to read https://www.mersenne.org/various/math.php and then maybe return and resume here.

1. "Natural numbers" are the counting numbers 1, 2, 3, ... https://en.wikipedia.org/wiki/Natural_number
2. Expression of math operations here follow usual conventions and so are indicated as follows: addition +, subtraction -, division /, multiplication * or implied (as in the expression 2 k p = 2 * k * p), exponentiation of a to the b power a^b, square root sqrt(), modulo a mod b, equal =, less than or equal <=.
3. I use here n, a, b, f or k for natural numbers that may be composite or prime, but p for primes. Occasionally a hopefully helpful subscript is attached.
4. Natural numbers are either prime (having no natural numbers greater than one but smaller than themselves as exact integer divisors), or composite with factor(s) greater than one and less than the composite number. Five is an example of a prime. Six is an example of a composite: 6 = 2 * 3.
5. Finding and verifying a single nontrivial factor (a natural number 1 < f < n) of a natural number n proves it is composite, not prime. By definition. https://en.wikipedia.org/wiki/Prime_number
6. One is not considered a prime, but a more special case.
7. Smallest possible factor candidates are more likely to be factors than larger candidates. Two divides half the natural numbers, 3 a third, 5 1/5, f 1/f. So it's more efficient to search for factors with the smallest potential factors first.
8. The largest possible smallest prime factor of a natural number is, the largest natural number no greater than the square root of the number. f_max <= sqrt(n)
9. To search for factors of a number, it's sufficient to check only the primes below the square root of the number. Composite numbers can be skipped as potential factors, since their prime factors will divide any number they would, and some the composites won't. For example, 4 = 2 * 2, 6 = 2 * 3, 2 divides 14, 3 divides 15, but 4 or 6 divide neither. Thirteen is prime and it is sufficient to trial factor it with 2 and 3, since sqrt(13) ~3.6055 and the next prime, 5, exceeds 13's square root.
10. Mersenne numbers are a small subset of the natural numbers, having the form of a simple function M(n) = 2ⁿ - 1 where n is a natural number greater than 1.
11. Given a factor a of a number n = a b, the cofactor of a is b = n / a. (definition copied from http://mathworld.wolfram.com/Cofactor.html)
12. Any Mersenne number with a composite exponent n is composite; cannot be a prime. See https://www.mersenneforum.org/showpo...13&postcount=4
13. Mersenne primes are a small subset of the set of Mersenne numbers with prime exponents.
14. Any factors of Mersenne numbers with prime exponents are of the form f = 2 k p + 1, where p is the prime exponent, and k is a natural number.
15. Numbers 2 k p + 1 can only be factors of Mersenne numbers with prime exponent if 2 k p + 1 = either 1 or 7, mod 8.
16. Multiple methods of computerized factoring are employed for Mersenne numbers. Which are worthwhile, and the extent or level of effort to which they are worthwhile, depend on the size of the exponent, the efficiency of algorithm and implementation, and characteristics of the hardware involved.
17. For some additional background, see https://www.mersenne.org/various/math.php regarding trial factoring, P-1 factoring, and the Lucas Lehmer test, https://www.mersenneforum.org/showpo...17&postcount=9 regarding probable prime testing and the Gerbicz error check, and https://magazine.odroid.com/article/...tical-history/ for an excellent backgrounder including FFT based multiplication of very large numbers
18. Large amounts of effort have been invested in developing and optimizing factoring and primality testing code relevant to Mersenne numbers for Intel cpus, nonIntel cpus, and gpus from NVIDIA, AMD and also trial factoring on Intel integrated graphics processors. There is summary info about these at http://www.mersenneforum.org/showpos...91&postcount=2
19. Trial division is one factorization method. Much more about it is available at https://www.mersenneforum.org/showpo...23&postcount=6 and https://www.mersenneforum.org/showpo...4&postcount=18 and elsewhere
20. For exponents much smaller than the current GIMPS search area, ECM (elliptic curve method) is also useful. But not at the current Great Internet Mersenne Prime Search (GIMPS) first-test or double-check wavefront of activity.
21. P-1 factoring is another useful method, including at currently active and higher exponents. See also https://en.wikipedia.org/wiki/Pollar...92_1_algorithm and https://www.mersenneforum.org/showpo...4&postcount=17
22. Eventually, factorization attempts produce diminishing returns, declining to the point where it is more efficient to run either a conclusive primality test (Lucas-Lehmer test), or a quite reliable probable-prime test (PRP3) that can prove a number composite but cannot prove it prime. See also https://www.mersenneforum.org/showpo...7&postcount=12
23. In such lengthy computations, errors will sometimes occur. For error rates see https://www.mersenneforum.org/showpo...3&postcount=19
24. The programs contain various error checks that are performed during the computation. These often allow retreating to the point before an error was detected and attempting that portion of the computation again, which can save the lengthy computation if the error is not reproducible.
25. Some applications report the final error counts with the result. Results with counts of detected errors that may be serious concerning result accuracy can be scheduled for early checking.
26. Primality tests are done at least twice, to catch the approximately 2 percent chance of incorrect result per test, with certain precautions taken to ensure results are arrived at independently. The final result of a test mod 2⁶⁴ (called 64-bit residue or res64) is reported to the primenet server. In the case of mismatches for the same exponent and primality test type, additional runs are made until matches are obtained. A coordinated effort to follow up on mismatches is at https://www.mersenneforum.org/showthread.php?t=24148
27. Much more on error types and handling is available at https://www.mersenneforum.org/showthread.php?t=24136

Some additional reading that may be of use at some point includes:
"A Friendly Introduction to Number Theory", Joseph H. Silverman, https://www.math.brown.edu/~jhs/frint.html
The Prime Pages https://primes.utm.edu/
Knuth's Algorithms, Donald Knuth
Prime Numbers and Computer Methods for Factorization, Hans Riesel
Number Theory Web http://www.numbertheory.org/ntw/
"Prime Numbers: A Computational Perspective", Crandall and Pomerance
"Humble Pi", Matt Parker
"The C Programming Language", Kernighan and Ritchie https://en.wikipedia.org/wiki/The_C_...mming_Language

(Thanks to Batalov, Dylan14, and LaurV for contributing to the accuracy and readability of this post.)

[kriesel]

Originally Posted by Batalov

Sorry, no, not better. Now this post looks like a tumor. Volume keeps growing, information content stays constant.

To quote from Linda Richman, "A little basic background" is neither little nor basic. "Talk amongst yourselves. I am feeling varklempt" (...after reading just 1/3 of it).

Sticking to the same question as before (and just that, for brevity): "current item #14" still says "For example, 2⁶ - 1 = (2²-1)² 2³-1." Which neither explains the point, nor is (ahem) correct.

(2²-1)² 2³-1 = 71, not 63.

I began writing this is an attempt to go from beginning definitions to a rudimentary basis for understanding or a bit more, with links forward, both for sincere newbies, and as a place to point nonsensical trolls and perhaps save time correcting or countering them. (Trolls can be initially amusing but quickly become tiresome.)

I'm open to constructive suggestions for the title, organization, and content.
Re https://www.mersenneforum.org/showpo...32&postcount=2, I saw M6 != M(6) and previously missed the missing parentheses, since added. (In the usual notation, M6=2¹⁷-1; for other readers, https://www.mersenne.org/primes/)

[Dylan14]

A few suggestions:
For 5. it should be that a single nontrivial factor of a natural number proves the number composite (meaning a number other than 1 or the number itself).
For 20. link to the full list of programs (which is https://www.mersenneforum.org/showpo...91&postcount=2).
And finally, perhaps after 28., we should note that some tests need to be done 3 times (or more) due to mismatches, and that there is a dedicated effort to handle these (https://www.mersenneforum.org/showthread.php?t=24148).

[kriesel]

Originally Posted by LaurV

You do not need to write 2kp+1 with spaces. My joke related to the "operation of k" was to say that you need to be constant in notation, and do not use "x" for multiplication, but it was not my intention to say that writing 2kp with no spaces is wrong.

No worries. Your post led me to more generally reviewing conventions used, and state them, and getting rid of some ambiguities and inconsistencies along with making it I think more readable in spots. For example I had used f2 when meaning f₂ not f times 2.
Thanks also to Dylan14.

[Batalov]

Parentheses are important but that is only the first problem that comes up with that explanation.

Originally Posted by kriesel

For example, 2⁶ - 1 = 2^(2*3) - 1 = (2²-1)² (2³-1)

No. That's not algebra, that's like explaining that "this chemical reaction works because of... alchemistry!"
"Abracadabra, 63 = 3 * 3 * 7 = {and because of that} = (2²-1)² (2³-1)"

No, the "3"s here are not (2²-1)². they are (2+1)(2²-2¹+1)

Straightforward explanation:
2⁶ - 1 = (2³)² - 1 = (2³+1)(2³-1), because this is a x² - 1 and you learned this at school.
Or
2⁶ - 1 = (2²)³ - 1 = (2²-1)(2⁴+2²+1), because this is a x³ - 1 and you learned this at school or you learned this now. Take a piece of paper, open the parentheses, and observe how everything cancels.
That is sufficient. If you want to get fancy, you can continue and say, "but there is more,
(2³+1) = (2+1)(2²-2¹+1) and that equals 3 *3 "

Originally Posted by kriesel

...and 2¹⁵-1 = 2^(3*5) - 1 = 32767 = 7 * 31 * 151 = (2³ - 1) (2⁵ - 1) 151.

Same thing. Because there is no explanation what 151 is, there is no coherent story just "this is so, because I said so".

Instead:
2¹⁵ - 1 = (2⁵)³ - 1 = (2⁵-1)(2¹⁰+2⁵+1)
Or
2¹⁵ - 1 = (2³)⁵ - 1 = (2³-1)(2¹²+2⁹+2⁶+2³+1)
What's more for every 2^(r*s) - 1 (with s>1), have a look at how the above factorization repeats every time: https://primes.utm.edu/notes/proofs/Theorem2.html

And finally, there is a much better way. Just say - "you will benefit from reading this ( https://www.mersenne.org/various/math.php ). Ask questions if you will have them."
P95's webpage is coherent, brief and convincing, and has links to more detailed explanations. Yours leaves the reader more confused that they were when they started reading it.

[Dr Sardonicus]

As is well known,

(xⁿ - 1) /(x - 1) = x^n-1 + x^n-2 + ... + 1.

Now let a > 1 and b > 1 be integers. We apply the above formula to x^ab - 1. If we substitute x^a for x and b for n, we obtain

(x^ab - 1)/(x^a - 1) = x^{ab - a} + x^ab-2a + ... + 1.

Similarly, substituting x^b for x and a for n,

(x^ab - 1)/(x^b - 1) = x^{ab - b} + x^ab-2b + ... + 1.

The ne plus ultra of this is the "cyclotomic factorization" corresponding to the factorization into cyclotomic polynomials



Examples of its application may be found in this Forum, e.g. here

For more on the application of cyclotomic polynomials to integer factorization I suggest this paper.

[hansl]

From new participant reference:

Originally Posted by kriesel

Mersenneforum.org covers many different ways of aiding the GIMPS progress, through trial factoring, P-1 factoring, Lucas-Lehmer testing, probable-prime testing, double checking, etc. of Mersenne numbers, 2p-1.

Needs a superscript: 2^p-1

2[sup]p[/sup]-1