Re: Mersenne: MersenneInfo: What Happened?
On Mon, Nov 01, 1999 at 07:35:03PM -0800, Stefan Struiker wrote: Haven't received any forwards since Friday Oct. 29th... That's because the list is so silent. We need more life. Allow me :-) Poaching is evil. The millennium starts year 2001. GIMPS is cooler that distributed.net and SETI@Home combined. And of course, we shouldn't start discussions like this ;-) /* Steinar */ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: LL and Pollard-rho in one?
The behavior of the recursion x[n+1] = x[n]^2 - 2 can be precisely
analyzed. (In fact, it is because of this that the LL-test works at
all.) For a fixed prime p, the periodicity depends on the factorization
of either p-1 (if x[1]^2-4 is a quadratic residue mod p) or p+1 (if
x[1]^2-4 is a quadratic nonresidue mod p). In either case, let the
factorization be t*2^m where t is odd. Without going into excruciating
detail, the length of the non-periodic portion starting with x[1] will
be at most m, and the length of the loop will be a divisor of phi(t)/2
(the Euler totient function). (The behavior of the recursion x[n+1] =
x[n]^2 is similar, except that only the factorization of p-1 is
involved.) For example, when p = 41, the loops are {-1}, {2}, {6,-7},
{14,-11,-4} and {8,-20,-12,19,-10,16}. The value x[1] = 13 has the
non-periodic portion 13, 3, 7 of length 3 before entering the {6,-7}
loop, corresponding to the factorization 41-1 = 5*2^3. The lengths of
the loops {2} and {6,-7} are factors of phi(5)/2 = 2. Similarly, the
lengths of the loops {-1}, {14,-11,-4} and {8,...,16} are factors of
phi(21)/2 = 6.
From the point of view of factorization, these periods are much too long
to be practical. If we use x[n+1] = x[n]^2 + k, where k 0 and k
-2, then empirically the length of the loops mod p will be much smaller
than those for k = 0 or k = -2, while the length of the non-periodic
portion can easily be greater than m. For example, the recursion x[n+1]
= x[n]^2 - 6 mod 41 has three loops, {-2}, {3}, and {14,26}, and the
initial value x[1] = 0 has a non-periodic part of length 9. This is why
Pollard-rho works best for values of k other than 0 and -2.
An efficient Pollard-rho-like algorithm for factoring a Mersenne number
Mp is based on the iteration x[n+1] = x[n]^p + k. The idea is that
x[n+1] - x[n] = x[n]^p - x[n-1]^p = (x[n] - x[n-1]) * f[n], where f[n] =
(x[n]^p - x[n-1]^p) / (x[n] - x[n-1]) is known to have prime factors
which are all congruent to 1 mod p. Since Mp must also have prime
factors which are congruent to 1 mod p, this increases the chance that
gcd(x[n+1] - x[n], Mp) will produce a factor of Mp. Note that x[n+1] -
x[n] = f[n]*f[n-1]*f[n-2]*...*f[j]*(x[j] - x[j-1]), thus if any of the
terms in f[n]*f[n-1]*...*f[j] has a factor in common with Mp, this will
show up in the gcd. Ordinary Pollard-rho will also (given enough
iterations) find a factor of Mp, but the probability of this happening
within the first p-2 steps is minuscule. On the other hand, it would
cost little, after a failed LL-test, to calculate the gcd of the
difference of the last two results with Mp, just in case this happens to
reveal a factor. For that matter, one could just take the difference
between the final result and the last value stored in the p file.
Maybe if prime95 saved the final result in an r file, this test
could be performed later.
One interesting sidelight to this. The usual test for primality of a
Fermat number is to start with x[1] = 3, then calculate x[n+1] = x[n]^2
mod Fk up to x[2^k] mod Fk, which will be equal to -1 if and only if Fk
is in fact prime. Alternatively, one could start with y[1] = 3+1/3 mod
Fk (i.e., y[1] = (Fk+10)/3), then calculate y[n+1] = y[n]^2 - 2 mod Fk
up to y[2^k-1] mod Fk, which will be equal to 0 if and only if Fk is in
fact prime. This is because y[n] = x[n] + 1/x[n] mod Fk, thus y[2^k] =
(-1) + 1/(-1) = -2 mod Fk, thus y[2^k-1]^2 - 2 = y[2^k] = -2 mod Fk,
which implies y[2^k-1] = 0 mod Fk. If we calculate mod Fk(Fk+2) instead
of mod Fk, then the calculations can be carried out by prime95 with only
trivial modifications, and at the end we will have to reduce y[2^k-1]
mod Fk(Fk+2) to y[2^k-1] mod Fk to complete the test. Of course, there
are no longer any Fk within reach of current computers, so this is
merely of academic interest.
I suggested another (small) group of potential primes for testing in an
earlier message, but it never got through to the list (most likely
because my e-mail address has changed). Let F3(n) = (2^3^(n+1) - 1) /
(2^3^n - 1) = 2^(2*3^n) + 2^3^n + 1. F3(n) grows more quickly than the
Fermat numbers, so there aren't very many within reach of current
computers. There is a primality test for F3(n) which is similar to that
for Fermat numbers. 5 is a quadratic nonresidue of F3(n) for all n, thus
if F3(n) is prime, then 5^((F3(n)-1)/2) = -1 mod F3(n). On the other
hand, if 5^((F3(n)-1)/2) = -1 mod F3(n), and q is a divisor of F3(n),
then the congruence also holds mod q, which implies that q = 1 mod
2^3^n. However, since (2^3^n + 1)^2 F3(n), it is not possible for
F3(n) to have two factors both of which are congruent to 1 mod 2^3^n,
thus if 5^((F3(n)-1)/2) = -1 mod F3(n), F3(n) must be prime. Thus, start
with x[1] = 5 and calculate x[j+1] = x[j]^2 mod 2^3^(n+1)-1 up to
x[3^n+1], then y[1] = 5*x[3^n+1] mod 2^3^(n+1)-1, then y[j+1] = y[j]^2
mod 2^3^(n+1)-1 up to y[3^n]. Reduce y[3^n] mod 2^3^(n+1)-1 to y[3^n]
mod F3(n). If the result is -1, then F3(n) is
Re: Mersenne: Questions about prime.ini syntax, and hardware advice.
On 27 Oct 99, at 21:13, Albert Garrido wrote:
I'm currently trying to configure the Time command, as listed in the
docs, to
get the prime95 client to function as follows.
User ID=XYZABC
Time=1-5/18:00-0:00,1-5/0:00-08:00,6-7/0:00-24:00
(reset of Prime.ini)
Anyhow, it doesn't seem to work, and I tried a few other syntax forms,
but
what would usually happen is that either the app runs at 6:00PM and then
goes
to sleep at 6:01. I inserted the line Priority=1 after the Time line,
and it
doesn't do much. I couldn't find an explanation of the time variables
on the
FAQ, I'm hoping someone's been down this road before.
This is slightly tricky not very well documented - though there is
explanatory text in the "undoc.txt" file which comes with the
official v19 distribution (and also with late betas of v19).
The trick is:
(a) the "Time=" line(s) should appear at the end of the file;
(b) any "Priority=" or "DiskWriteTime=" directives must appear
_after_ the "Time=" line to which they apply.
This allows you to use different priority disk write time at
different times of day, even if the program is running 24 x 7.
The downside is that you _cannot_ have "Priority=" or
"DiskWriteTime=" before the first "Time=" line; if you do, then the
time directives will not work as expected.
Also, the end point in your first time interval should be 24:00 not
0:00. The end time must always be greater than the start time.
I would suggest you resequence your Prime.INI file as follows:
[ all other lines]
Time=1-5/00:00-08:00
Time=1-5/18:00-24:00
Time=6-7/00:00-24:00
If you have any Priority= or DiskWriteTime= directives, delete them
from the "top section" make copies after each of the Time=
directives.
This should run the program at all times except 08:00-18:00
(according to your system clock) Monday to Friday.
I'm doing something a bit similar, and it does work; the end of my
Prime.INI file looks like this:
Time=1-7/00:00-08:05
Priority=1
DiskWriteTime=30
Time=1-7/20:00-24:00
Priority=1
DiskWriteTime=30
[Runs the program from 20:00 to 08:05 7 days a week]
I know that Priority=1 DiskWriteTime=30 are defaults could
therefore be omitted. I was messing about!
Anyhow, it's an Athlon that's running at 900Mhz, besides the novelty
value of
that. How fast would something like this get through an average LL
test?
{Green with envy}
I don't know whether Kryotech does anything with the bus/memory
speed, if it's "just" a CPU speedup (i.e. a larger multiplier) then
the effect will be significantly less than 1.5 times as fast as a
"room temperature" Athlon @ 600 MHz. But then the Athlon should be
significantly faster than a PIII at the same bus CPU speed - even
without re-tuning to take advantage of the Athlon architecture.
My guess is, if the Krytotech module is driving the Athlon at 9x100
MHz, the performance is probably going to be almost exactly twice
that of a PIII-450 - which is about 10% better than the "standard"
benchmark PII-400 - so multiply the benchmark figures by 0.45. Should
do better than that if the bus speed is higher than 100 MHz.
Quite apart from anything else, it would be interesting to see how
well Prime95 _does_ run on an Athlon. Perhaps you would care to run a
QA test suite (takes about 12 hours on a PIII-450). You might also be
interested in parallel running some tests with the QA team; the extra
interest here is that this is probably as good a way as any of making
a name for yourself by finding a flaw in the Athlon FPU !!!
Regards
Brian Beesley
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Trial-factorers
On 27 Oct 99, at 17:23, Eric Hahn wrote: I'm looking for program(s) capable of trial-factoring prime exponent Mersenne numbers (using 2kp+1) meeting the following requirements: 1) Capable of trial-factoring any exponent 1 (at least to some considerably large number, say 1 trillion?) As I recall, Brian [Beesley] mentioned something once about having a program that could test an exponent of an arbitrary size... Brian?? Umm - I did write a "quick hack" which could handle exponents up to 1/6 * 2^32, but I never got round to putting a usable front end on it. Actually I thought that the release of the Prime95 v19 beta made it pretty redundant, and I was having a hard time with kidney stones. 2) Capable of testing a factor of any size. (even over the 2^76 limit of Prime95). I just know somebody is going to have to mention the time involved in testing factors of such a large size. Let me just say, I realize *exactly* how much time would be required... 3) Capable of trial-factoring a range of k's. (example: from k=1000 to k=2500) Well, I'm prepared to have a go. Could we tighten up the spec a bit? (a) There's also been some interest in something else that Prime95 doesn't do - trial factoring 2^p+1. (b) I assume we're only interested in 2kp+1 factors. This means that we will miss any factors which are not of this form. (Applies to Mersenne numbers with composite exponents, and all 2^p+1 numbers - though I believe that the "missed" exponents are easy to derive analytically.) (c) I presume we're looking for a program optimized for IA32 architecture. The mersfac* programs are available but are unlikely to be optimally efficient on any particular hardware platform. Given that, I suggest limits on exponent 2^62 and on factor 2^95 (these are convenient for the architecture). It's probably sensible to go for an application which runs in a "DOS box" rather than a proper windowed application. This makes it a bit easier (for me) to write also makes deriving a linux variant almost trivial. (Does anyone know for sure whether or not there's a DOS box in "Millenium"? I heard a nasty rumour...) If we can agree on that, then I have a basis to begin coding. Will certainly take a month or two to produce even a pre-pre-release as I am very pushed for time at the moment. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Mlucas on SPARC
Gimpsters, If there are people with SPARC systems with large external caches thinking about using Ernst Mayer's Mlucas for LL testing then make the switch. I will be switching from MacLucasUNIX on an E450 with 400Mhz CPU with 4Mb caches to Mlucas as soon as the current exponents finish. I ran a few tests to check on the speed differences with the current exponents and to my surprize on this system Mlucas is significantly faster. At 256K FFT I was seeing 0.11 secs/iter with Mlucas against 0.15 secs/iter for MLU, at 512K FFT the figures were 0.25 secs/iter and 0.29 secs/iter respectively. Mlucas uses far less memory that MLU and with a 4Mb cache you will really benefit from the larger cache size. I would add that this is using the 32-bit code as well. Mlucas runs significantly faster if you can compile and run it on a 64-bit Solaris 7 system. MLU is unusual in that it runs significantly slower in 64-bit mode. On small cache systems, MLU is faster for current exponents. I would like to upgrade the E450 to Solaris 7 and see what Mayer's code can do in 64-bit mode, but the owners won't let me :-( Bill Rea, Information Technology Services, University of Canterbury \_ E-Mail b dot rea at its dot canterbury dot ac dot nz / New Phone 64-3-364-2331, Fax 64-3-364-2332/) Zealand Unix Systems Administrator (/' _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Trial-factorers
Well, I'm prepared to have a go. Could we tighten up the spec a bit? (a) There's also been some interest in something else that Prime95 doesn't do - trial factoring 2^p+1. (Note that this form also form also has factors of the form k*p+1.) (b) I assume we're only interested in 2kp+1 factors. This means that we will miss any factors which are not of this form. (Applies to Mersenne numbers with composite exponents, and all 2^p+1 numbers - though I believe that the "missed" exponents are easy to derive analytically.) Yes, those mersenne numbers with composite exponents have factors of the form 2^d-1 where d|p, but the remaining unfactored portion must have factors of the form k*p+1. (I believe that is Legendre's theorem) (or rather a consequence of it) It's probably sensible to go for an application which runs in a "DOS box" rather than a proper windowed application. This makes it a bit easier (for me) to write also makes deriving a linux variant almost trivial. (Does anyone know for sure whether or not there's a DOS box in "Millenium"? I heard a nasty rumour...) Egad! If true then it would be added to the long list of complaints I have with microsoft. If we can agree on that, then I have a basis to begin coding. Will certainly take a month or two to produce even a pre-pre-release as I am very pushed for time at the moment. No need to rush, I wouldn't call the need for such a program urgent. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
