Carolina Garate

Piotr Bilinski

François Bremond

Francois Bremond

Pulsar Pulsar Pulsar

Crowd Event Recognition using HOG Tracker

come   L'archive ouverte pluridisciplinaire

Introduction

Just two decades ago, computer vision community had started to focus on the study of crowds in public areas or during public events [START_REF] Zhan | The Analysis of Crowd Dynamics: From Observations to Modeling[END_REF]. This study is motivated by the increasing need for public safety and the high level of degeneration risk especially when a large number of people (crowd) is involved.

In the research field related to crowd analytics we can find different sub-topics like crowd density estimation, crowd tracking, face detection and recognition in crowds, crowd behavior analysis, among others. We are interested in crowd behavior analysis, which is a newest area in the research community. Our goal is to automatically recognize crowd abnormal events in video sequences. In general, the usual process for activity analysis in a video sequence is composed of the following three stages [START_REF] Hu | Detecting Global Motion Patterns in Complex Videos[END_REF]: (1) detection, [START_REF] Rosten | Machine Learning for High-Speed Corner Detection[END_REF] tracking and (3) event recognition. This process can be applied to crowds as well as individuals.

We propose a new approach for crowd event recognition. The paper considers the second and the third stage of the process mentioned above, to improve the recognition stage. For this purpose in the tracking stage we compute, for every detected object in the first stage (detection), feature points (i.e. corner points) using FAST approach [START_REF] Rosten | Machine Learning for High-Speed Corner Detection[END_REF]. Then for each computed feature point we build a descriptor based on Histogram of Oriented Gradients (HOG) [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], to finally track these feature points through its respective descriptors. Finally, in the last stage (event recognition) we statistically analyze the vectors formed by the tracking of the feature points, to recognize a pre-defined event.

Previous Work

Nowadays, there are many research works related to crowd. The existent approaches in this field can be classified in two categories [START_REF] Benabbas | Global Analysis of Motion Vectors for Event Detection in Crowd Scenes[END_REF]. One of them is related to crowd event detection, and the other, to crowd density estimation. Some approaches for the second category are based on counting, either: faces, heads or persons [START_REF] Viola | Detecting Pedestrians Using Patterns of Motion and Appearance[END_REF][START_REF] Huang | Stereo-Based Human Head Detection from Crowd Scenes[END_REF] but their performance is low when there are occlusions. There are also approaches based on texture and motion area ratio [START_REF] Marana | Estimation of Crowd Density Using Image Processing[END_REF][START_REF] Lin | Estimation of Number of People in Crowded Scenes Using Perspective Transformation[END_REF][START_REF] Ma | On Pixel Count Based Crowd Density Estimation for Visual Surveillance[END_REF][START_REF] Rahmalan | On Crowd Density Estimation for Surveillance[END_REF], which are really useful for analysis for crowd surveillance. However, neither of them work for event recognition because they cannot detect abnormal situations.

Most of the methods in the first category aim at detecting abnormal events in crowd flows using motion patterns. Motion patterns correspond either to normal behaviors (frequent patterns) or abnormal behaviors (unusual patterns) [START_REF] Ihaddadene | Real-Time Crowd Motion Analysis[END_REF][START_REF] Mehran | Abnormal Crowd Behavior Detection Using Social Force Model[END_REF]. For example, Ihaddadene et al. [START_REF] Ihaddadene | Real-Time Crowd Motion Analysis[END_REF] approach detects abnormal motion variations using motion heat maps and optical flow. They compute points of interest (POI) in the regions of interest given by the maps. The variations of motion are estimated to highlight potential abnormal events using a pre-defined threshold. The approach does not need a huge amount of data to enable learning pattern frecuency but it is necessary to carefully define, in advance, an appropriate threshold and the regions of interest for every scenario. Mehran et al. [START_REF] Mehran | Abnormal Crowd Behavior Detection Using Social Force Model[END_REF] propose to use social force model for the detection of abnormal behaviors in crowds. The method consists in matching a grid of particles with the frame and moving them along the underlying flow field. Then the social force is computed between moving particles to extract interaction forces, to finally determine the on going behavior of the crowd through the change of interaction forces in time. The resultant vector field is denoted 1 as force flow, and is used to model the normal behaviors. The method captures the dynamics of crowd behavior without using object tracking or segmentation, nevertheless the obtained false positives could be problematic.

The tracking stage is another topic for the vision community. In the literature we can find several approaches for object tracking trying to solve the occlusion problem. Nevertheless, handling the occlusion for tracking people in crowd is often a harder problem to solve than for tracking individual. Most of the methods for tracking individuals with occlusion may not be so scalable to crowds. One scalable method is KLT [START_REF] Lucas | An Iterative Image Registration Technique with an Application to Stereo Vision[END_REF], which tracks feature points allowing multiple object tracking. Kaniche et al. [START_REF] Kaaniche | Tracking HOG Descriptors for Gesture Recognition[END_REF] propose a HOG tracker for gesture recognition, which can be extended to multiple object tracking in crowd. They select for each individual in the scene a set of points and characterize them by computing 2D HOG descriptors, then they track these descriptors to construct temporal HOG descriptors.

Our approach uses statistical pre-defined models of scenarios to detect crowd events in video frames. The utilization of these pre-defined models allows us a more flexible and general way to model scenarios. We use object tracking to estimate crowd direction and speed, in lieu of using a holistic approach for its higher accuracy. Others approaches use also object tracking as in [START_REF] Ihaddadene | Real-Time Crowd Motion Analysis[END_REF] (optical flow), however our approach is more robust because we are using HOG descriptors which better characterized the tracked points.

Crowd Tracking

This section describes the tracking process for crowd through the feature points computed for every object detected in a frame. We briefly describe the object detection process which does not belong to our contribution.

To perform object detection we use the technique proposed by Nghiem et al. [START_REF] Nghiem | Shadow Removal in Indoor Scenes[END_REF] to calculate the difference between the current image and the reference one (background). The idea is to set up the moving regions by grouping foreground neighbouring pixels, where moving regions are classified into objects depending on their size (crowds, persons, groups, etc.).

Once the moving objects are detected in the scene using moving segmentation we track these objects by tracking the feature points

Feature Points

After obtaining the detected moving objects in the current frame, we compute for each of them a set of feature points to track. For this, we use FAST approach [START_REF] Rosten | Machine Learning for High-Speed Corner Detection[END_REF]. However, any other corner detector approach could be applied like the one proposed by Shi et al. in [START_REF] Shi | Good Features to Track[END_REF]. Our method consists in a descendant sort out of the detected feature points using corner strength information. Then, from these points (beginning from the most significant, i.e. the one with the biggest value of corner strength) a subset of feature points is chosen to ensure a minimum distance: between them. And also between all tracked points in the corresponding object. The minimum distance improves the feature point distribution for an object and prevents mixing tracked points.

2D HOG Descriptor

We build a HOG descriptor [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF] for each detected feature point. To compute the descriptor we define around the feature point a block of 9 cells (3×3) where a cell is defined by a matrix of p × p pixels (p ∈ {3, 5}). Then, we compute the approximate absolute gradient magnitude (normalized) and gradient orientation for every pixel in the block using Sobel operator. Using gradient orientation we assign to each pixel from a cell one of the K orientation bins (by default K = 9). For each bin, we compute the sum of gradients of its pixel. Finally, we obtain for each cell inside a block a feature vector of K orientation bins. The 2D descriptor is then a vector for the whole block, concatenating the feature vectors of all its cells normalized by p.

Descriptor Tracking

The feature points detected in the previous frame are tracked in the current frame using the 2D HOG descriptors. In the current frame we calculate the mean over the trajectory, S GM , of an object speed within a time window using all speed values from the feature points that belong to the same object. If the feature point is newly detected in the current frame we assume that S GM = S mean , where S mean is the mean speed of the object at the current frame. To reduce the processing time we are using a searching window which is define based on a searching radius. For a given feature point F , the searching radius, R s , is computed:

R s = S GM + 1 T × (S mean -S GM ) (1)
Where T is the number of frames where F was tracked. From equation (1), R s is more accurate when F has a longer track.

The difference between two HOG descriptors, d n and d m , is defined by the equation:

E(d n , d m ) = 9×K i=1 M AX(v n i , v m i ) × (d n i -d m i ) 2 (2)
Where v n and v m correspond to the variances of the HOG descriptors of d n and d m , respectively, computed through out the time window.

Finally, we track F in the current frame comparing the difference (equation ( 2)) of the HOG descriptors between F and r (∀r a point inside the window of radius R s ). We choose the point r ′ in the current frame which better matches with the point F in the previous frame by computing the difference between their HOG descriptors.

We update the HOG descriptor of the tracked point by computing the equation below:

d F i = (1 -α)d r i + αd F i , i = 1 . . . 9 × K (3)
Where d F i is the mean HOG descriptor and d r i is the HOG descriptor of the point r in the current frame. α is a cooling parameter. In the same way, to update the variance of the mean descriptor bin in the current frame:

v F i = (1 -α) × |d r i -d F i | + αv F i , i = 1 . . . 9 × K (4)

Crowd Event Recognition

Crowd behavior can be characterized by regular motion patterns like direction, speed, etc. For this reason, the most robust and simple approach for crowd event recognition is to use pre-defined models of crowd events. In this section, we explain the crowd motion information computed to define and recognize the different crowd events used in this study. Our approach consists in modeling crowd events through the information obtained with the tracking of the feature points. We rely on those motion vectors of feature points computed over multiple frames. For us a vector is a collection of several elements which are the mean HOG descriptor, the start and end point of the trajectory of the tracked feature point, together with start and end time. The computed attributes (information) related to motion vectors are direction, speed, and crowd density.

Direction is the property that identifies the direction of the trajectory of feature points (called vectors). We divide the Cartesian plane into 8 parts where each part is a direction between the angles [α, α + 45] and α ∈ {0, 45, 90, 135, 180, 225, 270, 315}, see Figure 1. The angle of the vector is computed between the axis X (where x = 0 is the starting direction of the vector) and the vector, this measure decides in which of the 8 directions is classified the vector. After this, we calculate the principal crowd directions considering the density percentage of feature points in each direction. If this percentage is bigger than a threshold t we assume there is a crowd in that direction.

The speed is directly related to the length of the vectors. For each frame we calculate the speed of every vector considering its length and the number of tracking frames of the feature point associate to the vector. We obtain the crowd average speed using the speed of all the vectors in the frame. For crowd density we build a grid over the image and then we compute the density of feature points in each gridcell. This information will help us to recognize the crowd events. 6 crowd events are modeled, which are walking, running, evacuation, local dispersion, crowd formation and crowd splitting. The models defined for this study are described below:

• Walking: corresponds to a significant number of individuals moving at a low speed. We compute the mean speed, measured as pixels per frame, considering all vectors in a frame. We set up the threshold t 1 , and when the mean speed is under this threshold we recognize a crowd walking event.

• Running: corresponds to a significant number of individuals moving at a high speed. We compute the mean speed, measured as pixels per frame, considering all vectors in a frame. We use the same threshold t 1 , but when the mean speed is over t 1 we recognize a crowd running event.

• Evacuation: corresponds to a rapid dispersion of the crowd in different directions. We use the attributes direction and crowd density to recognize this event.

When there are more than 4 principal directions, when the minimum distance between the principal directions is over a threshold t 2 (euclidean distance between the grid-cells containing the feature points related to principal directions), and if the addition of the crowd density per principal direction is over a threshold t 3 , this event is recognized.

• Crowd Formation: corresponds to the merge of several individuals, where the individuals approach from different directions. Crowd density and the distance between the principal directions are used to model the current event. We set up the thresholds t 4 for the distance between the principal directions, and t 5 for the crowd density in the respective grid-cells. When the minimum distance is under t 4 and the crowd density is over t 5 , a crowd formation event is recognized.

• Crowd Splitting: corresponds to a cohesive crowd of individuals which splits into two or more flows. The crowd density and the distance between the principal directions are used to model the current event. We set up the thresholds t 6 for the distance between the main directions, and t 7 for the crowd density in the respective grid-cells. When the maximum distance is over t 6 and the crowd density is under t 7 , a crowd splitting event is recognized.

