法 $m$ での逆元（拡張ユークリッドの互除法）

$\gcd (23,100)=1$ であるから、$23$ は法 $100$ で逆元をもつ。拡張ユークリッドの互除法を用いて、$$23x\equiv 1(\mathrm{mod}100),0\le x\le 99$$ を満たす整数 $x$（すなわち $23^{-1}\mathrm{mod}100$）を求めよ。

合同式
$$23x\equiv 1(\mathrm{mod}100)$$
を満たす整数 $x$ のうち、$0\le x\le 99$ であるものを求めよ。すなわち、$23^{-1}\mathrm{mod}100$ を求めよ。

$\gcd (23,100)=1$ であるから、$23$ は法 $100$ で逆元をもつ。
$$23x\equiv 1(\mathrm{mod}100),0\le x\le 99$$
を満たす整数 $x$（すなわち $23^{-1}\mathrm{mod}100$）を、拡張ユークリッドの互除法を用いて求めよ。

$1000$ 以下の正の整数 $n$ で、次の 3 つの合同式をすべてみたすものを考える。
$$n\equiv 3(\mathrm{mod}4),2n\equiv 5(\mathrm{mod}7),3n\equiv 2(\mathrm{mod}11)$$
このような $n$ すべての和を求めよ。

素数 $p=17$, $q=23$ を用いて RSA 暗号の鍵を作る。$n=pq=391$ とし、公開鍵の暗号化指数を $e=5$ とする。秘密鍵の復号指数 $d$ は、$ed\equiv 1(\mathrm{mod}(p-1)(q-1))$ を満たす $1\le d<(p-1)(q-1)$ の整数とする。

平文 $m$（$0\le m<n$ を満たす整数）を $c\equiv m^e(\mathrm{mod}n)$, $0\le c<n$ により暗号化したところ、暗号文 $c=223$ が得られた。平文 $m$ を求めよ。

有限体 ${\mathbb{F}}_{19}$ 上の楕円曲線
$$E:y^2=x^3+4x+1$$
を考える。$E$ の ${\mathbb{F}}_{19}$ 有理点全体は、無限遠点 $O$ を単位元とし、通常の加法（弦と接線による加法）によって群をなす。

点 $P=(0,1)$ は $E$ 上の点である。$3P=P+P+P$ の座標 $(x,y)$ を求めよ。ただし $x,y$ は $0\le x,y\le 18$ の整数で表し、答えは $(x,y)$ の組で答えよ。

受信者は素数 $p=11$, $q=19$ を選び、$n=pq=209$ と暗号化指数 $e=7$ を公開鍵として公開した。送信者は平文 $m$（$0\le m\le 208$ を満たす整数）を
$$c\equiv m^e(\mathrm{mod}n),0\le c\le 208$$
によって暗号化し、暗号文 $c=68$ を受信者に送った。

受信者は秘密鍵の復号指数 $d$ を $ed\equiv 1(\mathrm{mod}(p-1)(q-1))$, $1\le d\le (p-1)(q-1)-1$ を満たす整数として求め、$m\equiv c^d(\mathrm{mod}n)$ により復号する。平文 $m$ を求めよ。

素数 $p=89$ と、法 $89$ の原始根 $g=3$ を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は $h=42$ である（秘密鍵 $x$ は $h\equiv g^x(\mathrm{mod}89)$ を満たす。$x$ は公開されていない）。

平文 $m$（$1\le m\le 88$ の整数）を暗号化するとき、送信者は整数 $k$ を選び、
$$c_1\equiv g^k(\mathrm{mod}89),c_2\equiv m{h}^k(\mathrm{mod}89)(0\le c_1,c_2\le 88)$$
として暗号文 $(c_1,c_2)$ を送る。

ある送信者が、本来は毎回選び直すべき $k$ を使い回して、2 つの平文 $m_1,m_2$ を同じ $k$ で暗号化した。得られた暗号文は
$$m_1\text{の暗号文}:(51,11),m_2\text{の暗号文}:(51,7)$$
である。攻撃者は何らかの方法で $m_1=20$ であることを知った。秘密鍵 $x$ を求めずに、平文 $m_2$（$1\le m_2\le 88$ の整数）を求めよ。

