path: root/rappels-maths.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}[subsection]
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newtheorem{defn}[comcnt]{Définition}
\newtheorem{prop}[comcnt]{Proposition}
\newtheorem{lem}[comcnt]{Lemme}
\newtheorem{thm}[comcnt]{Théorème}
\newtheorem{cor}[comcnt]{Corollaire}
\newtheorem{rmk}[comcnt]{Remarque}
\newtheorem{exmps}[comcnt]{Exemples}
\newcommand{\limp}{\mathrel{\Rightarrow}}
\newcommand{\liff}{\mathrel{\Longleftrightarrow}}
\newcommand{\pgcd}{\operatorname{pgcd}}
\newcommand{\ppcm}{\operatorname{ppcm}}
\newcommand{\signe}{\operatorname{signe}}
\newcommand{\tee}{\mathbin{\top}}
\renewcommand{\qedsymbol}{\smiley}
%
%
%
\begin{document}
\title{Rappels maths pour crypto}
\author{David A. Madore}
\maketitle
{\footnotesize
\begin{center}
CVS: \verb=$Id: rappels-maths.tex,v 1.2 2008-09-29 21:40:25 david Exp $=
\end{center}
\par}
\pretolerance=10000
\tolerance=8000
%
%
%
\section{Entiers}

\subsection{L'anneau des entiers}

$\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ ensemble des
entiers relatifs.  Sous-ensemble $\mathbb{N}$.

Opérations : $+$, $\times$.

Rappeler : $(\mathbb{Z},0,+)$ est un groupe abélien,
$(\mathbb{Z},0,+,1,\times)$ est un anneau commutatif.

Mieux : anneau intègre.

Éléments inversibles : $1$ et $-1$.

Relation d'ordre...

%
\subsection{Écriture $b$-adique}

Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'écrit de
façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i<b$
entiers naturels « presque tous nuls » (expliquer).

Écriture usuelle : $b=10$.  Informatique : $b=2$.  Un nombre « de $n$
bits » signifie : inférieur à $2^n$.

Multiplier par $b$ revient à décaler tous les chiffres d'un cran vers
la gauche.

On passe pour l'instant sur l'écriture des nombres négatifs.

%
\subsection{Remarques sur la complexité des opérations}

Addition de nombres de $n$ bits : algorithme naïf en $O(n)$.

Multiplication : plus compliqué.

Algorithme naïf en $O(n^2)$.

\emph{Multiplication de Karatsuba} : utilise récursivement
l'identité ${(a_1 w + a_0)} \penalty0 {(b_1 w + b_0)} = a_1 b_1 w^2 +
[(a_1+a_0)(b_1+b_0)-a_1 b_1-a_0 b_0] w + a_0 b_0$ pour une complexité
en $O(n^{\frac{\log 3}{\log 2}})$ (soit $O(n^{1.58\ldots})$).  Facile
à implémenter.

\emph{Multiplication de Strassen} : par transformée de Fourier
rapide, complexité en $O(n\,\log^2 n)$, difficile à implémenter.
Amélioration de Schönhage : $O(n\,\log n\,\log\log n)$ ---
complètement théorique.

%
\subsection{Divisiblité (exacte)}

Définition.  Terminologie « diviseur de », « multiple de ».  Relation
réflexive, transitive.  Pas tout à fait antisymétrique (mais vrai dans
les entiers naturels).

Note : Les entiers $1$ et $-1$ divisent tous les entiers.  L'entier
$0$ est divisible par tous les entiers.

%
\subsection{Nombres premiers}

Un \textbf{nombre premier} $p$ est un entier (par convention :
positif) divisible seulement par $1$, $-1$, lui-même et son opposé ;
mais par convention, $1$ et $-1$ (et $0$...) ne sont pas premiers.

Les premiers nombres premiers sont donc : $2$, $3$, $5$, $7$, $11$,
$13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$,
$59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$, $97$...

\medbreak

Sur leur répartition :

Il y en a une infinité (Euclide).

Pour tout $x>1$, il y a toujours un nombre premier $p$ tel que
$x\leq p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »).

Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à
$\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée
Poussin : « théorème des nombres premiers »).  Moralement : la
probabilité qu'un nombre de $n$ bits aléatoire soit premier est
environ $n\,\ln 2$.