• Local Dispersion: corresponds to localized movement of people within a crowd away from a given threat. This event is very similar to crowd formation/splitting because this model uses the same attributes, plus another one: the speed. Nevertheless the thresholds (also used for crowd formation/splitting) are different. Moreover, the threshold for the distance between the grid-cells has to be over a threshold t 8 and the crowd density has to be distributed between the grid-cells with more than 1 principal directions. The mean speed has to be under a threshold t 9 .

Experimental Results

To validate our approach we have tested the PETS Dataset S3, High Level, which contains four sequences respectively with timestamps 14 : 16, 14 : 27, 14 : 31 and 14 : 33.

For each sequence we use the videos recorded by camera 1 (View 1), and we consider that there are two video clips inside the sequences 14 : 16, 14 : 27 and 14 : 33 and one video clip for the sequence 14 : 31. A video clip is about 130 frames long. The videos depict the 6 crowd scenarios described in the previous section. The crowd scenarios are acted by about 40 people from Reading University Campus. All the experiments have been performed on one view and our plan is to complete the experiments on the other views. The thresholds used in the event models have been set up experimentally. We are currently designing a learning process to compute and optimize the thresholds.

Table 1 presents some measures to evaluate our approach: true positives (TP), false positives (FP) and sensitivity (SN). We consider TP as the crowd event that matched with the ground trouth for each frame, FP as the not matched crowd event recognized for each frame, and SN is defined as T P/(T P + F N ). Since the ground truth is not established for the S3 High Level, we have built the ground truth manually.

Table 2 contains the frame number of the 7 videos clips. Table 3 shows the significant time intervals where the pre-defined events were recognized for the 7 videos clips. The columns are the different videos. There are 6 rows which represent the crowd scenarios in our study. Each element of the table contains the frames where the event is Figure 2 shows some illustrations of the results of our approach. The black lines are the trajectories of the tracked feature points depicting their direction and length.

Conclusion

In this paper we have presented a novel approach for recognizing crowd events. The contributions are the combination of local and global analysis. The local analysis is achieved by tracking HOG descriptors and the global analysis is obtained by statistical analysis of the HOG motion patterns. Also, the use of HOG descriptors for tracking enables a high accuracy in crowd event recognition and a better characterization of feature points. The approach has successfully validated on PETS dataset. There are still some errors in the recognized events. These errors are mainly do to the set up the thresholds at the level of scenario models. For future work we plan to improve the threshold computation by automating the construction of scenario models. We are also currently computing the HOG motion vectors in 3D for the approach to be independence from the scene. The scenario

Figure 1 :

 1 Figure 1: Directions in the Cartesian Plane

Figure 2 :

 2 Figure 2: The first row presents the original frames and the second row the output of our approach

Table 1 :

 1 Measures to evaluate the approach

	Crowd Event	TP	FP	SN
	Crowd Splitting	844 222 0.79
	Crowd Formation 637 430 0.60
	Walking	976	90 0.92
	Running	982	85 0.92
	Evacuation	1035 31 0.97
	Local Dispersion	778 230 0.77

Table 2 :

 2 Frame number for each Video Clip The video clips named time stamp-B are the continuation of the video sequence time stamp, i.e. if the last frame of time stamp-A is 104 the first frame of time stamp-B is 105. Inside the brackets two time intervals are separated by ";". Significant time interval is when the size is bigger than 9 frames. False positives of crowd event can be detected as significant time intervals.

	Name VC First Frame Last Frame
	14:16-A	0	107
	14:16-B	108	222
	14:27-A	0	184
	14:27-B	185	333
	14:31	0	130
	14:33-A	0	310
	14:33-B	311	377
	recognized in the corresponding video clip.

models (besides the thresholds) are easy to model by users and can be extended to other crowd scenarios. Definition of a language for modeling these scenarios can also enhance the flexibility of the approach to pre-define the scenarios.


Xavier Caruso

Jérémy Le Borgne

Some algorithms for skew polynomials over finite fields

In this paper, we study the arithmetics of skew polynomial rings over finite fields, mostly from an algorithmic point of view. We give various algorithms for fast multiplication, division and extended Euclidean division. We give a precise description of quotients of skew polynomial rings by a left principal ideal, using results relating skew polynomial rings to Azumaya algebras. We use this description to give a new factorization algorithm for skew polynomials, and to give other algorithms related to factorizations of skew polynomials, like counting the number of factorizations as a product of irreducibles. Contents 1 The ring k[X, σ] 3 1.1 Some facts about k[X, σ] . . . . . . . . . . . . . . .

Introduction

The aim of this paper is to present several algorithms to deal efficiently with rings of skew polynomials over finite fields. These noncommutative rings have been widely studied, including from an algorithmic point of view, since they were first introduced by Ore in 1933. The main applications for the study of skew polynomials over finite fields are for errorcorrecting codes. The first significant results in terms of effective arithmetics in these rings, including an algorithm to factor a skew polynomial as a product of irreducibles, appear in Giesbrecht's paper [START_REF] Giesbrecht | Factoring in skew-polynomial rings over finite fields[END_REF]. In this paper, we give a factorization algorithm whose complexity improves on Giesbrecht's. We also describe various fast-multiplication algorithms for skew polynomials, and some additional algorithms such as a factorization-counting algorithm, or an algorithm generating the uniform distribution on the factorizations of a given skew polynomial. The first part of the article is mostly theoretical. Let k be a finite field of characteristic p, and let σ be an automorphism of k. We denote by k σ the subfield of k fixed by σ, and by r the order of σ on k. The ring k[X, σ] of skew polynomials with coefficients in k is a noncommutative ring, on which multiplication is determined by X • a = σ(a) • X for all a ∈ k. The first Theorem we shall prove is the following: Theorem (cf Theorem 1.2.1). The ring k[X, σ][1/X] is an Azumaya algebra over its centre k σ [X r ][1/X r ].

This Theorem has many important consequences for our purpose. The first one is the existence of a reduced norm map k[X, σ] → k[X r ], which turns out to have very nice properties related to factorizations. For instance, we shall explain how it can be used to establish a close link between factorizations of a skew polynomial and basic linear algebra over finite extensions of k σ . As an illustration, we will show how to use this theory to derive a formula giving the number of factorizations of any skew polynomial.

The second part of the paper deals with algorithmic aspects of skew polynomials. We start by giving various fast-multiplication algorithms and, as usual, we derive from them efficient algorithms to compute Euclidean division and gcd. Then, we reach the core algorithm of this paper: the factorization algorithm. Making an intensive use of the theory developped in the first part, we obtain a very efficient algorithm to factor a skew polynomial as a product of irreducible skew polynomials, SkewFactorization.

Theorem (cf Theorem 2.4.2). The algorithm SkewFactorization factors a skew polynomial of degree d in k[X, σ] with complexity Õ(dr 3 log q + d log 2 q + d 1+ε (log q) 1+o(1) + F (d, k σ )) bit operations, for all ε > 0. Here, F (d, K) denotes the complexity of the factorization of a (commutative) polynomial of degree d over the finite field K.

In [START_REF] Kedlaya | Fast modular composition in any characteristic[END_REF], Kedlaya and Umans described a factorization algorithm of polynomials over finite fiels whose complexity is: F (d, K) = (d 3/2+o(1) + d 1+o(1) log q) • (log q) 1+o(1) bit operations, where q is the cardinality of K. Assuming this value for F (d, K), we see that the terms d log 2 q and d 1+ε (log q) 1+o(1) are negligible compared to F (d, K). If furthermore r 3 ≪ d, also is the term dr 3 log q. With this extra assumption, the complexity of our algorithm is then comparable to the complexity of the factorization of a commutative polynomial of the same degree.

The complexity of our algorithm should be compared to the complexity of Giesbrecht's algorithm, which is: Õ(d 4 r 2 log q + d 3 r 3 log q + d • MM(dr) log q + d 2 r • log 2 q) bit operations 1 where MM(n) is the complexity of the multiplication of two n × n matrices.

The strategy of our algorithm is roughly comparable to the one of Giesbrecht's: in order to factor P , we find a multiple N of P lying in the centre of k[X, σ], we factor N in the centre (which is a commutative polynomial ring) and we recover a factorization of P from the factorization of N we have just computed. The two main improvments are the following. Firstable, we obtain better algorithms to achieve basic operations (like multiplication, Euclidean division and gcd's). Using them to factor a polynomial improves significantly the complexity. The second improvement (which is the most important) consists in taking a large benefit of the closed study of all involved objects we have done in the first part. For instance, in order to obtain the central multiple N , we just compute the reduced norm, for which efficient algorithms exist. In the same way, our theoretical results imply that, for some particular P , the quotient k[X, σ]/k[X, σ]P is endowed with a rich structure and we use it to replace computations with large matrices over k σ by computations with matrices of size at most r defined over a bigger field. Since usual arithmetics in field extensions is more efficient than computations with matrices (quasilinear vs subcubic), we gain a lot.

Eventually, we give an algorithm to compute the number of factorizations of a skew polynomial and we describe an algorithm to generate the uniform distribution on the factorizations of a skew polynomial.

All the algorithms described here have been implemented in sage, and some of them in magma. We discuss briefly about the implementation. This work was supported by the Agence Nationale de la Recherche, CETHop project, number ANR-09-JCJC-0048-01.

The ring k[X, σ]

1.1 Some facts about k[X, σ]

Let k be a finite field of characteristic p and let σ be an automorphism of k. We denote by k σ the subfield of k fixed by σ. Let r be the order of σ: r is also the degree of the extension k/k σ . We denote by k[X, σ] the ring of skew polynomials with coefficients in k. The underlying group is just k[X], and the multiplication is determined by the rule ∀a ∈ k, Xa = σ(a)X.

We recall some notions from [START_REF] Jacobson | Finite-dimensional division algebras over fields[END_REF], Chapter 1 (mainly §1.1 and 1.2). The centre of k[X, σ] is k σ [X r ]. The ring k[X, σ] is endowed with left-and right-euclidean division algorithms. Hence, there are also notions of right-and left-greatest common divisor, and left-and right-lowest common multiple (denoted respectively by rgcd, lgcd, llcm, rlcm). Of course, every element of k[X, σ] can be written as a product of irreducible elements of k[X, σ]. However, a such factorization is not unique in general. The first result that describes how two factorizations of a skew polynomial as a product of irreducibles are related is due to Ore. Before stating it, let us give a definition:

Definition 1.1.1. Let P, Q ∈ k[X, σ] be two skew polynomials. Then P and Q are similar if there exist U, V ∈ k[X, σ] such that rgcd(P, V ) = 1, llcm(Q, U ) = 1 and U P = QV .
Even though it may not be clear at first glance, this is an equivalence relation. Remark that in the case σ = id, this just means that P and Q are equal up to multiplication by an element of k × . We then have the following theorem:

Theorem (Ore, [START_REF] Ore | Theory of non-commutative polynomials[END_REF]). Let P 1 , . . . , P n and Q 1 , . . . , Q m be irreducible skew polynomials.

If P 1 • • • P n = Q 1 • • • Q m ,
then m = n and there exists a permutation τ of {1, . . . , n} such that for all 1 ≤ i ≤ n, P i is similar to Q τ (i) .

However, the converse of this theorem is false. In general, if the P i and Q i are pairwise similar, P i and Q i are not even similar. An interesting point of view on skew polynomials is that of ϕ-modules that we shall elaborate on later. For now, it is enough to say that a ϕ-module over k is a k[X, σ]-module of finite type. If P ∈ k[X, σ] is nonzero, a typical example of a ϕ-module over k is k[X, σ]/k[X, σ]P , which is "the ϕ-module associated to P ". Then, two skew polynomials are similar if and only if the associated ϕ-modules are isomorphic, and Ore's theorem is just a restatement of the Jordan-Hölder Theorem in the category of ϕ-modules.

The ring k[X, σ][1/X] is an Azumaya algebra

The aim of this section is to prove the Theorem 1.2.1 and to give several consequences. Let us now recall the statement of the Theorem:

