M. GHEDBANE Nasser

he holomorph of the group G, usually denoted by Hol (G), is the natural semidirect product Aut (G) G of G by its automorphism group Aut (G).
Let λ : G −→ S (G) , g 7 −→ fg : (x 7 −→ gx) the left regular representation of G. In this paper we will show that the group Hol (G) is isomorphic to the group λ (G) Aut (G). Also, we describe the public key exchange in the group λ (G) Aut (G).

Let p be a prime number. In this paper, we investigate on the p-
adic metric space over the words. More precisely, using this distance,
we define a metric spaces over the free monoids and the free groups.
After that, we study their quotient topologys and some properties.

Let Σ∗ is the free monoid over a finite alphabet Σ and H a subgroup of a given group GA group code X is the minimal generator of X∗ with X∗= Ψ− 1 (H), where Ψ is a morphism from the free monoid Σ∗ to the group G. A generating function is just a different way of writing a sequence. Generating functions transform problems about sequence into problems about functions. In this paper, we will give a several formulas for the generating functions of Xand X∗.

he object of wreath product of permutation groups is
defined the actions on cartesian product of two sets. In this paper
we consider S (Γ) and S (∆) be permutation groups on Γ and ∆
respectively, and S (Γ)∆ be the set of all maps of ∆ into the permu-
tations group S (Γ). That is S (Γ)∆ = {f : ∆ −→ S (Γ)}. S (Γ)∆
is a group with respect to the multiplication defined by for all δ in
∆ by (f1f2) (δ) = f1 (δ) f2 (δ). After that, we introduce the notion
of S (∆) actions on S (Γ)∆ : S (∆) × S (Γ)∆ −→ S (Γ)∆ , (s, f ) 7 −→
s · f = f s, where f s (δ) = (f ◦ s−1) (δ) = (f s−1) (δ) for all δ ∈ ∆.
Finaly, we give the wreath product W of S (Γ) by S (∆), and the
action of W on Γ × ∆

et F3d is the finite field of order 3d with d be a positive integer, we consider A4:=F3d[ε]=F3d[X]/(X4) is a finite quotient ring, where ε4=0. In this paper, we will show an example of encryption and decryption. Firstly, we will present the elliptic curve over this ring. In addition, we study the algorithmic properties by proposing effective implementations for representing the elements and the group law. Precisely, we give a numerical example of cryptography (encryption and decryption) by using two methods with a secret key.

Let Fq [ε] := Fq [X]/(X4 − X3) be a finite quotient ring where ε4 =
ε3, with Fq is a finite field of order q such that q is a power of a prime
number p greater than or equal to 5. In this work, we will study the elliptic
curve over Fq [ε], ε4 = ε3 of characteristic p 6 = 2, 3 given by homogeneous
Weierstrass equation of the form Y 2Z = X3 + aXZ2 + bZ3 where a and b
are parameters taken in Fq[ε]. Firstly, we study the arithmetic operation of
this ring. In addition, we define the elliptic curve Ea,b(Fq [ε]) and we will
show that Eπ0 (a),π0(b)(Fq ) and Eπ1(a),π1(b)(Fq) are two elliptic curves over
the finite field Fq, such that π0 is a canonical projection and π1 is a sum
projection of coordinate of element in Fq [ε]. Precisely, we give a classification
of elements in elliptic curve over the finite ring Fq [ε].

Let F3 d is the finite field of order 3d with d be a positive integer, we consider A4:= F3 d [ε]= F3 d [X]/(X4) is a finite quotient ring, where ε4= 0 [5]. In this paper, we will show an example of encryption and decryption. The motivation for this paper came from the observation that communications, industrial automation and many more. On the other hand, cryptography is the study of mathematical techniques related to aspects of information security [6]. Firstly, we study the elliptic curve over this ring. Furthermore, we study the algorithmic properties by proposing effective implementations for representing the elements and the group law. Finally, we give an example cryptographic (encryption and decryption) with a secret key.

The basic idea behind multivariate cryptography is to choose a system of polynomials which can be
easily inverted (central map). After that one chooses two affine invertible maps to hide the structure of the central
map. Fellows and Koblitz outlined a conceptual key cryptosystem based on the hardness of POSSO.
Let Fps be a finite field of ps elements, where p is a prime number, and s ∈ N, s ≥ 1. In this paper, we used the
act of GLn (Fps ) on the set F n
ps and the transformations group, to present the public key cryptosystems based on
the problem of solving a non-linear system of polynomial equations.