Beaucoup de questions ouvertes.  Par exemple : Conjecture des nombres
premiers jumeaux : existe-t-il une infinité de nombres premiers $p$
tels que $p+2$ soit aussi premier (tels que $3$, $5$, $11$, $17$,
$29$, $41$, $59$, $71$...) ?

\smallbreak

\textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors
$p$ divise $a$ ou $p$ divise $b$.

%
\subsection{Décomposition en facteurs premiers}

Pour tout entier $n$ \emph{non nul}, il existe une écriture
\emph{unique} (à l'ordre près) de $n$ comme produit d'une \emph{unité}
($1$ ou $-1$) et de nombres premiers : en regroupant les facteurs
premiers $p$,
\[
n = u\, 2^{v_2(n)} \, 3^{v_3(n)} \cdots p^{v_p(n)}\cdots
\]

Ici, $v_p(n)$ (un entier naturel) est l'exposant de la plus grande
puissance de $p$ qui divise $n$ : on l'appelle \emph{valuation
$p$-adique} de $n$.  Presque tous ces nombres sont nuls, ce qui permet
de donner un sens au produit infini.  Dire que $b|a$ signifie $v_p(b)
\leq v_p(a)$ pour tout $p$.

Quant à $u$, c'est simplement le signe de $n$.

%
\subsection{Remarques sur la complexité}

Toujours pour des nombres de $n$ bits.

