Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

## Re: [Maxima-discuss] polynomial factoring

 Re: [Maxima-discuss] polynomial factoring From: Richard Fateman - 2014-06-04 02:05:25 ```commercial macsyma died on big example after 27:08 and 106 megabytes, "bad argument to generic function" error message. RJF ```

 Re: [Maxima-discuss] polynomial factoring From: Edward A Romana - 2014-06-03 19:36:42 ```~~~

Good suggestion.

http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm

Apparently some form of the Cantor–Zassenhaus algorithm
is implemented, in the  cas
PARI/GP  http://pari.math.u-bordeaux.fr

Surprisingly Synaptic has pari-gp

Out of the box

~ \$  gp

GP/PARI CALCULATOR Version 2.5.0 (released)
amd64 running linux (x86-64/GMP kernel) 64-bit version
compiled: Nov 17 2011, gcc-4.6.2 (Ubuntu/Linaro 4.6.2-2ubuntu1)
(readline v6.2 enabled, extended help enabled)
Copyright (C) 2000-2011 The PARI Group
PARI/GP is free software, covered by the GNU General Public License.

? factor(29393939394959493827457202345757668765438765454332769876713711)

In about 24 seconds pari returns

[685033115156805089 1]
[42908786078511223223908363905347628100309199 1]

but over a polynomial

? factor(2*q0^5*x1^2*y2^2-4*q0^5*x1*x2*y1*y2+2*q0^5*x2^2*y1^2)
***   at top-level: factor(2*q0^5*x1^2*y
***                 ^--------------------
*** factor: sorry, factor for general polynomials
..*** is not yet implemented.
***   Break loop: type 'break' to go back to GP
~ \$

unfortunately on the surface  pari-gp does not appear helpful

In the blink of an eye Maxima
(%i20)  factor(2*q0^5*x1^2*y2^2-4*q0^5*x1*x2*y1*y2+2*q0^5*x2^2*y1^2);
(%o20) 2*q0^5*(x1*y2-x2*y1)^2

and also in the same 24 seconds Maxima returns
(%i27) factor(29393939394959493827457202345757668765438765454332769876713711);
(%o27)685033115156805089*42908786078511223223908363905347628100309199

Ed

~~~

-----Original Message-----
>From: Robert Dodier
>Sent: Jun 2, 2014 2:02 PM
>To: maxima-discuss@...
>Subject: Re: [Maxima-discuss] polynomial factoring
<...>
>
>As an idea for moving development forward -- maybe we can borrow code
>from one of the other open source math software projects. I don't know
>which ones have polynomial factoring algorithms, but it might (or might
>not) be easier to evaluate the existing implementations and borrow code
>from one of them, than to write it from scratch.
>
>best
>
>Robert Dodier
>
>______________________________________________
>Maxima-discuss mailing list
>Maxima-discuss@...
>https://lists.sourceforge.net/lists/listinfo/maxima-discuss

; ```
 Re: [Maxima-discuss] polynomial factoring From: Edward A Romana - 2014-06-06 19:27:06 ```~~~

Henry,

David G. Cantor and Hans Zassenhaus in
http://web.boun.edu.tr/yilmhuse/birkmath/20042005spr/483/docs/cantorbaba.pdf
say that for factorization there are
"...two standard methods; one is due to E. Berlekamp, the other
appears to be a "folk method". Both are described by D.E.Knuth,
"The Art of Computer Programming, Seminumerical Algorithms", Vol. 2 [pp. 381-397].

Also in my previous post to this thread, it is not correct to say that
the Cantor-Zassenhaus method 'supersedes' the Berlekamp method.
I think the Cantor Zassenhaus method applies
a probabilistic and other methods to the Berlekamp method

Ed

~~~

-----Original Message-----
>From: Henry Baker
>Sent: Jun 3, 2014 11:32 AM
>To: Robert Dodier
>Cc: maxima-discuss@...
>Subject: Re: [Maxima-discuss] polynomial factoring
>
>I recall building versions of Maxima back in the early-to-middle
>1990's, and those versions did NOT have C code. So if C code
>happened, it would have been in the late 1990's or early 2000's.
>
>At 11:15 AM 6/3/2014, Robert Dodier wrote:
>>On 2014-06-03, Henry Baker wrote:
>>
>>> Could someone please email to me a copy of Schelter's C code for
>>> Berlekamp's algorithm?
>>
>>I have a copy of Maxima 5.0 which I grabbed (as a tarball) probably
>>from Bill Schelter's old Maxima pages at U Texas, but maybe somewhere
>>else ... anyway, I don't see any C code for factoring there. It seems
>>to date to 1994. I think there were other numbered releases in Bill's
>>time (maybe up to about 5.8?) which maybe one could find by scouring
>>the interwebs.
>>
>>It is plausible that Git might have the old factoring code -- one
>>could, I guess, look at the first commit and see what is in there ...
>>
>>Just throwing out some ideas -- hope this helps.
>>
>>Robert Dodier
>
>
>------------------------------------------------------------------------------
 Re: [Maxima-discuss] polynomial factoring From: Richard Fateman - 2014-06-04 02:05:25 ```commercial macsyma died on big example after 27:08 and 106 megabytes, "bad argument to generic function" error message. RJF ```
 Re: [Maxima-discuss] polynomial factoring From: Henry Baker - 2014-06-04 02:14:29 ```Hi Richard: This doesn't sound right, because I seriously doubt that generic functions are involved in polynomial factoring, even in commercial Macsyma. I suspect that the generic function has to do with some GC-related error message. 106 MBytes is probably not sufficient, no matter which algebra system is used. Is there any way to pre-allocated 500MBytes or more? At 07:05 PM 6/3/2014, Richard Fateman wrote: >commercial macsyma died on big example after 27:08 and 106 megabytes, >"bad argument to generic function" error message. > >RJF ```