Números primos com o Maxima (CAS)
Factorização em números primos: maxima CAS
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 abortedPalavras chave/keywords: maxima, primos, matemática
Criado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:26]
(c) Tiago Charters de Azevedo