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/
