%Version 3 October 2023
% See section 11 of the User Manual for version history
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                                 %%
%% Please do not use \input{...} to include other tex files.       %%
%% Submit your LaTeX manuscript as one .tex document.              %%
%%                                                                 %%
%% All additional figures and files should be attached             %%
%% separately and not embedded in the \TeX\ document itself.       %%
%%                                                                 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%\documentclass[referee,sn-basic]{sn-jnl}% referee option is meant for double line spacing

%%=======================================================%%
%% to print line numbers in the margin use lineno option %%
%%=======================================================%%

%%\documentclass[lineno,sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style

%%======================================================%%
%% to compile with pdflatex/xelatex use pdflatex option %%
%%======================================================%%

%%\documentclass[pdflatex,sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style


%%Note: the following reference styles support Namedate and Numbered referencing. By default the style follows the most common style. To switch between the options you can add or remove �Numbered� in the optional parenthesis. 
%%The option is available for: sn-basic.bst, sn-vancouver.bst, sn-chicago.bst%  
 
%%\documentclass[sn-nature]{sn-jnl}% Style for submissions to Nature Portfolio journals
%%\documentclass[sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style
\documentclass[sn-mathphys-num]{sn-jnl}% Math and Physical Sciences Numbered Reference Style 
%%\documentclass[sn-mathphys-ay]{sn-jnl}% Math and Physical Sciences Author Year Reference Style
%%\documentclass[sn-aps]{sn-jnl}% American Physical Society (APS) Reference Style
%%\documentclass[sn-vancouver,Numbered]{sn-jnl}% Vancouver Reference Style
%%\documentclass[sn-apa]{sn-jnl}% APA Reference Style 
%%\documentclass[sn-chicago]{sn-jnl}% Chicago-based Humanities Reference Style

%%%% Standard Packages
%%<additional latex packages if required can be included here>

\usepackage{graphicx}%
\usepackage{multirow}%
\usepackage{amsmath,amssymb,amsfonts}%
\usepackage{amsthm}%
\usepackage{mathrsfs}%
\usepackage[title]{appendix}%
\usepackage{xcolor}%
\usepackage{textcomp}%
\usepackage{manyfoot}%
\usepackage{booktabs}%
\usepackage{algorithm}%
\usepackage{algorithmicx}%
\usepackage{algpseudocode}%
\usepackage{listings}%
%%%%

%%%%%=============================================================================%%%%
%%%%  Remarks: This template is provided to aid authors with the preparation
%%%%  of original research articles intended for submission to journals published 
%%%%  by Springer Nature. The guidance has been prepared in partnership with 
%%%%  production teams to conform to Springer Nature technical requirements. 
%%%%  Editorial and presentation requirements differ among journal portfolios and 
%%%%  research disciplines. You may find sections in this template are irrelevant 
%%%%  to your work and are empowered to omit any such section if allowed by the 
%%%%  journal you intend to submit to. The submission guidelines and policies 
%%%%  of the journal take precedence. A detailed User Manual is available in the 
%%%%  template package for technical guidance.
%%%%%=============================================================================%%%%

%% as per the requirement new theorem styles can be included as shown below
\theoremstyle{thmstyleone}%
\newtheorem{theorem}{Theorem}%  meant for continuous numbers
%%\newtheorem{theorem}{Theorem}[section]% meant for sectionwise numbers
%% optional argument [theorem] produces theorem numbering sequence instead of independent numbers for Proposition
\newtheorem{proposition}[theorem]{Proposition}% 
\newtheorem{corollary}[theorem]{Corollary}% 
%%\newtheorem{proposition}{Proposition}% to get separate numbers for theorem and proposition etc.

\theoremstyle{thmstyletwo}%
\newtheorem{example}{Example}%
\newtheorem{remark}{Remark}%

\theoremstyle{thmstylethree}%
\newtheorem{definition}{Definition}%

\raggedbottom
%%\unnumbered% uncomment this for unnumbered level heads

\newcommand{\noi}{\noindent}
\newcommand{\ds}{\displaystyle}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}

\begin{document}

\title[A Novel RSA Attack Leveraging Christoffel and Stern-Brocot Tree Properties]{A Novel RSA Attack Leveraging Christoffel and Stern-Brocot Tree Properties}

%%=============================================================%%
%% GivenName	-> \fnm{Joergen W.}
%% Particle	-> \spfx{van der} -> surname prefix
%% FamilyName	-> \sur{Ploeg}
%% Suffix	-> \sfx{IV}
%% \author*[1,2]{\fnm{Joergen W.} \spfx{van der} \sur{Ploeg} 
%%  \sfx{IV}}\email{iauthor@gmail.com}
%%=============================================================%%

\author*[1]{\fnm{Abhishek} \sur{Krishnamoorthy}}\email{krishnamoorthyabhishek@gmail.com}

\author[2]{\fnm{Robinson} \sur{Thamburaj}}\email{robinson@mcc.edu.in}
\equalcont{These authors contributed equally to this work.}

\affil*[1,2]{\orgdiv{Department of Mathematics}, \orgname{Madras Christian College}, \orgaddress{\city{Chennai}, \postcode{600059}, \state{Tamil Nadu}, \country{India}}}

%%==================================%%
%% Sample for unstructured abstract %%
%%==================================%%

\abstract{This research paper explores the properties of Christoffel Words, which are formed using a binary alphabet. These words have been extensively studied by Jean Berstel, Christophe Reutenauer, and others, due to their intriguing combinatorial and geometrical characteristics. We have established specific combinatorial properties of the Christoffel and Stern-Brocot trees, which in certain cases can be effectively utilized to compute the modulo multiplicative inverse of a natural number and have also presented a novel algorithm to attack the RSA cryptosystem using this application.}

%%================================%%
%% Sample for structured abstract %%
%%================================%%

% \abstract{\textbf{Purpose:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.
% 
% \textbf{Methods:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.
% 
% \textbf{Results:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.
% 
% \textbf{Conclusion:} The abstract serves both as a general introduction to the topic and as a brief, non-technical summary of the main results and their implications. The abstract must not include subheadings (unless expressly permitted in the journal's Instructions to Authors), equations or citations. As a guide the abstract should not exceed 200 words. Most journals do not set a hard limit however authors are advised to check the author instructions for the journal they are submitting to.}

\keywords{Christoffel words, Christoffel Tree, Stern-Brocot Tree, continued fractions, modulo multiplicative inverse, RSA, cryptosystems}

%%\pacs[JEL Classification]{D8, H51}

%%\pacs[MSC Classification]{35A01, 65L10, 65L12, 65L20, 65L70}

\maketitle

\section{Introduction}\label{sec1}

In the realm of number theory, the modulo multiplicative inverse of a natural number holds a significant role. It refers to a natural number that, when multiplied by the original number and taken modulo a given modulus, equals the natural number 1. This concept is pivotal in various cryptographic applications, such as the RSA algorithm, Diffie-Hellman key exchange, and elliptic curve cryptography. Calculating modulo multiplicative inverse of a natural number $a$ modulo another natural number $b$ that is relatively prime to it traditionally involves the Euclidean algorithm, known for its efficiency with a time complexity of ${O}({log}({min}{({a},{b})}))$. This paper explores alternative methods by examining the structural properties of Christoffel and Stern-Brocot Trees, offering a new approach that streamlines the computation of modulo multiplicative inverses.

The study of Christoffel words, coined by Jean Berstel in 1990, has a rich mathematical history dating back to the late 1800s. These words have deep connections in various mathematical fields such as combinatorics and Diophantine equations\cite{3},algebra \cite{10}, discrete geometry \cite{9} and music theory \cite {8}. We refer the readers to \cite{1,2,3} and \cite{6} to gain insights in the studies conducted on the Combinatorics on words, specifically on the combinatorics of Christoffel words.  Section 2 consists of the preliminary definitions and results which are required for the results that are established in section 3. In sections 4 and 5 we have presented a novel approach to attack the RSA cryptosystem using the results of section 3. 

\section{Preliminaries}

\begin{definition}[\cite{1}]
The Christoffel word of slope $\frac{a}{b}$, where $a$ and $b$ are relatively prime, is a sequence of $a+b$ letters chosen from a binary alphabet $\{x, y\}$ defined as follows:\\
Let $r_i = ia \text{ mod } n$, $i = 0, 1, 2, \ldots, n$, where $n=a+b$. Then $w = C(\frac{a}{b})$ is given by $w[i] = \begin{cases} x & 
\text{if } r_{i-1} < r_i \\ y & \text{if } r_{i-1} > r_i \end{cases}$ for $i = 1, 2, \ldots, n$; where $w[i]$ denotes the letter in the $i^{th}$ position of $w$.\\
\end{definition}

\noi{\bf Example:}
For the Christoffel word $C(\frac{4}{7})$, we have\\
$r_0 = 0$, $r_1 = 4$, $r_2 = 8$, $r_3 = 1$, $r_4 = 5$, $r_5 = 8$, $r_6 = 2$, $r_7 = 6$, $r_8 = 10$, $r_9 = 3$, $r_{10} = 7$, $r_{11} = 0$\\
Therefore, $C(\frac{4}{7}) = xxyxxyxxyxy$\\

The equivalent geometric definition of Christoffel words is given below. \\

\begin{definition}[\cite{1}]
The lower Christoffel path of slope $\frac{a}{b}$ where $a$ and $b$ are relatively prime is the path in the plane from (0, 0) to $(b, a)$ in the integer lattice $Z \times Z$ that satisfies the following two conditions:
\begin{itemize}
\item The path lies below the line segment that begins at (0, 0) and ends at $(b, a)$.
\item The region in the plane enclosed by the path and the line segment contains no other part of $Z \times Z$ besides those of the path.
\end{itemize}
By encoding every horizontal step in the lower Christoffel path by the letter $x$ and every vertical step in the lower Christoffel path by the letter $y$ we get the Christoffel word of slope $\frac{a}{b}$.
\end{definition}

\begin{figure}[h!]
\centering
\includegraphics{rsafig1.jpg}
\caption{The Christoffel word of slope $\frac{4}{7}$}
\label{fig2.1}
\end{figure}

In the below definition $\{x, y\}^\ast$ denotes the set of all words on the binary alphabet $\{x, y\}$.

\begin{definition}[\cite{1}]
Suppose $a$ and $b$ are relatively prime. The label of a point $(i, j)$ on the lower Christoffel path of slope $\frac{a}{b}$ is the number $\frac{ia-jb}{b}$ which represents the vertical distance from the point $(i, j)$ to the line segment from (0, 0) to $(b, a)$.
\end{definition}

\begin{figure}[h!]
\centering
\includegraphics{rsafig2.jpg}
\caption{The labels of the points on the Christoffel path of slope $\frac{4}{7}$}
\label{fig2.2}
\end{figure}
\ \\
\noi{\bf Notation:} $\{x, y\}^\ast$ denotes the set of all possible words on the binary alphabet $\{x, y\}$.\\

\begin{definition}[\cite{1}]
An endomorphism $G$ of $\{x, y\}^\ast$ is a mapping from $\{x, y\}^\ast$ to $\{x, y\}^\ast$ satisfying for any word $w = a_0 a_1 \ldots a_r \in \{x, y\}^\ast$, as follows:\\
$G(w) = G(a_0 a_1 \ldots a_r) = G(a_0) G(a_1) \ldots G(a_r)$.\\
A Christoffel morphism is an endomorphism of the free monoid $\{x, y\}^\ast$ that sends each Christoffel word onto a Christoffel word. Thus, $G$ is defined by the images of $x$ and $y$ and so we identify $G$ with the pair $(G(x), G(y))$.\\
\end{definition}

\noi{\bf Examples:} The morphisms $G = (x, xy)$ and $D = (xy, y)$ are Christoffel morphisms.

The following result can be found in \cite{1}.\\

\begin{theorem}[\cite{1}]
The morphisms $G$ maps the Christoffel word of slope $\frac{a}{b}$ to the Christoffel word of slope $\frac{a}{a+b}$. The morphism $D$ maps the Christoffel word of slope $\frac{a}{b}$ to the Christoffel word of slope $\frac{a+b}{b}$.\\
\end{theorem}

\noi{\bf Standard factorization of a Christoffel word}\\

\begin{definition}[\cite{1}]
Suppose $a$ is relatively prime to $b$, $(a, b > 0)$, The standard factorization of the Christoffel word $w$ of slope $\frac{a}{b}$ is the factorization $w = (w_1, w_2)$ where $w_1$ encodes the portion of the Christoffel path from (0, 0) to the closest point $C$ on the path having label $\frac{1}{b}$ and $w_2$ encodes the portion from $C$ to $(b, a)$. \\

For example, the standard factorization of the Christoffel word of slope $\frac{4}{7}$ is given by $w = (xxy, xxyxxyxy)$.\\
It has also been shown in \cite{1} that, given a Christoffel word w of slope $\frac{a}{b}$, $w$ can always be factorized as the product of two words $w_1$ and $w_2$ where both $w_1, w_2$ are Christoffel words and this factorization is unique.\\
\end{definition}

\noi{\bf The Christoffel Tree}\\

The Christoffel tree is an infinite binary tree where each node is of the form $(u, v)$ which represents a Christoffel word occurring in its standard factorization form and the left, right descendants of which are $(u, uv)$ and $(uv, v)$ respectively. The root of this tree is the Christoffel word of slope $\frac{1}{1}$, i.e. $(x, y)$. It is shown in \cite{1} that every Christoffel word appears exactly once on this tree.

\begin{figure}[h!]
\centering
\includegraphics{rsafig3.jpg}
\caption{The Christoffel Tree}
\label{fig2.3}
\end{figure}
\ \\
\noi{\bf The Stern-Brocot Tree}\\

The mediant of two fractions $\frac{a}{b}$ and $\frac{c}{d}$ is $\frac{a+c}{b+d}$. This operation gives rise to the Stern-Brocot sequence as follows:\\
Let $S_0$ denote the sequence $\frac{0}{1}$, $\frac{1}{0}$ (we view $\frac{1}{0}$ as a formal fraction for the purposes of the construction of the successive terms of the sequence).\\
For $i > 0$, $S_i$ is constructed from $S_{i-1}$ by inserting between consecutive elements of the sequence their median. The first few iterations of this process yields the following sequence:\\

\noi $\frac{0}{1}, \frac{{1}}{{1}}, \frac{1}{0}$ \qquad $(S_1)$\\
$\frac{0}{1}, \frac{{1}}{{2}}, \frac{1}{1}, \frac{{2}}{{1}}, \frac{1}{0}$ \qquad $(S_2)$\\
$\frac{0}{1}, \frac{{1}}{{3}}, \frac{1}{2}, \frac{{2}}{{3}}, \frac{1}{1}, \frac{{3}}{{2}}, \frac{2}{1}, \frac{{3}}{{1}}, \frac{1}{0}$ \qquad $(S_3)$\\
$\frac{0}{1}, \frac{{1}}{{4}}, \frac{1}{3}, \frac{{2}}{{5}}, \frac{1}{2}, \frac{{3}}{{5}}, \frac{2}{3}, \frac{{3}}{{4}}, \frac{1}{1}, \frac{{4}}{{3}}, \frac{3}{2}, \frac{{5}}{{3}}, \frac{2}{1}, \frac{{5}}{{2}}, \frac{3}{1}, \frac{{4}}{{1}}, \frac{1}{0}$ \qquad $(S_4)$\\

\begin{definition}[\cite{1}]
The Stern-Brocot Tree is an infinite binary tree in which the vertices of the
$i^{th}$ $(i > 0)$, level are the mediants obtained in the $i^{th}$ iteration of the Stern-Brocot sequence. \\
\end{definition}

\begin{figure}[h!]
\centering
\includegraphics{rsafig4.jpg}
\caption{The Stern-Brocot Tree}
\label{fig2.4}
\end{figure}

\begin{definition}[\cite{1}]
For a natural number $k$, the $k^{th}$ diagonal of the Stern-Brocot tree $L_k$ is the sequence made up of each $k^{th}$ term from each level beginning at the first level and the $k^{th}$ right diagonal of the Stern-Brocot tree $R_k$ is the sequence made up of each $k^{th}$ term taken from the end of each level beginning at the first level.\\

\noi The first few  and right diagonals are mentioned below:
\begin{align*}
L_1 & = \left\{ \frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \ldots \right\}, & L_2 & = \left\{ \frac{2}{1}, \frac{2}{3}, \frac{2}{5}, \ldots \right\}, 
& L_3 & = \left\{ \frac{3}{2}, \frac{3}{5}, \frac{3}{8}, \ldots \right\} \dots\\
R_1 & = \left\{ \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \ldots \right\}, & R_2 & = \left\{ \frac{1}{2}, \frac{3}{2}, \frac{5}{2}, \ldots \right\}, 
& R_3 & = \left\{ \frac{2}{3}, \frac{5}{3}, \frac{8}{3}, \ldots \right\} \dots
\end{align*}
\end{definition}

We refer the readers to \cite{4} and \cite{5} for a comprehensive understanding of the properties of the Stern-Brocot Tree.

\begin{theorem}[\cite{1}]
The Christoffel Tree is isomorphic to the Stern-Brocot Tree via the map that associates to the vertex $(u, v)$ of the Christoffel tree, the function $\frac{{uv}_y}{{uv}_x}$. (Here ${uv}_y$ denotes the number of $y'$s in the Christoffel word $uv, {uv}_x$ denotes the number of $x'$s in the Christoffel word $uv$.) The inverse map associates to a fraction $\frac{a}{b}$ the pair $(u, v)$ where $(u, v)$ is the standard factorization of the Christoffel word of slope $\frac{a}{b}$.
\end{theorem}

\begin{definition}[\cite{2}]
Let $w = C \left( \frac{a}{b} \right)$, the Christoffel word of slope $\frac{a}{b}$ then the directive sequence $\Delta \left( \frac{a}{b} \right) = i_1 i_2 \dots i_n$ where $i_k \in \{0, 1\}$ denotes the path from the root of the Christoffel tree to the Christoffel word $C \left( \frac{a}{b} \right)$ as follows: at step $k$ if $i_k = 0$ then go otherwise if $i_k = 1$ go right.
\end{definition}

\begin{theorem}[\cite{1}]
Let $w$ be a Christoffel word of slope $\frac{a}{b}$ where the continued fraction of $\frac{a}{b}$ is given by $[a_0, a_1, \ldots, a_z] = [a_0, a_1, \ldots a_z - 1, 1]$. Then the directive sequence of this Christoffel word has the following form\\
$\Delta \left( \frac{a}{b} \right) = 1^{a_0} 0^{a_1} \dots p^{a_{z-1}}$ where $p \in \{0, 1\}$.\\
Here $[a_0, a_1, \ldots, a_z] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{\cdots + \cfrac{1}{a_z}}}$
\end{theorem}

\section{Results}

\begin{theorem}
Let $r_{n,j}$ denote the $j^{th}$ term of the $n^{th}$ row of the Stern-Brocot tree. If $j$ is of the form $j = 2^km - 2^{k-1}$ where $k \geq 2$, $m > 0$, then $r_{n,j} = r_{n-1,\frac{j}{2} + } r_{n-k,m}$ and if $j = 2^km - 2^{k-1} + 1$ where $k \geq 2$, $m > 0$, then $r_{n,j} = r_{n-1,\frac{j-1}{2}+1} + r_{n-k,m}$, where + denotes the mediant operation of the Stern-Brocot tree.
\end{theorem}

\begin{proof}
Consider an arbitrary term of the Stern-Brocot tree, say $r_{a,b}$ i.e. the $b^{th}$ term of the $a^{th}$ row. From the construction of the Stern-Brocot tree it can be observed that this term serves as one of the mediants to the terms in the succeeding rows of the form $r_{a+1,2b-1}$, $r_{a+{2,2}^2b-2}$, $r_{a+{3,2}^3b-2^2}$, $\ldots$, $r_{a+n,2^nb-2^{n-1}}$, $\ldots$ and terms of the form $r_{a+1,2b}$, $r_{a+{2,2}^2b-1}$, $r_{a+{3,2}^3b-3}$, $\ldots$ $r_{a+n,2^n-2^{n-1}+1}$, $\ldots$.\\
Thus if $j = 2^km-2^{k-1}$ or $j = 2^km-2^{k-1}+1$ then one of the mediants of $r_{n,j}$ is given by $r_{n-k,m}$. Furthermore, the other mediant for any term $r_{n,j}$ of the Stern-Brocot tree where $j$ is even is given by the $\frac{j}{2}th$ term in the preceding row and if $j$ is odd it is given by the $\frac{j-1}{2}+1 \ th$ term of the preceding row.
\end{proof}

\begin{theorem}\label{thm3.2}
Let $r_{n,j}$ denote the $jth$ term of the $nth$ row of the Stern-Brocot tree given by the fraction $\frac{a}{b}$. If $\frac{c}{d}$ is any fraction of the Stern-Brocot tree of the form $r_{n+k,2^kj-2^{k-1}+1}$, where $k = 1, 2, 3, \ldots$ then $c^{-1}\text{ mod }(c+d) = a+b$.
\end{theorem}

\begin{proof}
Consider the Christoffel word $w$ of slope $\frac{a}{b}$ and suppose $(w_1, w_2)$ is its standard factorization.\\
Since the standard factorization is obtained at the point of the Christoffel path that is closest to the line segment joining the origin to $(b, a)$, thus the label of the point $(i, j)$, that is closest to the line segment is given by $\frac{1}{b}$.\\
That is, $\frac{(ia-jb)}{b} = \frac{1}{b}$., from which $ai = 1+bj$, where $i+j$ is the length of $w_1$\\
Consider now the product 
\begin{align*}
a(i+j)\text{ mod }(a+b) & = ai + aj\text{ mod }(a+b)\\
& = 1+bj+aj\text{ mod }(a+b)\\
& = 1+(a+b)j\text{ mod }(a+b)\\
& = 1\text{ mod }(a+b) 
\end{align*}
Thus, if $w = (w_1, w_2)$ is the standard factorization of the Christoffel word of slope $\frac{a}{b}$ then we have
$a|w_1| = 1\text{ mod }(a+b)$ where $|w_1|$ denotes the length of the word $w_1$.\\
The Christoffel words corresponding to the terms of the Stern-Brocot tree of the form $r_{n+k,2^kj-2^{k-1}+1}$ for $k = 1, 2, 3, \ldots$ in their respective standard factorization form are as follows:\\
$(w_1w_2, w_2), (w_1w_2, w_1w_2w_2), (w_1w_2, w_1w_2w_1w_2w_2), \ldots$\\
Thus, in each of these Christoffel words, the length of the first word of their respective standard factorizations is given by $|w_1|+|w_2| = a+b$.\\
Using which we conclude that $c^{-1}\text{ mod }(c+d) = a+b$.
\end{proof}

\begin{remark}
The above result can be used to determine for a given natural number $k$, all the possible natural numbers along with their respective modulos that have $k$ as their modulo multiplicative inverse.\\
For example, if $k = 5$, to determine the set of all natural numbers and the respective modulos that have 5 as their modulo multiplicative inverse we need only consider fractions in the Stern-Brocot tree of the form $\frac{a}{b}$ where $a+b = 5$.  Since $a, b$ must be relatively prime there are $\phi(5)$ such possible fractions, where $\phi$ denotes the Euler’s Totient function.\\
These fractions are given by $\frac{1}{4}, \frac{2}{3}, \frac{3}{2}$ and $\frac{4}{1}$.\\
For the $r_{n,j}th$ term of the Stern-Brocot tree, the terms of the form $r_{n+k,2^kj-2^{k-1}+1}$ are found on the Stern-Brocot tree by going right at the $r_{n,j}th$ node and consecutively left thereafter. Thus, we can determine those fractions using the directive sequence of $r_{n,j}$ as shown below.\\
$\frac{1}{4} = \{0, 4\}$ which has the directive sequence is $1^0 0^3$. Thus, taking a right turn at the node $\frac{1}{4}$ we get the directive sequence $1^0 0^3 1^1$ and the corresponding continued fraction is $\{0, 3, 2\} = \frac{2}{7}$. Taking consecutive lefts after the node $\frac{2}{7}$ on the Stern-Brocot tree we get the continued fractions $\{0, 3, 1, 2\} = \frac{3}{11}$, $\{0, 3, 1, 3\} = \frac{4}{15}$, $\ldots$, $\frac{n+1}{4n+3}$,$\ldots$ where $n = 1, 2, 3, \ldots$\\
Using the above result, we have $(n+1)^{-1}\text{ mod }(5n+4) = 5$ which can be easily verified, since $5(n+1) = 5n+5 = 1\text{ mod }(5n+4)$.\\
Similarly, for the fraction $\frac{2}{3}$, we obtain fractions of the form $\frac{2n+1}{3n+1}$ for $n = 1, 2, 3, \ldots$ satisfying $(2n+1)^{-1}= 5\text{ mod }(5n+2)$.
For the fraction $\frac{3}{2}$, the fractions $\frac{3n+2}{2n+1}$ for $n = 1, 2, 3, \ldots$ satisfy $(3n+2)^{-1} = 5\text{ mod }(5n+3)$.\\
For the fraction $\frac{4}{1}$, the fractions $\frac{4n+1}{n}$ for $n = 1, 2, 3, \ldots$ satisfy $(4n+1)^{-1} = 5\text{ mod }(5n+1)$\\
Hence theorem \ref{thm3.2} can be a useful tool in determining the set of all numbers along with their respective modulos that has $k$ as their modulo multiplicative inverse for any natural number $k$.\\
\end{remark}

\noi{\bf Notation:} We label the $x'$s and $y'$s of a Christoffel word as explained in the following example. For the Christoffel word $w$ of slope $\frac{3}{2}$ that is $xyxyy$, $w[1]$ denotes the $1st$ $x$ of $w$, $w[3]$ denotes the $2nd$ $x$ of $w$, $w[2]$ denotes the $1st$ $y$ of $w$, $w[4]$ denotes the $2nd$ $y$ of $w$ and $w[5]$ denotes the $3rd$ $y$ of $w$. 

\begin{theorem}\label{thm3.3}
Let $\frac{a}{b}$ be the first term of the $kth$ left diagonal of the Stern-Brocot tree, $k > 1$ and $w_\frac{a}{b}$ its corresponding Christoffel word. If $ai = 1\text{ mod }(a+b)$ where $w_\frac{a}{b}[i]$ is the $jth$ $y$ of $w_\frac{a}{b}$, then $c(i+(n-1)j) = 1\text{ mod }(c+d)$ where $\frac{c}{d}$ is the $nth$ term of $L_k$.
\end{theorem}

\begin{proof}
Since $a$ and $b$ are relatively prime, the values $ai\text{ mod }(a+b)$ for $i = 0, 1, 2, \dots (a+b)$ assumes each value from 0 to $a+b-1$ exactly once, except for 0. From the algebraic definition of the Christoffel word the $ith$ letter of the word is $y$ if $a(i-1)\text{ mod }(a+b) > ai\text{ mod }(a+b)$.\\
Therefore, if $ai = 1\text{ mod }(a+b)$ where $a \neq 1$ then the $ith$ position of the Christoffel word of slope $\frac{a}{b}$ always corresponds to the letter $y$ and this position helps determine the modulo multiplicative inverse of $a\text{ mod }(a+b)$. \\
We only consider the left diagonals $L_k$ where $k > 1$ since these diagonals have elements of the form $\frac{a}{b}$ where $a > 1$.\\
We obtain the modulo multiplicative inverse of $c\text{ mod }(c+d)$ by examining the shift in the position of this letter $y$ in the successive terms of the left diagonals. \\
Suppose $w_\frac{a}{b}$ denotes the first word of the left diagonal $L_k$ and $w_\frac{a}{b}[i]$, the $jth$ $y$ of $w_\frac{a}{b}$ where $ai = 1\text{ mod }(a+b)$. Thus, the number of $y'$s prior to $w_\frac{a}{b}[i]$ is $j-1$. Each of the successive terms of the left diagonal are of the form $\frac{a}{b}$, $\frac{a}{a+b}$, $\frac{a}{2a+b}$, $\ldots$ which is a result of applying the Christoffel morphism $G = (x, xy)$ on the corresponding Christoffel words of those slopes.  This causes the letters $x$ to remain unchanged and the letter $y$ to be replaced by the word $xy$ due to which the $jth$ $y$ that was in the $ith$ position of the word shifts to the $(i+j)th$ position in the next word of the left diagonal. Proceeding in this way the position of the letter $y$ shifts from the $ith$ position to the position $i + (n - 1)j$ for the $nth$ word of the left-diagonal which is the Christoffel word of slope $\frac{c}{d}$, thus we have, $c(i+(n-1)j) = 1\text{ mod }(c+d)$.
\end{proof}

\noi{\bf Remark:} A similar result can be found for the right diagonals, which we state below, the proof of which can be argued using the Christoffel morphism $D = (xy, y)$. 

\begin{corollary}\label{cor3.3}
Let $\frac{a}{b}$ be the first term in $R_k$, the $kth$ right diagonal of the Stern-Brocot tree, $k > 2$ and $w_\frac{a}{b}$ its corresponding Christoffel word. If $ai = 1\text{ mod }(a+b)$ where $w_\frac{a}{b}[i]$ is the $jth$ $y$ of $w_\frac{a}{b}$, then $c(ni-(n-1)j) = 1\text{ mod }(c+d)$.
\end{corollary}

\begin{remark}\label{rem3.1}
Theorem \ref{thm3.3} and Corollary \ref{cor3.3} can be used to determine the modulo multiplicative inverse of a natural number with respect to a sequence of relatively prime numbers and the modulo multiplicative inverse of a sequence of natural numbers with respect to a sequence of relatively prime numbers using the information from the first term of the left or right diagonals of the Christoffel and Stern-Brocot trees. This removes the need for repeated division involved in the Euclidean algorithm for each pairs of numbers proving to be an efficient tool. This is illustrated in the examples below:\\
Consider the left diagonal $L_3 = \left\{ \frac{3}{2}, \frac{3}{5}, \frac{3}{8} \ldots, \frac{3}{3n-1}, \ldots \right\}$. The Christoffel word of slope $\frac{3}{2}$ is $w = xyxyy$. Since $3.2 = 1\text{ mod }5$ and $w[2]$ denotes the $1st$ $y$ of $w$, thus $3(2+(n-1)1) = 3(n+1) = 1\text{ mod }(3n+2)$ for $n = 1, 2, 3, \ldots$.\\
Thus, we can determine the modulo multiplicative inverse of 3 with respect to a sequence of relatively prime numbers using the first term of the left diagonal $L_3$.\\
For the right diagonal $R_3 = \left\{ \frac{2}{3}, \frac{5}{3}, \frac{8}{3}, \ldots \frac{3n-1}{3}, \ldots \right\}$. The Christoffel word of slope $\frac{2}{3}$ is $w = xxyxy$. Since $2.3 = 1\text{ mod }5$ and $w[3]$ denotes the $1st$ $y$ of $w$, thus $(3n-1)(3n-(n-1)1) = (3n-1)(2n+1) = 1\text{ mod }(3n+2)$ for $n = 1, 2, 3, \ldots$
\end{remark}

\section{An application of the Christoffel and Stern-Brocot tree in attacking the RSA cryptosystem}

In the RSA cryptosystem, Bob generates a product of two large prime numbers $N = pq$ and shares it publicly, along with an enciphering key $e_k$ that satisfies the property $g.c.d(e_k, \phi(n)) = 1$, where $\phi$ is the Euler's totient function. Anyone can use Bob's public key to send him a message, by converting the plaintext message into an integer $m$, encrypting it using the enciphering key $e_k$ and the product $N$ by computing $c = m^{e_k}(\text{mod }N)$, and sending the resulting cipher text $c$ to Bob. Bob uses his knowledge of $p-1$ and $q-1$ to calculate a deciphering key $d_k$ that solves the congruence $e_k d_k \equiv 1\text{ mod }(p-1)(q-1)$. With this deciphering key, Bob can decrypt the received cipher text $c$ and obtain Alice's original message.\\
Bob's public key consists of the product of two secret primes $p$ and $q$, denoted by $N$. If an eavesdropper named Eve knows the value of $(p-1)(q-1)$, she can decrypt messages sent to Bob by solving the congruence $x^{e_k} \equiv c\text{ mod }N$. The expression for $(p-1)(q-1)$ can be expanded as $(p-1)(q-1) = N - (p+q) + 1$, from which we have $p+q = N+1-(p-1)(q-1)$. Since Bob has already published the value of $N$, Eve knows it. \\
We now illustrate with two toy examples, how theorem \ref{thm3.2} can be used to perform an attack on the RSA cryptosystem to guess the possible values of $(p-1)(q-1)$ and in turn find the values of $p$ and $q$. The attack we present here works on the assumption that $p$ and $q$ are two primes with the same number of digits.

\begin{example}
Suppose Bob shares his public key $(e_k = 7, N = 187)$.   To find the possible values of $(p-1)(q-1)$, we consider all fractions on the Stern-Brocot tree of the form $\frac{a}{b}$ where $a+b = 7$, where $a$ and $b$ are relatively prime. There are $\phi(7)$ such fractions. These are $\frac{1}{6}, \frac{2}{5}, \frac{3}{4}, \frac{4}{3}, \frac{5}{2}$ and $\frac{6}{1}$.\\
 Since the deciphering key $d_k$ satisfies $7d_k \equiv 1\text{ mod }\phi(187)$, using theorem \ref{thm3.2} we consider the fractions $\frac{c}{d}$ in the Stern-Brocot tree which are terms of the form $r_{n+k,2^kj-2^{k-1}+1}$ for $k = 1, 2, 3, \ldots$ where $\frac{a}{b}$ is the $r_{n,j}th$ term of the Stern-Brocot tree as each of these terms will satisfy $7c \equiv 1\text{ mod }(c+d)$. Thus $c+d$ is a possible value of $\phi(187) = (p-1)(q-1)$. These terms can be found as explained in remark \ref{rem3.1}.\\
For the fraction $\frac{1}{6}$ we get terms of the form $\frac{2}{11}, \frac{3}{17}, \ldots, \frac{n+1}{6n+5}, \ldots$ Thus, one set of possible values for
$(p-1)(q-1)$ is obtained by the sum $n+1+6n+5 = 7n+6$ for $n = 1, 2, 3, \ldots$\\
Similarly, when examined for the fractions $\frac{2}{5}, \frac{3}{4}, \frac{4}{3}, \frac{5}{2}$ and $\frac{6}{1}$ the other possible set of values for
$(p-1)(q-1)$ respectively are $7n+3, 7n+2, 7n+5, 7n+4$ and $7n+1$.\\
From the construction of the Stern-Brocot Tree, if $\frac{c}{d}$ is one of the $r_{n+k,2^kj-2^{k-1}+1}$ terms then it is seen that $c+d$ is of the form $(a+b)n+d$ where $n = 1, 2, 3, \ldots$ and $d < a+b$, $\gcd{(a+b,d)} = 1$.\\
Thus, the possible values of $(p-1)(q-1)$ are of the form $e_kn+d$ where $e_k$ is the encryption key, $d$ is a natural number satisfying $d < e_k$ and $d$ is relatively prime to $e_k$, where $n = 1, 2, 3, \ldots$\\
So $p+q$ is of the form $pq+1-(e_kn+d)$.\\
We can further give a better choice of values for $n$ by observing that since $pq = 187$, $p+q$ must be a 2 digit number.\\
The reasoning for this is from the following observation. If $p$ and $q$ are two $m$ digit numbers whose product $pq < \frac{1}{4} (10)^{2m}$ then $p+q$ is an $m$ digit number. Additionally, if $pq \geq \frac{1}{4} (10)^{2m}$ then $p+q$ is an $m+1$ digit number.\\
Further since $d$ can take the values 1, 2, 3, 4, 5, 6 we get, $n > 12$ since if $n \le 11$, then $188-(7n+d)$ will never be a 2 digit number. Similarly, we can also deduce that $n < 26$ for $p+q$ to be a 2 digit number.\\
Thus, the possible values for $p+q$ are of the form $188-(7n+d)$ where $d$ can take the values 1, 2, 3, 4, 5, 6 and $12 \le n \le 25$.\\
When $n = 12$ the only values of $d$ that can be considered are 5 and 6 as only these values will result in a two-digit number for $p+q$. Similarly, when $n = 25$ the only values $d$ may assume are 1, 2 and 3 or else $p+q$ will be a single digit number \\
Now we know the values of $pq$ and the possible values of $p+q$. To get the correct value of $p, q$ we substitute these possible values in the quadratic equation $x^2-(p+q)x+187 = 0$, which can be written as $x^2-(188-(7n+d))x+187 = 0$ until we receive a solution consisting of two natural numbers. This is realized when $n = 22$ and $d = 6$, we get the quadratic equation, $x^2-(188-160)x+187 = 0$ i.e $x^2-28x+187 = 0$ whose roots are 11 and 17 which are the values of $p$ and $q$.
\end{example}

\begin{example}
If $pq = 2430101$, $e_k = 948047$, to determine the values of $p$ and $q$ we follow the same approach as above. \\
Since $pq = 2430101$, $p+q$ must be a 4 digit number.\\
We now consider the values $2430102-(948047n+d)$ where $d < 948047$ and $g.c.d(948047, d) = 1$ such that $2430102-(948047n+d)$ is a 4 digit number. If $n = 1$ this is impossible and if $n = 3$ we have $948047n+d) > 2430101$. Therefore $n = 2$.\\
Thus, $p+q$ is of the form $1896094+d$.\\
Substituting the values of $pq$ and the possible values of $p+q$ in the equation we have, 
\[x^2-(2430102-(1896094+d))x+2430101 = 0\]
This equation gives us a positive integer solution when $d = 530798$. The solutions are 1987 and 1223, which are the values of the two primes considered for this RSA cryptosystem. \\
Based on this attack using properties of the Stern-Brocot Tree we present a novel algorithm that can be used to attack the RSA cryptosystem.
\end{example}

\section{The Algorithm to attack the RSA Cryptosystem}

\begin{enumerate}
\item Using the value of $pq$ determine the number of digits in $p+q$ as shown above. 

\item Let $w$ and $y$ denote the smallest and largest natural number respectively for which $pq+1-w$ and $pq+1-y$ respectively have the same number of digits as $p+q$.

\item Determine the values of $n$ using the inequality $\lc \frac{w-(e_k-1)}{e_k} \rc \le n \le \lc \frac{y-(e_k-1)}{e_k} \rc$

\item For each $n$ determined in step 3 and for each $1 \le d < e_k$ such that $g.c.d(d, e_k) = 1$

\item If both solutions of $x^2-(pq+1-(e_kn+d))x+pq = 0$ are natural numbers

\item Print solutions
\end{enumerate}

Steps 1,2 and 3 are used to determine the possible values of $n$ for which $pq+1-(e_kn+d)$ will give us the same number of digits as $p+q$. In step 3, we use $e-1$ as this is the largest possible value of $d$.\\
Steps 4 and 5, use the values of $n$ and $d$ to determine the values of $p$ and $q$.\\
The first three steps in the above algorithm can be determined in constant time. The Euclidean algorithm that computes the g.c.d of two natural numbers $a$ and $b$ runs in $O(\log(\min{(a, b)})$. Step 4 checks each number from 1 to $e_k-1$ to determine if a number is relatively prime to $e_k$. Since the largest possible value for $d$ is $e_k-1$, this step is bounded by $O(e_k \log e_k)$. Computing the solutions of quadratic equations can be done in constant time. Thus, if there are $m$ possible values of $n$ determined in step 3, then the total time taken for the algorithm is $O({me}_k \log e_k)$. 

\section{Conclusion}

This article expands the understanding of the class of Christoffel words by investigating their combinatorial properties. Previous studies \cite{1,2} and \cite{3} have already explored certain aspects of this class, and our work builds upon these findings. We introduce novel properties by employing the Christoffel and Stern-Brocot trees to address the computation of modular multiplicative inverses for natural numbers. One contribution lies in the significance of Theorem \ref{thm3.2}, which plays a crucial role in determining the set of natural numbers for which a given number acts as the modulo multiplicative inverse. Additionally, leveraging the ordering of terms in the Christoffel and Stern-Brocot Trees through left or right diagonal sequences, Theorems \ref{thm3.3} and corollary \ref{cor3.3} allow for the computation of modular multiplicative inverses for a sequence of natural numbers using information derived solely from the first term of the sequence. We have shown an application of the Christoffel and Stern-Brocot Trees in attacking the RSA cryptosystem. Further investigation of these properties and their practical implications in Cryptography, particularly in the context of modular arithmetic-based encryption and decryption key computation, presents an intriguing avenue for future research. By delving deeper into these findings, researchers can potentially enhance the security and efficiency of cryptographic systems.

\begin{thebibliography}{99}
\bibitem{1} Berstel Jean, Lauve Aaron, Reutenauer Christophe, Saliola Franco: Combinatorics on Words Christoffel Words and Repetitions in Words. American Mathematical Society (2009) 
\bibitem{2} Lama Tarsissi: Balance properties on Christoffel words and applications. General Mathematics [math.GM]., Universite Grenoble Alpes (2017)
\bibitem{3} Reutenauer Christophe: From Christoffel Words to Markoff Numbers. Oxford University Press (2019)
\bibitem{4} Bates Bruce,Tognetti Keith: Locating Terms in the Stern-Brocot Tree. European Journal of Combinatorics {\bf 31}(3), 1020--1033 (2010). https://doi.org/10.1016/j.ejc.2007.10.005
\bibitem{5} Bates Bruce,Bunder Martin, Tognetti Keith: Linking the Calkin-Wilf and Stern-Brocot Trees. European Journal of Combinatorics {\bf 31}(7), 1637--1661 (2010). https://doi.org/10.1016/j.ejc.2010.04.002
\bibitem{6} Lothaire, M.: Combinatorics on Words. Cambridge University Press (2003)
\bibitem{7} Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman: An Introduction to Mathematical Cryptography. Springer. First Indian Reprint (2011)
\bibitem{8} Manuel Dominguez, David Clampitt, Thomas Noll: WF Scales, ME Sets, and Christoffel Words. Mathematics and Computation in Music. (MCM 2007), 477-488(2013)
\bibitem{9} S.Brlek, J-O Lachaud, X. Provencal, C. Reutenauer: Lyndon + Christoffel = digitally convex. Pattern Recognition. Volume 42, Issue 10 (2009). https://doi.org/10.1016/j.patcog.2008.11.010
\bibitem{10} Christian Kassel. Christophe Reutenauer: Sturmian morphisms, the braid group $B_4$, Christoffel words and bases of $F_2$.  Annali di Matematica Pura ed Applicata,Volume 186, pages 317–339,  Springer (2007) 
\end{thebibliography}

\end{document}