Theorem 1.2.1. The ring k[X, σ][1/X] is an Azumaya algebra over k σ [X r ][1/X r ]. Proof. Let us denote by R the ring k[X, σ][1/X] and by C its centre k σ [X r ][1/X r ].
By definition, it is enough to show that for every prime ideal P of C, R/P ⊗ C Frac(C/P) is a central simple algebra over Frac(C/P). The case P = (0) is exactly [START_REF] Jacobson | Finite-dimensional division algebras over fields[END_REF], Theorem 1.4.6. The other prime ideals of C are of the form (N ) with N ∈ k σ [X r ] monic irreducible and different from X r . Fix such an irreducible polynomial N . Denote by E the field of fractions of C/(N ). Let us first show that R N = R ⊗ C E is simple. Let I ⊂ R N be a two-sided ideal. Assume that I = (0), and let x ∈ R N be a nonzero element of I. First remark that every element of R N can be written as P ⊗ 1. Indeed, if t is the class of X r is E = C/(N ), then 1 ⊗ t = X r ⊗ 1. Therefore, we can write x = P ⊗ 1 with P ∈ k[X, σ]/(N ). Now assume that x and P are chosen such that the number of nonzero coefficients of P is minimal (with x ∈ I \ {0}). We can assume that P is monic of degree d. We have P -XP X -1 ∈ I, and this polynomial has less nonzero coefficients than P , so that it is zero. Similarly, if a ∈ k × , Pσ d (a) -1 P a = 0. This shows that x is central. Since the centre of R N is a commutative finite integral E-algebra, it is a field, so x is invertible and I = R N . It remains to prove that this centre is exactly E. We just need to solve the equations X

deg(N )-1 i=0 a i X i = deg(N )-1 i=0 a i X i+1 and α deg(N )-1 i=0 a i X i = deg(N )-1 i=0 a i X i α for α a generator of k/k σ . It is easy to see that the solutions are exactly (the reduction modulo N of) elements of k σ [X r ], so that the centre of R N is E.
This result has various corollaries that are interesting for questions about factoring skew polynomials.

Corollary 1.2.2. Let N ∈ k σ [X r ] be a nonzero polynomial that is not a power of X. Then C/N C and R/N R are Morita-equivalent.

Proof. Since R is an Azumaya algebra over C, R/N R is an Azumaya algebra over C/N C. Since C/N C is a finite commutative ring, its Brauer group is trivial, hence R/N R and C/N C represent the same class in this Brauer group.

Corollary 1.2.3. Let N ∈ k σ [X r ] be an irreducible polynomial different from X. Let E N be the quotient field C/(N ). Then R/N R ≃ M r (E N ),
the ring of r × r matrices with coefficients in E N .

Proof. By corollary 1.2.2, R/N R is a ring of matrices with coefficients in E N . The result follows from the fact that R/N R has dimension r 2 deg N over k σ .

One of the usual objects associated to Azumaya algebras is the notion of reduced norm. This notion will be very important in the rest of the paper. In our situation, it is a multiplicative morphism

N : k[X, σ][1/X] → k σ [X r ][1/X r ] which can be defined as follows. Consider the largest étale subalgebra of k[X, σ][1/X], which is k[X r ][1/X r ]. Then, N (x) is nothing but the determinant of the right-multiplication by P on k[X, σ][1/X] considered as a k[X r ][1/X r ]-module. Using that k[X, σ] is a free module of rank r over k[X r ] (with basis (1, X, . . . , X r-1 ) for example), we deduce directly that N maps k[X, σ] to k σ [X r ].
We furthermore note that, if P is the central skew polynomial (i.e. P ∈ k σ [X r ]), the (right-)multiplication by P acts on a k[X, σ] by (left-)multiplication by P and therefore has determinant P r . Therefore N (P ) = P r provided that P ∈ k σ [X r ].

Remark 1.2.4. The property of being an Azymaya algebra could certainly be generalized to some other skew polynomal rings, for instance k[X, ∂] where ∂f = f ′ +f ∂. For Azumaya algebras over rings whose Brauer group is trivial, many results of this paper should remain true. Since the triviality of the Brauer group is used strongly, there would probably be variations in the expected theorems when the Brauer group is nontrivial.

Reinterpretation in terms of Galois representations

In this section, we give a reinterpretation of the Morita equivalence in terms of Galois representations, recovering a variation of a theorem of Katz. Let us first give one definition.

Definition 1.3.1. A ϕ-module over k is a finite dimensional k-vector space D endowed with an endomorphism ϕ : D → D that is semilinear with respect to σ, i.e. for all x ∈ D and a ∈ k, ϕ(λx) = σ(λ)ϕ(x). A ϕ-module is said to be étale if the map ϕ is injective.

By definition, a ϕ-module (resp. an étale ϕ-module) over k is exactly a left-k[X, σ]module having finite dimension over k.

Definition 1.3.2. If P ∈ k[X, σ], the ϕ-module D P associated to P is k[X, σ]/k[X,
σ]P , endowed with the semilinear map ϕ given by left-multiplication by X. We say that P is étale if D P is étale. (It exactly means that the constant coefficient of P is nonzero.) Remark 1.3.3. Two skew polynomials P and Q are similar if and only if

D P ≃ D Q .
The Morita equivalence shows the following: Corollary 1.3.4. The category of étale ϕ-modules over k is equivalent to the category of finite dimensional k σ -vector spaces endowed with an invertible endomorphism.

Proof. Let D be an étale ϕ-module over k. Since D has finite dimension over k, it is annihilated by some ideal (N ) of C. By 1.2.2, the categories of left-R/N R-modules and C/N C-modules are equivalent and we are done.

This corollary can also be seen as a variation of the following theorem: Theorem (Katz). Let K be a field of characteristic p > 0 endowed with a power of the Frobenius endomorphism σ. Then the category of étale ϕ-modules over K is equivalent to the category of K σ -representations of the absolute Galois group of K.

Indeed, if σ(a) = a p s , let K = kF p s . Then K σ = k σ , and the absolute Galois group of K is a procyclic group, so that a representation of this group is just the data of an invertible endomorphism of a k σ -vector space of finite dimension (giving the action of a generator of the group). The functor giving this equivalence is explicit: the representation corresponding to an étale ϕ-module D over k is Hom ϕ (D, K sep ).

Proposition 1.3.5. Let (D, ϕ) be a ϕ-module over k, and let σ r be the generator of the absolute Galois group of kF p s . Then the action of σ r on the k σ -representation V corresponding to D is isomorphic to ϕ r :

(V ⊗ k σ k, σ ⊗ 1) ≃ (D, ϕ r ).
Proof. It is enough to prove the result when ϕ r is cyclic. Let f ∈ V = Hom ϕ (D, K sep ). Then for x ∈ D, σ r f (x) = f (ϕ r (x)). This shows that the polynomials annihilating σ r and ϕ r are the same. The characteristic and minimal polynomials of σ r are the same, and equal to the characteristic polynomial of ϕ r , so these two endomorphisms are conjugate.

Using the fact that two skew polynomials are similar if and only if the corresponding ϕ-modules are isomorphic, we immediately get:

Corollary 1.3.6. Let P, Q ∈ k[X, σ].
The skew polynomials P and Q are similar if and only if the k σ [X r ]-modules (D P , ϕ r ) and (D Q , ϕ r ) are isomorphic.

Since ϕ r is a k-linear map, testing if these k σ [X r ] are isomorphic is completely straightforward.

Factorizations

In this section, we study some properties related to factorizations of skew polynomials and the structure of the corresponding ϕ-modules. First recall that if P is a monic étale skew polynomial, there is a bijection between all factorizations of P as a product of monic irreducible skew polynomials, one the one hand, and all Jordan-Hölder sequence of the corresponding ϕ-module, on the other hand. By theorem 1.3.5, these factorizations are also in bijection with Jordan-Hölder sequence of D P (viewed as a k σ [X r ]-module). We shall see how we can use this to count the number of factorizations of P .

Another definition of the norm

Recall that we have defined the (reduced) norm of a skew polynomial P ∈ k[X, σ] as the determinant of the right-multiplication by P acting on the k[X r ]-module k[X, σ]. Proposition 1.3.5 allows us to give an equivalent definition: Lemma 1.4.1. Let P ∈ k[X, σ] be monic and let (D P , ϕ) be the corresponding ϕ-module. Then the norm N (P ) is the characteristic polynomial of ϕ r . If P = a P with P monic, then N (P ) = N k/k σ (a) • N ( P ).

Proof. Let m P be the right-multiplication by P acting on k[X, σ]. Since both P → N (P ) = det m P and P → χ ϕ r are multiplicative, it is enough to prove the Lemma when P is monic irreducible. Let π : k[X, σ] → D P be the canonical projection. We have π • m P = 0. Since π is surjective, the multiplication by det m P is also zero in D P . This means that the minimal polynomial of the multiplication by X r on D P is a divisor of det m P . Since P is irreducible, this minimal polynomial is the characteristic polynomial χ of ϕ r . It is then enough to show (1) that the degree of N (P ) is the same as the degree of χ and (2) that N (P ) is monic. Write P = P 0 + XP 1 + • • • + X r-1 P r-1 with the P i 's in k[X r ]. In the basis (1, X, . . . , X r-1 ), the matrix of m P is:

         P 0 X r σ(P r-1 ) . . . . . . X r σ r-
P r-1 • • • • • • • • • σ r-1 (P 0 )          .
Let 0 ≤ i ≤ r -1 be the greatest integer such that the degree of P i is maximal, and denote by δ this degree. In the sum giving the determinant of this matrix, we have the term

P i σ(P i ) • • • σ r-i-1 (P i )X r σ r-i (P i ) • • • σ r-1 (P i ),
whose degree is δ(ri) + (δ + 1)i = δr + i (as a polynomial in X r ). All the other terms of the determinant have degree less than this, so N (P ) = det m P has degree δr + i = deg P = deg χ and is monic.

Proposition 1.4.2. Let N be the reduced norm map on k[X, σ]. Then the following properties hold:

• ∀P ∈ k[X, σ], P is a right-and left-divisor of N (P ) in k[X, σ],
• ∀P ∈ k[X, σ], P is irreducible if and only if

N (P ) is irreducible in k σ [X r ],
• If P, Q ∈ k[X, σ] and P is irreducible, then P and Q are similar if and only if

N (P ) = N (Q) (up to multiplicative constant).
Proof. The first fact is well-known (see for instance [START_REF] Jacobson | Finite-dimensional division algebras over fields[END_REF], Proposition 1.7.1). It can be seen easily from the fact that if (D P , ϕ) is the ϕ-module associated to P , then

N (P )(ϕ) = 0. Indeed, the left-ideal {R ∈ k[X, σ] | R(ϕ) = 0} is exactly k[X, σ]P .
For the second assertion, remark that P is irreducible if and only if D P is simple, which holds if and only if the corresponding representation is irreducible. This is true if and only

if the characteristic polynomial of ϕ r is irreducible in k σ [X r ].
Finally, we have already seen that the similarity class of a skew polynomial is determined by the conjugacy class of the action of ϕ r on the corresponding ϕ-module (corollary 1.3.6).

For irreducible elements, this is completely determined by the characteristic polynomial of ϕ r , i.e. the reduced norm.

Since P is a divisor of N (P ), we can expect that if Ñ is some irreducible factor of N (P ) in k σ [X r ], then rgcd( Ñ , P ) would be a nonconstant right-divisor of P . This is actually always true and formalized by the following lemma:

Lemma 1.4.3. Let P ∈ k[X, σ] be étale and monic. Let N = N (P ). If N = N 1 • • • N m with all N i 's irreducible. Then there exist P 1 , . . . , P m ∈ k[X, σ] such that P = P 1 • • • P m and for all 1 ≤ i ≤ m, N (P i ) = N i .
Moreover, P m can be chosen as an irreducible right-divisor of rgcd(P, N m ).

Proof. By induction on m, it is enough to prove the last assertion. Let V P be the Galois representation corresponding to the ϕ-module D P via Katz's equivalence of categories (cf Theorem 1.3). Using Proposition 1.3.5, we find that V P has a subrepresentation which is isomorphic to the quotient k σ [X r ]/N m (where σ r acts by multiplication by X r ). Hence, there exists a surjective map D P → D Pm where P m is some skew polynomial of reduced norm N m . It implies that P m is a right divisor P and then also a right divisor of rgcd(P, N m ). This concludes the proof.

Remark 1.4.4. This result shows how to determine the similarity classes of irreducible skew polynomials appearing in a factorization of P . It also shows that any order is possible for the appearance of these similarity classes in a factorization of P .

When Ñ is an irreducible factor of N (P ), the right greatest common divisor rgcd( Ñ , P ) is never constant, so if we want to factor P as a product of irreducible polynomials, we only need to know how to factor skew polynomials which are right-divisors of irreducible elements of the centre k σ [X r ].

1.4.2 On the structure of D P when P divides an irreducible central polynomial

