Subject: bpv (was problems with Maxima in Ubuntu 9.04)
From: Stavros Macrakis
Date: Wed, 6 May 2009 07:00:24 -0400
Thanks for the explanation.
I agree with you that factor should not be printing bpv.
-s
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)
>> (%o5)
>> 149*3989*74195127103*6854870037011*100612041036938568804690996722352077
> 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 :
> n:1$
> 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 :
> ftp://ftp.mathematik.uni-muenchen.de/pub/forster/aribas/v/alnth/p1factor.ari
> The book
> http://www.mathematik.uni-muenchen.de/~forster/books/azth/algzth.html
> 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
>