Pari/GP - and it' really fast in factoring - isn't able to factor
135*2^1204-1 within 1 hour on my machine. Will it take hours, months,
years? I don't know. That depends on the two largest prime factors.
With Maxima I cannot reproduce an infinite loop (claimed in bug report
2506). After some minutes I get
Error in MACSYMA-TOP-LEVEL [or a callee]: Contiguous blocks exhausted.
Currently, 1670 pages are allocated.
Use ALLOCATE-CONTIGUOUS-PAGES to expand the space.
About (float n) in get-one-factor-pollard:
The variable 'terms' stores an upper bound of how much steps will be
done in Brent's variant of Pollard rho before a collision check (gcd #
1) is performed. Lots of authors take constant values here. E.g. Otto
Forster, the author of Aribas, takes 200. Ohers take 20. I don't know
if there is a lucky number. Andrej Vodopivec, the author of
get-one-factor-pollard, obviously uses a value which is adjusted to
the number to be factored (after all the small primes < 10000 are
factored out). Maybe a good thing.
(One should keep in mind that Pollard rho works with randomly
generated numbers.)
(float n) for numbers greater or equal to 2^1024 is definitely not a
good thing - regardless of whether we want to factor such a number or
not. If you don't expect that (log n) will work it will be possible to
use numbers as 'terms' which have about the same size as (log n).
Maybe something like (integer-length n) or (ash (integer-length n)
-1). Maybe (isqrt (integer-length n)) is better. Let's see if I find
some time in the next weeks to check this out.
HTH
Volker van Nek
2012/12/3 Raymond Toy <toy.raymond at gmail.com>:
>
> While taking a quick peek at Bug 2506, I get an error in cmucl in
> get-one-factor-pollard. It's computing (float n) where n is
> 135*2^1204-1, which doesn't fit into a double float. In fact,
> get-one-factor-pollard is really computing (ceiling (log (float n))).
> Is there a reason why we try to float n before taking the log? Plain
> (log n) should work. (Although, it might be that some implementations
> also fail in this case, but that's an implementation bug.)
>
> Ray
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima