Tiago Charters work gallery about contact

Uma das principais vantagens do uso de software livre é o partilhar-e-aprender. Resolvi verificar se o software maxima (http://maxima.sourceforge.net) fazia a factorizarão de um número inteiro e que algoritmo usava. E como é software livre aqui está ele:

(defun get-one-factor-pollard (n lim)
  (let* ((x (+ (random (- n 3)) 2))
         (a (+ (random (- n 2)) 1))
         (b (+ (random (- n 5)) 1))
         (y x) (d 1) (r 2) (j 1) (k)
         (terms (ceiling (log (float n)))))
    (setq b (/ b (gcd a b)))
    (loop while (= d 1) do
         (setq y x)
         (incf j r)
         (dotimes (i r)
           (setq x (mod (+ (* a (mod (* x x) n)) b) n)))
         (setq k 0)
         (loop while (and (< k r) (equal d 1)) do
              (dotimes (i (min terms (- r k)))
                (setq x (mod (+ (* a (mod (* x x) n)) b) n))
                (setq d (mod (* d (- x y)) n)))
              (setq d (gcd d n))
              (incf k terms))
         (setq r (* 2 r))
         (when (< 0 lim j)
             (return-from get-one-factor-pollard d)))
    d))

Claro que também usa, se o número for muito grande, uma factorizarão com curvas elípticas. E é suficientemente rápido para calcular a factorizarão dos 8 primeiros números de Fermat:

(%i1) F(n):=2^(2^n)+1;
                                          n
                                         2
(%o1)                           F(n) := 2   + 1
(%i2) for n in [0,1,2,3,4,5,6,7] do ldisp(ifactors(F(n)))$
(%t2)                              [[3, 1]]

(%t3)                              [[5, 1]]

(%t4)                              [[17, 1]]

(%t5)                             [[257, 1]]

(%t6)                            [[65537, 1]]

(%t7)                      [[641, 1], [6700417, 1]]

(%t8)                 [[274177, 1], [67280421310721, 1]]

(%t9)        [[59649589127497217, 1], [5704689200685129054721, 1]]

E ainda

(%i2) F(8);
(%o2)
 115792089237316195423570985008687907853269984665640564039457584007913129639937
(%i3) ifactors(F(8));
(%o3) [[1238926361552897, 1],
           [93461639715357977769163558199606896584051237541638188580280321, 1]]
(%i4) ifactors(F(9));

Unrecoverable error: Pages out of range in make_writable.

Process maxima aborted

---

For attribution, please cite this page as:

Charters, T., "Números primos com o Maxima (CAS)": https://nexp.pt/maxima.html (23-01-2025 [00:04])

---

(cc-by-sa) Tiago Charters - tiagocharters@nexp.pt