[Maxima] bpv (was problems with Maxima in Ubuntu 9.04)
macrakis at alum.mit.edu
Wed May 6 06:00:24 CDT 2009
Thanks for the explanation.
I agree with you that factor should not be printing bpv.
On 5/6/09, reyssat <eric.reyssat at math.unicaen.fr> wrote:
> Stavros Macrakis a écrit :
>> (%i5) factor(50!+1);
>> bpv: 74195127103 <<<<<<<<<< hmm, I don't know what this means
>> Evaluation took 5.3100 seconds (5.3100 elapsed)
> bpv stands for big prime variation (see implementation of p-1
> factorisation method in ifactor.lisp).
> The usual p-1 factoring method due to Pollard can find a prime factor p
> of n if p-1 has only small prime factors (smaller than some
> computationaly reasonable bound B). A variation of this method extends
> it to the case where p-1 is the product of primes <B and ONE prime <B^2
> (much larger).
> The number 74195127103 found above has a prime factor p (in fact itself)
> having this form since p-1=2*3*83*283*526453 has only one "big prime"
> factor 526453.
> Conversely, using this big prime 526453, you can construct an n giving
> lots of bpv outputs. Try this :
> for i:1 thru 25 do (p:1+i!*526453, if primep(p) then n:n*p)$
> n; factor(n);
> The same algorithm, written in Pascal (?) can be found here with same
> notations as in ifactor.lisp :
> The book
> might contain a desciption of the algorithm, I couldn't and didn't check.
> In both implementations (pascal and lisp), a message is displayed when a
> factor using "big prime variation" has been found.
> I am not convinced of the usefulness of outputting the message in the
> algorithm, except for debugging or teaching purposes (which is probably
> the case for the algorithm by Forster mentioned above).
> Eric Reyssat
More information about the Maxima