In this paper, we construct an inverse monoid M (G)
associated to a given group G by using the notion of the join of
subgroups and then, by applying the left action of monoid M on
a semigroup S, we form a semigroup SωM on the set S × M.
The finally result is to build the semi direct product of groups
associated to the group action on an another group.

A transformation semigroup is a pair (Q; S) consisting of a finite set Q, a finite semigroup S
and a semigroup action λ : Q X S Q, (q, s  s (q) which means : i) q ? Q, s, t ? S : st (q) = s
(t (q)) , and (ii) s, t ? Sq ? Q, s (q) = t (q) s = t. A state machine or a semiautomation is
an ordered triple M = (Q, ∑, F ), where Q and are finite sets and F : Q X ∑ Q is a partial
function. This paper provides the construction of state machines associate a direct product,
the cascade product, and wreath product of transformations semigroups

The asymmetric encryption methods are based on difficult problems in mathematics.
Let
be the free monoid over a finite alphabet and a binary relation on

. The pair is called a Thue system.
The congruence generated by is defined as follows:
 , whenever

and or .

, whenever
with,

The word problem for on

is then following : given two words

, do we have
? [7]
In this paper we investigate on a public key cryptosystems based on the difficult word problem in free monoid, introduced
by Wagner and Magyarik in 1985. It's well known that the word problem is undecidable in general, meaning that there is
no algorithm to solve it. We introduce some cryptosystems based on the Thue Monoid Morphism Interpresentation where
the word problem is decidable in linear time

The asymmetric encryption methods are based on difficult problems in mathematics.
For a fixed set of elements S={s₁,...,s_{n}} in group G, a word in S is any expression of the sort s_{i₁}^{k₁}s_{i₂}^{k₂}...s_{i_{n}}^{k_{n}} where the exponents k_{j} are positive or negative integers, and s_{i₁},...,s_{i_{n}}∈S.
The word problem in a group G with respect to a subset S={s₁,...,s_{n}} is the question of telling whether two words in S are equal. It is known that in general the word problem is undecidable, meaning that there is no algorithm to solve it.
In this paper, we introduce a cryptosystem based on the word problem in a group G.

For any set of symbols, denotes the set of all words of symbols over , including the empty string . The set denotes the free monoid generated by under the operation of concatenation with the empty string serving as identity. Let R be a nite set. We de ne the binary relation )R as follows, where u; v 2 : u)R v if there exist x; y 2 and (l;m) 2 R with u = xly and v = xmy. The structure ;)R is a reduction system of words and the relation )R is the reduction relation. Let ;)R be a reduction system of words. The relation )R is Noetherian if there is no in nite sequence w0;w1; ::: 2 such that for all i 0;wi)R wi+1. In this paper, we study properties of reduction systems of words and give conditions under which a reduction system of word is Noetherian.

