Subject: Re: [stella] A7800 From: jvmatthe@xxxxxxxxxxxxx Date: Tue, 8 Dec 1998 20:57:07 -0500 (EST) |
I tried some simple methods of factoring the number sent to the list today, but without any luck. One method that I had implemented before (Pollard Rho) is probably not practical for this problem. I have read that it is useful only for primes under 2^32... However, I did let Maple (a symbolic computation program) have a crack at our number (hereafter called N) and after 100 minutes of calculation, gave up. (This was on a Sun Ultra 5, btw.) Then I tried asking Maple if it thought N was prime...it responded false, i.e. it thinks that the number is composite. This test isn't definitive; it's merely probabalistic, but fairly reliable. Next, going on the assumption that the primes were fairly close together, I tried hitting it with Fermat's method... Basically, you find X = first integer greater than sqrt(N). Then you look at Y = (X-i)^2-N for i = 0, 1, 2, ... and test to see if Y is a perfect square, i.e. Y = Z^2. If it is, then you have N = (X-i)^2 - Z^2 or, using the formula for the factorization of a difference of squares: N = (X-i-Z)*(X-i+Z) and thus you've factored N! I ran this for i = 0 .. 1e7 and got no hits. Unfortunately, X is of the order 1e142 (or something like that) so it would take us forever to keep going with this method (something like 10000 CPU seconds to do i=0..1e7) unless there were hundreds of us putting in tons of time. Of course, if we get lucky, it'll be shorter than that. I'm going to ask the experts in my dept if they can help with some pointers on how we can proceed. I don't think that any of them would want to take this on as a project, but perhaps we'll be surprised. Finally, if there were a *good* algorithm that we could use and someone could code it up in C or Fortran, I *might* be able to use some of the Cray time that my advisor and I have accumulated to throw some real power at this problem. If I recall correctly, when his last time period expired he had something like 12 hrs of Cray time unused. We'll see what develops. matt =========================================================================== ||| John V. Matthews, III | PO Box 50355 ||| NCSU Mathematics Graduate Student | Raleigh, NC 27650 / | \ http://www4.ncsu.edu/~jvmatthe | (919) 515 7324 =========================================================================== -- Archives (includes files) at http://www.biglist.com/lists/stella/archives/ Unsub & more at http://www.biglist.com/lists/stella/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [stella] A7800, John Saeger | Thread | Re: [stella] A7800, Paul Hart |
Re: [stella] A7800, John Saeger | Date | [stella] A7800, Keith W Gerdes |
Month |