有限体 ${\mathbb{F}}_{31}$ 上の楕円曲線
$$E:y^2=x^3+2x+5$$
を考えます。$E$ の ${\mathbb{F}}_{31}$ 有理点全体は、無限遠点 $O$ を単位元とし、通常の加法（弦と接線による加法）で群になります。

この曲線と基点 $P=(0,6)\in E({\mathbb{F}}_{31})$ を公開パラメータとして、アリスとボブが楕円曲線ディフィー・ヘルマン鍵共有を行います。アリスは秘密鍵 $a=3$ を選んで公開鍵 $A=aP$ を送り、ボブは秘密鍵 $b=5$ を選んで公開鍵 $B=bP$ を送ります。二人が共有する点を $S=abP$ とします。

$S$ の座標 $(x_S,y_S)$ を、$0\le x_S\le 30,0\le y_S\le 30$ の整数の組で求めてください。

RSA 暗号の受信者は、相異なる素数 $p,q$ を選んで $n=pq$ とし、公開鍵 $(n,e)=(437,5)$ を公開した。秘密鍵の復号指数 $d$ は
$$ed\equiv 1(\mathrm{mod}\phi (n)),1\le d<\phi (n)$$
を満たす整数である。ここで $\phi (n)=(p-1)(q-1)$ である。送信者は平文 $m$（$0\le m\le 436$ を満たす整数）を $c\equiv m^e(\mathrm{mod}n)$（$0\le c\le 436$）によって暗号化して送る。

いま攻撃者は、$p,q$ そのものは知らないが、$\phi (n)=396$ であることを知った。さらに暗号文 $c=98$ を傍受した。この暗号文に対応する平文 $m$ を求めよ。

素数 $p=59$ と、法 $59$ の原始根 $g=2$ を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は $h=40$ である。秘密鍵 $x$ は $h\equiv g^x(\mathrm{mod}59)$ を満たすが、公開されていない。

送信者は平文 $m$（$1\le m\le 58$ を満たす整数）を暗号化するとき、一時鍵 $k$ を選び、
$$c_1\equiv g^k(\mathrm{mod}59),c_2\equiv m{h}^k(\mathrm{mod}59)(0\le c_1,c_2\le 58)$$
として暗号文 $(c_1,c_2)$ を送る。

ある送信者が、本来は毎回取り替えるべき一時鍵 $k$ を、2 つの平文 $m_1$, $m_2$ の暗号化に同じ値のまま使ってしまった。その結果、送られた暗号文は次の 2 つである。
$$(c_1,c_2)=(28,56),(c_1^{\prime },c_2^{\prime })=(28,43)$$
攻撃者は、1 つ目の暗号文の平文が $m_1=23$ であることを知っている。このとき、2 つ目の暗号文の平文 $m_2$（$1\le m_2\le 58$）を求めよ。

素数 $p=101$ と法 $101$ の原始根 $g$ を用いるエルガマル暗号を考える。受信者の秘密鍵を $a$、公開鍵を $h\equiv g^a(\mathrm{mod}p)$ とする。平文 $m$（$1\le m\le 100$ の整数）は、送信者が整数 $k$（$1\le k\le 99$）を選び
$$c_1\equiv g^k,c_2\equiv m{h}^k(\mathrm{mod}p)(0\le c_1,c_2\le 100)$$
として暗号文 $(c_1,c_2)$ に暗号化される。

送信者は、誤って同じ $k$ を使い回して 2 つの平文 $m_1,m_2$ を暗号化し、暗号文 $(14,19)$ と $(14,45)$ をこの順に送った。盗聴者は $1$ つ目の平文が $m_1=20$ であることを知っている。$2$ つ目の平文 $m_2$ を求めよ。

素数 $p=31$ と、法 $31$ の原始根 $g=3$ を公開パラメータとするエルガマル暗号を考える。受信者は秘密鍵 $x=7$ を選び、公開鍵 $h\equiv g^x(\mathrm{mod}31)$（$0\le h\le 30$）を公開している。

