probabilistic splitting of same degree factors - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : Inert Functions : ProbSplit

ProbSplit - probabilistic splitting of same degree factors

Calling Sequence

ProbSplit(a, d, x, K) mod p

Parameters

a

-

univariate polynomial in x

d

-

positive integer

x

-

name

K

-

(optional) RootOf

p

-

prime integer

Description

• 

ProbSplit factors a monic square-free univariate polynomial over a finite field where it is known to contain factors of degree d only. The factorization is returned as a set of irreducible factors.

• 

This function is normally used with the DistDeg function which is used to split a polynomial into factors which contain factors of the same degree. The ProbSplit function can then be applied to split those factors.

• 

This function can also be used to compute the roots of a polynomial over a large finite field efficiently.  If a is square-free, p>2, then the product of linear factors g dividing a is given by Gcda,xpxmodp. The quantity Remxp,a,xmodp can be computed using efficiently for large p using Powmodx,p,a,xmodp. Applying ProbSplit(g, 1, x) mod p splits g into linear factors, hence obtaining the roots of a.

• 

The optional argument K specifies an extension field over which the factorization is to be done.  See Factor for further information. Note: only the case of a single field extension is implemented.

• 

Algorithm: a probabilistic method of Cantor-Zassenhaus is used to try to split the polynomial a of degree n into m=(n/d) factors of degree d. The average complexity is Olog2plog2mn2 assuming classical algorithms for polynomial arithmetic.

Examples

Factor the square-free polynomial a over GF(2)

a:=x6+x5+x3+x

a:=x6+x5+x3+x

(1)

DistDega,xmod2

x2+x,1,x4+x+1,4

(2)

This tells us that there are two linear factors, and one quartic factor. To complete the factorization we split the quadratic factor

ProbSplitx2+x,1,xmod2

x,x+1

(3)

Compute the roots of x^4-2=0 mod 10^10-33

a:=x42:p:=101033:

q:=Powmodx,p,a,xmodp

q:=9642432862x3

(4)

g:=Gcda,qxmodp

g:=x2+715134210

(5)

ProbSplitg,1,xmodp

x+1137017280,x+8862982687

(6)

aliasα=RootOfx2+x+1,x:

a:=x6+αx5+x3+αx+x

a:=αx5+x6+x3+αx+x

(7)

d:=DistDega,x,αmod2

d:=αx+x2,1,x4+α+x,2

(8)

seqProbSplitopf,x,αmod2,f=d

x,x+α,αx+x2+1,αx+x2+α

(9)

See Also

DistDeg, Factor, Factors, RootOf, Sqrfree

References

  

Cantor, D. G., and Zassenhaus, H. "A New Algorithm for Factoring Polynomials over a Finite Field." Mathematics of Computation, Vol. 36, (1981): 587-592.

  

Geddes, K. O.; Labahn, G.; and Czapor, S. R. Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992.


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam