今日のまとめ

• ユークリッドのアルゴリズム、拡張ユークリッドアルゴリズムの計算量は $\log^2$ オーダーである。
• ユークリッドのアルゴリズムは再帰的にも書けるが、リソースを圧迫するので奨められない。

課題１

• python, java 等を用いて、多倍長整数に対しても実行できるように拡張ユークリッドアルゴリズムをプログラミングし、 次の $(a,b)$ に対し、 $\mbox{gcd}(a,b)$ と、$\mbox{gcd}(a,b) = ax + by$ を満たす整数の組 $(x,y)$ をひとつ求めよ。
  1. $a = 123456789012345$, $b=234567890123456$　( どちらも 15 桁 )
  2. $a = 2^{2048}$, $b = 3^{1292}$
     ( python なら
        a = 2 ** 317
     のように書けばよい。java なら
        BigInteger a = (new BigInteger("2")).pow(2048);
        BigInteger a = (BigInteger.valueOf(2)).pow(2048);
     のように書く。)
• 提出期限 : 5月26日
• メールにて塩田まで。
• pdf