送信者は平文 $m$（$1\le m\le 30$ の整数）を、整数 $k$ を選んで
$$c_1\equiv g^k,c_2\equiv m{h}^k(\mathrm{mod}31)$$
により暗号文 $(c_1,c_2)$ に変換して送る。受信者が受け取った暗号文が $(c_1,c_2)=(19,22)$ であるとき、平文 $m$ を求めよ。

素数 $p=53$ と、法 $53$ の原始根 $g=2$ を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は $h=17$ である（秘密鍵 $x$ は $h\equiv g^x(\mathrm{mod}53)$ を満たすが、公開されていない）。

平文 $m$（$1\le m\le 52$ の整数）を暗号化するとき、送信者は乱数 $k$（$1\le k\le 51$ の整数）を選び、
$$c_1\equiv g^k(\mathrm{mod}53),c_2\equiv m{h}^k(\mathrm{mod}53)(0\le c_1,c_2\le 52)$$
として暗号文 $(c_1,c_2)$ を送る。

ある送信者が、2 つの平文 $m_1,m_2$ を暗号化する際に、誤って同じ乱数 $k$ を使ってしまい、暗号文はそれぞれ
$$(c_1,c_2)=(11,32),(c_1^{\prime },c_2^{\prime })=(11,38)$$
となった。攻撃者は、1 つ目の平文が $m_1=20$ であることを知っている。このとき、2 つ目の平文 $m_2$ を求めよ。

素数 $p=61$ と、法 $61$ の原始根 $g=2$ を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は $h=18$ である（秘密鍵 $x$ は $h\equiv g^x(\mathrm{mod}61)$ を満たすが、公開されていない）。

平文 $m$（$1\le m\le 60$ の整数）を暗号化するとき、送信者は乱数 $k$ を選び、
$$c_1\equiv g^k(\mathrm{mod}61),c_2\equiv m{h}^k(\mathrm{mod}61)(0\le c_1,c_2\le 60)$$
として暗号文 $(c_1,c_2)$ を送る。

ある送信者が、2 つの平文 $m_1$, $m_2$ を暗号化する際に、誤って同じ乱数 $k$ を使ってしまった。その結果、暗号文はそれぞれ
$$(c_1,c_2)=(6,11),(c_1^{\prime },c_2^{\prime })=(6,42)$$
となった。攻撃者は何らかの方法で $m_1=25$ であることを知った。このとき、秘密鍵 $x$ や乱数 $k$ を求めずに得られる $m_2$（$1\le m_2\le 60$ の整数）を求めよ。

素数 $p=23$ について、$g=5$ は法 $23$ の原始根である（$5$ の法 $23$ での位数は $22$）。

合同式
$$x^5\equiv 7(\mathrm{mod}23),1\le x\le 22$$
を満たす整数 $x$ はただ $1$ つ存在する。その $x$ を求めよ。

$p,q$ を相異なる奇素数とし、$n=pq$、$\phi =(p-1)(q-1)$ とおく。正の整数 $e,d$ は $ed\equiv 1(\mathrm{mod}\phi )$ をみたすとする（RSA 暗号の公開鍵 $(n,e)$ と秘密鍵 $d$）。中国剰余定理を使った高速な復号（CRT-RSA）のために、次を定める。
- $d_p$ を $d$ を $p-1$ で割った余り、$d_q$ を $d$ を $q-1$ で割った余りとする（$0\le d_p\le p-2$、$0\le d_q\le q-2$）。
- 整数 $u$ を、$qu\equiv 1(\mathrm{mod}p)$ をみたす整数のうちの 1 つとする（$p,q$ は相異なる素数なので、このような $u$ は存在する）。

$0\le c<n$ をみたす整数 $c$（暗号文）に対して、
- $m_p$ を $c^{d_p}$ を $p$ で割った余り、$m_q$ を $c^{d_q}$ を $q$ で割った余り（$0\le m_p\le p-1$、$0\le m_q\le q-1$）、
- $h$ を $u(m_p-m_q)$ を $p$ で割った余り（$0\le h\le p-1$）、
- $m=m_q+qh$

とおく。ここで $c$ は $n$ と互いに素であるとは限らない（$c=0$ や、$c$ が $p$ または $q$ の倍数である場合も含む）。また、整数 $a$ に対して $a^0=1$ と定める（$a=0$ のときも含む）。このとき、$0\le m<n$ かつ $m\equiv c^d(\mathrm{mod}n)$ であることを証明せよ。

ただし、フェルマーの小定理と、「整数 $x$ が相異なる素数 $p,q$ のそれぞれで割り切れるならば $pq$ で割り切れる」ことは用いてよい。

$1729=7\cdot 13\cdot 19$ である。$x^2+x+1$ が $1729$ で割り切れるような正の整数 $x$ のうち、最小のものを求めよ。

素数 $p=73$ について、$g=5$ は法 $73$ の原始根である（$5$ の法 $73$ での位数は $72$）。
$$5^x\equiv 42(\mathrm{mod}73),0\le x\le 71$$
を満たす整数 $x$（$42$ の底 $5$ に関する離散対数）を求めよ。

英字 $26$ 文字を $\mathrm{A}=0,\mathrm{B}=1,\dots ,\mathrm{Z}=25$ と数に対応させ、アフィン暗号
$$E(x)\equiv ax+b(\mathrm{mod}26)$$
で 1 文字ずつ暗号化する。ここで鍵 $(a,b)$ は $0\le a\le 25$, $0\le b\le 25$ を満たす整数で、$a$ は $26$ と互いに素である（暗号化は 1 対 1 である）。

ある暗号文について、平文の文字 $\mathrm{E}$ が $\mathrm{M}$ に、平文の文字 $\mathrm{G}$ が $\mathrm{A}$ に暗号化されていることがわかった。この暗号の復号関数を
$$D(y)\equiv cy+d(\mathrm{mod}26),0\le c\le 25,0\le d\le 25$$
の形に表すとき、整数の組 $(c,d)$ を求めよ。

有限体 ${\mathbb{F}}_{13}$ 上の楕円曲線
$$E:y^2=x^3+3x+5$$
を考える。$E$ の ${\mathbb{F}}_{13}$ 有理点全体に無限遠点 $O$ を単位元として通常の加法（弦と接線による加法）を入れた群において、点 $P=(1,3)$ をとる。

点 $2030P$ の座標 $(x,y)$ を求めよ。ただし $x,y$ は $0\le x\le 12$, $0\le y\le 12$ を満たす整数で表し、$(x,y)$ の組で答えよ。

有限体 ${\mathbb{F}}_{23}$ 上の楕円曲線
$$E:y^2=x^3+2x+9$$
を考える。$E$ の ${\mathbb{F}}_{23}$ 有理点全体は、無限遠点 $O$ を単位元とし、通常の加法（弦と接線による加法）で群をなす。点 $P=(0,3)\in E({\mathbb{F}}_{23})$ について、$nP=O$ となる最小の正の整数 $n$（$P$ の位数）を求めよ。

有限体 ${\mathbb{F}}_{17}$ 上の楕円曲線
$$E:y^2=x^3+3x+4$$
を考える。$E$ の ${\mathbb{F}}_{17}$ 有理点全体は、無限遠点 $O$ を単位元とし、通常の加法（弦と接線による加法）で群をなす。

$E$ 上の $2$ 点
$$P=(0,2),Q=(1,5)$$
について、$kP=Q$ を満たす最小の正の整数 $k$ を求めよ。ただし $kP$ は $P$ を $k$ 個加えた点を表す。

$p$ を奇素数とする。整数 $a$ に対し、$\left(\frac{a}{p}\right)$ はルジャンドル記号を表す（$p\mid a$ のときは $\left(\frac{a}{p}\right)=0$ と定める）。

$1\le n\le p-3$ を満たす整数 $n$ のうち、$n$ と $n+2$ がともに $p$ を法とする平方剰余であるものの個数を $N$ とする（$p=3$ のときは $N=0$ である）。このとき
$$N=\frac{1}{4}\left(p-5-2\left(\frac{-1}{p}\right)-\left(\frac{2}{p}\right)-\left(\frac{-2}{p}\right)\right)$$
が成り立つことを証明せよ。

ただし、ルジャンドル記号の乗法性 $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$、$a\equiv b(\mathrm{mod}p)$ ならば $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$ であること、および $1,2,\dots ,p-1$ のうち平方剰余と平方非剰余がちょうど $\frac{p-1}{2}$ 個ずつあることは用いてよい。