Let M be a monoid and X a non-empty set. M will be called a transformation monoid on X if
there is a mapping  : M  X ?! X, for which we write  (m; x) = m
x and which satises the
conditions:
1) (m1m2)
x = m1
(m2
x), for each x 2 X and for each m1;m2 2 M.
2) 1M
x = x, for each x 2 X.
Let M and N be two monoids. Let NM be the set of all functions dened on M with values in N.
In this paper, we prove that the set NM forms a monoid shch that for any '; 2 NM, let ' 2 NM
in NM be dened for all m 2 M by: (' ) (m) = ' (m) (m), the monoid M is a transformation
monoid on NM in the following was:
if m 2 M; ' 2 NM, then (m
') (x) = 'm (x) = ' (xm) for x 2 M, and the set of all pairs (m; ')
where m 2 M; ' 2 NM, with multiplications operation given by: (m; ') (m0; ) = (mm0; ' m)
where m;m0 2 M and '; 2 NM is a monoid. On the other hand, we present the direct product,
the cascade product and wreath product of state machines, also we calculate the monoids of state
machines.
Keywords: Free Monoid; Monoid of State Machine; Morphism of Monoids; State Machine; Trans-
formation Monoid; Wreath Product of Monoids

Le présent polycopié reprend un cours de premiére année Master, spécialité Algèbre et
Mathématiques Discrètes, donné à l’Université de Mohamed Boudiaf-M’sila pendant les an-
nées 2016-2018. Le but de ce cours était de présenter aux étudiants les notions de base
concernant les semigroupes, les automates …nis et les grammaires algébriques. Nous sup-
posons que le lecteur a une bonne connaissance de les premiers principes de la théorie des
ensembles.
Ce travail se situe dans le cadre de la théorie des semigroupes, automates …nis et des
langages formels. La théorie des langages formels est née d’une tentative de modélisation
des langues naturelles.
Historiquement, les deux mécanismes très connus pour dé…nir un langage de mots …nis
d’une manière formelle sont principalement les suivants :
(1) Un mécanisme qui consiste à donner un processus de genération des mots, qui conduit
à la notion de grammaire.
(2) Un deuxième mécanisme de reconnaissance qui est réalisé à l’aide d’automate.
Ce travail est composé de cinq chapitres.
Le premier chapitre consiste en un rappel des notions et notations utilisées par la suite :
relations binaires et leurs propriétés, monoïdes, mots et langages, homomorphismes des
monoïdes.
Dans le second chapitre, on fait une étude sur les semi-systèmes de réécriture ainsi que
certaines de leurs propriétés telles que : la terminaison et la con‡uence.
Dans le troisième chapitre, on donne les notions et les propriétés de base des automates
…nis.
Nous aborderons et traiterons, dans le quatrième chapitre la notion de grammaire al-
gébrique.
Le chapitre cinque sera consacré au fonctions primitives récursives, complexité d’un
algorithme et l’indécidabilité.
Nous avons d’ailleurs inclus un nombre considérable d’exemples. Les chapitres de ce
polycopié ce terminent par des exercices non corrigés.

In this work, we are interested in decomposition of group. Let G be a group, and let N be a normal subgroup of G, we shall show how multiplication in G can be viewed as a two-step process consisting of multiplication in the quotient G/N followed by multiplication in N.
The object of wreath product of permutation groups is defined the actions on cartesian product of two sets. In this paper we consider S(Γ) and S(Δ) be permutation groups on Γ and Δ respectively, and S(Γ)^{Δ} be the set of all maps of Δ into the permutations group S(Γ). That is S(Γ)^{Δ}={f:Δ→S(Γ)}. S(Γ)^{Δ} is a group with respect to the multiplication defined by for all δ in Δ by (f₁f₂)(δ)=f₁(δ)f₂(δ). After that, we introduce the notion of S(Δ) actions on S(Γ)^{Δ} :
S(Δ)×S(Γ)^{Δ}→S(Γ)^{Δ},(s,f)↦s⋅f=f^{s}, where
f^{s}(δ)=(f∘s⁻¹)(δ)=(fs⁻¹)(δ) for all δ∈Δ. Finaly, we give the wreath product W of S(Γ) by S(Δ), and the action of W on Γ×Δ.

The asymmetric encryption methods based on difficult problems in mathematics. Wagner and Magyarik outlined a conceptual key cryptosystem based on the hardness of the word problem for finitely presented monoids. In this paper, we give a condition on the relation of a rewrite system to show that the congruence generated by this relation is included in the syntactic congruence class of any word modulo congruence associated morphism of monoids. Also we use this included to present the public-key cryptosystems based on Thue Monoid Morphism Interpretation (TMMI).

Let be an alphabet. A subset of the free monoid is a code over if for all and, the condition: implies and for. In other words, a set is a code if any word in can be written uniquely as a product of words in ([BP84]). It is not always easy to verify a given set of words is a code. In this paper, we give the construction and representation by deterministic finite automata of some variable length codes.

Notre recherche dans cette thËse se situe dans le cadre de semi-systËmes de rÈÈcriture dit
aussi semi-systËme de Thue et le problËme du mot dans un monoÔde. Un semi-systËme de
rÈÈcriture est un couple (; R) o˘  est un alphabet et R est un ensemble Öni de couples de
mots sur , i.e, R  

o˘ 

est le monoÔde libre engendrÈ par  muni de líopÈration
la concatÈnation des mots.
LíÈtude des propriÈtÈs des semi-systËmes de rÈÈcriture forme un domaine trËs important
depuis de nombreuses annÈes. Parmi les propriÈtÈs les plus ÈtudiÈes et les plus importantes
des semi-systËmes de rÈÈcriture se trouvent la terminaison qui assure líexistence díun rÈsultat
‡ un calcul et la conáuence qui nous permet de garantir líunicitÈ de ce rÈsultat.
Dans ce travail on donne des critËres pour assurer la propriÈtÈ de terminaison dans les deux
cas suivants:
Dans le premier cas, on utilise un morphisme non contractant entre le semi-systËme (; R)
en question et un autre semi-systËme possÈdant dÈj‡ cette propriÈtÈ. Dans le second cas,
on utilise une fonction poids entre le semi-systËme (; R) et un ensemble muni díun ordre
bien fondÈ.
Soit (; R) un semi-systËme de rÈÈcriture. La congruence ()
R
engendrÈe par R est dÈÖnie
par:
 w()
R
w
0
, síil existe x; y de 

et (r; s) 2 (R [ R1
) tels que w = xry et w
0 = xsy,
 w
()
R
w
0
, síil existe une suite Önie de mots u0; u1; :::; un de 
avec,
u0 = w; ui()
R
ui+1; 80  i  n 1 et un = w
0
.
Une prÈsentation (par gÈnÈrateurs et relations) díun monoÔde M est la donnÈe díun
alphabet  et díune relation binaire R sur 

tels que M soit isomorphe au quotient de 

par la congruence notÈe ()
R
engendrÈ par R, i.e, M = 
=
()
R
.
Etants donnÈes deux semi-systËmes de rÈecriture (1; R1) et (2; R2). Nous avons dÈterminÈ quelques conditions sur les relations R1 et R2 qui permettent díassurer líexistence díun
morphisme entre les monoÔdes 

1
=
()
R1
et 

2
=
()
R2
pour assurer le passage entre les deux
monoÔdes quotients. Díautre part, on donne une relation spÈciÖque R sur 
qui fait du
monoÔde quotient 
=
()
R
un groupe.
Le problËme du mot dans un monoÔde libre quíon peut formuler comme suit : Etant
donnÈs le semi-systËme de rÈÈcriture (; R) et les deux mots w; w0 de 

, dÈterminer si
on peut dÈriver w
0 ‡ partir de w en utilisant la congruence engendrÈ par R, cíest-‡-dire
w
()
R
w
0
. Ce problËme est connu quíil est en gÈnÈral indÈcidable.
EnÖn, on síintÈresse au protocole ATS-monoÔde , líidÈe de ce protocole est de transformer
un semi-systËme de Thue (; R) pour lequel le problËme du mot est indÈcidable en un semisystËme de Thue (
; R) o˘  

pour lequel le problËme du mot est dÈcidable en
temps linÈaire. Plus prÈcisÈment, on donne des attaques contre ATS-monoÔde dans des cas
spÈciÖques et quelques exemples sur ces cas.
MOTS CLES : MonoÔde libre, semi-systËmes de rÈÈcriture de mots (semi-systËme de
Thue), morphisme de monoÔdes, la fermeture díune relation binaire, ordre bien fondÈ, problËme du mot dans un monoÔde, cryptographie ‡ clÈ publique, les bases de GrÙbner.

Let A be the free monoid over a Önite alphabet A and R a
binary relation on A. The congruence generated by R is deÖned as follows:
 xuy $R
xvy, whenever x; y 2 A and uRv or vRu
 w
$R
w
0
, whenever u0; u1; :::; un 2 A with,u0 = w; ui $R
ui+1; 80  i 
n 1; un = w0
.
A presentation (by generators and relations) of a monoid M is a pair
S = (A; R) such that M is isomorphic to the quotient of A by the congruence
noted $R
generated by R , i.e, M = A=
$R
. We consider two systems of
rewriting S1 = (A1; R1) and S2 = (A2; R2). The purpose of this study is
to determine some conditions on the relations R1 and R2 that ensure the
existence of a morphism between the quotient monoids A
1
=
$R1
and A
2
=
$R2
.
We give also a speciÖc relation R on A making the quotient monoid A=
$R
a group.

Let be a deterministic finite automata, the purpose of this study is to determine some conditions on the transition function of that ensure the existence of some properties. We give also a specific equivalence relation on set.

In this work, we are interested in ATS-monoid protocol (proposed by PJ Abisha, DG Thomas G. and K. Subramanian, the idea of this protocol is to transform a system of Thue S1=(Σ, R) for which the word problem is undecidable a system of Thue S2=(∆, Rθ) or θ⊆∆×∆ for which the word problem is decidable in linear time. Specifically, it gives attacks against ATS monoid in spésifiques case and thenme examples of these cases.

Based on some result given in ? , concerning the termination of a semi-Thue systeme, we give some results illustrated by some examples to give some Noetherian semi-Thue systems.

Let Σ∗ be the free monoid over a finite alphabet Σ and H a subgroup of a given group G. A group code X is the minimal generator of X∗ with X∗= Ψ− 1 (H), where Ψ is a morphism from the free monoid Σ∗ to the group G. In general, it is not obvious to detect if a subset X of Σ∗ is a code or not. In this paper, we use the fact that the syntactic monoid M (X∗) of X∗ is isomorphic to the transition monoid of the minimal automaton recognizing X∗, to giving some examples of groups codes based on the following two results from [1]: 1) The subset X of Σ∗ is a group code if and only if the monoid M (X∗) is a group. 2) Let X⊆ Σ∗ be a finite code, the syntactic monoid M (X∗) is a group if and only if X= Σn for some a positif integer n. And in this case, the group M (X∗) is a cyclic group of order n.

Dans ce travail, on s'intéresse au protocole ATS-monoïde (proposé par P. J. Abisha, D. G. Thomas et K. G. Subramanian), l'idée de ce protocole est de transformer un système de Thue S₁=<Σ,T> pour lequel le problème du mot est indécidable en un système de Thue S₂=<Δ,T_{θ}> où θ⊆Δ×Δ pour lequel le problème du mot est décidable en temps linéaire. Plus précisément, on donne des attaques contre ATS-monoïde dans des cas spésifiques et quelques exemples sur ces cas
Mots clés: Monoïde libre, Système de Thue, morphisme de monoïdes, La fermeture d'une relation binaire, Problème du mot dans un monoïde, Cryptographie à clé publique.
MSC(2010): 94A60, 68Q42, 20M05.

Une présentation (par générateurs et relations) d'un monoïde M est la donnée d'un alphabet Σ et d'une relation binaire ℜ sur Σ^{∗} tels que M soit isomorphe au quotient de Σ^{∗} par la congruence notée ↔ engendré par ℜ, i.e, M≅Σ^{∗}/↔.
Etants données deux systèmes de réecriture S₁=<Σ₁,ℜ₁> et S₂=<Σ₂,ℜ₂>. L'objet de cette étude est de déterminer quelques conditions sur les relations ℜ₁ et ℜ₂ qui permettent d'assurer l'existence d'un morphisme entre les monoïdes quotient Σ₁^{∗}/↔ et Σ₂^{∗}/↔. D'autre part, on donne une relation spécifique ℜ sur Σ^{∗} qui fait du monoïde quotient Σ^{∗}/↔ un groupe.

Let Σ be an alphabet. A subset X of the free monoid Σ^{∗} is a code over Σ if for all m,n≥1 and x₁,...,x_{n},y₁,...,y_{m}∈X, the condition:

x₁x₂...x_{n}=y₁y₂...y_{m} implies n=m and x_{i}=y_{i} for i=1,...,n.
In other words, a set X is a code if any word in X⁺ can be written uniquely as a product of words in X [1]. It is not always easy to verify a given set of words is a code. For this purpose, it is shown [1,6], Let G be a group and H a subgroup of G. Let ψ:Σ^{∗}→G be a surjective morphism, ψ⁻¹(H) it is generated by a biprefix code called a group code. The remainder of this paper is organized as follows. In section 2, some mathematical preliminaries.In section 3, we use the fact that the syntactic monoid M(X^{∗}) of X^{∗} is isomorphic to the transition monoid of the minimal automaton recognizing X^{∗}, to giving some examples of groups codes and we show that the submonoid X^{∗} generated by the group code X is a complete submonoid of the free monoid Σ^{∗}. Finally, we draw our conclusions in section 4.