\textbf{Tests de primalité :} \emph{polynomiaux}.  Un test polynomial
\emph{déterministe} est connu depuis seulement récemment
(Agrawal-Kayal-Saxena), démontrablement en $O(n^{12})$, sans doute
meilleur ($O(n^3)$ ?).  En pratique, des tests probabilistes sont
suffisants et plus efficaces (p.e., Miller-Rabin « pratiquement » en
$O(n^2)$) éventuellement complétés par des certificats de primalité
(p.e., test d'Atkin).

\textbf{Algorithmes de factorisation :} \emph{lents}.  Font appel à
des résultats difficiles de théorie algébrique et analytique des
nombres.  La meilleure méthode connue (« méthode du crible général de
corps de nombres ») a une complexité « attendue » (et heuristique) en
$O(e^{n^{1/3}\,(\log n)^{2/3}\,(\textrm{cte}+o(1))})$ (avec
$\textrm{cte} \approx 2$).

On ne pourra donc pas envisager d'utiliser la décomposition en
facteurs premiers pour calculer les pgcd.

%
\subsection{Valuation $p$-adique}

Si $n$ est un entier et $p$ un nombre premier, $v_p(n)$ est l'exposant
de la plus grande puissance de $p$ qui divise $n$.  Si $a/b$ est un
rationnel, on pose $v_p(a/b) = v_p(a)-v_p(b)$ (ne dépend pas de la
représentation $a/b$ choisie).  Par convention, $v_p(0) = +\infty$.

Quelle est la valuation $2$-adique de $192$ ?  $3$-adique ?
$5$-adique ?  Quelles sont les valuations $p$-adiques de
$-\frac{24}{11}$, pour tous les $p$ possibles ?

Propriétés de $v_p$ : produit (cf. lemme de Gauß), inégalité sur la
somme (et cas d'égalité)...  Dire que $x \in \mathbb{Q}$ est entier
signifie exactement $v_p(x) \geq 0$ pour tout $p$.

%
\subsection{Division euclidienne}

Si $a$ est un entier relatif et $b$ un entier naturel \emph{non nul},
il existe un unique couple $(q,r)$ tel que :
\begin{itemize}
\item $q$ est un entier relatif,
\item $r$ est un entier naturel tel que $0\leq r<b$, et
\item $a = bq + r$.
\end{itemize}
On dit que $q$ est le \emph{quotient} et $r$ le \emph{reste} de la
\textbf{division euclidienne} de $a$ par $b$.  (On appelle aussi $a$
le \emph{dividende} et $b$ le \emph{diviseur}.)

Si $b\geq 2$, dans l'écriture $b$-adique de $a$, le dernier chiffre
($a_0$ avec les notations précédentes) est égal au reste $r$ de la
division euclidienne de $a$ par $b$.

Dire que $r=0$ signifie exactement que $b$ divise $a$ (la division
euclidienne est alors \emph{exacte}).

\medbreak

\textbf{Algorithme naïf :} (celui de l'école primaire) en $O(n^2)$.

\textbf{Algorithme sophistiqué :} en $O(n\,\log n\,\log\log n)$ avec
Schönhage-Strassen + méthode de Newton (+ subtilités).

Méthode de Newton : on inverse $b$ (en précision fixe) en itérant $x
\leftarrow 2x - bx^2$.

Souvent implémentée \textbf{en matériel} pour certaines tailles
d'entiers (p. ex., division entière de 128 bits par 64 bits).

%
\subsection{PGCD}

Si $m_1,\ldots,m_\ell$ sont des entiers, on dit qu'un entier $c$ est
un \textbf{plus grand commun diviseur} (en abrégé : \emph{pgcd}) des
$m_i$ lorsque :
\begin{itemize}
\item $c$ divise chaque $m_i$ (i.e, $c$ est un diviseur commun
  des $m_i$), et
\item tout entier $d$ qui divise chaque $m_i$ (i.e., tout diviseur
  commun des $m_i$) divise aussi $c$.
\end{itemize}
En principe, le pgcd des $m_i$ est défini au signe près (si $c$ est un
pgcd des $m_i$ alors $-c$ l'est aussi) : en imposant qu'il soit
positif il devient unique et on parle alors \emph{du} pgcd des $m_i$.

Exemple : le pgcd de $6$ et $10$ est $2$ ; le pgcd de
  $6$, $10$ et $15$ est $1$.

\medbreak

Le pgcd \emph{existe} toujours : on peut le trouver à partir de la
décomposition en facteurs premiers par
\[
v_p(\pgcd(m_1,\ldots,m_\ell)) = \min(v_p(m_1),\ldots,v_p(m_\ell))
\]
(pour tout nombre premier $p$).  Mais ce n'est pas une méthode
efficace de calcul !

\textbf{Notation :} Parfois $m_1\wedge \cdots \wedge m_\ell$, mais
cette notation peut être utilisée pour d'autres sortes de bornes inf.
Certains textes anglais utilisent $(m,m')$ pour le pgcd de deux
entiers.  La notation $\pgcd(\cdots)$ est évidemment la plus claire.

\medbreak

\textbf{Quelques propriétés :}
\begin{itemize}
\item le pgcd d'un seul entier $m$ est lui-même (et le pgcd de zéro
entiers est $0$),
\item le pgcd est associatif (par exemple\\
  $\pgcd(m_1,m_2,m_3) = \pgcd(\pgcd(m_1,m_2),m_3)$),
\item le produit est distributif sur le pgcd\\
  ($\pgcd(cm_1,\ldots,cm_\ell) = |c|\,\pgcd(m_1,\ldots,m_\ell)$),
\item on peut toujours effacer des $0$ d'un pgcd,
\item dès qu'un des entiers est $1$ ou $-1$, le pgcd est $1$,
\item le pgcd d'une famille infinie se définit sans difficulté.
\end{itemize}

%
\subsection{Entiers premiers entre eux}

Lorsque $\pgcd(m_1,\ldots,m_\ell)=1$, on dit que les $m_i$ sont
\textbf{premiers entre eux} \emph{dans leur ensemble}.

Lorsque $\pgcd(m_i,m_j)=1$ pour tous $i\neq j$, on dit que les $m_i$
sont premiers entre eux \emph{deux à deux}.

\textbf{Lemme de Gauß amélioré :} Si $m$ et $n$ sont premiers entre
eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$.

\textbf{Dirichlet :} La probabilité pour que deux entiers « tirés au
  hasard » soient premiers entre eux est $\frac{6}{\pi^2}$.

%
\subsection{PPCM}

Définition analogue au PGCD.  Exemple : le ppcm de $6$ et $10$
est $30$ ; le ppcm de $6$, $10$ et $15$ est aussi $30$.  Lien avec la
DFP (pour un nombre fini d'entiers).  Le ppcm d'une famille infinie
d'entiers est défini, mais parfois surprenant (quel est le PPCM de
tous les nombres premiers ?).

%
\subsection{Relation de Bézout}

Si $a$ et $b$ sont premiers entre eux (c'est-à-dire $\pgcd(a,b) = 1$)
il existe des entiers $u$ et $v$ tels que $au + bv = 1$ (on verra
pourquoi plus loin) : on appelle cette égalité une \textbf{relation de
  Bézout}\footnote{Étienne Bézout (1730--1783), avec un accent aigu.}
entre $a$ et $b$.

Réciproquement, l'existence d'une relation de Bézout entre $a$ et $b$
implique que $a$ et $b$ sont premiers entre eux (et alors les
coefficients, $u$ et $v$, sont aussi premiers entre eux).  En effet,
tout diviseur commun de $a$ et $b$ doit diviser $au+bv$.

Exemple : $42\times 38 - 55 \times 29 = 1$ constitue une relation de
Bézout entre $42$ et $55$.  On verra plus loin comment obtenir une
relation de Bézout.

Naturellement, ajouter $b$ à $u$ et $-a$ à $v$ donne une nouvelle
relation de Bézout entre $a$ et $b$.  Donc il n'y a pas unicité.

Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$
(écrits sous forme irréductible) sont \emph{adjacents}.

\medbreak

Plus généralement, si $\pgcd(a,b) = d$, on peut trouver $u$ et $v$
tels que $au+bv = d$.

%
\subsection{Algorithme d'Euclide}

Soit à calculer le pgcd de deux entiers $a$ et $b$.
\textbf{L'algorithme d'Euclide} pour ce faire est le suivant :
\begin{itemize}
\item Initialiser : $(m,n) \leftarrow (|a|,|b|)$.
\item Tant que $n\neq 0$, répéter :
\begin{itemize}
\item Faire $(m,n) \leftarrow (n,r)$ où $r$ est le reste de la division
  euclidienne $m=nq+r$ de $m$ par $n$.
\end{itemize}
\item Renvoyer $m$ (le pgcd recherché).
\end{itemize}

\smallskip
\textbf{Invariant :} $\pgcd(m,n) = \pgcd(a,b)$ (constant)

\medbreak
Exemple : soit à calculer le pgcd de $a=98$ et
$b=77$ :
\begin{itemize}
\item $(m,n)=(98,77)$ ; division euclidienne $98 = 77\times 1 + 21$ ;
\item $(m,n)=(77,21)$ ; division euclidienne $77 = 21\times 3 + 14$ ;
\item $(m,n)=(21,14)$ ; division euclidienne $21 = 14\times 1 + 7$ ;
\item $(m,n)=(14,7)$ ; division euclidienne $14 = 7\times 2 + 0$ ;
\item $(m,n)=(7,0)$ ; on renvoie $7$.
\end{itemize}

\medbreak
\textbf{Algorithme d'Euclide « étendu »} : L'idée est
de « remonter » les coefficients dans l'algorithme d'Euclide : la
dernière division $m=nq+1$ donne une relation $1 = m-nq$ puis on
remplace $n$ (qui est lui-même un reste de division euclidienne) et
ainsi de suite jusqu'à trouver une relation entre les entiers $a$ et
$b$ de départ.

En mémoire constante, cela donne :

Soit à calculer une relation de Bézout entre deux entiers $a$ et $b$
(premiers entre eux) :
\begin{itemize}
\item $(m,n,u,v,u',v') \leftarrow (|a|,|b|,\signe(a),0,0,\signe(b))$.
\item Tant que $n\neq 0$, répéter :
\begin{itemize}
\item Division euclidienne de $m$ par $n$ : soit $m =
nq+r$.
\item Remplacer $(m,n,u,v,u',v') \leftarrow (n,r,u',v',u-qu',v-qv')$.
\end{itemize}
\item Vérifier $m=1$ (le pgcd est bien $1$).
\item Les coefficients recherchés sont $u$ et $v$ (on a $au+bv = 1$).
\end{itemize}

\textbf{Invariants :} $au+bv=m$ et $au'+bv'=n$.

%
\section{Congruences et entiers modulaires}

\subsection{Congruence}

Soit $m$ un entier fixé pour le moment :

Si $x$ et $x'$ sont entiers, on dit que $x$ et $x'$ sont
\textbf{congrus} modulo $m$, noté $x \equiv x' \pmod{m}$, lorsque
$x-x'$ est multiple de $m$.  Relation réflexive, symétrique,
transitive.

Compatibilité avec les opérations : (à $m$ fixé,) si $x\equiv x'$ et
$y \equiv y'$ alors $x+y \equiv x'+y'$ et $xy \equiv x'y'$.  À $m$
variable : si $m|m'$ alors $x \equiv x' \pmod{m'}$ implique $x\equiv
x' \pmod{m}$ (la congruence modulo $m'$ est \emph{plus fine} que
modulo $m$).

Représentants : si $m \geq 1$ alors chaque entier est congru
modulo $m$ à l'un des nombres $0,1,2,\ldots,(m-1)$ (le reste de sa
division euclidienne par $m$ !).

Exemple de $\mathbb{Z}/2\mathbb{Z}$ avec pair=$\bar 0$ et impair=$\bar
1$.

On veut définir $\mathbb{Z}/m\mathbb{Z} = \{\bar 0, \bar 1, \bar 2,
\ldots, \overline{m-1}\}$ de façon analogue : pour ajouter $\bar x$ et
$\bar y$, on consière $\bar x + \bar y = \overline{x+y}$ et $\bar x\,
\bar y = \overline{xy}$.  Reste à savoir ce que la barre veut dire !

%
\subsection{Généralité sur les quotients}

Généralité : soit $E$ un ensemble et $\sim$ une relation d'équivalence
(i.e., réflexive, symétrique, transitive) sur $E$, on appelle
$E/{\sim}$ l'ensemble des classes d'équivalence de $E$ modulo $\sim$
(la classe d'équivalence d'un élément $x\in E$ est l'ensemble des
éléments $x'\in E$ tels que $x\sim x'$).  On note $\pi \colon E \to
(E/{\sim})$ la fonction qui envoie $x\in E$ sur sa classe
d'équivalence $\pi(x) = \bar x$.  Ainsi : $\pi(x) = \pi(x')$ ssi $x
\sim x'$.  (Moralement : on a transformé la relation d'équivalence
$\sim$ en une vraie égalité.)

Si on a sur $E$ une opération binaire, disons, $\tee$, telle que $x
\sim x'$ et $y \sim y'$ impliquent $(x\tee x') \sim (y\tee y')$ (on
dit que $\sim$ est \emph{compatible} avec l'opération $\tee$), alors
on peut définir une opération binaire $\mathbin{\bar\top}$ sur
$E/{\sim}$ par $\pi(x) \mathbin{\bar\top} \pi(x') = \pi(x\tee x')$.

L'application $\pi\colon E \to (E/{\sim})$ préserve alors l'opération
$\tee$ et on dit qu'il s'agit d'un \emph{morphisme} (d'ensembles munis
d'une opération binaire $\tee$).

%
\subsection{Calculs dans $\mathbb{Z}/m\mathbb{Z}$}

Vision concrète de $\mathbb{Z}/m\mathbb{Z}$ pour $m\geq 1$ : on
travaille avec les nombres $0,\ldots,m-1$ (qui sont des
\emph{représentants} arbitraires des $m$ classes de congruences
modulo $m$).  Les opérations sont faites dans les entiers mais ensuite
on se ramène à une classe représentée par un entier entre $0$ et $m-1$
en effectuant une division euclidienne par $m$.

Exemple : si $m=10$, on a $\bar 8 + \bar 5 = \bar 3$ et $\bar 8 \times
\bar 5 = \bar 0$.

(Note : en fait, pour l'addition, il suffit de soustraire
éventuellement $m$ si le résultat l'excède : pas besoin de faire une
vraie division euclidienne.)

Les ordinateurs travaillent naturellement dans
$\mathbb{Z}/2^r\mathbb{Z}$ avec $r$ valant typiquement $16$, $32$ ou
$64$.

Note importante : Le choix des représentants $0,\ldots,m-1$ est
arbitraire : on pourrait tout aussi bien choisir $1,\ldots,m$ ou bien
$-\lfloor\frac{m-1}{2}\rfloor,\ldots,\lfloor\frac{m}{2}\rfloor$ (ou
encore des choses tout à fait arbitraires).

\medbreak

Et si $m\leq 1$ ?
\begin{itemize}
\item On a $\mathbb{Z}/1\mathbb{Z} = \{\bar 0\}$, et les opérations
  sont triviales ($\bar 0 + \bar 0 = \bar 0$ et $\bar 0 \times \bar 0
  = \bar 0$).
\item On a $\mathbb{Z}/0\mathbb{Z} = \mathbb{Z}$.
\item Si $m<0$ alors $\mathbb{Z}/m\mathbb{Z} =
  \mathbb{Z}/(-m)\mathbb{Z}$.
\end{itemize}

En général quand on parle de $\mathbb{Z}/m\mathbb{Z}$ on sous-entend
$m\geq 1$, parfois même $m \geq 2$ !

%
\subsection{Premières propriétés de $\mathbb{Z}/m\mathbb{Z}$}

C'est un anneau commutatif.  Il n'est \emph{pas intègre} en général :
on peut avoir $ab=\bar 0$ dans $\mathbb{Z}/m\mathbb{Z}$ alors que $a
\neq \bar 0$ et $b \neq \bar 0$ (exemple : $\bar 2 \times \bar 5 =
\bar 0$ dans $\mathbb{Z}/10\mathbb{Z}$).

Surjection canonique : c'est l'application $\pi\colon \mathbb{Z} \to
\mathbb{Z}/m\mathbb{Z}$ qui envoie $x\in\mathbb{Z}$ sur sa classe de
congruence modulo $m$.  C'est un \emph{morphisme d'anneaux}, i.e., il
préserve l'addition et la multiplication et envoie $0$ et $1$ sur $0$
et $1$.

Si $m|m'$, il y a une application naturelle $\mathbb{Z}/m'\mathbb{Z}
\to \mathbb{Z}/m\mathbb{Z}$ car les classes modulo $m'$ sont plus
fines que modulo $m$.  (Exemple : connaître la congruence modulo $4$
permet de connaître la congruence modulo $2$.)  C'est également un
morphisme d'anneaux.

%
\subsection{Inversibles de $\mathbb{Z}/m\mathbb{Z}$}

Si $a$ et $m$ sont premiers entre eux, alors on sait qu'on peut
trouver une relation de Bézout $au + mv = 1$.  On a alors $\bar a \bar
u = \bar 1$ : on dit que $\bar a$ est \emph{(multiplicativement)
  inversible} dans $\mathbb{Z}/m\mathbb{Z}$, ou est une \emph{unité}
de cet anneau.  Réciproquement, si on peut trouver $\bar u$ tel que
$\bar a \bar u = \bar 1$, alors $a$ est premier à $m$.

On appelle $(\mathbb{Z}/m\mathbb{Z})^\times$ l'ensemble des
inversibles multiplicatifs de $\mathbb{Z}/m\mathbb{Z}$.  C'est un
groupe pour la multiplication (plus généralement, dans tout anneau
commutatif $A$, l'ensemble des inversibles/unités de $A$ forme un
groupe noté $A^\times$).

On note $\varphi(m)$ le cardinal de $(\mathbb{Z}/m\mathbb{Z})^\times$.

%
%
%
\end{document}