ProbSplit - Maple Programming 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

Parameters

Description

Examples

References

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)

ax6+x5+x3+x

ax6+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

ax42:p101033:

qPowmodx,p,a,xmodp

q9642432862x3

(4)

gGcda,qxmodp

gx2+715134210

(5)

ProbSplitg,1,xmodp

x+1137017280,x+8862982687

(6)

aliasα=RootOfx2+x+1,x:

ax6+αx5+x3+αx+x

aαx5+x6+x3+αx+x

(7)

dDistDega,x,αmod2

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

(8)

seqProbSplitopf,x,αmod2,f=d

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

(9)

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.

See Also

DistDeg

Factor

Factors

RootOf

Sqrfree

 


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