Let N ∈ k σ [X r ] be a monic irreducible polynomial, and let E = k σ [X r ]/(N ). Let P ∈ k[X, σ] be a right-divisor of N .
The previous section has shown that factoring skew polynomials can be reduced to factoring skew polynomials of this form. In this theoretical section, we begin a close study of the structure of D P . All the results we are going to prove will play a very important role in the next section when we will be interested in designed a fast algorithm for factorization of skew polynomials.

We first remark that, since N (N ) = N r , the norm of P is N e for some integer e ∈ {1, . . . , r}.

Lemma 1.4.5. The ϕ-module D N is isomorphic to a direct sum of r copies of a simple ϕ-module.

Proof. It follows directly from Corollary 1.2.2.

The Lemma implies that if P is a right-divisor of N with N (P ) = N e , then the ϕ-module D P = k[X, σ]/k[X, σ]P is isomorphic to a direct sum of e copies of a simple ϕ-module. From this, we deduce that End ϕ (D P ) ≃ M e (E).

Ring of endomorphisms From now on, we write

N = P Q for some Q ∈ k[X, σ]. Note that it implies that QN = QP Q; therefore N Q = QP Q (since N lies in the centre)
and, simplifying by Q, we get N = QP . In other words P and Q commute. The following proposition compares the ϕ-module D P = k[X, σ]/k[X, σ]P and its ring of endomorphisms.

Proposition 1.4.6. The map

D P → End ϕ (D P ) R → m QR : D P → D P x → xQR
is a surjective additive group homomorphism.

Note that since

P Q = QP = N is central in k[X, σ],
the map above is well-defined. Indeed, we have to check that if x ≡ x ′ (mod P ) and R ≡ R ′ (mod P ) then xQR ≡ x ′ QR ′ (mod P ). Writing x ′ = x + SP and R ′ = R + T P , we have:

x ′ QR ′ = xQR + SP QR + (xQT + SP Q)P ≡ xQR + SN R ≡ xQR + SRN ≡ xQR + SRQP ≡ xQR (mod P )
which is exactly what we want. In order to prove the proposition, we will need the following lemma, that states that in the case P = N , that map is in fact an isomorphism.

Lemma 1.4.7. Let N ∈ k[X, σ].
Then the map:

D N → End ϕ (D N ) R → m R : D N → D N x → xR
is an isomorphism of rings.

Proof. The fact that our map is a morphism of rings is straightforward. It is injective because R = m R (1). For the surjectivity, we remark that if N is a commutative polynomial of degree δ, D N has dimension δr 2 over k σ and, on the other hand, that if E is the field

k σ [X r ]/(N ), End ϕ (D N ) is isomorphic to M r (E), so it also has dimension δr 2 .
Proof of Proposition 1.4.6. We have the exact sequence of ϕ-modules:

0 → k[X, σ]P/k[X, σ]N → D N → D P → 0,
and D Q is isomorphic to k[X, σ]P/k[X, σ]N via the multiplication by P . Since D N ≃ D ⊕r P , this sequence is split. Let s : D P → D N be a section. We have P s(1) = s(P ) ≡ 0 (mod N ), so there exists S ∈ D N such that P s(1) = N S. Thus s(1) = QS. On the other hand, QS = s(1) ≡ 1 (mod P ). Hence there exists some V ∈ k[X, σ] such that

QS + V P = 1. It implies that D P is isomorphic to k[X, σ]QS/k[X, σ]N via the multiplication by QS.
Let u ∈ End ϕ (D P ), and let A = u(1) Proof. Since R → m QR is surjective, the probability that m QR is equal to u ∈ End ϕ (D P ) is proportional to the cardinality of the fiber above u. We conclude the proof by remarking that k-linearity together with surjectivity implies that all fibers have the same cardinality. Some remarks about rgcd's and llcm's Let us present a rather elementary geometric point of view on rgcd's and llcm's in skew polynomial rings. If P ∈ k[X, σ] is a divisor of an irreducible commutative polynomial N of norm N e , and P 1 is a right-divisor of

