# Entropoid Based Cryptography

Danilo Gligoroski Department of Information Security and Communication
Technologies, Norwegian University of Science and Technology - NTNU

###### Abstract

The algebraic structures that are non-commutative and non-associative known as
entropic groupoids that satisfy the _"Palintropic"_ property i.e.,
$x^{\mathbf{A}\mathbf{B}}=(x^{\mathbf{A}})^{\mathbf{B}}=(x^{\mathbf{B}})^{\mathbf{A}}=x^{\mathbf{B}\mathbf{A}}$
were proposed by Etherington in ’40s from the 20th century. Those relations
are exactly the Diffie-Hellman key exchange protocol relations used with
groups. The arithmetic for non-associative power indices known as
Logarithmetic was also proposed by Etherington and later developed by others
in the 50s-70s. However, as far as we know, no one has ever proposed a
succinct notation for exponentially large non-associative power indices that
will have the property of fast exponentiation similarly as the fast
exponentiation is achieved with ordinary arithmetic via the consecutive rising
to the powers of two.

In this paper, we define ringoid algebraic structures $(G,\boxplus,*)$ where
$(G,\boxplus)$ is an Abelian group and $(G,*)$ is a non-commutative and non-
associative groupoid with an entropic and palintropic subgroupoid which is a
quasigroup, and we name those structures as Entropoids. We further define
succinct notation for non-associative bracketing patterns and propose
algorithms for fast exponentiation with those patterns.

Next, by an analogy with the developed cryptographic theory of discrete
logarithm problems, we define several hard problems in Entropoid based
cryptography, such as Discrete Entropoid Logarithm Problem (DELP),
Computational Entropoid Diffie-Hellman problem (CEDHP), and Decisional
Entropoid Diffie-Hellman Problem (DEDHP). We post a conjecture that DEDHP is
hard in Sylow $q$-subquasigroups. Next, we instantiate an entropoid Diffie-
Hellman key exchange protocol. Due to the non-commutativity and non-
associativity, the entropoid based cryptographic primitives are supposed to be
resistant to quantum algorithms. At the same time, due to the proposed
succinct notation for the power indices, the communication overhead in the
entropoid based Diffie-Hellman key exchange is very low: for 128 bits of
security, 64 bytes in total are communicated in both directions, and for 256
bits of security, 128 bytes in total are communicated in both directions.

Our final contribution is in proposing two entropoid based digital signature
schemes. The schemes are constructed with the Fiat-Shamir transformation of an
identification scheme which security relies on a new hardness assumption:
computing roots in finite entropoids is hard. If this assumption withstands
the time’s test, the first proposed signature scheme has excellent properties:
for the classical security levels between 128 and 256 bits, the public and
private key sizes are between 32 and 64, and the signature sizes are between
64 and 128 bytes. The second signature scheme reduces the finding of the roots
in finite entropoids to computing discrete entropoid logarithms. In our
opinion, this is a safer but more conservative design, and it pays the price
in doubling the key sizes and the signature sizes.

We give a proof-of-concept implementation in SageMath 9.2 for all proposed
algorithms and schemes in an appendix.

Keywords: Post-quantum cryptography, Discrete Logarithm Problem, Diffie-
Hellman key exchange, entropic, Entropoid, Entropoid Based Cryptography

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contribution
  2. 2 Mathematical Foundations for Entropoid Based Cryptography
    1. 2.1 General definition of Logarithmetic
    2. 2.2 Entropic Groupoids Over $(\mathbb{F}_{p})^{L}$
    3. 2.3 Succinct Notation for Exponentially Large Bracketing Shapes
    4. 2.4 Dichotomy between odd and even bases
  3. 3 Hard Problems in Entropoid Based Cryptography
    1. 3.1 DELP is secure against Shor’s quantum algorithm for DLP
  4. 4 Concrete instances of Entropoid Based Key Exchange and Digital Signature Algorithms
    1. 4.1 Choosing Parameters For a Key Exchange Algorithm Based on DELP
    2. 4.2 Digital Signature Scheme Based on CDERP
      1. 4.3 Digital Signature Scheme Based on reducing CDERP to DELP for Specific Roots $\mathbf{B}$
      2. 5 Conclusions
      3. A Examples for $\mathbb{E}_{{11}^{2}}$, $\mathbb{E}_{{13}^{2}}$, $\mathbb{E}_{{19}^{2}}$ and $\mathbb{E}_{{23}^{2}}$
        1. B Observation for the dichotomy between even and odd bases
          1. C Proof-of-concept SageMath Jupyter implementation of the algorithms given in "Entropoid Based Cryptography"

##  1 Introduction

The arithmetic of non-associative indices (shapes or patterns of bracketing
with a binary operation $*$) has been defined as _"Logarithmetic"_ by
Etherington in the ’40s of the 20th century. One of the most interesting
properties that have been overlooked by modern cryptography is the Discrete
Logarithm problem and the Diffie-Hellman key exchange protocol in the non-
commutative and non-associative logarithmetic of power indices. In light of
the latest developments in quantum computing, Shor’s quantum algorithm that
can solve DL problem in polynomial time if the underlying algebraic structures
are commutative groups, and the post-quantum cryptography, it seems that there
is an opening for a _rediscovery_ of Logarithmetic and its applications in
Cryptography.

Etherington himself, as well as other authors later ([1], [2]), noticed that
the notation of shapes introduced in [3] quickly gets complicated (and from
our point of view for using them for cryptographic purposes, incapable of
handling exponentially large indices).

Inspired by the work of Etherington, in a series of works in ’50s, ’60s and
’70s of the last century, many authors such as Robinson [4], Popova [5], Evans
[6], Minc [7], Bollman [8], Harding [1], Dacey [2], Bunder [9], Trappmann
[10], developed axiomatic number systems for non-associative algebras which in
many aspects resemble the axiomatics of ordinary number theory. While the
results from that development are quite impressive such as the fundamental
theorem of non-associative arithmetic (prime factorization of indices [6]), or
the analogue of the last Fermat Theorem [5, 6, 7], the construction of the
shapes was essentially sequential. In cryptography, we need to operate with
power indices of exponential sizes. Thus, we have to define shapes over non-
associative and non-commutative groupoids that allow fast exponentiation,
similarly as it is done with the consecutive rising to the powers of two in
the standard modular arithmetic, while keeping the variety of possible
outcomes of the calculations, as the flagship aspect of the non-commutative
and non-associative structures.

###  1.1 Our Contribution

We first define a general class of groupoids $(G,*)$ (sets $G$ with a binary
operation $*$) over direct products of finite fields with prime
characteristics $(\mathbb{F}_{p})^{L}$ that are _"Entropic"_ (for every four
elements $x,y,z$ and $w$, if $x*y=z*w$ then $x*z=y*w$). Then, for $L=2$ we
find instances of those operations $*$ that are nonlinear in
$(\mathbb{F}_{p})^{2}$, non-commutative and non-associative. In order to
compute the powers $x^{a}$ where $a\in\mathbb{Z}^{+}$, of elements $x\in G$,
due to the non-associativity, we need to know some exact bracketing shape
$a_{s}$, and we denote the power indices as pairs $\mathbf{A}=(a,a_{s})$.
Etherington defined the Logarithmetic of indices $\mathbf{A}$, $\mathbf{B}$,
by defining their addition $\mathbf{A}+\mathbf{B}$ and multiplication
$\mathbf{A}\mathbf{B}$ as
$x^{\mathbf{A}+\mathbf{B}}=x^{\mathbf{A}}*x^{\mathbf{B}}$ and
$x^{\mathbf{A}\mathbf{B}}=(x^{\mathbf{A}})^{\mathbf{B}}$. He further showed
that the power indices of entropic groupoids, satisfy the _"Palintropic"_
property i.e.,
$x^{\mathbf{A}\mathbf{B}}=(x^{\mathbf{A}})^{\mathbf{B}}=(x^{\mathbf{B}})^{\mathbf{A}}=x^{\mathbf{B}\mathbf{A}}$
which is the exact form of the Diffie-Hellman key exchange protocol.

We further analyze the chosen instances of entropic groupoids for how to find
left unit elements, how to compute the multiplicative inverses, how to define
addition in those groupoids, and how to find generators $g\in G$ that generate
subgroupoids with a maximal size of $(p-1)^{2}$ elements. We show that these
maximal multiplicative subgroupoids are quasigroups. We also define Sylow
$q$-subquasigroups. Having all this, we define several hard problems such as
Discrete Entropoid Logarithm Problem (DELP), Computational Entropoid Diffie-
Hellman problem (CEDHP), and Decisional Entropoid Diffie-Hellman Problem
(DEDHP). We post a conjecture that DEDHP is hard in Sylow $q$-subquasigroups.
Next, we propose a new hard problem specific for the Entropoid algebraic
structures: Computational Discrete Entropoid Root Problem (CDERP).

We propose instances of Diffie-Hellman key exchange protocol in those
entropic, non-abelian and non-associative groupoids. Due to the hidden nature
of the bracketing pattern of the power index (if chosen randomly from an
exponentially large set of possible patterns), it seems that the current
quantum algorithms for finding the discrete logarithms, but also all classical
algorithms for solving DLP (such as Pollard’s rho and kangaroo, Pohlig-
Hellman, Baby-step giant-step, and others) are not suitable to address the
CLDLP.

Based on CDERP, we define two post-quantum signature schemes.

Our notation for power indices that we introduce in this paper differs from
the notation that Etherington used in [3], and is adapted for our purposes to
define operations of rising to the powers that have exponentially (suitable
for cryptographic purposes) big values. However, for the reader’s convenience
we offer here a comparison of the corresponding notations: the shape $s$ in
[3] means a power index $\mathbf{A}=(a,a_{s})$ here; degree $\delta(s)$ in [3]
means $a$ here; the notations of altitude $\alpha(s)$ and mutability $\mu(s)$
in [3] do not have a direct interpretation in the notation of
$\mathbf{A}=(a,a_{s})$ but are implicitly related to $a_{s}$.

##  2 Mathematical Foundations for Entropoid Based Cryptography

###  2.1 General definition of Logarithmetic

######  Definition 1.

A groupoid $(G,*)$ is an algebraic structure with a set $G$ and a binary
operation $*$ defined uniquely for all pairs of elements $x$ and $y$ i.e.,

$\forall x,y\in G,\ \ \ \exists!\ (x*y)\in G.$ (1)

The following definitions are taken and adapted for our purposes, from [3],
[11], [12] and [13].

######  Definition 2.

We say the binary operation $*$ of the groupoid $(G,*)$ is entropic, if for
every four elements $x,y,z,w\in G$, the following relation holds:

$\text{If}\ \ \ x*y=z*w\ \ \ \text{then}\ \ \ x*z=y*w.$ (2)

######  Definition 3.

Let $x\in G$ is an element in the groupoid $(G,*)$ and let $a\in\mathbb{N}$ is
a natural number. A bracketing shape (pattern) for multiplying $x$ by itself,
$a$ times is denoted by $a_{s}$ i.e.

$a_{s}\colon\underbrace{(x*\ldots(x*x)\ldots)}_{a\text{\ copies of }x}.$ (3)

The pair $\mathbf{A}=(a,a_{s})$ is called a power index.

Let us denote by $S_{a}$ the set of all possible bracketing shapes $a_{s}$
that use $a$ instances of an element $x$ i.e.

$S_{a}(x)=\\{a_{s}\ |\ a_{s}\text{\ is a bracketing shape with}\ a\text{
instances of an element}\ x\\}.$ (4)

######  Proposition 1.

If $\mathbf{A}=(a,a_{s})$ is a power index, then

$|S_{a}(x)|=C_{a-1}=\frac{1}{a}\binom{2a-2}{a-1},$ (5)

where $C_{a-1}$ is the $(a-1)$-th Catalan number [14, Sequence A000108]. ∎

Two of those bracketing shapes are characteristic since they can be described
with an iterative sequential process starting with $x*x$ absorbing the factors
$x$ one at a time either in the direction from left to right or from right to
left (in [3] shapes that absorb the terms one at a time are called primary
shapes).

######  Definition 4.

We say that the power index $\mathbf{A}=(a,a_{s})$ has a primary left-to-right
bracketing shape if

