Subject: bpv (was problems with Maxima in Ubuntu 9.04)
From: reyssat
Date: Wed, 06 May 2009 11:04:46 +0200
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