∈ D P . For all x ∈ k[X, σ], u(x) = xu(1) = xA. In other words, u is the mulitplication by A, i.e. u = m A . We then want to show that m A is of the form m QR for some R ∈ D P . Let ũ the endomorphism of k[X, σ]QS/k[X, σ]N deduced from u: we have ũ(QS) = AQS. Since D N = k[X, σ]QS/k[X, σ]N ⊕ k[X, σ]P/k[X, σ]N (
P of norm N e 1 , then k[X, σ]P 1 /k[X, σ]P ⊂ D P is a sub-E-vector space F 1 of D P of dimension e -e 1 .
If P 2 is another right-divisor of P of norm N e 2 , it defines a sub-E-vector space F 2 of dimension ee 2 .

The intersection and sum of these vector spaces have a description in terms of rgcd's and llcm's: Lemma 1.4.9. Let R = rgcd(P 1 , P 2 ) and let M = llcm(P 1 , P 2 ). Then:

• F 1 + F 2 = k[X, σ]R/k[X, σ]P , • F 1 ∩ F 2 = k[X, σ]M/k[X, σ]P .
Proof. Left to the reader.

Remark 1.4.10. We will mainly use this Lemma when P 1 is irreducible. Then k[X, σ]P 1 /k[X, σ]P is an hyperplane in D P . If we take the image of this hyperplane under any automorphism of D P , we get another hyperplane, and it is likely that the intersection of this hyperplane with k[X, σ]P 1 /k[X, σ]P has codimension 2 in D P , and hence it is an hyperplane in k[X, σ]P 1 /k[X, σ]P . We get this way an irreducible divisor of the quotient of the right division of P by P 1 .

Counting factorizations

In this section, we explain how to compute the number of factorizations of a monic skew polynomial P ∈ k[X, σ] as a product of monic irreducible polynomials.

Lemma 1.4.11. Let P ∈ k[X, σ] be a monic étale skew polynomial. Assume that N (P ) = N e with N irreducible of degree d, and P is a right-divisor of N . Then the number of factorizations of P as a product of monic irreducible skew polynomials is the q d -factorial

[e] q d ! = (q de -1)•••(q d -1) (q d -1) e
Proof. By induction on e, it is enough to prove that P has exactly q de -1 q d -1 monic irreducible right-divisors. The number of monic irreducible right-divisors is also the number of simple sub-ϕ-modules of k[X, σ]/k[X, σ]P . Such submodules are in bijection with k σ [X r ]/(N )lines in k[X, σ]/k[X, σ]P (if P 1 is an irreducible right-divisor of P , every irreducible rightdivisor of P can be written as the image of P 0 by an endomorphism of k[X, σ]/k[X, σ]P ), so it has the cardinality of the projective space P(E e ), which is q de -1 q d -1 .

Let us now define the type of a skew polynomial P . Recall first that the endomorphism ϕ r of D P defined over k σ can be put into Jordan form, and that a Jordan block is by definition an invariant subspace in a basis of which the restriction of ϕ r has a matrix of the form:

         A I 0 • • • 0 0 A I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I 0 • • • • • • 0 A          , with A having a characteristic polynomial that is irreducible in k σ [X r ].
We will say that a Jordan block has size i if the number of matrices A that appear in this block is i.

Definition 1.4.12. Let P ∈ k[X, σ]. Assume that N (P ) = N e for some integer e. For i ≥ 1, let e i be the number of Jordan blocks of (D P , ϕ r ) of size at least i. Let n be the largest index such that e i = 0, we say that P has type (e 1 , . . . , e n ).

This means that if P has type (e 1 , . . . , e n ), the action of σ r on the corresponding representation has exactly e 1 Jordan blocks, e 2 of which contain a block of the form A I 0 A , etc.

Remark 1.4.13. The type is determined by the nonincreasing sequence (a 1 , . . . , a m ), a i being the size of the i-th largest Jordan block of (D p , ϕ r ). The Young diagram associated to (a 1 , . . . , a m ) is dual to the one associated to (e 1 , . . . , e n ). We will say that (a 1 , . . . , a m ) is the dual sequence of (e 1 , . . . , e n ). We also say that (a 1 , . . . , a m ) is the dual type of P .

A skew polynomial P ∈ k[X, σ] has type (e) (with 1 ≤ e ≤ r) if and only if it is a divisor of an irreducible polynomial N ∈ k[X, σ].

Definition 1.4.14. Let P ∈ k[X, σ] be a monic skew polynomial. Let N a 1 1 • • • N at t be the factorization of N (P ) as a product of monic irreducible polynomials. For 1 ≤ i ≤ t, let (e (i) 1 , . . . , e (i) n i ) be the type of the restriction of ϕ r to the characteristic invariant subspace associated to N i . We say that P has type:

(N 1 , (e (1) 1 ), . . . , e (1)
n 1 ), . . . , (N t , (e

(t)
1 , . . . , e (t) nt )). As we have seen before, if P ∈ k[X, σ] is a monic polyomial, then the set of all factorizations of P as a product of monic irreducible polynomials is in bijection with the Jordan-Hölder sequences for the ϕ-module D P . It is also in bijection with all bases of D P in which ϕ r has Jordan form. This can be described in terms of the types of some factors of P , as we are going to explain now.

First, we assume that N (P ) = N e with N ∈ k σ [X r ] irreducible. Let (e 1 , . . . , e n ) be the type of P . We denote by V the representation associated to D P , with g the endomorphism through which σ r acts on V . If W is any nonzero irreducible invariant subspace of V , the action of g on W is given by the companion matrix of N in some basis. Let (a 1 , . . . , a m ) be the dual sequence of (e 1 , . . . , e n ) as defined in Remark 1.4.13.

Lemma 1.4.15. Let δ = deg N . Let 1 ≤ i ≤ m such that i = m or a i > a i+1 . Let i 0 be the smallest j such that a j = a i . Then there are q δ(i-1) +q δi +• • •+q δ(i 0 -1) invariant irreducible subspaces V ′ of V such that the quotient V /V ′ has a type whose dual is (a 1 , . . . , a i -1, a i+1 , . . . , a m ) (or (a 1 , . . . , a m-1 ) if i = m and a m = 1).

Proof. Denote by (ε 1,1 , . . . , ε 1,δ , ε 2,1 , . . . , ε 2,δ , . . .) a basis of V in which the matrix of g has Jordan form. More precisely, for all 1 ≤ i ≤ m, and for all 1 ≤ j ≤ t i and 1 ≤ l ≤ δ, we have g(ε j,l ) = ε j,l+1 if (j, l) is not of the shape (j, 1) for some integer j ≥ 2, or of the shape (j, δ) for some integer j ≥ 1, g(ε j,1 ) = ε δu,δ + ε δu+1,2 if j ≥ 2, and g(ε j,δ ) = δ l=1 α l e j,l , where δ l=1 α l X r(l-1) = N (it is the characteristic polynomial of the induced endomorphism on any irreducible invariant subspace). There are i 0 -1 Jordan blocks of g whose length is greater than the length of the i-th block. For λ = (λ 1,1 , . . . , λ 1,δ , . . . , λ i 0 -1,δ ) ∈ k σ δ(i 0 -1) , let v λ = e i 0 ,1 + i 0 -1 j=1 δ l=1 λ j,l e j,l . Since two such vectors v λ , v µ are not colinear, they generate distinct invariant subspaces V λ , V µ , which are clearly isomorphic to W . Moreover, the quotient V /V λ has the same type as V /V (0) because the map V → V that sends ε i 0 ,1 to v λ and is the identity outside the invariant subspace generated by ε i 0 ,1 is an isomorphism (its matrix is upper triangular). One can build the same way invariant subspaces with quotients of the same type as generated by vectors of the shape ε i 0 +1,1 + i 0 j=1 δ l=1 λ j,l ε j,l , . . . , ε i,1 + i-1 j=1 δ l=1 λ j,l ε j,l . There are exactly q δi 0 -1 + • • • + q δi-1 invariant subspaces that are built in this way. Doing such constructions for each i ′ satisfying the hypotheses of the lemma, we get exactly q δm -1 q δ -1 irreducible invariant subspaces, which means all of them. Among these subspaces, the ones for which the quotient has the requested shape are exactly the q δ(i 0 -1) + • • • + q δ(i-1) built for the first i we considered. This proves the lemma.

In order to compute the number of Jordan-Hölder sequences of g, consider the following diagram:

1 q δ . . . q δ(m-1) a 1 a 2 . . . a m with a 1 ≥ . . . ≥ a m . An admissible path is a transformation of this table into another table

1 q δ . . . q δ(m ′ -1) a ′ 1 a ′ 2 . . . a ′ m ′ such that • either m ′ = m -1, a ′ j = a j for 1 ≤ j ≤ m -1, if a m = 1;
• or m ′ = m, a ′ j = a j for all j = i, with 1 ≤ i ≤ m such that a i > a i+1 .

To such a path γ, we affect a weight w(γ), which is the sum of the coefficients written above the cells of the first table containing the same number a i as the cell whose coefficient was lowered in the second table. Here is an example of a table and all the admissible paths with the corresponding weights:

1 q δ q 2δ q 3δ 3 2 2 1 1 w w n n n n n n n n n n n n q δ +q 2δ q 3δ & & N N N N N N N N N N N
1 q δ q 2δ q 3δ 2 2 2 1 1 q δ q 2δ q 3δ 3 2 1 1

1 q δ q 2δ 3 2 2
By lemma 1.4.15, the weight of an admissible path from one table to another, is the number of irreducible invariant subspaces of an endomorphism g with type whose dual is given by the first table such that the quotient has the type given by the second table. Therefore, a sequence of admissible paths ending to an empty table represents a class of Jordan-Hölder sequences. Thus the number of distinct sequences in this class is the product of the weights of the paths along the sequence. Hence, the number of Jordan-Hölder sequences for g is (γ 1 ,...γτ ) τ i=1 w(γ i ) the sum being taken on all sequences (γ 1 , . . . , γ τ ) of admissible paths ending at the empty table (so τ = m j=1 a j ). Corollary 1.4.16. Let P ∈ k[X, σ] be a monic étale polynomial of dual type (a 1 , . . . , a m ). Then the number of factorizations of P as a product of monic irreducible polynomials is

(γ 1 ,...γτ ) admissible τ i=1 w(γ i ).
Example 1.4.17. If P has type (e) (so that its dual type is (1, . . . , 1)), then there is only one admissible path, and the number of factorizations is [q δ ] e = e i=1 q δi -1 q δ -1 . Example 1.4.18. If P has type (1, . . . , 1), (so that its dual type is (a)), there is only one admissible path, and only one factorization. The formula also shows that polynomials of this type are the only ones that have a unique factorization. These polynomials have already been studied for their interesting properties, under the name of lclm-indecomposable (see [START_REF] Nathan | The theory of rings[END_REF], Chap. 3, Th. 21 and 24 for properties, and [START_REF] Boucher | Self-dual skew codes and factorization of skew polynomials[END_REF] for applications).

For the general case, there is no such nice formula, but we can still explain how to get the number of factorizations. By the Chinese remainders Theorem, V is a direct sum of invariant subspaces on which the induced endomorphisms have minimal polynomial that is a power of an irreducible. Here, the type of g is defined again as the data of ((W 1 , T 1 ), . . . , (W s , T s )) where the W l 's are the distinct classes of irreducible invariant subspaces of V , and the T l 's are the tables representing the types of the endomorphisms induced on the corresponding subspaces of V . The notion of dual type can be defined as previously, as well as the notion of admissible path.

Proposition 1.4.19. Let g be an endomorphism of an F q -vector space V . Assume that the dual type of g is ((W 1 , T 1 ), . . . , (W s , T s )). Denote by δ i the dimension of W i , and by τ i the sum of the coefficients in table T i . Then the number of Jordan-Hölder sequences of g is

(τ 1 + • • • + τ s )! τ 1 ! • • • τ s ! (Γ 1 ,...,Γs) w(Γ 1 ) • • • w(Γ s ),
the product being taken over all the s-uples (Γ 1 , . . . , Γ s ) of admissible path sequences ending at the empty tables.

Proof. From a chain of admissible paths ending at ((W 1 , ∅), . . . , (W s , ∅)), it is possible to extract its W l -part Γ l for all 1 ≤ l ≤ s. By definition, it is the sequence of all the paths involving a change in the table associated to W l . Such a chain is a sequence of admissible paths from T l ending at the empty table. It is clear that the weight of the path sequence is the product of the weights of the Γ l 's. Therefore, it does not depend on the way the Γ l 's were combined together. The admissible path sequences that end at ((W 1 , ∅), . . . , (W s , ∅)) are all the different ways to recombine admissible path sequences from all the (W i , T i ) to the empty table. The weight of such a sequence is the product of the weights of the W l -parts. There are as many recombinations as anagrams of a word that includes τ l times the letter W l for all 1 ≤ l ≤ s, τ l being the sum of the integers appearing in T l . The result then follows directly from the previous discussion an the fact that the number of anagrams of a word that includes τ l times the letter W l is the multinomial coefficient

(τ 1 +•••+τs)! τ 1 !...τs! .
Example 1.4.20. Assume g has dual type ((W 1 , (a 1 )), . . . , (W s , (a s ))). It is easy to see that the only admissible path sequence for (W l , (t l )) has weight 1. Hence the number of Jordan-Hölder sequences of g is (a 1 +•••+as)! a 1 !...as! . This generalizes remark 1.4.18

Corollary 1.4.21. Let P ∈ k[X, σ] monic étale. Let ((W 1 , T 1 ), . . . , (W s , T s )) be the type of P . Then the number of factorizations of P as a product of monic irreducible polynomials is

(τ 1 + • • • + τ s )! τ 1 ! • • • τ s ! (Γ 1 ,...,Γs) w(Γ 1 ) • • • w(Γ s ),
the product being taken over all the s-uples (Γ 1 , . . . , Γ s ) of admissible path sequences ending at the empty tables.

In the next section, we describe an algorithm for counting the number of factorizations of a skew polynomial relying on this theory.

Remark 1.4.22. If N (P ) is a power of an irreducible commutative polynomial N , say N (P ) = N a , then the type of P can be determined as follows: let P 1 = P , and for i ≥ 1, define Q 1 = rgcd(P i , N ) and P i = P i+1 Q i . Let m be minimal such that Q m+1 = 1. Then for all 1 ≤ i ≤ m , N (Q i ) = N e i for some integer 1 ≤ e i ≤ r, and the type of P is (e 1 , . . . , e m ). The type can also be determined by looking at the degrees of the successive rgcd's of P with N, N 2 , N 3 , . . .

Computational aspects

This section deals with several computational aspects of skew polynomial rings. In the first part, we describe algorithms for arithmetics in these rings: multiplication, Euclidean division, gcd's and lcm's, and we give their complexities. Then, we give algorithms to compute the reduced norm of a skew polynomial as defined in the theoretical part. We use these algorithms and some other theoretical results to give a fast factorization algorithm. We give a detailed computation of the complexity of this algorithm. Finally, we describe algorithms for factorization-counting and random factorizations.

Throughout this section, we will use the following notations:

• MM(n) is the number of operations (in k σ ) needed to compute the product of two n × n matrices with coefficients in k σ .

• SM(n, r) is the number of operations (in k σ ) needed to multiply two skew polynomials with coefficients in k of degree at most n.

We recall that we have proved in §2.1.1 that one can take SM(n, r) = Õ(nr 2 ). Regarding matrix multiplication, the naive algorithm gives MM(n) = O(n 3 ) but it is well known that this complexity can be improved. For instance, using Strassen's algorithm, one have MM(n) = O(n log 2 7 ). Today, the best known asymptotic complexity for matrix multiplication is due to Vassilevska Williams [START_REF] Williams | Multiplying matrices faster than coppersmith-winograd[END_REF] and is about O(n 2.3727 ).

We use the common Õ notation: if f and g are two real functions defined on the integers, we say that f

(n) = Õ(g(n)) if there is some integer m such that f (n) = O(g(n) log m (n)).
We also assume that all usual arithmetics with polynomials can be done in quasilinear time. In particular, we assume that all usual operations (basically addition, multiplication and inverse) in an extension of k σ of degree d requires Õ(d) operations in k σ . We refer to [START_REF] Von | Modern computer algebra[END_REF] for a presentation of algorithms having these complexities. Regarding the Frobenius morphism on k, we assume that all the conjugates of an element a ∈ k can be computed in O(r 2 ) operations in k σ .

Fast arithmetics in skew polynomial rings

This section is dedicated to basic algorithms for arithmetics in skew polynomial rings.

Multiplication

Let A, B ∈ k[X, σ], both of degree ≤ d. We give several algorithms to compute the product AB and we compare their complexities.

The classical algorithm Let us recall that the classical algorithm of [START_REF] Giesbrecht | Factoring in skew-polynomial rings over finite fields[END_REF], Lemma 1.1 (which throughout this section will be referred to as "Giesbrecht's algorithm") has complexity Õ(d 2 r + dr 2 ). This algorithm uses the explicit formula for the coefficients of the product of two skew polynomials

: if A = d 1 i=0 a i X i and B = d 2 i=0 b i X j , then their product is d 1 +d 2 i=0 i j=0 a j σ j (b i-j ) X i .
For each coefficient b i of B, the list of the images of b i under all the powers of σ can be computed in O(r 2 ) operations in k σ . Hence, all the σ j (b i-j ) that may appear in the above formula can be computed in Õ(d 2 r 2 ). Once we have these coefficients, it remains to compute the product, which is done with O(d 1 d 2 ) operations in k, so the total complexity is Õ(d 2 r 2 + d 1 d 2 r). To write it more simply, if both polynomials have degree less than d, then their product can be computed in Õ(d 2 r + dr 2 ) operations in k σ .

Reduction to the commutative case Here, we use fast multiplication for commutative polynomials to multiply skew polynomials. Write A = r-1 i=0 A i X i , with each A i in k[X r ]. For 0 ≤ i ≤ r -1, we denote by B (i) the skew polynomial deduced from B by applying σ i to all coefficients. Then we have:

AB = r-1 i=0 A i B (i) X i . Since A i ∈ k[X r ],
it is easy to see that the product A i B (i) is the same as the product of these polynomials computed in k[X]. The algorithm is the following:

1. Compute the B (i) .

Compute all the products

A i B (i) . 3. Compute the sum AB = r-1 i=0 A i B (i) X i .
Lemma 2.1.1. The number of operations needed in k σ for the multiplication of two skew polynomials of degree at most d by the above algorithm is Õ(dr 2 ).

Proof. We may assume that both A and B have degree d. For step 1., we need to compute all the conjugates of the d coefficients of B, which can be done in O(dr 2 ) operations in k σ . The multiplications of step 2. as multiplications of elements of k[X] can be done in Õ(d) multiplications of elements of k, which corresponds to Õ(dr) operations in k σ . The total complexity of this step is then Õ(dr 2 ) operations in k σ . Finally, there are less than 2dr additions of elements of k to do in step 3., which is done in O(dr 2 ). The global complexity is therefore Õ(dr 2 ).

Remark 2.1.2. This complexity is apparently better than those of Giesbrecht's algorithm (the term dr 2 has gone) but we want to note that Giesbrecht's algorithm can beat this "commutative method" if the degree of B is much more less than the degree of A. Indeed, in that case the dominant term in Giesbrecht's complexity is d 1 d 2 r which can be competitive with d 1 r 2 if r is large compared to d 2 .

We are now going to present two variants of Karatsuba's multiplication to the noncommutative case. Actually, it will turn out that the resulting algorithms are asymptotically slower than the "commutative method"; nevertheless, we believe that they can be better in some cases and, for this reason, we include them in this paper.

The plain Karatsuba method

Let A, B ∈ k[X, σ]. Write A = A 0 + X mr A 1 and B = B 0 + X mr B 1 , with m = ⌊ max{deg A,deg B} 2r ⌋.
We can then write:

AB = C 0 + X mr C 1 + X 2mr C 2 , with C 0 = A 0 B 0 , C 1 = A 0 B 1 + A 1 B 0 and C 2 = A 1 B 1 , because X mr lies in the center of k[X, σ]. If we set P = (A 0 + A 1 )(B 0 + B 1 ), we get the fact that C 1 = P -C 0 -C 2 .
Hence, we can recover the product AB doing the 3 multiplications C 0 = A 0 B 0 , C 2 = A 1 B 1 and P = (A 0 + A 1 )(B 0 + B 1 ). Let MS(d) be the number of multiplications needed in k σ to multiply two elements of k[X, σ] of degree ≤ d using this method. We get:

SM(d, r) ≤ 3 • SM d 2 ≤ 3 log(d/r) log 2
• SM(r). The Karatsuba-and-matrix method The previous Karatsuba method relies on the classical multiplication for polynomials of degree < r. Here, we propose another fast multiplication method for polynomials of degree up to r 2 /2, that can be combined with the Karatsuba method.

Let N ∈ k σ [X r ] be the defining polynomial of the extension k/k σ . We will denote by t a root of N in k. By Lemma 1.2.3, the ϕ-module k[X, σ]/N is isomorphic to M r (k). Here, the isomorphism can be given explicitely. Indeed, the isomorphism of this Lemma maps A ∈ k[X, σ]/N to the matrix of the right multiplication by A in some basis of the k-vector space k[X, σ]/N . Let us choose the basis 1, X, . . . , X r-1 . If a ∈ k, the matrix of the right multiplication by a is given by:

M a =       a 0 • • • 0 0 σ(a) . . . . . . . . . . . . . . . . . . 0 • • • 0 σ r-1 (a)      
.

The matrix of multiplication by X is:

M X =       0 1 • • • 0 0 . . . . . . 0 . . . . . . . . . 1 t • • • 0 0       . So, if A = r 2 -1 i=0 a i X i ∈ k[X, σ]
, the image of A (mod N ) can be computed easily by the previous isomorphism. More precisely, write A = r-1 i=0 A i X i with A i ∈ k[X r ] of degree < r. Then the matrix of m A is:

M A =       A 0 (t) σ(A r-1 )(t) • • • σ r-1 (A 1 )(t) tA 1 (t) σ(A 0 )(t) • • • . . . . . . . . . . . . σ r-1 (A r-1 )(t) tA r-1 (t) • • • tσ r-2 (A 1 )(t) σ r-1 (A 0 )(t)      
.

The matrix M A can be computed as follows. We first evaluate all the polynomials A i 's at all the conjugates of t. Using efficient algorithms (see [START_REF] Von | Modern computer algebra[END_REF], §10), it requires Õ(r 3 ) operations in k σ . We can then compute σ j (A i )(t) by applying σ j to A i (σ -j (t)). Computing all these quantites requires Õ(r 4 ) further operations in k σ . Then to obtain M A , it remains to multiply some of the previous coefficients by t, which requires at most Õ(r 3 ) further operations in k σ . Computing M A can then be done with complexity Õ(r 4 ).

We can go in the other direction following the same ides. We first divide by t all coefficients above the diagonal of M A . We then apply σ 0 to the first column, σ r-1 to the second column, . . ., σ to the last column and, finally, recover the A i 's by interpolation. As before, the complexity is Õ(r 4 ) operations in k σ .

Once noticed these facts, the idea is quite simple: let A, B ∈ k[X, σ] of degree < r 2 /2. We compute the corresponding matrices M A , M B , then the product M A M B and finally recover the coefficients of (the reduction modulo N ) of AB. This whole algorithm can be done in Õ(r 4 ) operations in k σ .

Combining this with Karatsuba multiplication (but using this as soon as we hit polynomials of degree < r 2 /2), we get:

SM(d, r) = Õ ( d r 2 ) log 3 log 2 • SM( r 2 2 , r) = Õ(d log 3 log 2 r 4-2 log 3 log 2 )
provided that d > r 2 . This is about Õ(d 1.58 r 0.83 ).

Remark 2.1.3. The most expensive step of the previous algorithm is the application of the Frobenius. Hence, if we are working over a finite field where applying Frobenius can be done efficiently, our complexity may decrease to O(r • MM(r)) -which beats the "commutative method". If we take M M (r) = O(r 2.3727 ), the resulting final complexity becomes Õ(d 1.58 r 0.2 ).

Euclidean division

Let A, B ∈ k[X, σ] with deg A ≥ deg B. We want to compute the right-Euclidean division of A by B:

A = QB + R, with deg R < deg B.
The following algorithm is based on the Newton iteration process presented for example in [GG03], §9.1, which uses reciprocal polynomials. Our algorithm is an almost direct adaptation of it, the only subtlety here is that the map sending a skew polynomial to its reciprocal polynomial is not a morphism.

Lemma 2.1.4. For n ≥ 0, we denote by k[X, σ] ≤n the subspace of skew polynomials of degree at most n. Let

τ n : k[X, σ] ≤n → k[X, σ -1 ] ≤n n i=0 a i X i → n i=0 a n-i X i .
Then τ n is k-linear, bijective, and for all P, Q ∈ k[X, σ], with deg P ≤ n and deg Q ≤ m, we have:

τ n (P )τ m (Q (n) ) = τ m+n (P Q).
Proof. The k-linearity is trivial, as well as bijectivity.

Let P = n i=0 a i X i and Q = m j=0 b j X j . Then the coefficient of X l in the product P Q is c l = i+j=l a i σ i (b j ).
Hence, the coefficient of

X l in τ m+n (P Q) is c n+m-l = i+j=l a n-i σ n-i (b m-j ). This is clearly the coefficient of X l in the product τ n (P )τ m (Q (n) ), computed in k[X, σ -1 ].
Let us now describe the Euclidean division algorithm. Let n = deg A and m = deg B. According to the previous formula, if A = QB + R is the right-Euclidean division of A by B, we have:

τ n (A) = τ n-m (Q)τ m (B (n-m) ) + τ n (R). Since deg R < m, τ n (R) is divisible by X n-m+1
. The idea is to compute an approximation of the left-inverse of B = τ m (B (n-m) ) in k[[X, σ -1 ]] (the ring of skew power series, which is defined in the obvious way, and is only used here to sketch the idea of the algorithm). Once we get such an approximation Q, truncated at precision X n-m , we know that

τ n (A) Q B - τ n (A) ∈ X n-m k[X, σ -1 ],
and by applying τ -1 n , we get the quotient Q. Computing successive approximations of Q is done by Newton iteration: let B 0 be the constant coefficient of B, we define Q0 = B -1 0 , and Qi+1 = 2 Qi -Qi B Qi , truncated at

X 2 i . Lemma 2.1.5. For all i ≥ 0, Qi B -1 ∈ X 2 i k[X, σ -1 ].
Proof. The proof goes by induction on i. By construction, Q0 B -1 ∈ Xk[X, σ -1 ]. Now assuming that the result is true for some i ≥ 0, we have:

Qi+1 B -1 = 2 Qi B -Qi B Qi B -1 = -(1 -Qi B) 2 ∈ X 2 i+1 k[X, σ -1 ]
and we are done.

Proposition 2.1.6. The algorithm REuclideanDivision returns the quotient and remainder of the right-division of A of degree n by B of degree m in Õ(SM(n, r)) operations in k σ .

Then Q = Q * , and either (B, R) and

(B, R * ) coincide up to 2(n -deg Q) or R = 0 or n -deg Q < deg B -deg R.

Now, we want to carry this approximation further down the sequence of quotients when doing the Euclidean algorithm. For

A 0 , A 1 , A * 0 , A * 1 ∈ k[X, σ] monic, with deg A 0 > deg A 1 and deg A * 0 > deg A * 1 , we write: A 0 = Q 1 A 1 + ρ 2 A 2 , A * 0 = Q * 1 A * 1 + ρ * 2 A * 2 , . . . . . . A i-1 = Q i A i + ρ i+1 A i+1 , A * i-1 = Q * i A * i + ρ * i+1 A * i+1 , . . . . . . A ℓ-1 = Q ℓ A ℓ , A * ℓ * -1 = Q * ℓ * A * ℓ * , with for all i, deg A i+1 < deg A i , with ρ i ∈ k × and A i monic. From this sequence, we define for 1 ≤ i ≤ ℓ, m i = deg Q i , n i = deg A i , and for n ∈ N, η(n) = max    0 ≤ j ≤ ℓ | 1≤i≤j m i ≤ n    .
We define analogously m * i , n * i and η * . Then the following lemma quantifies how much the first results in the Euclidean algorithm only depend on the highest-power terms of the entires;

Lemma 2.1.9 ([GG03], Lemma 11.3.). Let n ∈ N, h = η(n) and h * = η * (n). If (A 0 , A 1 ) and (A * 0 , A * 1 ) coincide up to 2n, then h = h * , Q i = Q * i and ρ i+1 = ρ * i+1 for 1 ≤ i ≤ h. Let us now describe the extended Euclidean Algorithm. Algorithm 2: FastExtendedRGCD Input: A 0 , A 1 ∈ k[X, σ] monic, n 0 = deg A 0 ≥ deg A 1 = n 1 and n ∈ N with 0 ≤ n ≤ n 0 . Output: M ∈ M 2 (k[X, σ]) such that M A 0 A 1 = A h A h+1 with h = η(n).
Theorem 2.1.10 ([GG03], Theorem 11.5.). The algorithm FastExtendedRGCD works correctly and uses at most O(SM(n, r) log n) operations in k σ if A 0 has degree d ≤ 2n. In particular, it allows to compute the rgcd and llcm with Õ(SM(d, r)) operations in k σ .

Proof. The proof for correctness is exactly the same as the one in [START_REF] Von | Modern computer algebra[END_REF] and relies on the previous two lemmas. Let us give more details about the complexity of the algorithm. Denote by T (n 0 , n 1 , n) the time needed to call FastExtendedRGCD on two skew polynomials A 0 , A 1 of degrees n 0 , n 1 , with parameter n. Set d = ⌊n 0 /2⌋. Then we have:

T (n 0 , n 1 ) ≤ T (2d, 2d -(n 0 -n 1 ), d) + T (2d * , 2d * -(n j -n j-1 ), d * ) + O(SM(d, r)).
The term SM(n 0 , r) here comes from the multiplications needed from matrix multiplications (all the polynomials in these matrices have degree at most n 0 ) and one due to the Euclidean division algorithm. The result follows by induction from the fact that d * = ⌈n/2⌉.

Computing the norm

In this section, we give algorithms to compute the reduced norm of a skew polynomial. Let N = N k/k σ be the norm from k to k σ . Let P ∈ k[X, σ] of degree d. We give two different ways to compute the norm, depending on whether d is greater or smaller than r. Let us start with the first case, d < r:

Proposition 2.2.1 ([Jac96], Proposition 1.7.1). Let P ∈ k[X, σ] of degree d < r, P = d i=0 a i X i .
Then

N (P ) = (-1) rd N (a 0 ) + (-1) r(d-1) N (a 1 )X r + • • • + N (a d )X rd .
This Proposition gives a direct way to compute N (P ): this is done by computing the norms of its d coefficients. Since all the conjugates of an element of k can be computed in Õ(r 2 ) operations in k σ , and the product of r elements of k requires Õ(r 2 ) operations in k σ , the norm of an element of k can be computed in Õ(r 2 ) operations in k σ . Hence, by Proposition 2.2.1, we get an algorithm to compute N (P ) in Õ(dr 2 ) operations in k σ when r < d.

Let us now address the case d ≥ r. We use the fact that N (P ) is the determinant of multiplication by X r on D P , seen as a k[X r ]-module. Let t ∈ k be a primitive element over k σ , and let π t ∈ k σ [X r ] be its minimal polynomial over k σ . Let R 0 ∈ k σ [X r ] be a polynomial of degree n > d/r. Let R be the polynomial obtained by composition:

R = π t • R 0 . We work in the ring A = k σ [X r ]/R.
The idea is the following: if R is irreducible, then A is a field extension of k σ , and there is a natural embedding of k into A, mapping t to R 0 . Then we can write the matrix of multiplication by P in k[X, σ] seen as a module over k[X r ], and map it to a matrix with coefficients in A. Then we can compute the determinant of this matrix, which is the image ν of the norm of P by the map k[X r ] → A. Since it is known to be a polynomial with coefficients in k σ of degree d, and since [A : k σ ] > d, the coefficients of the N (P ) are exactly the coefficients of ν written in the canonical basis of A.

Actually, all of the above still holds if A is not a field, except that we may not use algorithms for determinants over fields to compute ν. However, we can still obtain this determinant efficiently by computing the Hermite normal form of the matrix of multiplication by P in the Euclidean domain A. So in practice, all we have to do is write the matrix of multiplication by P as a matrix with coefficients in k[X r ]. Write P = P 0 + P 1 X +

• • • + P r-1 X r-1 .
As stated in the proof of Lemma 1.4.1, in the canonical basis 1, X, . . . , X r-1 , the matrix of multiplication by P is:

        
P 0 X r σ(P r-1 ) . . . . . . X r σ r-1 (P

P r-1 • • • • • • • • • σ r-1 (P 0 )         
.

We map this matrix to A by taking X r to its residue class modulo R, and t to R 0 (mod R).

Then, we compute its determinant ν (using Smith normal form), and we can read the coefficients of N (P ) on ν.

If P has degree d, the complexity of these operations is: O(dr 2 ) operations to compute all the conjugates of the P i 's under the action of the Frobenius. Multiplication by X r is free in k[X r ]. This yields a total of O(dr 2 ) operations to compute the matrix, and then O(dr 3 ) operations in k σ to get its determinant. Hence, P can be computed in O(dr 3 ) operations in k σ .

To sum it up, if r < d, then we can compute N (P ) in O(dr 2 ), and if r ≥ d, we can compute it in O(dr 3 ) operations in k σ .

A fast factorization algorithm

Let P ∈ k[X, σ] be a monic polynomial. Our aim is to give an algorithm to compute a factorization of P as a product of irreducible skew polynomials. The idea of the algorithm is to reduce that problem to the problem of factoring polynomials of type (e) (using rgcd's with factors of the norm of P ) and then to factor polynomials of type (e). For the sake of brevity, in the algorithms we will use the notation A/B for the quotient of the right-division of A by B.

Reduction to the type-(e) case

The following algorithm recursively computes the rgcd of a polynomial P with a central polynomial (whose irreducible factors are all irreducible factors of N (P )) and writes it as a product of polynomials of type (e) (for some integer e depending on the factor).

Factoring a polynomial of type (e)

Let us now explain how to factor a polynomial P of type (e). Clearly, N (P ) = N e with N ∈ k σ [X r ] irreducible. In this case, we know that P is a divisor of N , we write P Q = N and will work with k

[X, σ]Q/(N ) rather than k[X, σ]/k[X, σ]P . Let R ∈ k[X, σ]Q/(N ). Right-multiplication by R is an endomorphism of k[X, σ]Q/(N ) that is a space of dimension e. Hence, there exist λ 0 , . . . , λ e-1 ∈ E such that R e = e-1 i=0 λ i R i . Now assume that F (T ) = T e -e-1 i=0 λ i T i ∈ E[T ] has a root α ∈ E. Then R -α is a zero- divisor in k[X, σ]Q/(N )
. Indeed, α is an eigenvalue of multiplication by R, so there exists some S ∈ k[X, σ]Q/(N ) such that S(Rα) is zero in k[X, σ]Q/(N ). Write R = RQ and S = SQ, then S(Q Rα) is divisible by P , so that the right gcd of Q Rα is a divisor of P . Moreover, if α is the only eigenvalue of the multiplication by R (with multiplicity one), then this divisor is irreducible. We will see that this happens with good probability. Once we get an irreducible factor, we can proceed recursively to factor P . However, we can also use a slightly more efficient trick relying on the knowledge of an irreducible factor.

Algorithm 3: Type_e_Factorization Input: P ∈ k[X, σ], (N 1 , . . . , N m ) irreducible such that N (P ) = N i , ordered by nondecreasing degree Output: P 1,1 , P 1,2 , . . . , P 1,m 1 , . . . , P n,1 , . . . , P n,mn ∈ k[X, σ] and N 1 , . . . , N n ∈ k σ [X r ] irreducible such that P = i j P i,j and each P i,j has type e j and norm N

e j 1 d 1 = deg N 1 ; 2 for 1 ≤ i ≤ m -1 do d i+1 = d i + deg N i+1 ; 3 d = d m ; δ = d/ log d; 4 i = min{1 ≤ j ≤ m -1 | d j > d + δ/2}; 5 if [d -δ/2, d + δ/2] ∩ {d 1 , . . . , d m-1 } = ∅ then 6 j = m;
. , N i-1 )), {P j | i ≤ j ≤ m}; 12 13 M = N i • • • N m ; 14 Q 1 = rgcd(P, M ); Q 2 = P/M ; 15 return Type_e_Factorization(Q 2 , (N 1 , . . . , N i )), Type_e_Factorization(Q 1 , (N i , . . . , N m ));
Assume we know an irreducible right factor P 1 of P , and write P = P 2 P 1 . Let R ∈ k[X, σ] and let A = rgcd(P, P 1 QR). Now let B = llcm(A, P 1 ) = BP 1 . Since P is a right multiple of both P 1 and A, B is a divisor of P . Hence, B is a divisor of P 2 . In general, A and B should have the same degree as P 1 , yielding an irreducible factor of P 2 . The precise probability study will appear in §2.4.2. The following two algorithms describe how to factor a polynomial P of type (e): the first one finds one irreducible factor of P , and the second one performs the "lcm trick" to factor P as a product of irreducibles given one irreducible right factor.

There are at most log d rgcd's of a skew polynomial of degree at most d with skew polynomials of degree at most dr, which takes Õ(SM(dr, r)) operations, and all the other computations are cheaper than this. Again, we have:

C(d, r) ≤ C d 1 + 1 log d , r + Õ(SM(dr, r)) ≤ 2 • C d 1 + 1 log d , r + Õ(SM(dr, r)).
Let us assume that the Õ(SM(dr, r)) appearing in the above inequality is ≤ cdr 3 log α d for some constants c, α (we use the fact that SM(d, r) = Õ(dr 2 )). We are going to show that there exists a constant c ′ such that

C(d, r) ≤ c ′ dr 3 log α+1 d.
We want to have:

C(d, r) ≤ 2c ′ d 2 1 + 1 log d r 3 log α+1 d 2 1 + 1 log d + cdr 3 log α d.
This implies that: Since it is possible to choose such a c ′ , the proof is complete.

C(d, r) ≤ c ′ dr 3 log α+1 d 1 - log 2 log d + O 1 log 2 d α+1 + c ′ dr 3 log α d + cdr 3 log α+1 d. If we choose c ′ such that c ′ + c -c ′ (α + 1) log 2 + O
FirstFactor We shall detail the complexity of all the steps of this algorithm. In the following, P has type (e) and norm N e , with e ≤ r. The degree of N as an element of k σ [X r ] is δ, so that the degree of P is δe.

1. Compute Q ∈ k[X,
σ] such that P Q = N . This Euclidean division can be done with complexity SM(dr, r). Note that this step is done only once even if the loop fails to find a divisor.

2. Choose a random element R ∈ k[X, σ]/k[X, σ]P and compute RQ, . . . , (RQ) e modulo N . This requires e multiplications of skew polynomials of degree δr plus one reduction modulo N at each step. After having remarked the reduction modulo N of a skew polynomial is equal to its reduction modulo N in the ring of usual polynomials, we see that it costs only Õ(δ 2 r) operations in k σ . The whole cost of this step is then O(e • SM(δr, r)).

3. Find a linear dependence between the powers of RQ of the following for:

e i=0 a i (RQ) i = 0. (1)
where all a i 's are in E. Even though the element (RQ) i naturally live in a space of dimension r 2 over E, we know the first e of them are linearly dependent, and we can work in a vector space of dimension e over E by projection. Hence, the complexity of this step is δ • MM(e).

4. Check whether the polynomial F (T ) = e i=0 a i T i (where the a i 's are defined by formula (1)) has a root in E. For this, it is enough to compute the gcd of F with T #E -T . Noting that #E = q δ with q = #k σ , we can first compute T #E modulo F (T ) by first raising T to the q-th power modulo F (T ) (using classical fast exponentiation) and then performing O(log δ) modular compositions. Using Corollary 5.2 of [START_REF] Kedlaya | Fast modular composition in any characteristic[END_REF], this can be done in Õ(δ log 2 q + e 1+ε (δ log q) 1+o(1) ) bit operations, for all ε > 0 (the first term corresponds to the fast exponentiation and the second to the modular compositions). It then remains to compute the gcd of two polynomials over E of degree ≤ e, which can be achieved with Õ(eδ) more operations in k σ . 5. Compute the right gcd of P with a skew polynomial of degree δr, which costs Õ(SM(δr, r)) operations in k σ . Note that this step is done only once even if the loop fails to find a divisor.

Since any operation in k σ requires Õ(log q) bit operations, the total complexity of this algorithm is Õ(SM(δr, r) • e log q + MM(e) • δ log q + δ log 2 q + e 1+ε (δ log q) 1+o(1) ) bit operations. Using SM(n, r) = Õ(nr 2 ) and MM(n) = O(n 3 ) and noting that e ≤ r, this becomes Õ(δer 3 log q + δ log 2 q + e 1+ε (δ log q) 1+o( 1) ) for all ε > 0. We will see in §2.4.3 why the probability of failure is bounded from below independently on the data of the problem.

FactorStep This algorithm computes a factorization of P (still of type (e)) when P , knowing a factor of P . The next irreducible factor is computed with one rgcd and one llcm between polynomials of degree at most δr. This operation may fail (in which case, we repeat it with a new random input) but we will see in the next section that the propability of failure is very small. Hence, in order to compute the complexity, it is safe to assume that failures never append. As it is shown in §2.1.10, this has complexity Õ(SM(δr, r)).

Hence the complexity of this step is Õ(δr 3 ).

Global complexity

Let us sum up all the previous step complexities to give the complexity of the whole factorization algorithm.

Theorem 2.4.2. The algorithm SkewFactorization runs in Õ(dr 3 log q + d log 2 q + d 1+ε (log q) 1+o(1) + F (d, k σ ))

bit operations to factor a skew polynomial of degree d. Here, F (d, K) denotes the complexity of the factorization of a (commutative) polynomial of degree d over the finite field K.

Proof. Computing the norm of P ∈ k[X, σ] of degree d takes O(dr 3 ) operations in k σ . Factoring the norm N (P ) (that has degree d as an element of k σ [X r ]) takes by definition F (d, k σ ) operations in k σ . Then, the algorithm Type_e_Factorization runs in Õ(dr 3 ) operations in k σ . Let P 1 , . . . , P m be the factors of P obtained after Type_e_Factorization. Assume that P i has type e i and degree δ i e i . Then for each i, the factorization of P i takes Õ(δ i e i r 3 log q + δ i e i log 2 q + e 1+ε (δ log q) 1+o(1) ) bit operations (it uses FirstFactor and FactorStep). So, to factor P given its "type-(e)-factorization", we need Õ(dr 3 log q + d log 2 q + d 1+ε (log q) 1+o(1) ) bit operations. Putting all the steps together, we get the desired complexity.

Remark 2.4.3. Of course, this result is true provided that the probabilities of success of the probabilistic parts of the algorithm are bounded from below independently of d and r.

This is what we will show in the next part.

Probability of finding a factor

The function FactorStep finds an irreducible factor of P whenever the random endomorphism "multiplication by R" has exacly one (simple) eigenvalue in E. By Corollary 1.4.8, if R is uniformly distributed in k[X, σ]Q/(N ), then m R is uniformly distributed in End(k[X, σ]Q/(N )). Therefore, we want to evaluate the probability for an endomorphism of a E-vector space of dimension e to have a unique eigenvalue in E. Let B d be the probability that a d × d matrix with coefficients in E has 0 as a simple, unique eigenvalue in E. Obviously, setting q = #E, this is 1 q times the probability that a d × d matrix has a simple, unique eigenvalue in E. We can write:

q d 2 B d = #P(E d ) • q d-1 q (d-1) 2 • A d-1 = 1 -1 q d 1 -1 q • A d-1 q .
where A i denotes the probability that a i×i matrix with coefficients in E has no eigenvalue in E.

Let us now detail how to obtain a bound on A i . By [START_REF] Peter | Derangements and eigenvalue-free elements in finite classical groups[END_REF], Theorems 4.1 and 4.2, we get the formula for the generating series:

+∞ i=0 A i z i = 1 1 -z G(z)
where G(z) = +∞ i=1 1 -z q i q-1 . If we write G(z) = i C i z i , then for all i ≥ 0, A i = i j=0 (-1) j C j . Lemma 2.4.4. We have the following formulas:

• A 0 = C 0 = 1 • C 1 = 1 • C 2 = q 2(q+1)
Proof. The first two assertions follow easily from identifying the coefficients of 1 and z in the power series G. For the third formula, identifiying the coefficient of z 2 gives:

C 2 = +∞ i=1 (q -1)(q -2) 2q 2i + i<j (q -1) 2 q i+j .
The result then follows from the usual formulas for sums of geometric progressions.

Next, remark that:

+∞ i=0 C i = i≥1 1 + 1 q i q-1 and +∞ i=0 (-1) i C i = i≥1 1 - 1 q i q-1
.

Combining both expressions, we get:

2 • +∞ i=0 C 2i+1 = i≥1 1 + 1 q i q-1 - i≥1 1 - 1 q i q-1
.

Studying the function q → i≥1 (1 + q -i ) q-1 -i≥1 (1q -i ) q-1 are non-decreasing, we find that the the sum +∞ i=0 C 2i+1 is smaller than its limit when q goes to infinity:

+∞ i=0 C 2i+1 ≤ 1 2 e - 1 e .
Now, it is clear that for all i ≥ 0, A i ≥ C 0 + C 2 -+∞ i=0 C 2i+1 = 1 + q 2(q+1) -1 2 e -1 e . Note that this quantity is ≥ 0.15 for all q, and ≥ 0.3 when q ≥ 23.

Probability of finding another factor

As usual, we assume that P is a right-divisor of N ∈ k σ [X r ] irreducible, with N (P ) = N e and deg N = δ. We have seen that once we know an irreducible factor of P , there is an easy way to factor it without using FirstFactor again. The following lemma makes this more precise: Lemma 2.4.5. Let P = P 2 P 1 with P 1 irreducible and P 2 reducible, and let R be a random variable following the uniform distribution on k[X, σ]. Let A = rgcd(P, P 1 QR) and B = llcm(A, P 1 ) = BP 1 . Then the probability that B is an irreducible right factor of P 2 is at least 1 -1 q δ(e-1) Proof. We work in k[X, σ]/N . Remark then that AQ = rgcd(N, P 1 QRQ) and that B = llcm(AQ, P 1 Q). We see the multiplication by RQ as an endomorphism m RQ of k[X, σ]Q/N . Since R follows the uniform distribution, so does m RQ . Remark that m RQ (k[X, σ]P 1 Q/N ) is a sub-ϕ-module of k[X, σ]/Q. It is actually equal to k[X, σ]AQ/N . Indeed, k[X, σ]P 1 QRQ ⊂ k[X, σ]AQ, and AQ ∈ k[X, σ]P 1 QRQ/N by definition. Then, we remark that the projection along k[X, σ]P 2 onto k[X, σ]P 1 Q/N maps the sub-ϕ-module U Qk[X, σ]/N to llcm(U, P 1 )Qk[X, σ]/N . In particular, BQk[X, σ]/N is the projection of m RQ (P 1 Qk[X, σ]/N ) onto k[X, σ]P 1 Q/N . Therefore, B is an irreducible right-factor of P 2 unless m RQ (k[X, σ]P 1 Q/N ) = k[X, σ]P 1 Q/N . Since m RQ is uniformly distributed in the endomorphisms of D P and k[X, σ]P 1 Q/N has cardinal q de(e-1) while D P has cardinal q de 2 , this happens with probability 1 q d(e-1) .

Other algorithms related to factorizations

In this section, we give some more details on other algorithms that could have interesting applications. The theoretical material on which they rely is only what appears in previous sections.

  decomposition of ϕ-modules), we can extend ũ to D N by setting ũ(P ) = 0. By Lemma 1.4.7, there exists T ∈ D N such that for all x ∈ D N , ũ(x) = xT . In particular:P T ≡ 0 (mod N ) QST ≡ AQS (mod N ) Since V P T + QST = T ,we have QST ≡ T (mod N ). So, for x ∈ D N , we get ũ(xQS) = xQST = xQSAQS = (xQSA)QS. Hence, for x ∈ D P , u(x) = xQSA. Setting R = SA, we have u = m QR . Corollary 1.4.8. Let R be a random variable uniformly distributed on D P . Then the right multiplication by QR, m QR , is uniformly distributed on End ϕ (D P ) ≃ M e (E).

  Hence, this method allows to multiply polynomials of degree ≤ d in time O ( d r ) log 3 log 2 SM(r) provided that d > r. Using Giesbrecht's algorithm for multiplication of skew polynomials of degree < r, we get a complexity of O d log 3 log 2 r 3-log 3 log 2 , which is around O d 1.58 r 1.41 .

7 while j ≥ i do 8 P

 8 j = rgcd(P, N j ); 9 j = jdeg P j / deg N j ; 10 P = P/P j ; 11 return Type_e_Factorization(P, (N 1 , . .

1 log 2

 2 d ≤ 0 for d large enough, then induction shows that for d large enough, C(d, r) ≤ c ′ dr 3 log α+1 d.

In Giesbrecht's paper, the complexity is given in number of operations in k σ . Since any operation in k σ requires Õ(log q) bit operations (using fast algorithms), the complexity we have given is just from Giesbrecht's one by multiplying by Õ(log q).

if A 1 = 0 or n < n 0n 1 then return 0, 1 0

Algorithm 1: REuclideanDivision

Proof. We have already seen that the result of this algorithm is correct. In order to compute B, O(mr 2 ) operations are needed. The while loop in the algorithm has log 2 (nm + 1) steps, and at the i-th step, we compute the product of skew polynomials of degree 2 i , so the global complexity of this is log 2 (n-m+1) i=0 SM(2 i , r) = Õ(SM(nm, r)). Computing (τ n (A) (mod X n-m )) Q has the same complexity. Finally, we compute the product QB in SM(max m, nm, r) operations, and R = A -QB in Õ(SM(n, r)) operations.

Greatest common divisors and lowest common multiples

This section describes an algorithm adapted directly from Algorithm 11.4 of [START_REF] Von | Modern computer algebra[END_REF], to compute the right-gcd R of two skew polynomials A and B, together with skew polynomials U, V such that U A + V B = R. As we have seen before, this also gives almost directly the left-lcm of A and B.

This algorithm relies on the fact that in the Euclidean division, the highest-degree terms of the quotient only depend on the highest-degree terms of the dividend and divisor.

, with the convention that a j = 0 for j / ∈ {0, • • • , d}. Then, for n ≥ 0, A (n) is a skew polynomial of degree n, and for n < 0. Note that for all i ≥ 0,

and n ∈ Z, we say that (A, B) and

Then we have the following:

R * as the quotient and remainder in the right-divisions:

When executed for n = n 0 , the above algorithm gives an immediate way to compute the right-gcd and left-lcm of A 0 and A 1 . Indeed, in this case, we get a matrix

] such that of type (e), N (P ) = N e , N is irreducible and P 1 is an irreducible right factor of P Output: Irreducible polynomials P 1 , . . . , P e such that Glueing together the three previous algorithms, we get a complete factorization algorithm. We assume that the function Factorization returns the factorization of a (commutative) polynomial as a product of irreducible polynomials ordered by their degrees.

Algorithm 6: SkewFactorization

7 return (P i,j,l );

Complexity

In this section, we analyze the complexity of the factorization algorithm. The complexity will be expressed in terms of the degree d of the skew polynomial that is to be factored, the degree r of k/k σ , and the cardinal q of k σ .

Complexity of the steps

Let us detail the complexity of the steps of our factorization algorithm.

Type-(e)-factorization We have the following lemma, giving the complexity of the algorithm Type_e_Factorization.

Then the algorithm Type_e_Factorization applied to P and N 1 , . . . , N m returns a correct result with Õ(dr 3 ) operations in k σ .

Proof. Let us prove the result by induction on d. Let (N 1 , a 1 ), . . . , (N m , a m ) be the irreducible polynomials that are given as arguments, and δ i = deg N i for 1 ≤ i ≤ m. We assument that the N i 's are ordered so that the sequence of δ i is nondecreasing. There are two cases to look at.

If there exists

then we choose the minimal (i, a) (for the lexicographical order) having this property. We write N l = N a i i-1 j=1 N a j j , and N r = N/N l . Then we write P r = rgcd(P, N r ), and define P l as the quotient in the right-division of P by P r . The algorithm is then applied to (P l , N l , (N 1 , a 1 ), . . . , (N i , a)) and (P r , N r , (N i , a ia), . . . , (N m , a m )).

The number of operations needed for this is denoted by C(d, r). In this case, we have:

Indeed, the operations we have to do before starting the recursive steps are: computing a product of (commutative) polynomials in k σ [X r ] such that the sum of their degrees is less than d 1 + 1 log d , computing the right gcd of P with a polynomial of degree less than dr, and dividing P by this gcd. The most expensive part is the computation of the gcd, and it costs Õ(SM(dr, r)).

In the other case, there is no (i, a) such that i-1 j=1

Hence, for (i, a) such that i-1 j=1 a j δ j + aδ i > d 2 1 + 1 log d , we know that δ i > d log d , and there are at most log d such couples (i, a). In this case, the algorithm is to compute N l , N r as before, and then the successive gcd's of P the N i 's having the previous property, and apply the algorithm with the last quotient P l and N l .

Counting factorizations

This algorithm uses the formula given in corollary 1.4.21, and is recursive. First, we give the algorithm computing the number of factorizations of a skew polynomial as a function of its type: Algorithm 7: CountFactorizationsStep Input: (δ, (e 1 , . . . , e n )) an integer and a nonincreasing sequence of integers Output: The number of factorizations a skew polynomial whose norm is a power of an irreducible of degree δ and that has dual type (a 1 , . . . , a n )

The following algorithm gives the number of factorizations of a given skew polynomial as the product of its leading coefficient and monic irreducible skew polynomials. We assume that we have a function DualType that computes the dual of a nondecreasing sequence of integers.

Algorithm 8: CountFactorizations

Input:

The number of factorizations of P as a product of its leading coefficient and monic irreducible polynomials

13 a = DualType(e 1 , . . . , e j-1 );

For some applications of skew polynomials, it could be interesting to have an algorithm that returns a factorization of a given skew polynomial P , following the uniform distribution on all factorizations of this skew polynomial. In this section, we describe such an algorithm. Since we do not want to simply list all factorizations of P and pick one randomly (because there can be so many factorizations, so this would have a very bad complexity), we want an algorithm that can simulate the uniform distribution on the right-factors of P . Let us first explain how to do this when P has type (e).

Assume P has type (e) and norm N e , and let E = k σ [X r ]/(N ). As usual, d = deg N and q = #k σ . Suppose that we know one irreducible right-factor P 0 of P . This factor correponds to a E-line in D P = k[X, σ]/k[X, σ]P . The orbit of this line under the action of End ϕ (D P ) is the set of all E-lines in D P , corresponding to all irreducible right-divisors of P . We now want to find one element u ∈ End ϕ (D P ) such that End ϕ (D P ) = E(u), so that in order to simulate the uniform distribution on the irreducible right-divisors of P , it is enough to simulate the uniform distribution on the polynomials of degree < e with coefficients in E and compute the image of our line under the action of M (u), where M is the polynomial that we get. Let us estimate the probability to find such a u. Since End ϕ (D P ) ≃ M e (E), we want to know the probability that, for a fixed nonzero vector x ∈ E e , an element u ∈ M e (E) admits an element of the line Ex as a cyclic vector. The number of u ∈ M(E) that have this property is (q d -1)(q deq d ) • • • (q deq d(e-1) ). Hence the probability to find a u with the desired property is

which is greater than 0.53 1 -1 q d by [NP98], Lemma 2.2 (applied to computing the value of the infinite product when q d = 4).

Once we know how to randomly get a divisor of a polynomial of type (e), the idea of the algorithm to get a random factorization of any skew polynomial P is the following: compute the type of P , and randomly choose an irreducible divisor N i of N (P ) (with uniform distribution). Compute Q = rgcd(N i , P ) and randomly find a right-irreducible divisor P 1 of Q with the previous algorithm. Let Q 1 P 1 = Q. Compute the type of Q 1 . Keep the factor P 1 with the same probability as the ratio of irreducible right-divisors of Q yielding a left-divisor of the type of Q 1 (this can be done counting the factorizations of Q and Q 1 , which depends only on their types). Write P = RP 1 and randomly factor R. By construction, it is clear that the factorization we get in the end is uniformly distributed among all factorizations of P .

Implementation

All algorithms presented in this article were implemented is sage. The source code is available on the CETHop website at the URL: http://cethop.math.cnrs.fr/documents/skew_polynomials-sage.tgz A magma package is also available; it includes some of the algorithms presented here (and, in particular, the factorization algorithm). It can be downloaded at the URL: http://cethop.math.cnrs.fr/documents/skew_polynomials.m