$a_{s}\colon\underbrace{((\ldots((x*^{\leavevmode\hbox to4.67pt{\vbox
to4.67pt{\pgfpicture\makeatletter\hbox{\hskip 2.33311pt\lower-2.33311pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}x)*x)\ldots)*^{\leavevmode\hbox
to4.67pt{\vbox to4.67pt{\pgfpicture\makeatletter\hbox{\hskip
2.33311pt\lower-2.33311pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}x)}_{a\text{\ copies
of }x}.\leavevmode\hbox to4.35pt{\vbox
to13.01pt{\pgfpicture\makeatletter\hbox{\hskip 2.17625pt\lower-1.59998pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {
{}{}{}{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}{}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ {}{}{}{}{}}{}{ {}{}{}{}{}}{
{}{}{}{}{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{{}{}} {}{}}{}{}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{{}{}} {}{}}{}{}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}{}{{
{\pgfsys@beginscope{} {} {} {}
\pgfsys@moveto{1.99997pt}{0.0pt}\pgfsys@lineto{-1.19998pt}{1.59998pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@lineto{-1.19998pt}{-1.59998pt}\pgfsys@fill\pgfsys@endscope}}
}{}{}{{}}{}{}{{}}\pgfsys@moveto{-0.69458pt}{-3.93927pt}\pgfsys@curveto{1.97626pt}{11.2083pt}{-1.97626pt}{11.2083pt}{0.34729pt}{-1.96965pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.17365}{-0.98482}{0.98482}{0.17365}{0.34727pt}{-1.96965pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ (6)

We shortly write it as: $\mathbf{A}\equiv x_{(a-1,x)\texttt{to-right}}$,
denoting that it starts with $x$ and applies $a-1$ right multiplications by
$x$. For some generic and unspecified bracketing shape $s$ the notation

$s_{(k,x)\texttt{to-right}}$

denotes a sequential extension of $s$ by $k$ right multiplications by $x$.
This includes the formal notation $s\equiv s_{(0,x)\texttt{to-right}}$ which
means the shape $s$ itself extended with zero right multiplications by $x$.

We say that the power index $\mathbf{A}=(a,a_{s})$ has a primary right-to-left
bracketing shape if

$a_{s}\colon\underbrace{(x*^{\leavevmode\hbox to4.67pt{\vbox
to4.67pt{\pgfpicture\makeatletter\hbox{\hskip 2.33311pt\lower-2.33311pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}(\ldots(x*(x*^{\leavevmode\hbox
to4.67pt{\vbox to4.67pt{\pgfpicture\makeatletter\hbox{\hskip
2.33311pt\lower-2.33311pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}x)\ldots))}_{a\text{\
copies of }x}.\leavevmode\hbox to4.35pt{\vbox
to11.61pt{\pgfpicture\makeatletter\hbox{\hskip 2.17625pt\lower-11.4083pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {
{}{}{}{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}{}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ } { {}{}{}{}{}}{}{
{}{}{}{}{}}{ {}{}{}{}{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{{}{}} {}{}}{}{}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{{}{}} {}{}}{}{}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}}
{}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{}{{}}\pgfsys@moveto{-0.69458pt}{3.93927pt}\pgfsys@curveto{1.97626pt}{-11.2083pt}{-1.97626pt}{-11.2083pt}{0.34729pt}{1.96965pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.17365}{0.98482}{-0.98482}{0.17365}{0.34727pt}{1.96965pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ (7)

We shortly write it as: $\mathbf{A}\equiv x_{(x,a-1)\texttt{to-left}}$,
denoting that it starts with $x$ and applies $a-1$ left multiplications by
$x$. For some generic and unspecified bracketing shape $s$ the notation

$s_{(x,k)\texttt{to-left}}$

denotes a sequential extension of $s$ by $k$ left multiplications by $x$. This
includes the formal notation $s\equiv s_{(x,0)\texttt{to-right}}$ which means
the shape $s$ itself extended with zero left multiplications by $x$.

######  Definition 5.

Every power index $\mathbf{A}=(a,a_{s})$ can be considered as an endomorphism
on $G$ (a mapping of $G$ to itself)

$\mathbf{A}\colon x\rightarrow x^{\mathbf{A}}.$ (8)

If $\mathbf{A}=(a,a_{s})$ and $\mathbf{B}=(b,b_{s})$ are two mappings, we
define their sum $\mathbf{A}\mathbf{+}\mathbf{B}$ as the power index of the
product of two powers i.e.:

$x^{\mathbf{A}\mathbf{+}\mathbf{B}}=x^{\mathbf{A}}*x^{\mathbf{B}},$ (9)

and we define their product $\mathbf{A}\mathbf{\times}\mathbf{B}$ (or shortly
$\mathbf{A}\mathbf{B}$) as the power index of an expression obtained by
replacing every factor in the expression of the shape $b_{s}$ by a complete
shape $a_{s}$ i.e.:

$x^{\mathbf{A}\mathbf{B}}=(x^{\mathbf{A}})^{\mathbf{B}}.$ (10)

######  Definition 6.

If the sum of any two endomorphisms of $G$ is also and endomorphism of $G$, we
say that $G$ has additive endomorphisms.

######  Definition 7.

Let $(G,*)$ be a given groupoid. Two power indices $\mathbf{A}=(a,a_{s})$ and
$\mathbf{B}=(b,b_{s})$ are equal if and only if
$x^{\mathbf{A}}=x^{\mathbf{B}}$ for all $x\in G$.

######  Definition 8.

The Logarithmetic $(L(G),\mathbf{+},\mathbf{\times})$ is the algebra over the
equated indices from Definition 7 with operations $\mathbf{+}$ and
$\mathbf{\times}$ as defined in Definition 5.

######  Definition 9.

If $x^{\mathbf{A}\mathbf{B}}=x^{\mathbf{B}\mathbf{A}}$ for all $x\in G$ and
for all power indices $\mathbf{A}$ and $\mathbf{B}$, we say that the groupoid
$(G,*)$ is palintropic.

######  Theorem 1 (Etherington, [12]).

If the groupoid $(G,*)$ has additive endomorphisms, then (i) power indices are
endomorphisms of $G$, (ii) $G$ is palintropic. ∎

######  Theorem 2 (Murdoch [15], Etherington, [12]).

If the groupoid $(G,*)$ is entropic, then for every $x,y\in G$

$(x*y)^{\mathbf{A}}=x^{\mathbf{A}}*y^{\mathbf{A}},$ (11)

and

$x^{\mathbf{A}\mathbf{B}}=(x^{\mathbf{A}})^{\mathbf{B}}=(x^{\mathbf{B}})^{\mathbf{A}}=x^{\mathbf{B}\mathbf{A}}.$
(12)

∎

######  Definition 10.

We say that $g\in G$ is the generator of the groupoid $(G,*)$ if

$\forall x\in G,\ \ \ \exists\mathbf{A},\ \ \text{such that}\ \ \
x=g^{\mathbf{A}}.$ (13)

In that case we write

$\langle g\rangle=G.$ (14)

Note: In the following subsection and the rest of the paper, we will overload
the operators $+$ and $\times$ for addition and multiplication of power
indices defined in the previous definitions, with the same operators for the
operations of addition and multiplication in the finite field
$\mathbb{F}_{p}$. However, there will be no confusion since the operations act
over different domains.

###  2.2 Entropic Groupoids Over $(\mathbb{F}_{p})^{L}$

Let a set $G$ is a direct product of $L$ instances of the finite field
$\mathbb{F}_{p}$ with $p$ elements, where $p$ is a prime number i.e.,

$G=\underbrace{\mathbb{F}_{p}\times\ldots\mathbb{F}_{p}}_{L}.$ (15)

Let $G=(\mathbb{F}_{p})^{L}$ for $L\geq 2$, and let us represent elements
$x,y,z,w\in G$ as symbolic tuples $x=(x_{1},\ldots x_{L})$, $y=(y_{1},\ldots
y_{L})$, $z=(z_{1},\ldots z_{L})$ and $w=(w_{1},\ldots w_{L})$.

######  Definition 11 (Design criteria).

The binary operation $*$ over $G$ should meet the following:

  1. Design criterium 1:

Entropic. The operation $*$ should be entropic as defined in (2).

  2. Design criterium 2:

Nonlinear. The operation $*$ should be nonlinear with the respect of the
addition and multiplication operations in the finite field $\mathbb{F}_{p}$.

  3. Design criterium 3:

Non-commutative. The operation $*$ should be non-commutative.

  4. Design criterium 4:

Non-associative. The operation $*$ should be non-associative.

One simple way to find an operation that satisfies the design criteria from
Definition 11 would be to define it for $L=2$ for the most general quadratic
$2L$-variate polynomials as follows:

$\displaystyle x*y=(x_{1},x_{2})*(y_{1},y_{2})=$
$\displaystyle(P_{1}(x_{1},x_{2},y_{1},y_{2}),P_{2}(x_{1},x_{2},y_{1},y_{2})),$
(16) $\displaystyle P_{1}(x_{1},x_{2},y_{1},y_{2})=$ $\displaystyle
a_{1}+a_{2}x_{1}+a_{3}x_{2}+a_{4}y_{1}+a_{5}y_{2}+a_{6}x_{1}y_{1}+a_{7}x_{1}y_{2}+a_{8}x_{2}y_{1}+$
$\displaystyle+a_{9}x_{2}y_{2}+a_{10}x_{1}^{2}+a_{11}x_{1}x_{2}+a_{12}x_{2}^{2}+a_{13}y_{1}^{2}+a_{14}y_{1}y_{2}+a_{15}y_{2}^{2},$
(17) $\displaystyle P_{2}(x_{1},x_{2},y_{1},y_{2})=$ $\displaystyle
b_{1}+b_{2}x_{1}+b_{3}x_{2}+b_{4}y_{1}+b_{5}y_{2}+b_{6}x_{1}y_{1}+b_{7}x_{1}y_{2}+b_{8}x_{2}y_{1}+$
$\displaystyle+b_{9}x_{2}y_{2}+b_{10}x_{1}^{2}+b_{11}x_{1}x_{2}+b_{12}x_{2}^{2}+b_{13}y_{1}^{2}+b_{14}y_{1}y_{2}+b_{15}y_{2}^{2},$
(18)

where 30 variables $a_{1},\ldots,a_{15}$ and $b_{1},\ldots,b_{15}$ are from
$\mathbb{F}_{p}$, and their relations are to be determined such that (2)
holds. It turns out that searching for those relations with 30 symbolic
variables is not a trivial task for the modern computer algebra systems such
as Sage [16] and Mathematica [17]. There are many ways how to simplify further
the $2L$-variate polynomials (2.2) and (2.2) by removing some of their
monomials. We present one such a simplification approach by defining the
operation $*$ as follows:

$\displaystyle x*y=(x_{1},x_{2})*(y_{1},y_{2})=$
$\displaystyle(P_{1}(x_{1},x_{2},y_{1},y_{2}),P_{2}(x_{1},x_{2},y_{1},y_{2})),$
(19) $\displaystyle P_{1}(x_{1},x_{2},y_{1},y_{2})=$ $\displaystyle
a_{1}+a_{2}x_{1}+a_{3}x_{2}+a_{4}y_{1}+a_{6}x_{1}y_{1}+a_{8}x_{2}y_{1},$ (20)
$\displaystyle P_{2}(x_{1},x_{2},y_{1},y_{2})=$ $\displaystyle
b_{1}+b_{2}x_{1}+b_{3}x_{2}+b_{5}y_{2}+b_{7}x_{1}y_{2}+b_{9}x_{2}y_{2}.$ (21)

######  Open Problem 1.

Define a generic and systematic approach for finding solutions that will
satisfy the design criteria of Definition 11 for higher dimensions ($L>2$) and
higher nonlinearity (the degree of the polynomials to be higher than 2).

For the simplified system (19) - (21) one solution that satisfies all design
criteria from Definition 11 is the following:

######  Definition 12.

Let $x=(x_{1},x_{2}),y=(y_{1},y_{2})$ be two elements of the set
$G=\mathbb{F}_{p}\times\mathbb{F}_{p}$. The operation $*$, i.e. $x*y$ is
defined as:

$(x_{1},x_{2})*(y_{1},y_{2})=\left(\frac{{a_{3}}({a_{8}}{b_{2}}-{b_{7}})}{{a_{8}}{b_{7}}}+{a_{3}}{x_{2}}+\frac{{a_{8}}{b_{2}}{y_{1}}}{{b_{7}}}+{a_{8}}{x_{2}}{y_{1}},-\frac{{b_{2}}({a_{8}}-{a_{3}}{b_{7}})}{{a_{8}}{b_{7}}}+\frac{{a_{3}}{b_{7}}{y_{2}}}{{a_{8}}}+{b_{2}}{x_{1}}+{b_{7}}{x_{1}}{y_{2}}\right),$
(22)

where $a_{3},a_{8},b_{2},b_{7}\in\mathbb{F}_{p}$, $a_{8}\neq 0$ and $b_{7}\neq
0$, and the operations $-$ and $/$ are the operations of subtraction and
division in $\mathbb{F}_{p}$.

######  Open Problem 2.

Find efficient operations $*$ that satisfy the design criteria of Definition
11 and have as little as possible operations of addition, subtraction,
multiplication and division in $\mathbb{F}_{p}$.

The next Corollary can be easily proven by simple expression replacements.

######  Corollary 1.

Let $G=(\mathbb{F}_{p})^{2}$, and let the operation $*$ is defined with
Definition 12. Then:

  1. 1.

The groupoid $(G,*)$ is entropic groupoid i.e., for every $x,y,z,w\in G$ if
$x*y=z*w$ then $x*z=y*w.$

  2. 2.

The element
$\mathbf{0}_{*}=\left(-\frac{a_{3}}{a_{8}},-\frac{b_{2}}{b_{7}}\right)$ is the
multiplicative zero for the groupoid $(G,*)$, i.e.

$\forall x\in G,\ \ \ x*\mathbf{0}_{*}=\mathbf{0}_{*}*x=\mathbf{0}_{*}\ \ .$
(23)

  3. 3.

The element
$\mathbf{1}_{*}=\left(\frac{1}{b_{7}}-\frac{a_{3}}{a_{8}},\frac{1}{a_{8}}-\frac{b_{2}}{b_{7}}\right)$
is the multiplicative left unit for the groupoid $(G,*)$, i.e.

$\forall x\in G,\ \ \ \mathbf{1}_{*}*x=x\ \ .$ (24)

  4. 4.

For every $x=(x_{1},x_{2})\neq\mathbf{0}_{*}$ its inverse multiplicative
element $x^{-1}_{*}$ with the respect of the left unit element
$\mathbf{1}_{*}$ is given by the following equation

$x^{-1}_{*}=\left(\frac{1-a_{3}b_{2}-a_{3}b_{7}x_{2}}{a_{8}(b_{2}+b_{7}x_{2})},\frac{1-a_{3}b_{2}-a_{8}b_{2}x_{1}}{b_{7}(a_{3}+a_{8}x_{1})}\right)\
\ ,$ (25)

for which it holds

$x*x^{-1}_{*}=x^{-1}_{*}*x=\mathbf{1}_{*}\ \ .$ (26)

∎

######  Proposition 2.

There are $p-1$ distinct square roots of the left unity $\mathbf{1}_{*}$, i.e.

$\mathbb{S}(p)=\\{x\ |\ x*x=\mathbf{1}_{*}\\},\ \ \text{and}\ \ \
|\mathbb{S}(p)|=p-1.$ (27)

∎

######  Definition 13.

Let $x=(x_{1},x_{2}),y=(y_{1},y_{2})$ be two elements of the set
$G=\mathbb{F}_{p}\times\mathbb{F}_{p}$. The additive operation $\boxplus$,
i.e. $x\boxplus y$ is defined as:

$(x_{1},x_{2})\boxplus(y_{1},y_{2})=\left(x_{1}+y_{1}+\frac{a_{3}}{a_{8}},x_{2}+y_{2}+\frac{b_{2}}{b_{7}}\right),$
(28)

where $a_{3},a_{8},b_{2},b_{7}\in\mathbb{F}_{p}$, are defined in Definition
12.

Let us denote by $\boxminus$ the corresponding "inverse" of the additive
operation $\boxplus$. Its definition is given by the following expression:

$(x_{1},x_{2})\boxminus(y_{1},y_{2})=\left(x_{1}-y_{1}-\frac{a_{3}}{a_{8}},x_{2}-y_{2}-\frac{b_{2}}{b_{7}}\right).$
(29)

We can use the operation $\boxminus$ also as a unary operator. If we write
$\boxminus x$ then we mean

$\boxminus x\stackrel{{\scriptstyle def}}{{=}}\mathbf{0}_{*}\boxminus
x=\left(-\frac{a_{3}}{a_{8}}-x_{1},-\frac{b_{2}}{b_{7}}-x2\right).$ (30)

One can check that "minus one" i.e. $\boxminus\mathbf{1}_{*}$ is also a square
root of the left unity i.e that it holds:
$\boxminus\mathbf{1}_{*}*\boxminus\mathbf{1}_{*}=\mathbf{1}_{*}$.

A consequence of Corollary 1 and Definition 13 is the following

######  Corollary 2.

The algebraic structure $(G,\boxplus,*)$ is a ringoid where $(G,\boxplus)$ is
an Abelian group with a neutral element $\mathbf{0}_{*}$, $(G,*)$ is a non-
commutative and non-associative groupoid with a zero element $\mathbf{0}_{*}$,
a left unit element $\mathbf{1}_{*}$ and $*$ is distributive over $\boxplus$
i.e.

$x*(y\boxplus z)=(x*y)\boxplus(x*z)\ \ \text{and}\ \ (x\boxplus
y)*z=(x*z)\boxplus(y*z).$ (31)

######  Definition 14.

The ringoid $\mathbb{E}_{p^{2}}=(G,\boxplus,*)$ with operation $*$ defined
with Definition 12 and operation $\boxplus$ defined with Definition 13 is
called a _Finite Entropic Ring_ or _Finite Entropoid_ with $p^{2}$ elements.
For given values of $p,a_{3},a_{8},b_{2}$ and $b_{7}$ it will be denoted as
$\mathbb{E}_{p^{2}}(a_{3},a_{8},b_{2},b_{7})$. 111The ringoid $(G,\boxplus,*)$
is neither a neofield (since $(G,*)$ is not a group), nor a Lie ring (since
the Jacobi identity is not satisfied), but is built with the operation $*$
given by the entropic identity (2). We are aware of the work of J.D.H. Smith
and A.B. Romanowska in [18] that refer to the entropic Jonsson-Tarski
algebraic varieties, but for our purposes, and to be more narrow with the
definition of the algebraic structure that we will use, we give a formal name
of this ringoid as ”Entropoid”.

In the rest of the text we will use interchangeably the notations
$\mathbb{E}_{p^{2}}(a_{3},a_{8},b_{2},b_{7})$ and if in text context, the
constants $a_{3},a_{8},b_{2},b_{7}$ are not important, just
$\mathbb{E}_{p^{2}}$. We will also assume that the choice for the parameters
is $a_{3}\neq 0$ and $b_{2}\neq 0$. To shorten the mathematical expressions,
when the meaning is clear from the context, we will also overload the symbol
$\mathbb{E}_{p^{2}}$ with two interpretations: as a set
$\mathbb{E}_{p^{2}}=G=\mathbb{F}_{p}\times\mathbb{F}_{p}$ and as an algebraic
structure $\mathbb{E}_{p^{2}}=(G,\boxplus,*)$.

######  Definition 15.

Let us define the subset $\mathbb{E}_{(p-1)^{2}}^{*}\subset\mathbb{E}_{p}$ as

$\mathbb{E}_{(p-1)^{2}}^{*}=\bigg{(}\Big{(}\mathbb{F}_{p}\setminus\Big{\\{}-\frac{a_{3}}{a_{8}}\Big{\\}}\Big{)}\times\Big{(}\mathbb{F}_{p}\setminus\Big{\\{}-\frac{b_{2}}{b_{7}}\Big{\\}}\Big{)}\bigg{)}.$
(32)

We say that the groupoid $(\mathbb{E}_{(p-1)^{2}}^{*},*)$ is the maximal
multiplicative subgroupoid of $\mathbb{E}_{p^{2}}$.

It is clear from Definition 15 that the multiplicative subgroupoid
$\mathbb{E}_{(p-1)^{2}}^{*}$ has $(p-1)^{2}$ elements $x=(x_{1},x_{2})$ such
that $x_{1}$ is not the first component and $x_{2}$ is not the second
component of the multiplicative zero $\mathbf{0}_{*}$. It has one additional
property: it is a quasigroup, and that is stated in the following Lemma.

######  Lemma 1.

The maximal multiplicative groupoid $(\mathbb{E}_{(p-1)^{2}}^{*},*)$ defined
in Definition 15 with the operation $*$ defined in Definition 12 is a non-
commutative and non-associative quasigroup with a left unit element
$\mathbf{1}_{*}$.

###### Proof.

Non-commutativity, non-associativity and the proof about the left unit element
come directly by the definition of the operation $*$, and Corollary 1. The
only remaining part is to prove that for every
$c=(c_{1},c_{2})\in\mathbb{E}_{(p-1)^{2}}^{*}$ and every
$d=(d_{1},d_{2})\in\mathbb{E}_{(p-1)^{2}}^{*}$, the equations $c*x=d$ and
$x*c=d$ have always solutions. It is left as an exercise for the reader to
replace the values of $c$ and $d$, to apply the definition of the operation
$*$ annd with simple polynomial algebra to get get two equations for $x_{1}$
and $x_{2}$ with a unique solution $x=(x_{1},x_{2})$. ∎

We will use the notation $(\mathbb{E}^{*}_{\nu},*)$ for the subgroupoids of
$(\mathbb{E}_{(p-1)^{2}}^{*},*)$, with $\nu$ elements. That means that if we
are given $(\mathbb{E}^{*}_{\nu},*)$, then
$\mathbb{E}^{*}_{\nu}\subseteq\mathbb{E}_{(p-1)^{2}}^{*}$, $\forall
x,y\in\mathbb{E}^{*}_{\nu}$, $x*y\in\mathbb{E}^{*}_{\nu}$ and
$|\mathbb{E}^{*}_{\nu}|=\nu$. Using the Etherington terminology, we will say
that the quasigroup $(\mathbb{E}_{(p-1)^{2}}^{*},*)$ and all of its
subquasigroups $(\mathbb{E}^{*}_{\nu},*)$ are _entropic quasigroups_.

######  Proposition 3.

If $(\mathbb{E}^{*}_{\nu},*)$ is a subgroupoid of
$(\mathbb{E}_{(p-1)^{2}}^{*},*)$, then $\nu$ divides $(p-1)^{2}$ i.e.
$\nu|(p-1)^{2}$ and $(\mathbb{E}^{*}_{\nu},*)$ is a subquasigroup of
$(\mathbb{E}_{(p-1)^{2}}^{*},*)$. ∎

The following Proposition is a connection between the subgroups of the
multiplicative group of a finite field, and the subgroupoids in the finite
entropoid. It is a consequence of Proposition 3 and the Lagrange’s theorem for
groups:

######  Proposition 4.

Let $\mathbb{F}_{p}$ be the finite field over which an entropoid
$\mathbb{E}_{p^{2}}$ is defined. Let $\Gamma\subseteq\mathbb{F}_{p}^{*}$ be a
cyclic subgroup of order $|\Gamma|$ of the multiplicative group
$\mathbb{F}_{p}^{*}$ and let $\gamma\neq-\frac{a_{3}}{a_{8}}$ and
$\gamma\neq-\frac{b_{2}}{b_{7}}$ is its generator, then $g=(\gamma,\gamma)$ is
a generator of a subgroupoid $(\mathbb{E}^{*}_{\nu},*)$ and $\nu$ divides
$|\Gamma|^{2}$.

Next, for our subquasigroups $(\mathbb{E}^{*}_{\nu},*)$ we will partially use
the Smith terminology in his proposed Sylow theory for quasigroups [19].

######  Definition 16.

Let $(\mathbb{E}^{*}_{\nu},*)$ be a subquasigroup of
$(\mathbb{E}^{*}_{(p-1)^{2}},*)$ and let $(p-1)^{2}$ be represented as product
of the powers of its prime factors i.e.$(p-1)^{2}=2^{e_{1}}q_{1}^{e_{2}}\ldots
q_{k}^{e_{k}}$. We say that $(\mathbb{E}^{*}_{\nu},*)$ is Sylow
$q_{i}$-subquasigroup if $\nu=q_{i}^{e_{i}}$ for $i\in\\{2,\ldots,k\\}$.

Before we continue, let us give one example.

Example 1.  Let the finite entropoid be defined as
$\mathbb{E}_{7^{2}}(a_{3}=6,a_{8}=3,b_{2}=3,b_{7}=4)$. In that case the
operation $*$ becomes:

$x*y=(x_{1},x_{2})*(y_{1},y_{2})=(6+6x_{2}+4y_{1}+3x_{2}y_{1},\ \ \
y_{2}+3x_{1}+4x_{1}y_{2}).$

All elements from $\mathbb{E}_{7^{2}}$ are presented in Table 1.

From Corollary 1 we get $\mathbf{0}_{*}=(5,1)$ and $\mathbf{1}_{*}=(0,6)$. The
elements that are highlighted in Table 1 (elements in the row and column where
the zero element $\mathbf{0}_{*}$ is positioned) are excluded from the
multiplicative subgroupoid $\mathbb{E}_{6^{2}}^{*}$.

Table 1: Representation of all 49 elements of $\mathbb{E}_{7^{2}}$. Table 2:
Results of rising different values $x$ to the powers from 2 to 5 with
different bracketing patterns $a_{s}$. The green highlighted cells are for the
representatives of a class of expressions that give the same result, and in
the brackets is the size of that class. Table 3: Results of rising different
values $x$ to the power of 6 with different bracketing patterns $a_{s}$.

We can make several observations from the values in Table 2 and Table 3:

  * •

As we would expect, $\mathbf{0}_{*}^{a}=\mathbf{0}_{*}$ and
$\mathbf{1}_{*}^{a}=\mathbf{1}_{*}$ for all $a$ and for all bracketing
patterns $a_{s}$.

  * •

Some values of $x$, raised to different patterns $a_{s}$ for the same value
$a$ tend to produce more different values, while some generate less different
values. For example, for $a=4$, for $x=(0,2)$ there are three different values
$(3,2)$, $(2,4)$ and $(4,3)$, while for $x=(0,3)$ there are two different
values $(3,3)$ and $(0,6)$.

  * •

For any $x$, for a given fixed $a$, the number of different values generated
with all patterns $a_{s}$ do not exceed $a-1$.

  * •

When the number of different values is $a-1$, the distribution of the patterns
over those $a-1$ values follows the distribution of Narayana numbers
$N(n,k)$[14, Sequence A001263]:

$a=4$:

1, 3, 1

$a=5$:

1, 6, 6, 1

$a=6$:

1, 10, 20, 10, 1

One can raise to different powers with different patterns all elements of
$\mathbb{E}_{7^{2}}$ and can count the total number of generated elements. In
Table 4 we show the size of the generated sets with all elements of
$\mathbb{E}_{7^{2}}$. The green highlighted elements with the value 36
generate the maximal multiplicative subgroupoid $(\mathbb{E}^{*}_{36},*)$. For
example, $(0,2)$ is the generator of $(\mathbb{E}^{*}_{36},*)$.

The yellow highlighted cells in Table 4 are for the elements that do not
belong to the multiplicative subgroupoid $((\mathbb{E}^{*}_{36},*)$.

Notice that the prime number $p=7$ can be represented as $p=2q+1=2*3+1$, and
that all elements of $\mathbb{E}_{7^{2}}$ can belong to different classes with
cardinalities that are divisors of $(p-1)^{2}=2^{2}q^{2}=2^{2}3^{2}$, i.e. the
cardinalities are $\\{1,2,3,4,6,9,18,36\\}$.

Table 4: The size of the sets $\langle(x_{1},x_{2})\rangle$ for
$x=(x_{1},x_{2})\in\mathbb{E}_{7^{2}}$ where $x_{1}$ represents the row number
and $x_{2}$ represents the column number.

∎

dot tree/.style= /tikz/>=Latex, for tree= anchor=center, base=bottom, inner
sep=1pt, fill=yellow, draw, circle, calign=fixed edge angles, , baseline,
before computing xy= where n children>=4 tempcounta/.option=n children,
tempdima/.option=!1.s, tempdimb/.option=!l.s, tempdimb-/.register=tempdima,
tempdimc/.process=RRw2+P tempcountatempdimb##2/(##1-1), for children=
if=>On>OR<&n1ntempcounta s/.register=tempdima, s+/.process=ORw2+P n tempdimc
(##1-1)*##2 , , , , , dot tree spread/.style= dot tree, for
tree=fit=rectangle, , add arrow/.style= tikz+= [thick, blue!15!gray] (current
bounding box.east) ++(2.5mm,0) edge [->] ++(10mm,0) ++(2.5mm,0) coordinate
(o);

$a$ |  $i=1$, $N(3,1)=1$ |  $i=2$, $N(3,2)=3$ |  $i=3$, $N(3,3)=1$
---|---|---|---
|  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[$x$][[$x$][[$x$][$x$]]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[$x$][[[$x$][$x$]][$x$]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[$x$][[$x$][$x$]]][$x$]]
$(x*(x*(x*x)))$ | $(x*((x*x)*x))$ | $((x*(x*x))*x)$
|  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[$x$][$x$]][[$x$][$x$]]] |
4 |  | $((x*x)*(x*x))$ |
|  |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[[$x$][$x$]][$x$]][$x$]] |
|  | $(((x*x)*x)*x)$ |
Table 5: Representation of all possible non-associative powers of $a=4$ as
planar binary trees, and the corresponding clastering in subsets with Narayana
numbers of elements.

######  Definition 17.

Let $2\leq a$ be an integer, and let $x$ be an element in $G$. An ordered list
$R_{a}(x)$ of $a-1$ bracketing shapes is called the list of associative class
representatives and is defined as:

$\displaystyle R_{a}(x)=[R_{a}(x)[0],R_{a}(x)[1],\ldots,$ $\displaystyle
R_{a}(x)[a-3],R_{a}(x)[a-2]],\text{where}$ $\displaystyle R_{a}(x)[0]$
$\displaystyle=x_{(x,a-1)\texttt{to-left}},$ $\displaystyle R_{a}(x)[1]$
$\displaystyle=(x_{(x,1)\texttt{to-left}}*x)_{(x,a-3)\texttt{to-left}},$
$\displaystyle R_{a}(x)[2]$ $\displaystyle=(x_{(x,2)\texttt{to-
left}}*x)_{(x,a-4)\texttt{to-left}},$ $\displaystyle\ldots,$ (33)
$\displaystyle R_{a}(x)[a-3]$ $\displaystyle=(x_{(x,a-3)\texttt{to-
left}}*x)_{(x,0)\texttt{to-left}},$ $\displaystyle R_{a}(x)[a-2]$
$\displaystyle=(x_{(x,a-2)\texttt{to-left}}*x),$

Note: We use the zero-based indexing style for the list members.

######  Lemma 2.

The bracketing shapes for $R_{a}(x)$ and $R_{a+1}(x)$ are related with the
following recurrent relations:

$\displaystyle R_{a+1}(x)[0]$ $\displaystyle=(x*R_{a}(x)[0]),$ $\displaystyle
R_{a+1}(x)[1]$ $\displaystyle=(x*R_{a}(x)[1]),$ $\displaystyle R_{a+1}(x)[2]$
$\displaystyle=(x*R_{a}(x)[2]),$ $\displaystyle\ldots,$ (34) $\displaystyle
R_{a+1}(x)[a-2]$ $\displaystyle=(x*R_{a}(x)[a-2]),$ $\displaystyle
R_{a+1}(x)[a-1]$ $\displaystyle=(R_{a}(x)[0]*x),$

###### Proof.

We will prove the lemma with induction by $a$. Let us first note that
$R_{2}(x)=[R_{2}(x)[0]\equiv(x*x)]$. For $a=3$ we have
$R_{3}(x)=[R_{3}(x)[0],R_{3}(x)[1]]$, where $R_{3}(x)[0]=x_{(x,3-1)\texttt{to-
left}}=(x*(x*x))=(x*R_{2}(x))$, and $R_{3}(x)[1]=(x_{(x,3-2)\texttt{to-
left}}*x)=((x*x)*x)=(R_{2}(x)[0]*x)$.

If we suppose that the recurrent relations (2) are true for $a$, then for
$a+1$ we have

  * •

$R_{a+1}(x)[0]\stackrel{{\scriptstyle def}}{{=}}x_{(x,a)\texttt{to-
left}}=(x*x_{(x,a-1)\texttt{to-left}})=(x*R_{a}(x)[0])$,

  * •

$R_{a+1}(x)[1]\stackrel{{\scriptstyle def}}{{=}}(x_{(x,1)\texttt{to-
left}}*x)_{(x,a+1-3)\texttt{to-left}}=(x*x_{(x,a-2)\texttt{to-
left}})=(x*R_{a}(x)[1])$,

  * •

$\ldots$,

  * •

$R_{a+1}(x)[a-2]\stackrel{{\scriptstyle def}}{{=}}(x_{(x,a-2)\texttt{to-
left}}*x)_{(x,0)\texttt{to-left}}=(x*R_{a}(x)[a-2])$,

  * •

$R_{a+1}(x)[a-1]\stackrel{{\scriptstyle def}}{{=}}(x_{(x,a-1)\texttt{to-
left}}*x)=(R_{a}(x)[0]*x)$.

∎

Example 2.  Let us present the bracketing shapes highlighted in green in Table
2 and in Table 3, in Example 16 with the notation introduced in Definition 17.

$a=4$ :

Out of 5 bracketing shapes, the following 3 are highlighted:

$i=1$:

$(x*(x*(x*x)))=x_{(x,3)\texttt{to-left}}$

$i=2$:

$(x*((x*x)*x))=(x_{(x,1)\texttt{to-left}}*x)_{(x,0)\texttt{to-left}}$

$i=3$:

$((x*(x*x))*x)=(x_{(x,2)\texttt{to-left}}*x)$

$a=5$ :

Out of 14 bracketing shapes, the following 4 are highlighted:

$i=1$:

$(x*(x*(x*(x*x))))=x_{(x,4)\texttt{to-left}}$

$i=2$:

$(x*(x*((x*x)*x)))=(x_{(x,1)\texttt{to-left}}*x)_{(x,2)\texttt{to-left}}$

$i=3$:

$(x*((x*(x*x))*x))=(x_{(x,2)\texttt{to-left}}*x)_{(x,1)\texttt{to-left}}$

$i=4$:

$((x*(x*(x*x)))*x)=(x_{(x,3)\texttt{to-left}}*x)$

$a=6$ :

Out of 42 bracketing shapes, the following 5 are highlighted:

$i=1$:

$(x*(x*(x*(x*(x*x)))))=x_{(x,5)\texttt{to-left}}$

$i=2$:

$(x*(x*(x*((x*x)*x))))=(x_{(x,1)\texttt{to-left}}*x)_{(x,3)\texttt{to-left}}$

$i=3$:

$(x*(x*((x*(x*x))*x)))=(x_{(x,2)\texttt{to-left}}*x)_{(x,2)\texttt{to-left}}$

$i=4$:

$(x*((x*(x*(x*x)))*x))=(x_{(x,3)\texttt{to-left}}*x)_{(x,1)\texttt{to-left}}$

$i=5$:

$((x*(x*(x*(x*x))))*x)=(x_{(x,4)\texttt{to-left}}*x)$

Let us also present in Table 5 and Table 6 the bracketing shapes for $a=4$ and
$a=5$ as planar binary trees (for $a=6$ it would be an impractically tall
table with 20 trees in one column). We see that the first rows in the tables
are exactly the highlighted green shapes from Table 2.

$a$ |  $i=1$, $N(4,1)=1$ |  $i=2$, $N(4,2)=6$ |  $i=3$, $N(4,3)=6$ |  $i=4$, $N(4,4)=1$
---|---|---|---|---
|  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[$x$][[$x$][[$x$][[$x$][$x$]]]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[$x$][[$x$][[[$x$][$x$]][$x$]]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[$x$][[[$x$][[$x$][$x$]]][$x$]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[$x$][[$x$][[$x$][$x$]]]][$x$]]
$(x*(x*(x*(x*x))))$ | $(x*(x*((x*x)*x)))$ | $(x*((x*(x*x))*x))$ | $((x*(x*(x*x)))*x)$
|  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[$x$][[[$x$][$x$]][[$x$][$x$]]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[$x$][$x$]][[[$x$][$x$]][$x$]]] |
| $(x*((x*x)*(x*x)))$ | $((x*x)*((x*x)*x))$ |
|  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[$x$][[[[$x$][$x$]][$x$]][$x$]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[$x$][[$x$][$x$]]][[$x$][$x$]]] |
5 |  | $(x*(((x*x)*x)*x))$ | $((x*(x*x))*(x*x))$ |
|  |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[$x$][$x$]][[$x$][[$x$][$x$]]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[$x$][[[$x$][$x$]][$x$]]][$x$]] |
|  | $((x*x)*(x*(x*x)))$ | $((x*((x*x)*x))*x)$ |
|  |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[[$x$][$x$]][$x$]][[$x$][$x$]]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[[$x$][$x$]][[$x$][$x$]]][$x$]] |
|  | $(((x*x)*x)*(x*x))$ | $(((x*x)*(x*x))*x)$ |
|  |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[[$x$][[$x$][$x$]]][$x$]][$x$]] |  dot tree, where n children=0 before computing xy=l*=1.0, s*=1.0, edge+=densely dashed, , [[[[[$x$][$x$]][$x$]][$x$]][$x$]] |
|  | $(((x*(x*x))*x)*x)$ | $((((x*x)*x)*x)*x)$ |
Table 6: Representation of all possible non-associative powers of $a=5$ as
planar binary trees, and the corresponding clastering in subsets with Narayana
number of elements.

∎

Since for any fixed integer $a$, the set $S_{a}(x)$ of all bracketing shapes
$\mathbf{A}=(a,a_{s})$ have $C_{a-1}=\frac{1}{a}\binom{2a-2}{a-1}$ elements
(equation (5)), for a generic non-commutative and non-associative groupoid
$(G,*)$, with a multiplicative operation $*$ we would expect that for some
elements $x\in G$ there would be up to $C_{a-1}$ different power values in the
set $\\{x^{\mathbf{A}}\\}$. However, for entropic groupoids
$(\mathbb{E}^{*}_{p^{2}}$ defined by Definition 11 and by the equation (22)
that is not the case, and the size of the set $\\{x^{\mathbf{A}}\\}$ is
limited to $a-1$ as we see it in Example 16 and Example 2.

######  Definition 18.

Let $\mathbb{E}_{p^{2}}$ be a given finite entropoid. We define an integer
$b_{max}$ by the following expression:

$b_{max}=\min\left\\{b\ |\ \frac{1}{b}\binom{2b-2}{b-1}>(p-1)^{2}\right\\}.$
(35)

The value $b_{max}$ is the smallest integer for which the Catalan number
$C_{b-1}=\frac{1}{b}\binom{2b-2}{b-1}$ surpasses the number of elements in the
maximal multiplicative subgroupoid $(G^{*},g)$. We will need it in the proof
of the next theorem.

######  Theorem 3 (Equivalent classes and their representatives).

Let $\mathbb{E}_{p^{2}}$ be given, and let $g$ is a generator of its maximal
multiplicative subgroupoid $(\mathbb{E}^{*}_{(p-1)^{2}},*)$, where $*$ is
defined by Definition 11 and by the equation (22). For every $3\leq
a<b_{max}$, evaluating the bracketing shapes of the set $S_{a}(g)$ gives a
partitioning in $a-1$ equivalent classes $S_{1,a(g)}$, $S_{2,a(g)}$, $\ldots$,
$S_{a-2,a(g)}$, $S_{a-1,a(g)}$, whose corresponding representatives are given
by the corresponding elements of $R_{a}(g)$ defined by the relation (17) and
the cardinality of the sets $S_{i,a(g)}$ for $i=1,\ldots,a-1$ is given by the
following expression

$|S_{i,a(g)}|=N(a-1,i)=\frac{1}{a-1}\binom{a-1}{i}\binom{a-1}{i-1},$ (36)

where $N(a-1,i)$ are the Narayana numbers.

###### Proof.

We will prove the theorem by induction on $a$ for the range $3\leq a<b_{max}$.
For $a\geq b_{max}$ there are not enough elements to be classified in classes
which total number surpass $(p-1)^{2}$ (as it is the number of elements of
$(\mathbb{E}^{*}_{(p-1)^{2}},*)$).

For $a=3$ the theorem is trivially true since there are just $a-1=2$
associative shapes. The first non-trivial case is for $a=4$. Taking
$g=(g_{1},g_{2})$, and using the definition for the operation $*$ given in
equation (22), by basic symbolic and algebraic expression replacements we get
that for all three shapes the end result is:

$\displaystyle R_{4}(g)[1]\equiv(g*((g*g)*g))=((g*g)*(g*g))=(((g*g)*g)*g)=$
$\displaystyle=\Bigg{(}$
$\displaystyle\frac{a_{8}^{3}g_{1}^{2}\left(b_{7}g_{2}+b_{2}\right)^{2}+2a_{3}a_{8}^{2}g_{1}\left(b_{7}g_{2}+b_{2}\right)^{2}+a_{3}\left(2a_{3}a_{8}b_{7}b_{2}g_{2}+a_{3}a_{8}b_{7}^{2}g_{2}^{2}+a_{3}a_{8}b_{2}^{2}-b_{7}\right)}{a_{8}b_{7}},$
$\displaystyle\frac{a_{3}^{2}b_{7}^{3}g_{2}^{2}+2a_{3}^{2}b_{2}b_{7}^{2}g_{2}+a_{8}^{2}b_{7}g_{1}^{2}\left(b_{7}g_{2}+b_{2}\right)^{2}+2a_{3}a_{8}b_{7}g_{1}\left(b_{7}g_{2}+b_{2}\right)^{2}+b_{2}\left(a_{3}^{2}b_{2}b_{7}-a_{8}\right)}{a_{8}b_{7}}\Bigg{)}$

We can also check that $R_{4}(g)[0]\equiv(g*(g*(g*g)))\neq(g*((g*g)*g))\equiv
R_{4}(g)[1]$, $R_{4}(g)[2]\equiv((g*(g*g))*g)\neq(g*((g*g)*g))\equiv
R_{4}(g)[1]$, and $R_{4}(g)[0]\equiv(g*(g*(g*g)))\neq((g*(g*g))*g)\equiv
R_{4}(g)[2]$. Thus for the case $a=4$ we have $S_{1,4(g)}=\\{R_{4}(g)[0]\\}$,
$S_{2,4(g)}=\\{R_{4}(g)[1]\equiv(g*((g*g)*g)),((g*g)*(g*g)),(((g*g)*g)*g)\\}$
and $S_{3,4(g)}=\\{R_{4}(g)[2]\\}$.

Let us now suppose that the claims of the theorem are true for $a$, i.e. that
the expressions (37) and (36) hold. Then, for $a+1$ we have the set
$S_{a+1}(g)$ that has $C_{a}=\frac{1}{a+1}\binom{2a}{a}$ elements, where
$C_{a}$ is the $(a)$-th Catalan number. We can now partition the set
$S_{a+1}(g)$ as follows:

$S_{a+1}(g)=S_{1,a(g)}\bigcup S_{2,a(g)}\bigcup\ldots\bigcup
S_{a-1,a(g)}\bigcup S_{a,a(g)},$ (37)

where $x_{(x,a-1)\texttt{to-left}}\in S_{1,a(g)}$, $(x_{(x,1)\texttt{to-
left}}*x)_{(x,a-3)\texttt{to-left}}\in S_{2,a(g)}$, $\ldots$,
$(x_{(x,a-3)\texttt{to-left}}*x)_{(x,1)\texttt{to-left}}\in S_{a-2,a(g)}$ and
$((x_{(x,a-2)\texttt{to-left}}*x)\in S_{a-1,a(g)}$.

The conditions that $g$ is a generator of the
$(\mathbb{E}^{*}_{(p-1)^{2}},*)$, and that $*$ is non-commutative and non-
associative operation are essential for obtaining that the element
$R_{a+1}(x)[a-1]=(R_{a}(x)[0]*x)$ of the subset $S_{a,a(g)}$ is different from
the element $R_{a+1}(x)[0]=(x*R_{a}(x)[0])$ of the subset $S_{1,a(g)}$.

Then,if we represent the Catalan number $C_{a}$ as a sum of Narayana numbers
$N(a,i)$:

$C_{a}=N(a,1)+N(a,2)+\ldots+N(a,a-1)+N(a,a),$

and if we use the recurrent relations for the representatives of the
equivalent classes given in Lemma 2 to get expressions for the representatives
of the partitions of $S_{a+1}(g)$, we obtain that the relations (37) and (36)
hold also for $a+1$. ∎

######  Open Problem 3.

In the proof of the Theorem 3, as a jump-start for the induction we used the
concrete instance for the entropic operation $*$ defined by the equation (22).
We do not know does the same partitioning in equivalent classes hold for
general entropic operations $*$, and it would be an interesting mathematical
problem to further investigate.

###  2.3 Succinct Notation for Exponentially Large Bracketing Shapes

Notation: In the rest of the text we assume that we work in finite entropoid
$\mathbb{E}_{p^{2}}$ and $g\in\mathbb{E}_{p^{2}}$ is a generator of some
multiplicative subgroupoid $(\mathbb{E}^{*}_{\nu},*)$, where $*$ is defined by
Definition 11 and by the equation (22). In Definition 17, Lemma 2 and Theorem
3 we use the symbol $a$ to represent any number (possibly exponentially large)
of multiplicative factors in the process of rising to the power of $a$. In our
pursuit for succinct representation of exponentially large indices, we will
keep the symbol $a$, but for smaller bracketing patterns of size
$\mathfrak{b}$ the role of the symbol $a$ in Definition 17, Lemma 2 and
Theorem 3 will be replaced by $\mathfrak{b}\geq 2$. Further, we will denote
the indices either as pairs $(\mathbf{A},\mathfrak{b})$ or as triplets
$(a,a_{s},\mathfrak{b})$ meaning
$(\mathbf{A},\mathfrak{b})=(a,a_{s},\mathfrak{b})$. The set of all power
indices will be denoted by $\mathbb{L}$ in resemblance to the logarithmetic of
power indices $(L(G),\mathbf{+},\mathbf{\times})$ $)$. We will write
$(\mathbf{A},\mathfrak{b})\xleftarrow{\mathbf{r}}\mathbb{L}$ to denote that
$(\mathbf{A},\mathfrak{b})$ was chosen uniformly at random from the set
$\mathbb{L}$ if $\mathfrak{b}\xleftarrow{\mathbf{r}}\mathbb{Z}_{>1}$,
$a\xleftarrow{\mathbf{r}}\mathbb{Z}_{p}^{*}$, and
$a_{s}\xleftarrow{\mathbf{r}}\mathbb{L}[a,\mathfrak{b}]$ where
$\mathbb{L}[a,\mathfrak{b}]$ is the set of all bracketing shapes defined in
Definition 19.

######  Definition 19 (Succinct power indices).

Let integer $\mathfrak{b}\geq 2$ be a base. The power index
$(\mathbf{A},\mathfrak{b})=(a,a_{s},\mathfrak{b})$ is defined as a triplet
consisting of two lists and an integer $\mathfrak{b}$. Let
$a\in\mathbb{Z}^{+}$ be represented in base $\mathfrak{b}$ as
$a=A_{0}+A_{1}\mathfrak{b}+\ldots+A_{k}\mathfrak{b}^{k}$, or in little-endian
notation with the list of digits $0\leq A_{i}\leq\mathfrak{b}-1$, as
$a=[A_{0},A_{1},\ldots,A_{k}]_{\mathfrak{b}}$. Let the bracketing pattern
$a_{s}$ be represented with a list of digits
$a_{s}=[P_{0},P_{1},\ldots,P_{k}]_{\mathfrak{b}-1}$ where $0\leq
P_{i}\leq\mathfrak{b}-2$ for $i=0,\ldots,k$. For base $\mathfrak{b}$ and
$a=[A_{0},A_{1},\ldots,A_{k}]_{\mathfrak{b}}\in\mathbb{Z}^{+}$ we denote the
set of all possible patterns $a_{s}$ by

$\mathbb{L}[a,\mathfrak{b}]=\\{a_{s}\
|a_{s}=[P_{0},\ldots,P_{k}]_{\mathfrak{b}-1},\text{ for all
}P_{j}\in\mathbb{Z}_{\mathfrak{b}-1},j=0,\ldots,k\\}.$ (38)

######  Definition 20 (Non-associative and non-commutative exponentiation).

For any $x\in\mathbb{E}_{p}$ we define $x^{(\mathbf{A},\mathfrak{b})}$ as
follows:

$\displaystyle w_{0}=$ $\displaystyle x,$ $\displaystyle w_{i}=$
$\displaystyle R_{b}(w_{i-1})[P_{i}],\text{\ for \ }i=1,\ldots,k,$ (39)
$\displaystyle j=$ $\displaystyle\text{index of the first nonzero digit
}A_{j}$ $\displaystyle x_{j}=$
$\displaystyle\left\\{\begin{array}[]{ll}w_{j}&\text{, if }A_{j}=1,\\\
R_{A_{j}}(w_{j})[P_{j}\mod(A_{j}-1)]&\text{, if }A_{j}>1.\end{array}\right.$
(42) $\displaystyle\text{for }i=j+1,\ldots,k$ $\displaystyle x_{i}=$
$\displaystyle\left\\{\begin{array}[]{ll}x_{i-1}&\text{, if }A_{i}=0,\\\
w_{i}*x_{i-1}&\text{, if }A_{i}=1\text{ and }P_{i-1}\text{ is even,}\\\
x_{i-1}*w_{i}&\text{, if }A_{i}=1\text{ and }P_{i-1}\text{ is odd,}\\\
R_{A_{i}}(w_{i})[P_{i}\mod(A_{i}-1)]*x_{i-1}&\text{, if }A_{i}>1\text{ and
}P_{i-1}\text{ is even,}\\\
x_{i-1}*R_{A_{i}}(w_{i})[P_{i}\mod(A_{i}-1)]&\text{, if }A_{i}>1\text{ and
}P_{i-1}\text{ is odd,}\end{array}\right.$ (48) $\displaystyle
x^{(\mathbf{A},\mathfrak{b})}=$ $\displaystyle x_{k}.$ (49)

######  Proposition 5.

For every base $\mathfrak{b}\geq 2$, every $x\in\mathbb{E}_{p^{2}}$, every
$a\in\mathbb{Z}^{+}$ and every bracketing pattern
$a_{s}=[P_{0},P_{1},\ldots,P_{k}]_{\mathfrak{b}-1}$, the value
$x^{(\mathbf{A},\mathfrak{b})}$ is a product of $a$ multiplications of $x$

$x^{(\mathbf{A},\mathfrak{b})}=x^{(a,a_{s},\mathfrak{b})}=\underbrace{(x*\ldots(x*x)\ldots)}_{a\text{\
copies of }x}.$

If $O^{*}_{\mathfrak{b}}$ denotes the number of operations $*$ used to compute
the result $x^{(\mathbf{A},\mathfrak{b})}$, then its value is given by the
following expression

$O^{*}_{\mathfrak{b}}=k(\mathfrak{b}-1)-1+\sum_{A_{i}\neq 0}A_{i}\ \ .$ (50)

###### Proof.

For the first part, let us define a counter $M(i)$ for $i=0,1,\ldots,k$, that
counts the number of times $x$ was multiplied in the procedure described in
equations (39) - (49) for a number
$m_{i}=[A_{0},A_{1},\ldots,A_{i}]_{\mathfrak{b}}$ consisting of the first $i$
digits of $a$.

Let us first notice that every value $w_{i}$, for $i=0,1,\ldots,k$ in (39) is
a result of $\mathfrak{b}^{k}$ multiplications of $x$. Now, our counting
should start at (42) with the value $x_{j}$ where $j$ is the index of the
first nonzero digit $A_{j}$. This means that if $j=0$, $M(0)=A_{0}=m_{0}$, and
if $j>0$, $M(j)=A_{j}\mathfrak{b}^{j}=m_{j}$. Then, for every next digit
$A_{i}$ for $i=j+1,\ldots,k$ we have that $M(j)=M(j-1)+A_{j}\mathfrak{b}^{j}$,
where the factor $\mathfrak{b}^{j}$ comes from the fact that $w_{j}$ is used
either as $1\mathfrak{b}^{j}$ or as $A_{j}\mathfrak{b}^{j}$ if $A_{j}>1$ in
the part $[P_{i}\mod(A_{i}-1)]$ of (48). The final result is that
$M(k)=\sum_{i=0}^{k}A_{j}\mathfrak{b}^{j}=a$.

The second part can be proved by counting the number of multiplications
performed in parts (39) and in parts (42)-(48). In the expression (39) we have
a fixed value $\mathfrak{b}$ \- so total number of multiplications is exactly
$k(\mathfrak{b}-1)$. Next, in (42) we have either $0$ multiplications (if
$A_{j}=0$), or $A_{j}-1$ multiplications (if $A_{j}>1$). Finally, in (48), for
$i=j+1,\ldots,k$ we apply $1$ multiplication with $x_{i-1}$ and $A_{i}-1$
multiplications in the expression $R_{A_{i}}(w_{i})[P_{i}\mod(A_{i}-1)]$,
which proves the equation (50). ∎

Proposition 5 ensures that Definition 20 defines a succinct notation for
exponentially large power indices with their bracketing shapes since:

  1. 1.

It is consistent procedure of rising to a power where the number of times that
$x$ is multiplied is exactly $a$, and

  2. 2.

An efficient procedure where the number of performed operations $*$ is
$O(\mathfrak{b}\log_{\mathfrak{b}}a)$.

The contribution of the non-associativity of the operation $*$ to the final
result comes from the expressions $w_{i}=R_{b}(w_{i-1})[P_{i}]$ of (39), and
from $R_{A_{j}}(w_{j})[P_{j}\mod(A_{j}-1)]$ of (42) and
$R_{A_{i}}(w_{i})[P_{i}\mod(A_{i}-1)]$ of (48). On the other hand, the
contribution of the non-commutativity of the operation $*$ comes from the
multiplication by $x_{i-1}$ from left or from right in (48).

The next Theorem is a direct consequence from Theorem 2 and the Proposition 5.

######  Theorem 4 (Basic theorem for exponentiation).

Let $x,y\in\mathbb{E}_{(p-1)^{2}}^{*}$. For every
$(\mathbf{A},{\mathfrak{b}_{1}}),(\mathbf{B},{\mathfrak{b}_{2}})\xleftarrow{\mathbf{r}}\mathbb{L}$

$(x*y)^{(\mathbf{A},{\mathfrak{b}_{1}})}=x^{(\mathbf{A},{\mathfrak{b}_{1}})}*y^{(\mathbf{A},{\mathfrak{b}_{1}})},$
(51)

and

$x^{(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})}=\big{(}x^{(\mathbf{A},{\mathfrak{b}_{1}})}\big{)}^{(\mathbf{B},{\mathfrak{b}_{2}})}=\big{(}x^{(\mathbf{B},{\mathfrak{b}_{2}})}\big{)}^{(\mathbf{A},{\mathfrak{b}_{1}})}=x^{(\mathbf{B},{\mathfrak{b}_{2}})(\mathbf{A},{\mathfrak{b}_{1}})}.$
(52)

∎

Note that different values of bases $\mathfrak{b}_{1}$ and $\mathfrak{b}_{2}$
in Theorem 4 do not affect the application of Theorem 2, since Theorem 2 holds
true for any bracketing shapes $\mathbf{A}$ and $\mathbf{B}$.

The arithmetic (Logarithmetic) for indices $(\mathbf{A},{\mathfrak{b}_{1}})$
and $(\mathbf{B},{\mathfrak{b}_{2}})$ is thus implicitly defined with Theorem
2 and Definition 5. Namely,
$(\mathbf{C},{\mathfrak{b}_{3}})=(\mathbf{A},{\mathfrak{b}_{1}})+(\mathbf{B},{\mathfrak{b}_{2}})$
iff
$x^{(\mathbf{C},{\mathfrak{b}_{3}})}=x^{(\mathbf{A},{\mathfrak{b}_{1}})}*x^{(\mathbf{B},{\mathfrak{b}_{2}})}$,
and
$(\mathbf{D},{\mathfrak{b}_{4}})=(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})$
iff
$x^{(\mathbf{D},{\mathfrak{b}_{4}})}=(x^{(\mathbf{A},{\mathfrak{b}_{1}})})^{(\mathbf{B},{\mathfrak{b}_{2}})}$
for all $x\in\mathbb{E}_{p^{2}}$.

######  Proposition 6.

Let $(\mathbf{A},{\mathfrak{b}_{1}})=(a,a_{s},\mathfrak{b}_{1})$ and
$(\mathbf{B},{\mathfrak{b}_{2}})=(b,b_{s},\mathfrak{b}_{2})$ be two power
indices where $a,b\in\mathbb{Z}^{+}$, and let
$(c,c_{s},\mathfrak{b}_{3})=(\mathbf{C},{\mathfrak{b}_{3}})=(\mathbf{A},{\mathfrak{b}_{1}})+(\mathbf{B},{\mathfrak{b}_{2}})$
and
$(d,d_{s},\mathfrak{b}_{4})=(\mathbf{D},{\mathfrak{b}_{3}})=(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})$.
Then, $c=a+b$ and $d=ab$.

###### Proof.

The proof is by direct application of Theorem 2 for powers in entropic
groupoids. ∎

While we know the values of $c$ and $d$ in $(\mathbf{C},{\mathfrak{b}_{3}})$
and $(\mathbf{D},{\mathfrak{b}_{4}})$, we do not know explicitly the shapes
$c_{s}$ and $d_{s}$.

######  Open Problem 4.

For a given entropoid $\mathbb{E}_{p^{2}}$ and two power indices
$(\mathbf{A},{\mathfrak{b}_{1}})$ and $(\mathbf{B},{\mathfrak{b}_{2}})$ as in
Definition 19 find the explicit forms for $(\mathbf{C},{\mathfrak{b}_{1}})$
and $(\mathbf{D},{\mathfrak{b}_{2}})$ such that
$(\mathbf{C},{\mathfrak{b}_{3}})=(\mathbf{A},{\mathfrak{b}_{1}})+(\mathbf{B},{\mathfrak{b}_{2}})$
and
$(\mathbf{D},{\mathfrak{b}_{3}})=(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})$.

Despite the efficiency of the procedure for non-associative and non-
commutative exponentiation given in Definition 20, we have to notice that for
a fixed base $\mathfrak{b}$ there are many bracketing shapes that are omitted
and can not be produced with the expressions (39) - (49). Apparently, for
$\mathfrak{b}=2$ the pattern
$a_{s}=[P_{0},P_{1},\ldots,P_{k}]_{\mathfrak{b}-1}$ where $0\leq
P_{i}\leq\mathfrak{b}-2$ for $i=0,\ldots,k$ becomes a constant pattern
$a_{s}=[0,0,\ldots,0]$, (that we denote shortly by $\mathbf{[0]}$) and only
the conditions for even $P_{i-1}$ apply in (48).

Still, we can use the limitations of Definition 20 for good: the fixed pattern
related to the base $\mathfrak{b}=2$ can help us propose heuristics for
efficient finding of generators for $(\mathbb{E}^{*}_{(p-1)^{2}},*)$. For that
purpose, let us first give several definitions and propositions about the
subgroupoids generated by elements of $\mathbb{E}_{p^{2}}$ with
${(\mathbf{A},2)}=(a,a_{s},2)=(a,\mathbf{[0]},2)$ indices and with general
indices $\mathbf{A}$.

######  Definition 21.

For every $x=(x_{1},x_{2})\in\mathbb{E}_{p^{2}}$, we define the set $\langle
x\rangle_{2}$ as

$\langle x\rangle_{2}=\\{x^{(\mathbf{A},2)}\ |\
(\mathbf{A},2)=(a,\mathbf{[0]},2),a\in\mathbb{Z}^{+}\\},$ (53)

and the set $\langle x\rangle$ as

$\langle x\rangle=\\{x^{\mathbf{A}}\ |\
\mathbf{A}=(a,a_{s}),a\in\mathbb{Z}^{+},a_{s}\text{\ a bracketing shape}\\}.$
(54)

We say the subgroupoid $(\langle x\rangle_{2},*)=(\mathbb{E}^{*}_{|\langle
x\rangle_{2}|},*)$ is a multiplicative cyclic subgroupoid of
$\mathbb{E}_{p^{2}}$ of order $|\langle x\rangle_{2}|$, and $(\langle
x\rangle,*)=(\mathbb{E}^{*}_{|\langle x\rangle|},*)$ is a multiplicative
subgroupoid of $\mathbb{E}_{p^{2}}$ of order $|\langle x\rangle|$.

Without a proof which is left as an exercise, we give the following two
propositions

######  Proposition 7.

If $s(x)_{2}=|\langle x\rangle_{2}|$ is the size of the set $\langle
x\rangle_{2}$, then

$s(x)_{2}\ |\ 2(p-1),$ (55)

and

$s_{max}(x)_{2}=\max_{x\in\mathbb{E}_{p^{2}}}(s(x)_{2})=2(p-1).$ (56)

∎

######  Proposition 8.

If $s(x)=\ |\langle x\rangle|$ is the size of the set $\langle x\rangle$, then

$s(x)\ |\ (p-1)^{2}$ (57)

and

$s_{max}(x)=\max_{x\in\mathbb{E}_{p}}s(x)=(p-1)^{2}.$ (58)

∎

The problem of finding an explicit analytical expression for the group
generators is still an open problem. One version of that problem is the famous
Artin’s conjecture on primitive roots [20]. However, there are efficient
heuristic algorithms that find generators of the multiplicative group of a
finite field (for example, see [21][Alg. 4.84, Note 4.82, Alg. 4.86]). We
especially point out the efficient algorithm Alg 4.86 in [21] for finding a
generator of $\mathbb{F}^{*}_{p}$ where $p$ is a safe prime. Inspired by that
algorithm, we propose here an efficient heuristic algorithm for finding a
generator $g$ of the maximal multiplicative quasigroup
$(\mathbb{E}^{*}_{(p-1)^{2}},*)$.

######  Definition 22.

A safe prime $p$ is a prime of the form $p=2q+1$ where $q$ is also a prime.

######  Conjecture 1.

Let $\mathbb{E}_{p^{2}}$ be an entropoid defined with a $\lambda$ bit safe
prime $p$, and let $g\in\mathbb{E}^{*}_{(p-1)^{2}}$. If the following
conditions are true

$\displaystyle g$ $\displaystyle\neq g^{(p,\mathbf{[0]},2)}$ (59)
$\displaystyle g*g$ $\displaystyle\neq g^{(p-1,\mathbf{[0]},2)}$ (60)
$\displaystyle(g*(g*g))$ $\displaystyle\neq g^{(p-2,\mathbf{[0]},2)}$ (61)
$\displaystyle(g*(g*g))$ $\displaystyle\neq((g*g)*g)$ (62)
$\displaystyle(g*(g*(g*g)))$ $\displaystyle\neq((g*(g*g))*g),$ (63)

then the probability that $g$ is the generator of $\mathbb{E}^{*}_{(p-1)^{2}}$
is

$\displaystyle Pr[g\text{ is generator of }G^{*}]$ $\displaystyle>1-\epsilon,\
\text{where }\epsilon<\frac{1}{2^{\lambda}}.$ (64)

The corresponding algorithm coming from Conjecture 1 is Algorithm 1.

Algorithm 1 $\mathtt{Gen}$: Find a generator $g$ for the multiplicative
quasigroup $(\mathbb{E}^{*}_{(p-1)^{2}},*)$.
Input: $\lambda$ bit safe prime $p$ and
$a_{3},a_{8},b_{2},b_{7}\in\mathbb{F}_{p}$ that define $\mathbb{E}_{p^{2}}$;
Output: Generator $g$ for $(\mathbb{E}^{*}_{(p-1)^{2}},*)$.

1:repeat

2: Set $Success\leftarrow\mathtt{True}$;

3: Choose random element $g\in G^{*}$;

4: Set $Success\leftarrow\big{(}Success\mathtt{\ and\ }(g\neq
g^{(p,\mathbf{[0]},2)})\big{)}$

5: Set $Success\leftarrow\big{(}Success\mathtt{\ and\ }(g*g\neq
g^{(p-1,\mathbf{[0]},2)})\big{)}$

6: Set $Success\leftarrow\big{(}Success\mathtt{\ and\ }(\ (g*(g*g))\neq
g^{(p-2,\mathbf{[0]},2)})\big{)}$

7: Set $Success\leftarrow\big{(}Success\mathtt{\ and\ }(\
(g*(g*g))\neq((g*g)*g))\big{)}$

8: Set $Success\leftarrow\big{(}Success\mathtt{\ and\ }(\
(g*(g*(g*g)))\neq((g*(g*g))*g))\big{)}$

9:until $Success$

10:Return $g$.

For a detailed demonstration of the Proposition 7, Proposition 8 and
Conjecture 1 see the Appendix A.

######  Open Problem 5.

For a given entropoid $\mathbb{E}_{p^{2}}$ prove the Conjecture 1 or construct
another exact or probabilistic efficient algorithm for finding generator of
$\mathbb{E}^{*}_{(p-1)^{2}}$.

A direct consequence from Proposition 7 and Proposition 8 is the following
corollary.

######  Corollary 3.

Let $g$ obtained with the Algorithm 1 be a generator of
$\mathbb{E}^{*}_{(p-1)^{2}}$, where $p=2q+1$ is a safe prime. Let
$y\xleftarrow{\mathbf{r}}\mathbb{E}^{*}_{(p-1)^{2}}$ be a randomly chosen
element from $\mathbb{E}^{*}_{(p-1)^{2}}$. Then the probability that there
exists a power index $(\mathbf{A},2)$ such that $y=g^{(\mathbf{A},2)}$ is

$Pr(\\{\exists(\mathbf{A},2)\text{ and }y=g^{(\mathbf{A},2)}\\})=\frac{1}{q}.$
(65)

###### Proof.

The proof of this Corollary is just a direct ratio between the size of the
cyclic subgroupoid and the size of the maximal entropic quasigroup:

$\frac{s_{max}(x)_{2}}{s_{max}(x)}=\frac{2(p-1)}{(p-1)^{2}}=\frac{1}{q}.$

∎

Having a heuristics for finding generators of the maximal quasigroup
$\mathbb{E}^{*}_{(p-1)^{2}}$, where $p=2q+1$ is a safe prime, it would be also
very beneficial if we can find generators for the Sylow $q$-subquasigroup
$\mathbb{E}^{*}_{q^{2}}$.

######  Conjecture 2.

Let $g$ be a generator of $\mathbb{E}^{*}_{(p-1)^{2}}$, where $p\geq 11$. Then

$g_{q}=(g*(g*(g*((g*g)*g)))),$ (66)

is the generator of the Sylow $q$-subquasigroup $\mathbb{E}^{*}_{q^{2}}$.

The corresponding algorithm coming from Conjecture 2 is Algorithm 2.

Algorithm 2 $\mathtt{GenQ}$: Find a generator $g_{q}$ for the Sylow
$q$-subquasigroup $\mathbb{E}^{*}_{q^{2}}$.
Input: $\lambda$ bit safe prime $p$ and
$a_{3},a_{8},b_{2},b_{7}\in\mathbb{F}_{p}$ that define $\mathbb{E}_{p^{2}}$;
Output: Generator $g_{q}$ for $\mathbb{E}^{*}_{q^{2}}$.

1:Set $g\leftarrow\mathtt{Gen}(\lambda,p,a_{3},a_{8},b_{2},b_{7})$;

2:Set $g_{q}\leftarrow(g*(g*(g*((g*g)*g))))$;

3:Return $g_{q}$.

######  Proposition 9.

Let $g$ be a generator of $\mathbb{E}^{*}_{(p-1)^{2}}$. Then for every
bracketing shape
$(\mathbf{A},\mathfrak{b})=(a,a_{s},\mathfrak{b})\in\mathbb{L}$ the following
relation hold:

$\bigg{(}g^{(\mathbf{A},\mathfrak{b})}\bigg{)}^{(p-1,\mathbf{[0]},2)}=\left\\{\begin{array}[]{rl}\mathbf{1}_{*},&\text{
if }a\text{ is even},\\\ \boxminus\mathbf{1}_{*},&\text{ if }a\text{ is
odd}.\end{array}\right.\\\ $ (67)

###### Proof.

We use the Theorem 4 and Proposition 6 to deduce that when working with base
$b=2$ we work with a cyclic groupoid. Then from Proposition 7 we know that the
order of $x=g^{(\mathbf{A},\mathfrak{b})}$ is $2(p-1)$. That means that the
order of $y=x^{(p-1,\mathbf{[0]},2)}$ is 2 i.e. $y^{2}=y*y=\mathbf{1}_{*}$.
Thus $y$ belongs to the set of square roots of the left unit $\mathbb{S}(p)$.
Now, if $y$ takes any value other than $\mathbf{1}_{*}$ or
$\boxminus\mathbf{1}_{*}$ it will lead to a result that the order of $x$ is
greater than $2(p-1)$ which is a contradiction. This leaves only two
possibilities: $y=\mathbf{1}_{*}$ or $y=\boxminus\mathbf{1}_{*}$. Again from
Theorem 4 and Proposition 6 we get that there must exist an index
$(\mathbf{B},2)=(b,\mathbf{[0]},2)$ such that
$(\mathbf{B},2)=(\mathbf{A},\mathfrak{b})(p-1,\mathbf{[0]},2)$. Thus
$b=a(p-1)$, and the result $y$ will depend on the parity of $a$. ∎

######  Proposition 10.

Let $g_{q}$ be a generator of the Sylow $q$ quasigroup
$\mathbb{E}^{*}_{q^{2}}$. Then for every bracketing shape
$(\mathbf{A},\mathfrak{b})=(a,a_{s},\mathfrak{b})\in\mathbb{L}$ the following
relations hold:

$\displaystyle\bigg{(}g_{q}^{(\mathbf{A},\mathfrak{b})}\bigg{)}^{(p-1,\mathbf{[0]},2)}$
$\displaystyle=\mathbf{1}_{*}$ (68)
$\displaystyle\bigg{(}g_{q}^{(\mathbf{A},\mathfrak{b})}\bigg{)}^{(q,\mathbf{[0]},2)}$
$\displaystyle=y,$ (69)

where $y$ belongs in a subset of the set of square roots of the left unit i.e.
$y\in\mathbb{S}_{q}(p)\subseteq\mathbb{S}(p)$, such that
$|\mathbb{S}_{q}(p)|=q$.

###### Proof.

Similar arguments hold for this situation with a distinction that now, the set
of all values $x=g_{q}^{(\mathbf{A},\mathfrak{b})}$ have order $q$ instead of
$2q$ that was in the previous case. That, means
$x^{(p-1,\mathbf{[0]},2)}=x^{(2q,\mathbf{[0]},2)}=\mathbf{1}_{*}$ and again
putting $y=x^{(q,\mathbf{[0]},2)}$ we have that $y^{2}=y*y=\mathbf{1}_{*}$.
So, $y$ must belong to $\mathbb{S}(p)$. If
$\mathbb{S}_{q}(p)\subseteq\mathbb{S}(p)$ is the subset from where $y$
receives its values, its cardinality must be $q$, otherwise it will generate
the whole multiplicative quasigroup $\mathbb{E}^{*}_{(p-1)^{2}}$. ∎

###  2.4 Dichotomy between odd and even bases

There are a few more issues with the bracketing shapes defined in Definition
20 that need to be discussed. As we see in Proposition 7 and Proposition 8,
the choice of the base $b$ influence the size of the generated sets when
raising to powers. It also influence the probability an element
$x\in\mathbb{E}^{*}_{(p-1)^{2}}$ to be an image of some generator raised to
some power index i.e.
$x=g^{(\mathbf{A},\mathfrak{b})}=g^{(a,a_{s},\mathfrak{b})}$. This means,
since $g$ is a generator, there is certainly some power index
$(\mathbf{A},\mathfrak{b})=(a,a_{s},\mathfrak{b})$ for which
$x=g^{(\mathbf{A},\mathfrak{b})}$, but when distributed over all patterns
$a_{s}=[P_{0},P_{1},\ldots,P_{k}]_{\mathfrak{b}-1}$, for some elements $x$
there will be many patterns that give $x=g^{(a,a_{s},\mathfrak{b})}$, while
for other elements $x$ there will be a few. To formalize this discussion we
adapt the approach that Smith proposed in [22] about the Shannon entropy of
completely partitioned sets, and the relations between Shannon entropy and
several instances of Rényi entropy (such as collision entropy and min-entropy)
studied by Cachin in [23] (see also the work of Skórski [24]).

For a given base $2\leq\mathfrak{b}\leq b_{max}$ and given generator
$g\in\mathbb{E}^{*}_{(p-1)^{2}}$, let us investigate how the sequence of sets
of shapes

$\displaystyle\mathbb{L}(i)=$ $\displaystyle\\{a_{s}\
|a_{s}=[P_{0},\ldots,P_{i}]_{\mathfrak{b}-1},\text{ for all
}P_{j}\in\mathbb{Z}_{\mathfrak{b}-1},j=0,\ldots,i\\},$ (70)

each with $(\mathfrak{b}-1)^{i}$ elements, are partitioned into $r_{i}$ sets
of mutually exclusive subsets

$\displaystyle\xi_{i}=$ $\displaystyle\\{C_{i,1},\ldots,C_{i,r_{i}}\\}.$ (71)

The partitioning is done due to the following conditions:

$\displaystyle\forall a_{s_{1}},a_{s_{2}}\in C_{i,j},$ $\displaystyle\ \ \
g^{(\mathfrak{b}^{i-1},a_{s_{1}},\mathfrak{b})}=g^{(\mathfrak{b}^{i-1},a_{s_{2}},\mathfrak{b})}=g_{i,j},$
(72) $\displaystyle\forall a_{s_{1}}\in C_{i,j_{1}},\text{ and }\forall
a_{s_{2}}\in C_{i,j_{2}},$ $\displaystyle\ \ \
g^{(\mathfrak{b}^{i-1},a_{s_{1}},\mathfrak{b})}\neq
g^{(\mathfrak{b}^{i-1},a_{s_{2}},\mathfrak{b})},\text{ when }j_{1}\neq j_{2}.$
(73)

As a short notation we write
$g^{(\mathfrak{b}^{i-1},\mathbb{L}(i),\mathfrak{b})}$ the set of all powers of
$g$ to $\mathfrak{b}^{i-1}$ with all possible shapes $\mathbb{L}(i)$.

If a shape $a_{s}$ is sampled uniformly at random from $\mathbb{L}(i)$, i.e.
if $a_{s}\xleftarrow{\mathbf{r}}\mathbb{L}(i)$, then
$g^{(\mathfrak{b}^{i-1},a_{s},\mathfrak{b})}$ determines the set $C_{i,j}$
where it belongs. The probability that $a_{s}$ belongs to $C_{i,j}$ depends on
the number of elements $n_{ij}=|C_{i,j}|$ and is calculated as

$\displaystyle p_{ij}=p(C_{i,j})=\frac{n_{ij}}{(b-1)^{i}}.$ (74)

The Shannon entropy $H_{1}$ of the partitioned set $\xi_{i}$ is defined with

$H_{1}(\xi_{i})=-\sum_{j=1}^{r_{i}}p(C_{i,j})\log p(C_{i,j}).$ (75)

Similarly, the Rényi entropy of order $\alpha$ for $\xi_{i}$ is defined as

$H_{\alpha}(\xi_{i})=\frac{1}{1-\alpha}\log\sum_{j=1}^{r_{i}}p(C_{i,j})^{\alpha},$
(76)

with the special instance for $\alpha=2$ which is called the Collision entropy

$H_{2}(\xi_{i})=-\log\sum_{j=1}^{r_{i}}p(C_{i,j})^{2}.$ (77)

Min entropy is defined as

$H_{\infty}(\xi_{i})=-\log\max_{C_{i,j}\in\xi_{i}}p(C_{i,j})=-\log\frac{\max
n_{ij}}{(\mathfrak{b}-1)^{i}}.$ (78)

The ordering relation (see [23, Lemma 3.2.]) among different entropies is

$H_{\infty}(\xi_{i})\leq H_{2}(\xi_{i})\leq H_{1}(\xi_{i})$ (79)

Let us point to the fact that the grouping of the shapes is governed by the
Narayana numbers given in equation (36) in Theorem 3. Thus, for even bases
$\mathfrak{b}$ there are $\mathfrak{b}-1$ classes that partition the set of
all possible shapes with cardinality expressed by the Narayana numbers
$N(\mathfrak{b}-1,i)=\frac{1}{\mathfrak{b}-1}\binom{\mathfrak{b}-1}{i}\binom{\mathfrak{b}-1}{i-1}$.
Since $\mathfrak{b}-1$ in that case is odd, there is one central dominant
Narayana number, and there will be one class of shapes that will have a
dominant number of members. For example, for $\mathfrak{b}=6$, the five
classes have cardinality $\\{1,10,20,10,1\\}$, so the central class is a
dominant one with 20 elements. For $\mathfrak{b}=8$ the seven classes have
cardinality $\\{1,21,105,175,105,21,1\\}$, so the central class is a dominant
one with 175 elements. On the other hand, for odd bases $\mathfrak{b}$, we
have grouping in even number of $\mathfrak{b}-1$ classes, the sequences of
Narayana numbers are completely symmetrical and there is not one but two
dominant classes. For example, for $\mathfrak{b}=7$, the six classes have
cardinality $\\{1,15,50,50,15,1\\}$, so two central classes are dominant with
50 elements.

For bigger bases $\mathfrak{b}$ we have observed the same pattern: for even
bases $\mathfrak{b}=2\mathfrak{b}_{1}$ the values of $\max n_{ij}$ that
determine the min entropy $H_{\infty}$ are increasing with the same
exponential speed as the values of $(\mathfrak{b}-1)^{i}$ increase. Looking at
the equation (78) it makes $\frac{\max n_{ij}}{(\mathfrak{b}-1)^{i}}$ to trend
to 1 i.e. $H_{\infty}$ trends to 0.

For odd bases $\mathfrak{b}=2\mathfrak{b}_{1}+1$, while there is increase of
$\max n_{ij}$ as $i$ increases, the ratio $\frac{\max
n_{ij}}{(\mathfrak{b}-1)^{i}}$ is actually decreasing, which makes
$H_{\infty}$ to increase.

See Appendix B for details about this observed dichotomy between even and odd
bases.

We summarize this discussion with the following Conjecture

######  Conjecture 3.

Let $g\in\mathbb{E}^{*}_{(p-1)^{2}}$ be a generator of the maximal
multiplicative subgroupoid of a given entropoid $\mathbb{E}_{p^{2}}$. For
every even base $\mathfrak{b}=2b_{1}<b_{max}$ the values
$n(\mathfrak{b},i)=\max n_{ij}$ are given by the following relation:

$n(\mathfrak{b},i)=(\mathfrak{b}-1)\bigg{(}(\mathfrak{b}-1)^{i-1}-(\mathfrak{b}-2)^{i-1}\bigg{)},$
(80)

which makes the following relation about the min entropy $H_{\infty}$

$H_{\infty}(\xi_{i})=1-\left(\frac{\mathfrak{b}-2}{\mathfrak{b}-1}\right)^{i-1}.$
(81)

The discussion so far was about the entropy of the pattern sets
$\mathbb{L}(i)$ partitioned to sets $\xi_{i}$ induced by rising a generator
$g$ to a special forms of powers $g^{(a,a_{s_{1}},\mathfrak{b})}$ where
$a=\mathfrak{b}^{i-1}$. This basically means that in the procedure for rising
to a power we use only the equations (39) and (42), since the numbers $a$ in
that case have in the little-endian notation the following forms
$a=[0,0,\ldots,1]_{\mathfrak{b}}$. One might hope that the entropy of $\xi$
for even bases will improve significantly if we work with generic numbers $a$
with a lot of non-zero digits $a=[A_{0},A_{1},\ldots,A_{k}]_{\mathfrak{b}}$.
However, that is not the case as it is showed in Figure 2 in Appendix B.

The experiments were conducted by generating a random entropoid
$\mathbb{E}_{p^{2}}$ with safe prime number $p$ with $\lambda$ bits. After
finding a generator $g$ for the multiplicative quasigroup
$\mathbb{E}^{*}_{(p-1)^{2}}$, we generated one random number
$a\in\mathbb{Z}_{(p-1)^{2}}$, and then we run the procedure of rising to a
power $g^{(a,a_{s},\mathfrak{b})}$ for random shapes
$a_{s}=[P_{0},\ldots,P_{i}]_{\mathfrak{b}-1}$ until the first collision.

As the size of the finite entropoid $\mathbb{E}_{p^{2}}$ increases, the
collision entropy for different even bases remains constant. On the other
hand, with the odd bases the situation is completely different. We see in
Figure 3 that as the size of the entropoid increases, the collision entropy
increases as well. A loose observation is that for $p$ being $\lambda$ bits
long, the collision entropy is $H_{2}(\xi)\approx\frac{\lambda}{2}$.

######  Open Problem 6.

For odd bases $\mathfrak{b}$ find proofs and find tighter bounds for the
collision entropy $H_{2}(\xi)$.

##  3 Hard Problems in Entropoid Based Cryptography

We now have enough mathematical understanding and heuristic evidence to
precisely formulate several hard problems in entropoid based cryptography, in
a similar fashion as the discrete logarithm problem, and computational and
decisional Diffie-Hellman problems are defined within the group theory. We
will use the notion of negligible function
$\mathtt{negl}:\mathbb{N}\mapsto\mathbb{R}$ for the function that for every
$c\in\mathbb{N}$ there is an integer $n_{c}$ such that $\mathtt{negl}(n)\leq
n^{-c}$ for all $n\geq n_{c}$.

######  Definition 23 (Discrete Entropoid Logarithm Problem (DELP)).

An entropoid $\mathbb{E}_{p^{2}}$ and a generator $g_{q_{i}}$ of one of its
Silow subquasigroups $\mathbb{E}^{*}_{\nu}$ are publicly known. Given an
element $y\in\mathbb{E}^{*}_{\nu}$ find a power index
$(\mathbf{A},\mathfrak{b})$ such that
$y=g_{q_{i}}^{(\mathbf{A},\mathfrak{b})}$.

######  Definition 24 (Computational Entropoid Diffie–Hellman Problem
(CEDHP)).

An entropoid $\mathbb{E}_{p^{2}}$ and a generator $g_{q_{i}}$ of one of its
Silow subquasigroups $\mathbb{E}^{*}_{\nu}$ are publicly known. Given
$g_{q_{i}}^{(\mathbf{A},\mathfrak{b}_{1})}$ and
$g_{q_{i}}^{(\mathbf{B},\mathfrak{b}_{2})}$, where
$(\mathbf{A},{\mathfrak{b}_{1}}),(\mathbf{B},{\mathfrak{b}_{2}})\xleftarrow{\mathbf{r}}\mathbb{L}$,
compute
$g_{q_{i}}^{(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})}$.

The similar reduction as with DLP and CDH is true for DELP and CEDHP: CEDHP
$\leq$ DELP i.e. CEDHP is no harder than DELP. Namely, if an adversary can
solve DELP, it can find $(\mathbf{A},{\mathfrak{b}_{1}})$ and
$(\mathbf{B},{\mathfrak{b}_{2}})$ and compute
$g_{q_{i}}^{(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})}$.

######  Definition 25 (Decisional Entropoid Diffie–Hellman Problem (DEDHP)).

An entropoid $\mathbb{E}_{p^{2}}$ and a generator $g_{q_{i}}$ of one of its
Silow subquasigroups $\mathbb{E}^{*}_{\nu}$ are publicly known. Given
$g_{q_{i}}^{(\mathbf{A},\mathfrak{b}_{1})}$,
$g_{q_{i}}^{(\mathbf{B},\mathfrak{b}_{2})}$ and
$g_{q_{i}}^{(\mathbf{C},\mathfrak{b}_{3})}$, where
$(\mathbf{A},{\mathfrak{b}_{1}}),(\mathbf{B},{\mathfrak{b}_{2}}),(\mathbf{C},\mathfrak{b}_{3})\xleftarrow{\mathbf{r}}\mathbb{L}$,
decide if
$(\mathbf{C},\mathfrak{b}_{3})=(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})$
or $(\mathbf{C},\mathfrak{b}_{3})\xleftarrow{\mathbf{r}}\mathbb{L}$.

Again, the similar reduction as with classical CDH and DDH, holds here: DEDHP
$\leq$ CEDHP i.e. DEDHP is no harder than CEDHP, since if an adversary can
solve CEDHP, it will compute
$g_{q_{i}}^{(\mathbf{A},{\mathfrak{b}_{1}})(\mathbf{B},{\mathfrak{b}_{2}})}$
and will compare it with $g_{q_{i}}^{(\mathbf{C},\mathfrak{b}_{3})}$.

As with the classical DDH for the multiplicative group $\mathbb{F}_{p}^{*}$
where DDH is easy problem, but for its quadratic residues subgroup $QR(p)$,
DDH is hard, we have a similar situation for DEDHP which is stated in the
following Lemma.

######  Lemma 3.

Let $\mathbb{E}_{p^{2}}$ be an entropoid and $g$ be a generator of its maximal
quasigroup $\mathbb{E}^{*}_{(p-1)^{2}}$. Then there is an efficient algorithm
that solves DEDHP in $\mathbb{E}^{*}_{(p-1)^{2}}$.

###### Proof.

The distinguishing algorithm can be built based on the distinguishing property
described in Proposition 9. ∎

On the other hand, based on Proposition 10 we can give the following plausible
conjecture.

######  Conjecture 4.

Let $\mathbb{E}_{p^{2}}$ be an entropoid, where $p=2q+1$ is a safe prime and
$g_{q}$ is the generator of its Sylow $q$-subquasigroup
$\mathbb{E}^{*}_{q^{2}}$. Then there is no algorithm $\mathcal{A}$ that solves
DEDHP in $\mathbb{E}^{*}_{q^{2}}$ with significantly higher advantage over the
strategy of uniformly random guesses for making the decisions.

######  Theorem 5.

If the DEDHP conjecture is true, then a Diffie-Hellman key exchange protocol
over finite entropoids is secure in the Canetti-Krawczyk model of passive
adversaries [25].

We will make here a slight digression, and will relate the classical DLP with
another problem over the classical group theory: finding roots. Then we will
just translate it for the case of finite entropoids.

######  Definition 26 (Computational Discrete Root Problem (CDRP)).

A group $G$ of order $N$ and its generator $g$ are publicly known. Given
$y=x^{b}$ and $b$, where $b\xleftarrow{\mathbf{r}}\mathbb{Z}_{N}$, compute
$x=\sqrt[b]{y}$.

In general, CDRP is an easy problem. However, there are instances where this
problem is still hard, and we will discuss those instances now.

One of the best generic algorithms for solving CDRP is by Johnston [26]. As
mentioned there, CDRP can be reduced to solving the DLP in $G$, i.e. CDRP
$\leq$ DLP. First of all $b$ is supposed to divide $N$, otherwise due to the
cyclic nature of the group $G$, it is a straightforward technique that finds
the $b$-th root: $x=\sqrt[b]{y}=y^{\frac{1}{b}\mod N}$. Let us denote
$g_{1}=g^{b}$, where $g$ is the generator of $G$. If we have a DLP solver for
$G$, and if there exists a solution for the equation $y=g_{1}^{a}$, then DLP
will find $a$ efficiently. Then we can compute $x$ as $x=g^{a}$. Johnston
noticed that if $\frac{N}{b}$ is small, then DLP solver will be efficient with
a complexity $O(\sqrt{\frac{N}{b}})$. On the other hand if $\frac{N}{b}$ is
not that small, Johnston made a reduction to another DLP solver, by heavily
using the reach algebraic structure of the finite cyclic groups generated by a
gennerator $g$. The other DLP solver computes a discrete log of
$x^{\frac{N}{b^{k}}}$ using the generator $g^{\frac{N}{b^{k-1}}}$, where $k$
is the largest power of $b$ such that $b^{k}$ still divides $N$. The generic
complexity of this DLP solver is $O((k-1)\sqrt{b})$. Now let us work in finite
field $\mathbb{F}_{p}$ with the following prime number: $p=2q^{3}+1$ where $q$
has $\lambda$ bits. So, if fix the $b$-th root to be exactly $b=q$, then for
the second DLP solver in the Johnson technique we have that $k=3$, and it has
an exponential complexity of $O((k-1)2^{\frac{\lambda}{2}})$.

######  Definition 27 (Computational Discrete Entropoid Root Problem (CDERP)).

An entropoid $\mathbb{E}_{p^{2}}$ and a generator $g$ of its multiplicative
quasigroups $\mathbb{E}^{*}_{(p-1)^{2}}$ are publicly known. Given
$y=x^{(\mathbf{B},\mathfrak{b})}$ and $(\mathbf{B},\mathfrak{b})$, where
$x,y\in\mathbb{E}^{*}_{(p-1)^{2}}$ and
$(\mathbf{B},\mathfrak{b})\xleftarrow{\mathbf{r}}\mathbb{L}$, compute
$x=\sqrt[(\mathbf{B},\mathfrak{b})]{y}$.

A similar discussion applies for CDERP that it is not harder than DELP, i.e.,
CDERP $\leq$ DELP. However, notice that it is not possible directly to extend
the Johnson technique to finite entropoids due to the lack of the associative
law and because $\mathbb{E}^{*}_{(p-1)^{2}}$ is not a cyclic structure. So, at
this moment, we can make the following plausible conjecture.

######  Conjecture 5.

Let $\mathbb{E}_{p^{2}}$ be an entropoid, where $p=2q+1$ is a safe prime with
$\lambda$ bits and $g$ is the generator of its multiplicative quasigroups
$\mathbb{E}^{*}_{(p-1)^{2}}$. Let $\mathcal{A}$ be an algorithm that solves
CDERP in $\mathbb{E}^{*}_{(p-1)^{2}}$. Then the probability, over uniformly
chosen $(\mathbf{B},\mathfrak{b})\xleftarrow{\mathbf{r}}\mathbb{L}$ that
$\mathcal{A}(x^{(\mathbf{B},\mathfrak{b})},(\mathbf{B},\mathfrak{b}))=x$ is
$\mathtt{negl}(\lambda)$.

We want to emphasize one essential comparison between CDRP in cyclic groups
$G$ of order $N$ and CDERP in the multiplicative quasigroups
$\mathbb{E}^{*}_{(p-1)^{2}}$. CDERP is easy problem for almost all root values
$b$ except when $b=q$ in groups that have orders $N$ divisible by $q^{k}$
where $k\geq 2$. CDERP is conjectured that is hard in
$\mathbb{E}^{*}_{(p-1)^{2}}$ (that has order $4q^{2}$) for every randomly
selected root $(\mathbf{B},\mathfrak{b})\xleftarrow{\mathbf{r}}\mathbb{L}$.
The conjecture is based on the fact that currently, there is no developed
Logarithmetic for the succinct power indices, but more importantly, that
$\mathbb{E}^{*}_{(p-1)^{2}}$ is neither a group nor a cyclic structure.

Continuing with the comparisons, let us now compare DELP with the classical
DLP in finite groups or in finite fields. Several differences are notable:

  1. 1.

Operations for DELP are non-associative and non-commutative operations in an
entropic quasigroup $(\mathbb{E}^{*}_{\nu},*)$. At the same time, DLP is
exclusively defined in groups $G$ that are mostly commutative (there are also
DLPs over non-commutative groups, such as the isogenies between elliptical
curves defined over the finite fields).

  2. 2.

All generic algorithms for solving DLP, exclusively without exceptions, use
the fact that the group $G$ is cyclic of order $N$, generated by some
generator element $g$ and that for every element $y\in G$ there is a unique
index $i\in\\{1,\ldots,N\\}$ such that $y=g^{i}$ (in multiplicative notion).
In DELP, there are generators for the multiplicative quasigroup
$\mathbb{E}^{*}_{(p-1)^{2}}$ which has order $(p-1)^{2}$, but
$\mathbb{E}^{*}_{(p-1)^{2}}$ is not a cyclic structure since for every
$y\in\mathbb{E}^{*}_{(p-1)^{2}}$ there are many indices
$(\mathbf{A},\mathfrak{b})$ such that $y=g^{(\mathbf{A},\mathfrak{b})}$, and
finding only one of them will solve the DELP. Thus, at first sight, it might
seem DELP is an easier task than DLP. However, with Proposition 11 (given
below), we show that DLP is no harder than DELP, i.e., DLP $\leq$ DELP.

  3. 3.

We can take a conservative approach for modeling the complexity of solving
DELP, and assume that eventually, an arithmetic (logarithmetic) for the power
indices in finite entropoids will be developed (Open problem 4). In that case,
an adaptation of the generic algorithms for solving DLP, such as Baby-step
giant-step, Pollard rho, Pollard kangaroo, or Pohlig–Hellman for solving DELP,
will address a problem with a search space size $N\approx p^{2}$. Since the
complexity of a generic DLP algorithm is $O(\sqrt{N})$ we get that solving
DELP with classical algorithms could possibly reach a complexity as low as
$O(p)$. Extending this thinking for potential quantum algorithms that will
solve DELP, we estimate that their complexity could potentially be as low as
$O(p^{1/2})$.

######  Proposition 11.

Let $p=2q+1$ is a safe prime number with $\lambda$ bits, and let
$\mathbb{E}_{p^{2}}(a_{3},a_{8},b_{2},b_{7})$ is a given entropoid. If
$\mathcal{A}$ is an efficient algorithm that solves DELP, then there exist an
efficient algorithm $\mathcal{B}$ that solves DLP for every subgroup $\Gamma$
of $\mathbb{F}_{p}^{*}$.

###### Proof.

Let us use the algorithm $\mathcal{A}$ for an entropoid
$\mathbb{E}_{p}(a_{3}=0,a_{8}=1,b_{2}=0,b_{7}=1)$. In that entropoid the
operation $*$ becomes

$(x_{1},x_{2})*(y_{1},y_{2})=(x_{2}y_{1},x_{1}y_{2}).$

Let $\Gamma\subseteq\mathbb{F}_{p}^{*}$ is a nontrivial subgroup. Then, since
$p=2q+1$ where $q$ is a prime number, $\Gamma$ is either the quadratic residue
group $\Gamma=QR(p)$ of order $q$ or $\Gamma=\mathbb{F}_{p}^{*}$ of order
$(p-1)$. Let $\gamma$ be a generator of $\Gamma$. Apparently $\gamma\neq 0$
i.e. $\gamma\neq-\frac{a_{3}}{a_{8}}$ and $\gamma\neq-\frac{b_{2}}{b_{7}}$.
Then from Proposition 4 it follows that $g=(\gamma,\gamma)$ is a generator of
some subgroupoid $(\mathbb{E}^{*}_{\nu},*)$, and the operation of
exponentiation of $g$ in the entropoid, reduces to exponentiation in a finite
field i.e.

$g^{(\mathbf{A},b)}=g^{(a,a_{s},b)}=(\gamma^{a},\gamma^{a}).$

Thus, for every received $\gamma^{a}$, the algorithm $\mathcal{B}$ constructs
the pair $(\gamma^{a},\gamma^{a})$ and asks the algorithm $\mathcal{A}$ to
solve it. $\mathcal{A}$ solves it efficiently and returns
$(\mathbf{A},\mathfrak{b})$, from which $\mathcal{B}$ extracts the discrete
logarithm $a$. ∎

So, in its generality, and currently without the arithmetic for the succinct
power indices defined with Definition 19, the best algorithms for solving DELP
are practically the generic algorithms for random function inversion, i.e.,
the generic guessing algorithms. Two of them are given as Algorithm 3 and
Algorithm 4.

Algorithm 3 Randomized search solver for (DELP)
Input: Entropoid $\mathbb{E}_{p^{2}}$, generator $g$ of
$\mathbb{E}_{(p-1)^{2}}^{*}$ and $y\in\mathbb{E}_{(p-1)^{2}}^{*}$.
Output:$(\mathbf{A},\mathfrak{b})$ such that
$y=g^{(\mathbf{A},\mathfrak{b})}$.

1:repeat

2: Set $(\mathbf{A},\mathfrak{b})\xleftarrow{\mathbf{r}}\mathbb{L}$, where
$\mathfrak{b}\geq 3$;

3:until $y=g^{(\mathbf{A},\mathfrak{b})}$

4:Return $(\mathbf{A},\mathfrak{b})$.

Algorithm 4 Brute force search solver for (DELP)
Input: Entropoid $\mathbb{E}_{p^{2}}$, generator $g$ of
$\mathbb{E}_{p^{2}}^{*}$ and $y\in\mathbb{E}_{p^{2}}^{*}$.
Output:$(\mathbf{A},\mathfrak{b})$ such that
$y=g^{(\mathbf{A},\mathfrak{b})}$.

1:Set $\mathfrak{b}=2\mathfrak{b}^{\prime}+1$, and $\mathfrak{b}\leq b_{max}$;

2:for $a=2$ to $(p-1)^{2}$ do

3: for $a_{s}\in\mathbb{L}[a,\mathfrak{b}]$ do

4: if $y=g^{(a,a_{s},\mathfrak{b})}$ then

5: Return $(\mathbf{A},\mathfrak{b})=(a,a_{s},\mathfrak{b})$.

6: end if

7: end for

8:end for

###  3.1 DELP is secure against Shor’s quantum algorithm for DLP

Shor’s quantum algorithm breaks algorithms that rely on the difficulty of DLP
defined over finite commutative groups. One of Shor’salgorithm’s crucial
components is the part of its quantum circuit that calculates the modular
arithmetic for raising $g$ to any power, with the repeated squaring. That part
of the Shor’s quantum circuit for the repeated squaring works if the related
group multiplication operation is associative and commutative. There are no
variants of Shor’s algorithm or any other quantum algorithm that will work if
the underlying algebraic structure is non-commutative. Additionally, DELP is
defined over entropoids that are both non-associative and non-commutative.

A designer of a quantum algorithm for solving DELP faces two challenges:

  1. 1.

Build quantum circuits that implement non-commutative operations of
multiplication $*$.

  2. 2.

Build quantum circuits that perform an unknown pattern of non-associative and
non-commutative multiplications $*$, where the number of possible patterns is
exponentially high.

We have to note that if the used base is $\mathfrak{b}=2$, the bracketing
pattern is known, and there is a possibility to "reuse" the Shor’s circuit.
However, as we see from Corollary 3 the probability that the answer from that
circuit will be correct is $\frac{1}{q}$. Thus, for $q$ being 128 or 256 bits,
it would be a very inefficient quantum algorithm.

##  4 Concrete instances of Entropoid Based Key Exchange and Digital Signature
Algorithms

###  4.1 Choosing Parameters For a Key Exchange Algorithm Based on DELP

Based on the discussion in Section 3 for achieving post-quantum security
levels of $2^{64}$ and $2^{128}$ qubit operations we propose finite entropoids
$\mathbb{E}_{p^{2}}$ to use safe prime numbers $p$ with 128 and 256 bits. For
estimating the number of $*$ operations for performing one power operation, we
use the equation (50). We see that the number depends on the odd base
$\mathfrak{b}$. Additionally, $*$ operation with a pre-computation of
expressions that involve $a_{3},a_{8},b_{2},b_{7}$ can be computed with six
modular additions and six modular multiplications in $\mathbb{F}_{p}$. The
expected number of modular operations and the total communication cost for two
security levels are given in Table 7. We can see that the number of modular
operations increases with $\mathfrak{b}$, while the communication costs in
both directions in total are 64 and 128 bytes, respectively.

A formal description of an unauthenticated Diffie-Hellman protocol over finite
entropoids is given as follows:

Agreed public parameters

  1. 1.

Alice and Bob agree on parameters for
$\mathbb{E}_{p^{2}}(a_{3},a_{8},b_{2},b_{7})$, where $p=2q+1$ is a prime
number with a size of $\lambda=128$ or $\lambda=256$ bits, $q$ is also a prime
number, the values $a_{3},a_{8},b_{2},b_{7}\in\mathbb{F}_{p}$ and operations
for non-commutative and non-associative multiplication and exponentiation are
defined as in Definition 12 and Definition 20

  2. 2.

Alice and Bob agree on the generator
$g_{q}=\mathtt{GenQ}(\lambda,p,a_{3},a_{8},b_{2},b_{7})$

  3. 3.

Alice and Bob agree on odd base $\mathfrak{b}$

Ephemeral key exchange phase

  1. 1.

Alice generates a random power index
$(\mathbf{A},\mathfrak{b})=(a,a_{s},\mathfrak{b})$ where
$a\in\mathbb{Z}^{*}_{p}$

  2. 2.

Alice computes $K_{a}=g_{q}^{(\mathbf{A},\mathfrak{b})}$ and sends it to Bob

  3. 3.

Bob generates a random power index
$(\mathbf{B},\mathfrak{b})=(b,b_{s},\mathfrak{b})$ where
$b\in\mathbb{Z}^{*}_{p}$

  4. 4.

Bob computes $K_{b}=g_{q}^{(\mathbf{B},\mathfrak{b})}$ and sends it to Alice

  5. 5.

Alice computes $K_{ab}=K_{b}^{(\mathbf{A},\mathfrak{b})}$

  6. 6.

Bob computes $K_{ba}=K_{a}^{(\mathbf{B},\mathfrak{b})}$

  7. 7.

$K_{ab}=K_{ba}$.

Table 7: Some efficiency metrics for entropoid based Diffie-Hellman key
exchange.

###  4.2 Digital Signature Scheme Based on CDERP

For defining a digital signature over finite entropoids, let us first fix the
base $\mathfrak{b}=257$. The reason for this is the fact that in that case for
any power index $(\mathbf{B},257)=(b,b_{s},257)$, the bracketing pattern part
$b_{s}=[P_{0},\ldots P_{k}]_{256}$ has a very convenient interpretation as a
list of bytes. Remark: Choosing a base $\mathfrak{b}=257$ might be too
conservative and expensive - making the computations of exponentiation very
slow. All proposed algorithms in this and the next sub-section can be carried
out with $\mathfrak{b}=17$, which is also convenient since the bracketing
patterns, in that case, become 4-bit nibbles. However, since this is the first
introduction of a new signature scheme based on a new hardness problem, we
propose more conservative parameters.

In the rest of this sub-section for the power indices instead of writing
$(\mathbf{B},257)$ we will omit the base part and will simply write the bold
letter $\mathbf{B}$ meaning $\mathbf{B}=(b,b_{s},257)$. We also assume that
the public parameters $\mathbb{E}_{p^{2}}(a_{3},a_{8},b_{2},b_{7})$, where
$p=2q+1$ is a prime number with a size of $\lambda\in\\{128,192,256\\}$ bits,
$q$ is also a prime number and the values
$a_{3},a_{8},b_{2},b_{7}\in\mathbb{F}_{p}$ are known and fixed.

We will use the NIST standardized cryptographic hash function
$\mathtt{SHAXXX}$ where $\mathtt{XXX}\in\\{256,384,512\\}$ and will use the
following notation. Let $M$ be any message, and let
$\mathtt{SHAXXX}(M)=h_{1}||h_{2}$ where
$|h_{1}|=|h_{2}|=\frac{\mathtt{XXX}}{2}$ bits. We define
$truncate_{\mathbb{L}}(\mathtt{SHAXXX}(M))=(h,h_{s})$ where $h=h_{1}$ and the
sequence of bits of $h_{1}$ are interpreted as a little-endian encoding for a
number $h\in\mathbb{Z}_{2^{\frac{\mathtt{XXX}}{2}}}$. We partition the bits of
$h_{2}$ in a list of $k_{max}\in\\{16,24,32\\}$ bytes $h_{2}=[P_{0},\ldots
P_{k_{max}-1}]_{256}$. Then we compute $k=\log_{257}h-1$. Finally we interpret
$h_{s}$ as a list of the first $k+1$ bytes $h_{s}=[P_{0},\ldots P_{k}]_{256}$.
If $k<k_{max}-1$ we truncate the remaining bytes. The set of all such power
indices $\mathbb{L}[h,257]$ is shortly denoted as $\mathbb{L}_{\mathtt{257}}$.
With this we defined a mapping
$Hash_{\mathtt{XXX}}:\\{0,1\\}^{*}\mapsto\mathbb{L}_{\mathtt{257}}$ as
follows:

$Hash_{\mathtt{XXX}}(M)=truncate_{\mathbb{L}}(\mathtt{SHAXXX}(M))=(h,h_{s},257).$
(82)

The signature scheme is designed by a Fiat-Shamir transformation [27] of an
identification scheme, and it looks similar to Schnorr identification scheme
[28], but the security is based on the hardness of CDERP.

Note: In this first version of the paper, we are not giving clear formal proof
of the scheme’s security in the EUF-CMA security model (Existential
Unforgeability under Chosen Message Attack). That proof will be given either
as a separate work or in the updated versions of this paper. Instead, we are
giving here an initial discussion about the security properties of the
proposed signature scheme.

Let us call the key generation algorithm $\mathtt{GenKey}$. It is given in
Algorithm 5. We assume that a generator $g$ for the quasigroup
$\mathbb{E}^{*}_{(p-1)^{2}}$ is publicly known and standardized and that a
power index $\mathbf{B}=Hash_{\mathtt{XXX}}(\mathtt{``abc"})$ is also
predetermined and fixed. The message $\mathtt{``abc"}$ can be any string such
as ‘‘This is a seed message for fixing the value of the public root."

Algorithm 5 $\mathtt{GenKey}$: Generate a key pair
$(\mathtt{PrivateKey},\mathtt{PublicKey})$.
Input: ;
Output: $(\mathtt{PrivateKey},\mathtt{PublicKey})$.

1:Set $x\xleftarrow{\mathbf{r}}\mathbb{E}^{*}_{(p-1)^{2}}$

2:Set $\mathtt{PrivateKey}=x$

3:Set $y=x^{\mathbf{B}}$

4:Set $\mathtt{PublicKey}=y$

5:Return $(\mathtt{PrivateKey},\mathtt{PublicKey})$

Let us now describe the following identification scheme:

Prover Verifier
[]
r r← E^*_(p-1)^2
I = r^B
*I
H r← L_257
*H
s = (x * r)^H
*s
checks whether  s^B =? (y * I)^H

Figure 1: An ID scheme based on the hardness of CDERP

Since $I$ is a uniformly random element from $\mathbb{E}^{*}_{(p-1)^{2}}$, and
$\mathbf{H}$ is a uniformly random element from $\mathbb{L}_{\mathtt{257}}$,
the distribution of $s$ is also uniformly random. Thus, an attacker can
simulate the transcripts of honest executions by randomly producing triplets
$(I,\mathbf{H},s)$, without a knowledge of the private key. However, since
$s=\sqrt[\mathbf{B}]{(y*I)^{\mathbf{H}}}$, if the produced transcripts are
verified and true, it implies that the attacker can compute the
$\mathbf{B}$-th root, i.e., can solve the CDERP. From this discussion, we give
(without proof) the following Theorem:

######  Theorem 6.

If the computational discrete entropoid root problem is hard in
$\mathbb{E}^{*}_{(p-1)^{2}}$, then the identification scheme given in Figure
4.2 is secure.

The Fiat-Shamir transformation of the identification scheme presented in
Figure 4.2 gives a digital signature scheme with three algorithms:
$\mathtt{GenKey}$ for key generation (already presented in Algorithm 5),
$\mathtt{Sign}$ for digital signing (given in Algorithm 6) and
$\mathtt{Verify}$ for signature verification (given in Algorithm 7).

Algorithm 6 $\mathtt{Sign}$: Sign a message.
Input: A message $M$, and $\mathtt{PrivateKey}=x$;
Output: $(M,\sigma)$ where $\sigma=(I,s)$ is the digital signature of the
message $M$.

1:Set $r\xleftarrow{\mathbf{r}}\mathbb{E}^{*}_{(p-1)^{2}}$

2:Set $I=r^{\mathbf{B}}$

3:Set $\mathbf{H}=Hash_{\mathtt{XXX}}(I||M)$

4:Set $s=(x*r)^{\mathbf{H}}$

5:Set $\sigma=(I,s)$

6:Return $(M,\sigma)$

Algorithm 7 $\mathtt{Verify}$: Verify a digital signature.
Input: A pair $(M,\sigma)$, and $\mathtt{PublicKey}=y$;
Output: True or False.

1:Set $\mathbf{H}=Hash_{\mathtt{XXX}}(I||M)$

2:if $s^{\mathbf{B}}\stackrel{{\scriptstyle?}}{{=}}(y*I)^{\mathbf{H}}$ then

3: Return True

4:else

5: Return False

6:end if

We check the correctness of the signature scheme as follows:

$s^{\mathbf{B}}=\big{(}(x*r)^{\mathbf{H}}\big{)}^{\mathbf{B}}=\big{(}x^{\mathbf{H}}\big{)}^{\mathbf{B}}*\big{(}r^{\mathbf{H}}\big{)}^{\mathbf{B}}=\big{(}x^{\mathbf{B}}\big{)}^{\mathbf{H}}*\big{(}r^{\mathbf{B}}\big{)}^{\mathbf{H}}=y^{\mathbf{H}}*I^{\mathbf{H}}=(y*I)^{\mathbf{H}}.$

An attacker can forge signatures in one of the following ways

  1. 1.

For an existing pair $(M,\sigma)$, find a second preimage $I||M^{\prime}$ such
that $\mathbf{H}=Hash_{\mathtt{XXX}}(I||M^{\prime})$. In that case
$(M^{\prime},\sigma)$ is a valid pair.

  2. 2.

Compute a discrete entropoid $\mathbf{B}$-root of $y$. In that case the
attacker will know the $\mathtt{PrivateKey}=x=\sqrt[\mathbf{B}]{y}$.

  3. 3.

Generate random $I$, random message $M$, and compute the corresponding
$\mathbf{H}=Hash_{\mathtt{XXX}}(I||M)$. Then compute a discrete entropoid
$\mathbf{B}$-root $s=\sqrt[\mathbf{B}]{z}$ where $z=(y*I)^{\mathbf{H}}$.

We want to emphasize that finding a collision
$\mathbf{H}=Hash_{\mathtt{XXX}}(I_{1}||M_{1})=Hash_{\mathtt{XXX}}(I_{2}||M_{2})$
is not enough to forge a signature since the attacker in order to produce $s$
has to perform the operation of computing a discrete entropoid
$\mathbf{B}$-root for $x=\sqrt[\mathbf{B}]{y}$ or for
$s=\sqrt[\mathbf{B}]{z}$.

However, there is a collision finding strategy that will help the attacker to
simulate the $\mathbf{B}$-root computation and that is the classical Diffie
and Hellman Meet-in-the-middle attack [29]. For achieving the goal of having a
probability 1/2 for finding $\mathbf{B}$-root $s=\sqrt[\mathbf{B}]{z}$ where
$z=(y*\sigma_{1})^{\mathbf{H}}$ the attacker needs to build two tables $T_{1}$
and $T_{2}$ where $T_{1}$ will contain pairs of elements from
$\mathbb{E}^{*}_{(p-1)^{2}}$ and $T_{2}$ will contain quadruples as described
below:

$\displaystyle T_{1}=$ $\displaystyle[(z_{i},z_{i}^{\mathbf{B}})\ |\ \text{for
}z_{i}\xleftarrow{\mathbf{r}}\mathbb{E}^{*}_{(p-1)^{2}},i\in\\{1,\ldots
p-1\\}]$ (83) and $\displaystyle T_{2}=$
$\displaystyle[(I_{i},M_{i},\mathbf{H}_{i},(y*I_{i})^{\mathbf{H}_{i}})\ |\
\text{for
}I_{i}\xleftarrow{\mathbf{r}}\mathbb{E}^{*}_{(p-1)^{2}},M_{i}\xleftarrow{\mathbf{r}}\\{0,1\\}^{*},\mathbf{H}_{i}=Hash_{\mathtt{XXX}}(I_{i}||M_{i}),i\in\\{1,\ldots
p-1\\}]$ (84)

During the build-up of the tables if the attacker is lucky, it can even find
an entry in $T_{1}$ that has an item $z_{i}^{\mathbf{B}}=y$. In that case it
found $\mathbf{B}$-root for $x=\sqrt[\mathbf{B}]{y}=z_{i}$. For the size of
$T_{1}$ being $p-1$, the probability of this event is
$\frac{p-1}{(p-1)^{2}}=\frac{1}{p-1}$. The attacker can also search for
collisions $z_{i}^{\mathbf{B}}=(y*I_{j})^{\mathbf{H}_{j}}$. If that happens,
it would found $\mathbf{B}$-root for $s=\sqrt[\mathbf{B}]{z_{i}}$. For the
size of $T_{1}$ and $T_{2}$ being $p-1$, the probability of this event is
around 0.5. So the memory complexity for this attack is
$O(2p)=O(2^{\lambda+1})$ and the time complexity is also $O(2^{\lambda+1})$.

$\lambda$, $\mathbb{F}_{p}$, $p=2q+1$, $\lambda=\lceil\log p\rceil$ |  EUF-CMA classical security |  EUF-CMA quantum security |  PublicKey size (bytes) |  PrivateKey size (bytes) |  Signature size (bytes)
---|---|---|---|---|---
128 | $2^{128}$ | $2^{85}$ | 32 | 32 |  64
192 | $2^{192}$ | $2^{128}$ | 48 | 48 |  96
256 | $2^{256}$ | $2^{171}$ | 64 | 64 |  128
Table 8: A summary table for the characteristics of the entropoid digital
signature scheme based on CDERP

For a similar quantum collision search, we first have to assume that the
attacker has overcome the challenges discussed at the end of Section 3.1.
While in this situation the associative pattern $\mathbf{B}$ used in table
$T_{1}$ is known and fixed, for every entry in table $T_{2}$ the associative
patterns $\mathbf{H}_{i}$ are entangled with the choices of $I_{i}$ and
$M_{i}$, and the output of the hash function
$\mathbf{H}_{i}=Hash_{\mathtt{XXX}}(I_{i}||M_{i})$. So, the attacker faces
again the two challenges: To build quantum circuits that implement non-
commutative operations of multiplication $*$, and to build quantum circuits
that perform an exponential number of non-associative and non-commutative
multiplication patterns. If it overcomes those challenges, we can assume that
the complexity for the quantum search [30] for entropoid collisions could be
as low as $O(q^{\frac{2}{3}})$.

As a summary of all discussion in this section, we give a Table 8.

###  4.3 Digital Signature Scheme Based on reducing CDERP to DELP for Specific
Roots $\mathbf{B}$

The signature scheme proposed in the previous sub-section is based on the new
assumption about the hardness of CDERP. In case that assumption turns out to
be false, we propose here an alternative and more conservative signature
scheme that relies its security on the hardness of solving the discrete
entropoid logarithm problem.

The more conservative scheme is similar to the one given in the previous sub-
section, with the following differences. The entropoid
$\mathbb{E}_{p^{2}}(a_{3},a_{8},b_{2},b_{7})$, is defined with a prime number
$p=2q+1$ where the bit size of $p$ is $\lambda\in\\{256,384,512\\}$ bits. The
root $\mathbf{B}$ as a public parameter has the following format:222The same
remark about the possibility to use base $\mathfrak{b}=17$ applies also for
this signature scheme. $\mathbf{B}=(q,b_{s},257)$, where $q$ is the prime
number in the construction of $p$, and
$b_{s}=\mathtt{SHAXXX}(\mathtt{``abc"})$. The mapping
$Hash_{\mathtt{XXX}}:\\{0,1\\}^{*}\mapsto\mathbb{L}_{q,\mathtt{257}}$ is now
defined as:

$Hash_{\mathtt{XXX}}(M)=(q,\mathtt{SHAXXX}(M),257).$ (85)

Now, with this different hashing, the algorithms $\mathtt{GenKey}$,
$\mathtt{Sign}$ and $\mathtt{Verify}$ are the same as in the previous case.

The same security analysis applies here, with one additional safety layer. Let
us suppose that a Logarithmetic for our succinct power indices will be
developed and that the Johnston root-finding algorithm will be adapted for the
entropoids $\mathbb{E}_{p^{2}}$. Since the size of maximal multiplicative
groupoid $\mathbb{E}_{(p-1)^{2}}$ is $4q^{2}$, and since we have a fixed value
$q$ in the public root value $\mathbf{B}=(q,b_{s},257)$, even the hypothetical
version of the Johnston algorithm will reduce to finding discrete entropoid
logarithm in $\mathbb{E}_{(p-1)^{2}}$.

The consequences of doubling the bit sizes of $p$ are the doubling of the keys
and signatures of the proposed signature scheme and are given in Table 9.

$\lambda$, $\mathbb{F}_{p}$, $p=2q+1$, $\lambda=\lceil\log p\rceil$ |  EUF-CMA classical security |  EUF-CMA quantum security |  PublicKey size (bytes) |  PrivateKey size (bytes) |  Signature size (bytes)
---|---|---|---|---|---
256 | $2^{128}$ | $2^{85}$ | 64 | 64 |  128
384 | $2^{192}$ | $2^{128}$ | 96 | 96 |  192
512 | $2^{256}$ | $2^{171}$ | 128 | 128 |  256
Table 9: A summary table for the characteristics of the entropoid digital
signature scheme based on reduction of CDERP to DELP

##  5 Conclusions

The algebraic structures that are non-commutative and non-associative known as
entropic groupoids that satisfy the _"Palintropic"_ property i.e.,
$x^{\mathbf{A}\mathbf{B}}=(x^{\mathbf{A}})^{\mathbf{B}}=(x^{\mathbf{B}})^{\mathbf{A}}=x^{\mathbf{B}\mathbf{A}}$
were proposed by Etherington in ’40s from the 20th century. Those relations
are exactly the Diffie-Hellman key exchange protocol relations used with
groups. The arithmetic for non-associative power indices known as
Logarithmetic was also proposed by Etherington and later developed by others
in the period of ’50s-’70s. However, there was never proposed a succinct
notation for exponentially large non-associative power indices that will have
the property of fast exponentiation similarly as the fast exponentiation is
achieved with ordinary arithmetic via the consecutive rising to the powers of
two.

In this paper, we defined ringoid algebraic structures $(G,\boxplus,*)$ where
$(G,\boxplus)$ is an Abelian group and $(G,*)$ is a non-commutative and non-
associative groupoid with an entropic and palintropic subgroupoid which is a
quasigroup, and we named those structures as Entropoids. We further defined
succinct notation for non-associative bracketing patterns and proposed
algorithms for fast exponentiation with those patterns.

Next, by analogy with the developed cryptographic theory of discrete logarithm
problems, we defined several hard problems in Entropoid based cryptography,
and based on that, we proposed an entropoid Diffie-Hellman key exchange
protocol and an entropoid signature schemes. Due to the non-commutativity and
non-associativity, the entropoid based cryptographic primitives are supposed
to be resistant to quantum algorithms. At the same time, due to the proposed
succinct notation for the power indices, the communication overhead in the
entropoid based Diffie-Hellman key exchange is very low: for 128 bits of
security, 64 bytes in total are communicated in both directions, and for 256
bits of security, 128 bytes in total are communicated in both directions.

In this paper, we also proposed two entropoid based digital signature schemes.
The schemes are constructed with the Fiat-Shamir transformation of an
identification scheme which security relies on a new hardness assumption:
computing roots in finite entropoids is hard. If this assumption withstands
the time’s test, the first proposed signature scheme has very attractive
properties: for the classical security levels between 128 and 256 bits, the
public and private key sizes are between 32 and 64, and the signature sizes
are between 64 and 128 bytes. The second signature scheme reduces the finding
of the roots in finite entropoids to computing discrete entropoid logarithms.
In our opinion, this is a safer but more conservative design, and the price is
in doubling the key sizes and the signature sizes.

We give a proof-of-concept implementation in SageMath 9.2 for all proposed
algorithms and schemes in Appendix C.

We hope that this paper will initiate further research in Entropoid Based
Cryptography.

## References

  * [1] EF Harding.  The probabilities of rooted tree-shapes generated by random bifurcation.  Advances in Applied Probability, pages 44–77, 1971.
  * [2] Michael F Dacey.  A non-associative arithmetic for shapes of channel networks.  In Proceedings of the June 4-8, 1973, national computer conference and exposition, pages 503–508, 1973.
  * [3] IMH Etherington.  On Non-Associative Combinations.  Proceedings of the royal society of Edinburgh, 59:153–162, 1940\.
  * [4] Abraham Robinson.  On non-associative systems.  Proceedings of the Edinburgh Mathematical Society, 8(3):111–118, 1949.
  * [5] Helen Popova.  Logarithmetics of non associative algebras.  Annexe Thesis Digitisation Project 2019 Block 22, 1951.
  * [6] Trevor Evans.  Nonassociative number theory.  The American Mathematical Monthly, 64(5):299–309, 1957.
  * [7] H Minc.  Theorems on nonassociative number theory.  The American Mathematical Monthly, 66(6):486–488, 1959.
  * [8] Dorothy Bollman et al.  Formal nonassociative number theory.  Notre Dame Journal of Formal Logic, 8(1-2):9–16, 1967.
  * [9] MW Bunder.  Commutative non-associative number theory.  Proceedings of the Edinburgh Mathematical Society, 20(2):133–136, 1976.
  * [10] Henryk Trappmann.  Arborescent numbers: higher arithmetic operations and division trees.  PhD thesis, Universität Potsdam, 2007.
  * [11] IMH Etherington.  Transposed algebras.  Proceedings of the Edinburgh Mathematical Society, 7(2):104–121, 1945.
  * [12] IMH Etherington.  Groupoids with additive endomorphisms.  The American Mathematical Monthly, 65(8P1):596–601, 1958.
  * [13] IMH Etherington.  Quasigroups and cubic curves.  Proceedings of the Edinburgh Mathematical Society, 14(4):273–291, 1965.
  * [14] Neil JA Sloane.  The on-line encyclopedia of integer sequences.  In Towards mechanized mathematical assistants, pages 130–130. Springer, 2007.
  * [15] DC Murdoch.  Quasi-groups which satisfy certain generalized associative laws.  American Journal of Mathematics, 61(2):509–522, 1939.
  * [16] William Stein and David Joyner.  Sage: System for algebra and geometry experimentation.  Acm Sigsam Bulletin, 39(2):61–64, 2005.
  * [17] Stephen Wolfram.  Mathematica: a system for doing mathematics by computer.  Addison Wesley Longman Publishing Co., Inc., 1991.
  * [18] Anna B Romanowska and Jonathan DH Smith.  On Hopf algebras in entropic Jónsson-Tarski varieties.  Bulletin of the Korean Mathematical Society, 52(5):1587–1606, 2015\.
  * [19] Jonathan DH Smith.  Sylow theory for quasigroups.  Journal of Combinatorial Designs, 23(3):115–133, 2015.
  * [20] D. R. HEATH-BROWN.  ARTIN’S CONJECTURE FOR PRIMITIVE ROOTS.  The Quarterly Journal of Mathematics, 37(1):27–38, 03 1986.
  * [21] Alfred J Menezes, Paul C Van Oorschot, and Scott A Vanstone.  Handbook of applied cryptography.  CRC press, 2018.
  * [22] Jonathan DH Smith.  Some observations on the concepts of information-theoretic entropy and randomness.  Entropy, 3(1):1–11, 2001.
  * [23] Christian Cachin.  Entropy measures and unconditional security in cryptography.  PhD thesis, ETH Zurich, 1997.
  * [24] Maciej Skórski.  Shannon entropy versus Renyi entropy from a cryptographic viewpoint.  In IMA International Conference on Cryptography and Coding, pages 257–274. Springer, 2015.
  * [25] Ran Canetti and Hugo Krawczyk.  Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels.  In Birgit Pfitzmann, editor, Advances in Cryptology – EUROCRYPT 2001, volume 2045 of Lecture Notes in Computer Science, pages 453–474. Springer, 2001.
  * [26] Anna M. Johnston.  A Generalized q-th Root Algorithm.  In Robert Endre Tarjan and Tandy J. Warnow, editors, SODA, pages 929–930. ACM/SIAM, 1999.
  * [27] Amos Fiat and Adi Shamir.  How to prove yourself: practical solutions to identification and signature problems.  In Proceedings on Advances in cryptology—CRYPTO ’86, pages 186–194, London, UK, 1987. Springer-Verlag.
  * [28] Claus P. Schnorr.  Efficient Identification and Signatures for Smart Cards.  In Gilles Brassard, editor, Advances in Cryptology – CRYPTO ’89, volume 435 of Lecture Notes in Computer Science. Springer, 1990.
  * [29] Whitfield Diffie and Martin E Hellman.  Special feature exhaustive cryptanalysis of the nbs data encryption standard.  Computer, 10(6):74–84, 1977.
  * [30] Seiichiro Tani.  Claw finding algorithms using quantum walk.  Theoretical Computer Science, 410(50):5285–5297, 2009.

##  Appendix A Examples for $\mathbb{E}_{{11}^{2}}$, $\mathbb{E}_{{13}^{2}}$,
$\mathbb{E}_{{19}^{2}}$ and $\mathbb{E}_{{23}^{2}}$

Let us define the following finite entropoids:

  1. 1.

$\mathbb{E}_{{11}^{2}}(a_{3}=9,a_{8}=1,b_{2}=8,b_{7}=9)$, which has
$\mathbf{0}_{*}=(2,4)$, $\mathbf{1}_{*}=(7,5)$ and
$x*y=(x_{1},x_{2})*(y_{1},y_{2})=(x_{2}y_{1}+9x_{2}+7y_{1}+10,\ \ \
9x_{1}y_{2}+8x_{1}+4y_{2}+10)$;

  2. 2.

$\mathbb{E}_{{13}^{2}}(a_{3}=10,a_{8}=2,b_{2}=3,b_{7}=9)$, which has
$\mathbf{0}_{*}=(8,4)$, $\mathbf{1}_{*}=(11,11)$ and
$x*y=(x_{1},x_{2})*(y_{1},y_{2})=(2x_{2}y_{1}+10x_{2}+5y_{1}+7,\ \ \
9x_{1}y_{2}+3x_{1}+6y_{2}+6)$;

  3. 3.

$\mathbb{E}_{{19}^{2}}(a_{3}=18,a_{8}=11,b_{2}=14,b_{7}=10)$, which has
$\mathbf{0}_{*}=(7,10)$, $\mathbf{1}_{*}=(9,17)$ and
$x*y=(x_{1},x_{2})*(y_{1},y_{2})=(11x_{2}y_{1}+18x_{2}+4y_{1}+17,\ \ \
10x_{1}y_{2}+14x_{1}+6y_{2}+7)$;

  4. 4.

$\mathbb{E}_{{23}^{2}}(a_{3}=15,a_{8}=13,b_{2}=9,b_{7}=14)$, which has
$\mathbf{0}_{*}=(13,1)$, $\mathbf{1}_{*}=(18,17)$ and
$x*y=(x_{1},x_{2})*(y_{1},y_{2})=(13x_{2}y_{1}+15x_{2}+10y_{1}+21,\ \ \
14x_{1}y_{2}+9x_{1}+2y_{2}+22)$.

We present their elements as square $p\times p$ arrays as in Example 16 and in
cells with coordinates $(x_{1},x_{2})$ we put the values that are the size of
the sets $\langle x\rangle_{2}$ and $\langle x\rangle$.

The colored cells has the following meaning:

  1. 1.

The yellow highlighted elements do not belong to the multiplicative quasigroup
$(\mathbb{E}_{{p}^{2}}^{*},*)$;

  2. 2.

The green highlighted elements $x=(x_{1},x_{2})$ are generators for both the
maximal length cyclic subgroupoid $\langle x\rangle_{2}$ with $2(p-1)$
elements, and are generators of the multiplicative quasigroup
$(\mathbb{E}_{{p}^{2}}^{*},*)$;

  3. 3.

The red highlighted elements $x=(x_{1},x_{2})$ are generators for a maximal
length cyclic subgroupoid $\langle x\rangle_{2}$ with $2(p-1)$ elements, but
are not generators of the multiplicative quasigroup
$(\mathbb{E}_{{p}^{2}}^{*},*)$.

  4. 4.

Blue highlighted element for $\mathbb{E}_{{11}^{2}}$ and
$\mathbb{E}_{{23}^{2}}$ denote the generators of the Sylow $q$-subgroupoids
with 25 and 121 elements (11 and 23 are "safe primes" i.e. $11=2\times 5+1$
and $23=2\times 11+1$).

$\NiceArray{rrrrrrrrrrr}[small,hvlines,first-row,first-col,code-
before={\pagecolor{red}{1-1,2-3,4-7,5-9,6-11,7-2,10-8,11-10}\pagecolor{green}{1-4,1-7,1-11,2-6,2-8,2-9,4-1,4-2,4-4,5-3,5-6,5-10,6-1,6-2,6-4,7-4,7-7,7-11,8-1,8-2,8-7,8-11,9-3,9-8,9-9,9-10,10-3,10-6,10-10,11-6,11-8,11-9}{3}{5}},columns-
width=4mm]&012345678910\\\ 0204102021020251020\\\ 11010201022010202042\\\
222221222222\\\ 3202052021020101024\\\ 41022010220104202010\\\
5202022021041010520\\\ 6420102021020521020\\\ 72020104212010101020\\\
81010202241020202010\\\ 92102010220102042010\\\ 101010410220220202010\\\ $

Table 10: The size of the sets $\langle x\rangle_{2}$ for
$x\in\mathbb{E}_{{11}^{2}}$

$\NiceArray{rrrrrrrrrrr}[small,hvlines,first-row,first-col,code-
before={\pagecolor{red}{1-1,2-3,4-7,5-9,6-11,7-2,10-8,11-10}\pagecolor{green}{1-4,1-7,1-11,2-6,2-8,2-9,4-1,4-2,4-4,5-3,5-6,5-10,6-1,6-2,6-4,7-4,7-7,7-11,8-1,8-2,8-7,8-11,9-3,9-8,9-9,9-10,10-3,10-6,10-10,11-6,11-8,11-9}\pagecolor{blue!20}{1-3,1-6,1-10,4-6,4-8,4-9,6-6,6-8,6-9,7-3,7-6,7-10,8-3,8-8,8-9,8-10}{3}{5}},columns-
width=4mm]&012345678910\\\ 02020251002251005525100\\\
1505020502100101001002010\\\ 222221222222\\\ 31001005100225202525520\\\
4101010050210050202010050\\\ 51001005100225202525520\\\
62020251002251005525100\\\ 710010025421100252525100\\\
850501002245010010010050\\\ 9101010050210050202010050\\\
10505020502100101001002010\\\ $

Table 11: The size of the sets $\langle x\rangle$ for
$x\in\mathbb{E}_{{11}^{2}}$

$\NiceArray{rrrrrrrrrrrrr}[small,hvlines,first-row,first-col,code-
before={\pagecolor{red}{1-3,1-7,2-10,2-13,3-10,3-13,4-3,4-7,5-4,5-6,8-2,8-8,10-2,10-8,13-4,13-6}\pagecolor{green}{1-11,1-12,2-11,2-12,3-11,3-12,4-11,4-12,5-1,5-9,6-2,6-4,6-6,6-8,7-3,7-7,7-10,7-13,8-1,8-9,10-1,10-9,11-3,11-7,11-10,11-13,12-2,12-4,12-6,12-8,13-1,13-9}{9}{5}},columns-
width=4mm]&0123456789101112\\\ 01262422424126824248\\\ 11228621284624242424\\\
26481226821224242424\\\ 36122442224612824248\\\ 42482242244824121263\\\
58241224224624862412\\\ 62122412262464248824\\\ 72424128286242426124\\\
82222122222222\\\ 92424382812242441262\\\ 104624621224122248824\\\
118246242241224812416\\\ 122484242242824661212\\\ $

Table 12: The size of the sets $\langle x\rangle_{2}$ for
$x\in\mathbb{E}_{{13}^{2}}$

$\NiceArray{rrrrrrrrrrrrr}[small,hvlines,first-row,first-col,code-
before={\pagecolor{red}{1-3,1-7,2-10,2-13,3-10,3-13,4-3,4-7,5-4,5-6,8-2,8-8,10-2,10-8,13-4,13-6}\pagecolor{green}{1-11,1-12,2-11,2-12,3-11,3-12,4-11,4-12,5-1,5-9,6-2,6-4,6-6,6-8,7-3,7-7,7-10,7-13,8-1,8-9,10-1,10-9,11-3,11-7,11-10,11-13,12-2,12-4,12-6,12-8,13-1,13-9}{9}{5}},columns-
width=4mm]&0123456789101112\\\ 0361248122124812364814414448\\\
1361248122124812364814414448\\\ 2361248122124812364814414448\\\
3361248122124812364814414448\\\ 4144483482481248144123693\\\
5161443614421441814416182436\\\ 6436144362361443641441616144\\\
71444812482486481446183612\\\ 82222122222222\\\ 9144483482481248144123693\\\
10436144362361443641441616144\\\ 111614491442144361441636419\\\
121444812482486481446183612\\\ $

Table 13: The size of the sets $\langle x\rangle$ for
$x\in\mathbb{E}_{{13}^{2}}$

$\NiceArray{rrrrrrrrrrrrrrrrrrr}[small,hvlines,first-row,first-col,code-
before={\pagecolor{red}{1-2,1-5,1-7,2-6,2-13,2-14,4-6,4-13,4-14,7-2,7-5,7-7,9-1,9-15,9-17,12-8,12-9,12-16,14-8,14-9,14-16,15-1,15-15,15-17,16-2,16-5,16-7,17-8,17-9,17-16,18-6,18-13,18-14,19-1,19-15,19-17}\pagecolor{green}{1-4,1-10,1-19,2-4,2-10,2-19,3-2,3-5,3-6,3-7,3-13,3-14,4-4,4-10,4-19,5-1,5-8,5-9,5-15,5-16,5-17,6-1,6-8,6-9,6-15,6-16,6-17,7-4,7-10,7-19,9-3,9-12,9-18,10-2,10-5,10-6,10-7,10-13,10-14,11-2,11-5,11-6,11-7,11-13,11-14,12-3,12-12,12-18,13-1,13-8,13-9,13-15,13-16,13-17,14-3,14-12,14-18,15-3,15-12,15-18,16-4,16-10,16-19,17-3,17-12,17-18,18-4,18-10,18-19,19-3,19-12,19-18}{8}{11}},columns-
width=4mm]&0123456789101112131415161718\\\
018361836361236623621841296181836\\\ 161218361236418936218363621861836\\\
2183631236363618184223636181818612\\\ 361218364361218183621836366921836\\\
4361846181818363662121818363636122\\\ 5361812218181836366212181836363646\\\
618361836364366636218121218291836\\\ 72222222222122222222\\\
8361836181821812121823666364363618\\\ 9183664363636181812263636181818112\\\
10183621236363618181223363618181864\\\ 11126361821863636182361818123643618\\\
12361812618181836362241818363636126\\\ 13126361861823636182361818436123618\\\
14361836181861812418236263612363618\\\ 1593618363612362636218124186181836\\\
16423618618636361823618181236123618\\\ 1724183612361291836218363661861836\\\
18361836181861841218236623612363618\\\ $

Table 14: The size of the sets $\langle x\rangle_{2}$ for
$x\in\mathbb{E}_{{19}^{2}}$

$\NiceArray{rrrrrrrrrrrrrrrrrrr}[small,hvlines,first-row,first-col,code-
before={\pagecolor{red}{1-2,1-5,1-7,2-6,2-13,2-14,4-6,4-13,4-14,7-2,7-5,7-7,9-1,9-15,9-17,12-8,12-9,12-16,14-8,14-9,14-16,15-1,15-15,15-17,16-2,16-5,16-7,17-8,17-9,17-16,18-6,18-13,18-14,19-1,19-15,19-17}\pagecolor{green}{1-4,1-10,1-19,2-4,2-10,2-19,3-2,3-5,3-6,3-7,3-13,3-14,4-4,4-10,4-19,5-1,5-8,5-9,5-15,5-16,5-17,6-1,6-8,6-9,6-15,6-16,6-17,7-4,7-10,7-19,9-3,9-12,9-18,10-2,10-5,10-6,10-7,10-13,10-14,11-2,11-5,11-6,11-7,11-13,11-14,12-3,12-12,12-18,13-1,13-8,13-9,13-15,13-16,13-17,14-3,14-12,14-18,15-3,15-12,15-18,16-4,16-10,16-19,17-3,17-12,17-18,18-4,18-10,18-19,19-3,19-12,19-18}{8}{11}},columns-
width=4mm]&0123456789101112131415161718\\\
0271088132410810836279324281361089272781324\\\
1271088132410810836279324281361089272781324\\\
28132433632432432481811223324324818181912\\\
3271088132436361082727324281108108279981324\\\
432416212181621621623243246212162162324324324366\\\
532416236216216216232432418236162162324324324418\\\
6271088132436361082727324281108108279981324\\\ 72222222222122222222\\\
810854324162181854108108162232454541083636324162\\\
9813249432432432481813629324324818181136\\\
108132433632432432481811223324324818181912\\\
1110854324162181854108108162232454541083636324162\\\
1232416212181621621623243246212162162324324324366\\\
1310854324162545418108361622324185436108108324162\\\
1410854324162545418108361622324185436108108324162\\\
15936813241081081089273242811083627272781324\\\
1636183241625454543610816223245418108108108324162\\\
17936813241081081089273242811083627272781324\\\
1836183241625454543610816223245418108108108324162\\\ $

Table 15: The size of the sets $\langle x\rangle$ for
$x\in\mathbb{E}_{{19}^{2}}$

$\NiceArray{rrrrrrrrrrrrrrrrrrrrrrr}[small,hvlines,first-row,first-col,code-
before={\pagecolor{red}{1-16,2-22,3-5,4-11,5-17,6-23,7-6,8-12,10-1,11-7,12-13,13-19,15-8,16-14,17-20,18-3,20-15,21-21,22-4,23-10}\pagecolor{green}{1-1,1-7,1-9,1-12,1-13,1-19,1-21,1-22,1-23,2-7,2-9,2-12,2-13,2-16,2-17,2-19,2-21,2-23,3-4,3-6,3-8,3-10,3-11,3-14,3-15,3-18,3-20,4-3,4-4,4-5,4-6,4-8,4-14,4-15,4-18,4-20,5-1,5-7,5-9,5-12,5-13,5-19,5-21,5-22,5-23,6-1,6-7,6-9,6-13,6-16,6-17,6-19,6-21,6-22,7-3,7-4,7-5,7-8,7-10,7-11,7-14,7-15,7-18,8-1,8-7,8-9,8-13,8-16,8-17,8-19,8-21,8-22,9-3,9-4,9-5,9-6,9-8,9-10,9-11,9-14,9-15,9-20,10-7,10-9,10-12,10-13,10-16,10-17,10-19,10-21,10-23,11-1,11-9,11-12,11-13,11-16,11-17,11-19,11-22,11-23,12-1,12-7,12-9,12-12,12-16,12-17,12-21,12-22,12-23,13-1,13-7,13-9,13-12,13-16,13-17,13-21,13-22,13-23,15-3,15-4,15-5,15-6,15-10,15-11,15-15,15-18,15-20,16-3,16-4,16-5,16-6,16-10,16-11,16-15,16-18,16-20,17-3,17-4,17-5,17-8,17-10,17-11,17-14,17-15,17-18,18-4,18-6,18-8,18-10,18-11,18-14,18-15,18-18,18-20,19-1,19-7,19-12,19-13,19-16,19-17,19-19,19-21,19-22,19-23,20-3,20-5,20-6,20-8,20-10,20-11,20-14,20-18,20-20,21-1,21-9,21-12,21-13,21-16,21-17,21-19,21-22,21-23,22-3,22-5,22-6,22-8,22-10,22-11,22-14,22-18,22-20,23-3,23-4,23-5,23-6,23-8,23-14,23-15,23-18,23-20}{14}{2}},columns-
width=4mm,]&012345678910111213141516171819202122\\\
04422222222244224421144442222444224422444444\\\
14222211224422442222444422224444224422444444\\\
22244444442244224444222244442222442244222222\\\
32224444444422442244422224444222442244222222\\\
44422222222244224411244442222444224422444444\\\
54422211222244224422224442224444224422444444\\\