Mersenne Digest Monday, November 15 1999 Volume 01 : Number 660 ---------------------------------------------------------------------- Date: Sat, 13 Nov 1999 19:49:44 +0100 (MET) From: Wojciech Florek <[EMAIL PROTECTED]> Subject: Mersenne: Modular arithemtic Hi all! S.A. Fulling from Texas A&M Univ. posted two articles at the Los Alamos Nat. Lab. archive. The first is on quantum computers and refers to the second one `abstracted' as "This is a pedagogical article cited in the foregoing research note" I'd be obliged if some of our number-theory/programming wizards will look at these articles (esp. the second). [To look visit http://xxx.lanl.gov/abs/quant-ph/9911050 and http://xxx.lanl.gov/abs/quant-ph/9911051 ] Is there something new? Is there something interesting for the GIMPS and other math projects? Regards Wojciech Florek (WsF) Adam Mickiewicz University, Institute of Physics ul. Umultowska 85, 61-614 Poznan, Poland phone: (++48-61) 8273033 fax: (++48-61) 8257758 email: [EMAIL PROTECTED] _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 13 Nov 1999 20:46:04 +0100 (MET) From: [EMAIL PROTECTED] Subject: Re: Mersenne: Modular arithemtic Wojciech Florek <[EMAIL PROTECTED]> notes: > Hi all! > > S.A. Fulling from Texas A&M Univ. posted two articles at > the Los Alamos Nat. Lab. archive. The first is on > quantum computers and refers to the second one `abstracted' as > > "This is a pedagogical article cited in the foregoing research note" > > > I'd be obliged if some of our number-theory/programming wizards > will look at these articles (esp. the second). > > [To look visit http://xxx.lanl.gov/abs/quant-ph/9911050 > and http://xxx.lanl.gov/abs/quant-ph/9911051 ] > > > Is there something new? > Is there something interesting for the GIMPS and other math projects? I looked only at the second article. It begins with the recurrence a[n+1] = a[n]^2 + (n + 3)*n*a[n] a[0] = 1 We can grind out a[1] = 1, a[2] = 5, a[3] = 75, a[4] = 6975, a[5] = 48845925, ... Author S.A. Fulling suggests computing the sequence by modular arithmetic (using primes below 2^16) to avoid big-integer computations. Then use the Chinese remainder theorem to get the final result. This technique is well-known, but it requires a good _upper bound_ on the final answer. Here we see a[2] = 5 > 2^2, and it is easy to prove a[n] > 2^(2^(n-1)) (n >= 2) The product of the primes below 65536 is obviously below 65536^65536 = 2^(2^20). So a[21] > 2^(2^20) > (product of primes below 65536) We can't determine a[21] uniquely from its remainder modulo these primes. An example where the CRT can be useful is determinant evaluation. Consider an n x n matrix of integers, all bounded by B in absolute value. The determinant of this matrix is a sum of n! products, each at most B^n, so the determinant is bounded by n! * B^n. The Hadamard inequality gives a better bound: n^(n/2) * B^n. A 100 x 100 matrix with integer entries up to 10^6 will have determinant bounded by 100^50 * (10^6)^100 = 10^700. We can evaluate this determinant modulo 150 primes near 60000, after which we know it uniquely. The modular evaluations can use Gaussian elimination. A direct approach using Gaussian elimination would involve many rational numbers with huge numerator and denominator, and soon become unwieldly. Direct evalation by minors avoids the fractions but needs 100! arithmetic operations. Peter Montgomery _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 16 Nov 1999 11:06:00 +1100 From: Simon Burge <[EMAIL PROTECTED]> Subject: Mersenne: Small buglet in mers package extract.c I just found a small buglet the the extract program from the mers package (notice the "will complete in..." line!): per120:~/mers 13> extract t4609673 c4609673 t4609673: exponent 4609673 FFT length 262144 iteration 4600003 (binary) c4609673: exponent 4609673 FFT length 262144 iteration 4605003 (binary) Exponent 4609673 will complete in roughly -1 minutes a second or so at about Tue Nov 16 08:01:09 1999 per120:~/mers 14> ls -l ?4609673 -rw-rw-r-- 1 simonb admin 2097176 Nov 16 07:29 c4609673 -rw-rw-r-- 1 simonb admin 2097176 Nov 16 06:55 t4609673 and the expontents finished by the time I looked again... Simon. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #660 ******************************
