Fwd: modular composition & M4RI

[Martin Albrecht]

Paul Zimmerman wrote at #3376:

"""
Thank you very much Michael and Martin. It seems indeed you had some fun
optimizing m4ri! Looking at the discussion, especially when I saw Gray code,
I wondered whether the techniques we used to multiply polynomials over GF(2)
might be useful too. See <http://hal.inria.fr/inria-00188261/en>.

My initial interest was modular composition: Brent and Kung's 1978 Algo 2.1
enables one to perform a fast modular composition using fast matrix
multiplication. In turn, modular composition enables to improve polynomial
factorisation or irreducibility tests.

Do you know if Sage implements modular composition, i.e, f(g) mod h over
GF(p)[x]?
"""

Since I don't know the answer, I'm forwarding it to [sage-devel].

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de

[Bill Hart]

I don't know if SAGE implements this, either modular composition or
decomposition.

Bill.

On 10 Jun, 13:02, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:

> _jab: martinralbre...@jabber.ccc.de