[Pythonプログラミング]1億年ぐらい掛かりそうな問題を高速に解くライブラリ : graphillion

2024年08月17日

カテゴリ:
Python
プログラミング

今回は1億年くらいかかりそうな問題を
高速に解く事ができるライブラリ
graphillion についてです。

解説動画はこちら

graphillion

膨大な数のグラフを簡単に操作するためのライブラリです。

グラフとはノードの集合とエッジの集合で構成された
抽象物のことで次のような頂点と線で構成されたものの事です。

2x2

この頂点をノード
線のことをエッジと呼んでいます。

これを応用した問題についてですが
1をスタート
81をゴールとした際に
二回同じところは通らないとして
行くことの出来るルートは何通りあるでしょうか

9x9

これを手計算で特にはかなりしんどいですよね。
このような膨大な数になるグラフを高速に解く事ができるのが
graphillionです。

元ネタ

一応こちらの元ネタは
下記のYouTube動画です。

この動画内では
先ほどの問題は4時間くらいかかっていたそうです。

それ以上のサイズになると計算量が膨大になるので
1億年以上掛かっても解ききれない
ということになっています。

組み合わせ数が爆発した際の
恐ろしさを感じさせる動画ですね。

graphillionのインストール

google colabでは下記コマンド実行のみです。

!pip install graphillion

graphillionの使い方

まずは必要なライブラリをインポートします。
グラフの描画に必要なものも合わせてインポートします。

# 必要なモジュールのインポート
from graphillion import GraphSet
import graphillion.tutorial as tl
import matplotlib.pyplot as plt
import networkx as nx
import random

グリッド表示をさせてみる

# N x M のサイズのグリッド表示
def draw_with_matplotlib(edges, n, m, figsize=(4, 3)):
    G = nx.Graph()
    G.add_edges_from(edges)
    pos,node_labels = {},{}
    for i in range(n):
        for j in range(m):
            node = i * m + j + 1
            pos[node] = (j, -i)
            node_labels[node] = str(node)

    plt.figure(figsize=figsize)
    nx.draw(G, pos, labels=node_labels, with_labels=True, node_size=200, node_color='lightblue', edge_color='gray')
    plt.show()

# サイズを指定
n, m = 2,2
universe = tl.grid(n, m)
GraphSet.set_universe(universe)
draw_with_matplotlib(universe, n + 1, m + 1)

glidメソッドで辺の数を指定します(頂点の数-1)

単純にパス(道順の総数)を計算する場合は
スタートの頂点の数値と
ゴールの頂点の数値を指定して
GraphSet.paths(start, goal)
で計算できます。

universe = tl.grid(2, 2)
GraphSet.set_universe(universe)
start, goal = 1, 9
paths = GraphSet.paths(start, goal)
print(f"パスの数 : {len(paths)}")

12

頂点が3x3の場合は
12通りである事がわかります。

この12通りを全通り描画してみましょう。

from graphillion import GraphSet
import graphillion.tutorial as tl
import matplotlib.pyplot as plt
import networkx as nx

def make_grid(n):
    edges = []
    for i in range(n):
        for j in range(n):
            if i < n - 1:
                edges.append((i * n + j + 1, (i + 1) * n + j + 1))
            if j < n - 1:
                edges.append((i * n + j + 1, i * n + (j + 1) + 1))
    return edges

def grid_paths(n):
    universe = make_grid(n)
    GraphSet.set_universe(universe)
    start = 1
    goal = n * n
    paths = GraphSet.paths(start, goal)
    return paths

def draw_paths_in_grid(paths, n):
    num_paths = len(paths)
    rows = 3
    cols = 4
    fig, axes = plt.subplots(rows, cols, figsize=(10, 6))
    G = nx.grid_2d_graph(n, n)
    pos = {(i, j): (j, n - 1 - i) for i in range(n) for j in range(n)}

    for i, path in enumerate(paths):
        row = i // cols
        col = i % cols
        ax = axes[row, col]
        path_edges = [(divmod(u - 1, n), divmod(v - 1, n)) for u, v in path]

        nx.draw(G, pos, with_labels=False, node_size=300, node_color='lightblue', edge_color='lightgray', ax=ax)
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2, ax=ax)
        ax.set_title(f'Path {i + 1}')
        ax.set_xticks([])
        ax.set_yticks([])

    for j in range(i + 1, rows * cols):
        fig.delaxes(axes.flatten()[j])

    plt.tight_layout()
    plt.show()

n = 3
paths = grid_paths(n)
draw_paths_in_grid(paths, n)

頂点4を通ってから頂点2を通る道順を出す
というようなこともできます。

# 何通りあるか
start = 1
goal = 9
key = 4
treasure = 2

paths = GraphSet.paths(start, goal)
paths_to_key = GraphSet.paths(start, key).excluding(treasure)
treasure_paths = paths.including(paths_to_key).including(treasure)
len(treasure_paths)

2

# 道順リストの描画
from graphillion import GraphSet
import graphillion.tutorial as tl
import matplotlib.pyplot as plt
import networkx as nx

def draw_paths_in_grid(paths, n):
    num_paths = len(paths)
    rows = 1
    cols = 2
    fig, axes = plt.subplots(rows, cols, figsize=(10, 6))
    G = nx.grid_2d_graph(n, n)
    pos = {(i, j): (j, n - 1 - i) for i in range(n) for j in range(n)}

    for i, path in enumerate(paths):
        row, col = divmod(i, cols)
        ax = axes[col] if rows == 1 else axes[row, col]
        path_edges = [(divmod(u - 1, n), divmod(v - 1, n)) for u, v in path]

        nx.draw(G, pos, with_labels=False, node_size=300, node_color='lightblue', edge_color='lightgray', ax=ax)
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2, ax=ax)
        ax.set_title(f'Path {i + 1}')
        ax.set_xticks([])
        ax.set_yticks([])

    for j in range(i + 1, rows * cols):
        fig.delaxes(axes.flatten()[j])

    plt.tight_layout()
    plt.show()


n, m = 2, 2
universe = tl.grid(n, m)
GraphSet.set_universe(universe)

start = 1
goal = 9
key = 4
treasure = 2

paths = GraphSet.paths(start, goal)
paths_to_key = GraphSet.paths(start, key).excluding(treasure)
treasure_paths = paths.including(paths_to_key).including(treasure)
draw_paths_in_grid(treasure_paths,n+1)

それでは冒頭の

9x9のサイズのグリッドだと
道順は何通りあるのでしょうか?

import time
universe = tl.grid(8, 8)
GraphSet.set_universe(universe)
start, goal = 1, 81
s_time = time.time()
paths = GraphSet.paths(start, goal)
times = time.time() - start
print(f"計算時間 : {times}")
print(f"パスのサイズ : {len(paths):,}")

計算時間 : 1723880338.8543057
パスのサイズ : 3,266,598,486,981,642

約3200兆通りです

1つ選んでみるとこんな結果でした。

9x9_ans

まとめ

膨大な数のグラフ計算を行う際には
graphillion ライブラリが有用です。

以下のような問題を高速に解く事ができます。
最短経路問題

全経路列挙問題

ネットワーク解析

配置問題
etc...

元ネタの

動画では恐ろしく掛かっていた時間も
圧倒的に短縮して解けているので
すごく有用なライブラリです。

グラフの計算を仕事で使う方は
ぜひ使ってみてください。

それでは。

[Pythonプログラミング]インタラクティブな可視化ライブラリAltairのご紹介

2024年08月10日

カテゴリ:
プログラミング
Python

今回はインタラクティブな可視化が行えるライブラリ
Altairのご紹介です。

解説動画はこちら

Altairライブラリについて

少ないコードで複雑なビジュアライゼーションを作成できる

可視化ライブラリです。

静止画でなくインタラクティブな
ビジュアライゼーションを行うことができます。

Pandasデータフレームと相性が良く
ダッシュボード制作などで活用されるケースが増えています。

他の可視化ライブラリとの違い

Altairの他にも沢山の可視化ライブラリがあります。

その中でもMatplolibは定番の可視化ライブラリですが
ドキュメントの数量は多く、全てを覚えるのはなかなか大変です。

AltairはPlotlyのようなインタラクティブな可視化が出来る事と
学習コストがかなり少ない事が大きな利点です。

可視化の目的によって
これらのライブラリを使い分けると良いでしょう。

Altairの使い方

1.ライブラリのインポート

Google ColabではそのままAltairを利用できます。

import pandas as pd
import numpy as np
import altair as alt
import warnings
warnings.filterwarnings('ignore', category=FutureWarning)

その他、必要なライブラリを読み込んでおきましょう。

2.データの用意

適当なデータをPandasデータフレームで作成しておきます。

# サンプルデータの作成
data = pd.DataFrame({
    'x': [1, 2, 3, 4, 5],
    'y': [2, 3, 4, 5, 6]
})

3.チャートの作成

Altairの基本的なチャートは、alt.Chartオブジェクトを使用して作成します。

mark_*メソッドでマーク（グラフの種類）を指定し

encodeメソッドでデータのエンコード（軸、色、大きさなど）を
指定する構文になっています。

チャート変数 = alt.Chart(データ変数).mark_point().encode(
  エンコード内容
)

# チャートの作成
chart = alt.Chart(data).mark_point().encode(
    x='x',
    y='y'
)

# チャートの表示（Jupyter Notebook環境などで）
chart

指定できるmark_*メソッド例として

mark_point：ポイントマーク（散布図）

mark_line：折れ線グラフ

mark_bar：棒グラフ

mark_circle：バブルチャート

mark_rect：矩形マーク（ヒートマップなど）

mark_boxplot：箱ひげ図

mark_errorband：エラーバンド

mark_errorbar：エラーバー

mark_geoshape：地理シェープ（地図）

mark_image：画像マーク

mark_area：エリアチャート

mark_rule：ルールマーク（基準線など）

mark_square：四角形マーク（散布図の一種）

mark_text：テキストマーク

mark_tick：ティックマーク

こんな感じのグラフを作成できます。

4. エンコーディング

encodeメソッドを使用して
データを視覚的な属性にマッピング出来ます。

x : x軸

y : y軸

color : 色

size : サイズ

shape : 形

tooltip : ホバー時に表示されるツールチップ

data = pd.DataFrame({
    'x': [1, 2, 3, 4, 5],
    'y': [2, 3, 4, 5, 6],
    'category': ['A', 'B', 'A', 'B', 'A']
})

chart = alt.Chart(data).mark_point().encode(
    x='x',
    y='y',
    color='category',
    tooltip=['x', 'y', 'category']
)
chart

5.インタラクティブ性の追加

interactiveメソッドを使用して

グラフにインタラクティブ機能（ズーム、パンなど）を
追加できます。

chart = alt.Chart(data).mark_point().encode(
    x='x',
    y='y',
    color='category'
).interactive()
chart

6.レイヤリングと複合グラフ

Altairでは複数のチャートをレイヤリングして
重ね合わせることも可能です。

+演算子を使用してチャートを合成します。

points = alt.Chart(data).mark_point().encode(
    x='x',
    y='y',
    color='category'
)

lines = alt.Chart(data).mark_line().encode(
    x='x',
    y='y',
    color='category'
)

combined_chart = points + lines
combined_chart

Altairグラフのコードサンプル

散布図

# サンプルデータの作成
np.random.seed(42)
data = pd.DataFrame({
    'x': np.random.randn(100),
    'y': np.random.randn(100),
    'category': np.random.choice(['A', 'B', 'C'], 100)
})

# インタラクティブな散布図の作成
scatter_plot = alt.Chart(data).mark_point().encode(
    x='x',
    y='y',
    color='category',
    tooltip=['x', 'y', 'category']
).interactive()
scatter_plot

棒グラフ

# サンプルデータの作成
data = pd.DataFrame({
    'category': ['A', 'B', 'C', 'D', 'E'],
    'value': [5, 3, 6, 7, 2]
})

# インタラクティブな棒グラフの作成
bar_chart = alt.Chart(data).mark_bar().encode(
    x='category',
    y='value',
    tooltip=['category', 'value']
).interactive()
bar_chart

折れ線グラフ

# サンプルデータの作成
data = pd.DataFrame({
    'date': pd.date_range(start='2023-01-01', periods=100),
    'value': np.random.randn(100).cumsum()
})

# インタラクティブな折れ線グラフの作成
line_chart = alt.Chart(data).mark_line().encode(
    x='date:T',
    y='value:Q',
    tooltip=['date:T', 'value:Q']
).interactive()
line_chart

ヒートマップ

# サンプルデータの作成
data = pd.DataFrame({
    'x': np.repeat(np.arange(1, 11), 10),
    'y': np.tile(np.arange(1, 11), 10),
    'value': np.random.randn(100)
})

# インタラクティブなヒートマップの作成
heatmap = alt.Chart(data).mark_rect().encode(
    x='x:O',
    y='y:O',
    color='value:Q',
    tooltip=['x', 'y', 'value']
).interactive()
heatmap

バブルチャート

# サンプルデータの作成
np.random.seed(42)
data = pd.DataFrame({
    'x': np.random.randn(100),
    'y': np.random.randn(100),
    'size': np.random.rand(100) * 100,
    'category': np.random.choice(['A', 'B', 'C'], 100)
})

# インタラクティブなバブルチャートの作成
bubble_chart = alt.Chart(data).mark_circle().encode(
    x='x',
    y='y',
    size='size',
    color='category',
    tooltip=['x', 'y', 'size', 'category']
).interactive()
bubble_chart

ヒストグラム

# データの生成
np.random.seed(42)
data = pd.DataFrame({
    'value': np.random.normal(loc=0, scale=1, size=1000)
})

# ヒストグラムの作成
histogram = alt.Chart(data).mark_bar().encode(
    alt.X('value:Q', bin=True, title='Value'),
    alt.Y('count()', title='Frequency')
).interactive()
histogram

箱ひげ図

# データの生成（例: 1000個のランダムな数値を3つのカテゴリに分ける）
np.random.seed(42)
data = pd.DataFrame({
    'category': np.random.choice(['A', 'B', 'C'], size=1000),
    'value': np.random.normal(loc=0, scale=1, size=1000)
})

# 箱ひげ図の作成
boxplot = alt.Chart(data).mark_boxplot().encode(
    x='category:O',
    y='value:Q'
).interactive()
boxplot

エリアチャート

# データの生成
data = pd.DataFrame({
    'year': [2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007],
    'value': [10, 15, 13, 17, 20, 19, 15, 10]
})

# エリアチャートの作成
areachart = alt.Chart(data).mark_area().encode(
    x='year:O',
    y='value:Q'
).interactive()
areachart

まとめ

Altairは可視化ライブラリの中でも比較的学習コストが低く
かなり使い勝手の良い可視化ライブラリです。

特にインタラクティブな可視化を行えるのが魅力的なライブラリで

最近はデータサイエンスやデータ分析の分野で広く採用されて来ています。

WEBアプリを作成できるStreamlitライブラリと相性が良く
簡易なアプリ作成やダッシュボード作成などにも向いています。

Matplotlibの可視化に物足りなくなって来たら
こちらのライブラリはオススメです。

それでは。

タグ：: #Python.プログラミング; #可視化; #インタラクティブ; #Altair

[Pythonプログラミング]Pandasの上位互換ライブラリPolarsで速度検証してみた

2024年08月03日

カテゴリ:
プログラミング
Python

今回はPandasの上位互換ライブラリ
Polarsのご紹介です。

解説動画はこちら

Polarsについて

Rustで実装された高速なデータ操作ライブラリ

Pandasに似たAPIを持ち
大規模データセットでより高速に動作するようです

Pandasの上位互換に当たりそうです。

導入方法について

Python3.7以上が必要です

Google Colabは導入済みなので
インストール不要です

インストール方法

pip install polars

大容量データの用意

Pandas , Polarsで同様のデータを使用するように

ランダム値で1000万行を用意しました。

こちらがデータ生成のコードです。

# ライブラリのインポート
import pandas as pd
import numpy as np
import polars as pl
import time

# サンプルデータを生成
np.random.seed(0)
num_rows = 10000000
names = ['Alice', 'Bob', 'Charlie', 'David', 'Eve', 'Frank', 'Grace', 'Hannah', 'Ivy', 'Jack', 'Karen', 'Leo']
genders = ['Male', 'Female', 'Other']
prefectures = ['Hokkaido', 'Aomori', 'Iwate', 'Miyagi', 'Akita', 'Yamagata', 'Fukushima', 
               'Ibaraki', 'Tochigi', 'Gunma', 'Saitama', 'Chiba', 'Tokyo', 'Kanagawa', 
               'Niigata', 'Toyama', 'Ishikawa', 'Fukui', 'Yamanashi', 'Nagano', 'Gifu', 
               'Shizuoka', 'Aichi', 'Mie', 'Shiga', 'Kyoto', 'Osaka', 'Hyogo', 'Nara', 
               'Wakayama', 'Tottori', 'Shimane', 'Okayama', 'Hiroshima', 'Yamaguchi', 
               'Tokushima', 'Kagawa', 'Ehime', 'Kochi', 'Fukuoka', 'Saga', 'Nagasaki', 
               'Kumamoto', 'Oita', 'Miyazaki', 'Kagoshima', 'Okinawa']
favorite_foods = ['Sushi', 'Ramen', 'Tempura', 'Soba', 'Udon', 'Yakitori', 'Okonomiyaki', 
                  'Takoyaki', 'Sashimi', 'Gyoza', 'Katsudon', 'Tonkatsu']

start_date = np.datetime64('2024-01-01')
end_date = np.datetime64('2024-12-31')
date_range_days = (end_date - start_date).astype(int) + 1

data = {
    'id': np.arange(1, num_rows + 1),
    'name': np.random.choice(names, num_rows),
    'gender': np.random.choice(genders, num_rows),
    'prefecture': np.random.choice(prefectures, num_rows),
    'favorite_food': np.random.choice(favorite_foods, num_rows),
    'age': np.random.randint(18, 70, size=num_rows),
    'salary': np.random.randint(210000, 1690000, size=num_rows),
    'day': start_date + np.random.randint(0, date_range_days, size=num_rows)
}
# データフレームを生成
df = pd.DataFrame(data)

# データを保存
df.to_csv("dataset.csv", index=False)

df.shape

(10000000, 8)

こんな感じのデータになります。

Polarsのデータの用意

# CSVファイルの読み込み
df2 = pl.read_csv("dataset.csv")

Pandasで作ったCSVをそのまま読み込みします。

PandasとPolarsの計算比較

1カラムをフィルタリングして
Groupby集計するコードです。

PandasとPolarsで掛かった秒数を計測します。

# データのフィルタリングと集計(Pandas)

# 計測開始
start_time = time.time()
result = df[df['age'] > 30].groupby('gender')['salary'].sum().reset_index()
print(result)

# 計測終了
end_time = time.time()

# 経過時間を計算
elapsed_time = end_time - start_time

print(f"経過時間: {elapsed_time} 秒")

経過時間: 3.2436938285827637 秒

# データのフィルタリングと集計(Polars)

# 計測開始
start_time = time.time()
result2 = df2.filter(pl.col("age") > 30).group_by("gender").agg(pl.sum("salary"))
print(result2)

# 計測終了
end_time = time.time()

# 経過時間を計算
elapsed_time = end_time - start_time

print(f"経過時間: {elapsed_time} 秒")

経過時間: 1.849299430847168 秒

掛かった時間は3/2くらいになっています。

今度は4つのカラムを条件にした
やや複雑な集計です。

# データのフィルタリングと集計(Pandas)

# 計測開始
start_time = time.time()

# 条件に基づいてデータをフィルタリング
average_salary = df[(df['age'] > 30) & 
                 (df['gender'] == 'Male') & 
                 (df['prefecture'] == 'Tokyo') & 
                 (df['favorite_food'] == 'Sushi')]['salary'].mean()

print(f"Average salary: {average_salary:.2f}")

# 計測終了
end_time = time.time()

# 経過時間を計算
elapsed_time = end_time - start_time

print(f"経過時間: {elapsed_time} 秒")

経過時間: 2.3793530464172363 秒

# データのフィルタリングと集計(Polars)

# 計測開始
start_time = time.time()
average_salary = df2.filter(
    (pl.col('age') > 30) & 
    (pl.col('gender') == 'Male') & 
    (pl.col('prefecture') == 'Tokyo') & 
    (pl.col('favorite_food') == 'Sushi')
)['salary'].mean()

# 結果を表示
print(f"Average salary: {average_salary:.2f}")

# 計測終了
end_time = time.time()

# 経過時間を計算
elapsed_time = end_time - start_time

print(f"経過時間: {elapsed_time} 秒")

経過時間: 0.4078397750854492 秒

こちらは6倍くらい早くなっています。

1億行くらいの計算において
5倍くらいは速いそうなので
触れ込みと同等の性能を感じられます。

まとめ

1000万行でも、条件が複雑になるほど差が出ていて

巨大なデータを扱う業界で
データ分析している人には有用なライブラリです。

そのほかにもデータの加工や
前処理も柔軟な記述が実現できたり

apply などの、加工で遅い部分を解消できるので
かなりオススメのライブラリになっています。

Pandasももう古いので
今後はPolars等が主流になっていくんだと
考えられますね

今回はPandasの上位互換である
Polarsについてお伝えしました。

それでは。

タグ：: #Python; #プログラミング; #Polars; #Pandas

[Pythonプログラミング]最近のPython文法-2024

2024年07月27日

カテゴリ:
プログラミング
Python

今回はまじめに
最近のPythonの文法をまとめてみました。

解説動画はこちら

さて最近のPythonの文法について
しばらく触れていなかったので
少し解説していきたいと思います。

今回はGoogle Colabを使用しているので
そのバージョンである3.10までの内容です。

文字列のフォーマット指定

f"文字列{変数}"
で文字列にデータを差し込みすることができます。

# 昔のフォーマット
name = "フリーザ"
hourly = 530000
text = "{0} : 私の時給は{1}円です。".format(name, hourly)
print(text)

# Fフォーマット
name = "フリーザ"
hourly = 530000
text = f"{name} : 私の時給は{hourly}円です。"
print(text)

フリーザ : 私の時給は530000円です。

フォーマットの指定もできます

{変数:指定文字列}

{変数:,} : 3桁区切り

{変数:.2f} : 小数点以下の指定(この場合は2桁)

# Fフォーマット
name = "フリーザ"
name2 = "ザーボン"
hourly = 530000
hourly2 = 2980.2983
text = f"{name} : 私の時給は{hourly:,}円です。"
print(text)
text2 = f"{name2} : 私の時給は{hourly2:.3f}円です。"
print(text2)

defaultdict

存在しないキーのデフォルト値を指定できます

通常の辞書型では最初にキーが存在しないと値を操作できません

# キーを初期化代入する必要がある
d = {}
for key in "aabbbc":
    if key not in d:
        d[key] = 0
    d[key] += 1

print(d)

defaultdictの場合は初期値を決められるので
コードを省略できます。

# defaultdictの場合
from collections import defaultdict
d = defaultdict(int)

for key in "aabbbc":
    d[key] += 1

#print(d)
print(d["a"])

2

関数の結果をキャッシュ

functools.lru_cacheを用いると
同じ引数の関数の結果をキャッシュでき
再帰の計算などが早く行えるようになります。

# キャッシュ無し
def fibonacci_old(n):
    if n < 2:
        return n
    return fibonacci_old(n-1) + fibonacci_old(n-2)
print(fibonacci_old(30))

msレベル

# キャッシュあり
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_cache(n):
    if n < 2:
        return n
    return fibonacci_cache(n-1) + fibonacci_cache(n-2)
print(fibonacci_cache(100))

usレベル

圧倒的に早くなります。

アンパック演算子

*を用いて変数への複数代入を行う

a, *b, c = [1,2,3,4,5,6]
print(a, b, c)

a, b, *c = [1,2,3,4,5,6]
print(a, b, c)

1 , [2,3,4,5] , 6
1 , 2 , [3,4,5,6]

ウォルラス演算子

:= で変数への代入と評価を同時にできるようになります

(a:=2) >= 2

True

WITH構文で複数ファイルのコンテキスト

with open(ファイル名) as 変数, open(ファイル名) as 変数 ... :

# ファイルを作っておく
import random
import string

for name in ["a","b","c"]:
  with open(name+".txt","w") as _w:
    text = ''.join([random.choice(string.ascii_lowercase) for i in range(10)])
    _w.write(text)

# with構文
with open("a.txt") as _a, open("b.txt") as _b, open("c.txt") as _c:
  print(_a.read())
  print(_b.read())
  print(_c.read())

match文

3.10でmatch文が導入された

他の言語でいうcase文ですね

match 条件:

case パターン：

return 戻り値

case パターン：

return 戻り値

# match文
def http_error(status):
    match status:
        case 400:
            return "ダメっすねー"
        case 404:
            return "見つからねっす"
        case 418:
            return "なんでしょね"
        case _:
            return "何言ってるか分かんねっす"

http_error(404)

見つからねっす

いつの間にか便利な機能が追加されていて
業務でも捗っている感じになっていました。

文法の知識は定期的にアップデートしていかないと
もったいないですね

今回は最近のPython文法についてでした
それでは。

タグ：: #python; #プログラミング; #文法

[Pythonプログラミング]最近の暗号について

2024年07月13日

カテゴリ:
プログラミング
Python

今回はランサムウェアの項にも出てきた
暗号化技術に関してです。

解説動画はこちら

前回のランサムウェアの項でも出てきた
暗号化の技術について
最近の暗号を取り上げてみました。

最近の暗号

・DES（Data Encryption Standard）

古い暗号化アルゴリズムであり、56ビットの鍵を使用

DESは現在では安全性の面で脆弱性が指摘されており
より強力な暗号化アルゴリズムが推奨

・AES（Advanced Encryption Standard）

DESの後継として開発された暗号規格

128ビット、192ビット、または256ビットの鍵を使用

AESは現在、広く採用されている暗号化標準であり
高いセキュリティレベルを提供

・RSA

公開鍵暗号方式の一つであり、暗号化と署名に使用

RSAは公開鍵と秘密鍵のペアを使用し
デジタル署名やセキュアな通信のために広く利用

・SHA-256(Secure Hash Algorithm)

256ビットのハッシュ関数

SHA-256は主にデジタル署名やメッセージ認証などの用途で使用され
データの一意のハッシュ値を生成

実際に暗号のコードを見てみましょう

DES暗号

from Crypto.Cipher import DES
from Crypto.Random import get_random_bytes

# 鍵を生成
key = get_random_bytes(8)

# データを暗号化する関数
def encrypt_data(data, key):
    cipher = DES.new(key, DES.MODE_ECB)
    padded_data = data + b"\0" * (8 - len(data) % 8)
    encrypted_data = cipher.encrypt(padded_data)
    return encrypted_data

# データを復号化する関数
def decrypt_data(encrypted_data, key):
    cipher = DES.new(key, DES.MODE_ECB)
    decrypted_data = cipher.decrypt(encrypted_data)
    return decrypted_data.rstrip(b"\0")

# データ
data = b"otupy"

# 暗号化
encrypted_data = encrypt_data(data, key)
print("暗号化されたデータ:", encrypted_data)

# 復号化
decrypted_data = decrypt_data(encrypted_data, key)
print("復号化されたデータ:", decrypted_data.decode())

AES暗号

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes

# 鍵を生成
key = get_random_bytes(16)

# データを暗号化する関数
def encrypt_data(data, key):
    cipher = AES.new(key, AES.MODE_ECB)
    padded_data = data + b"\0" * (16 - len(data) % 16)
    encrypted_data = cipher.encrypt(padded_data)
    return encrypted_data

# データを復号化する関数
def decrypt_data(encrypted_data, key):
    cipher = AES.new(key, AES.MODE_ECB)
    decrypted_data = cipher.decrypt(encrypted_data)
    return decrypted_data.rstrip(b"\0")

# データ
data = b"otupy"

# 暗号化
encrypted_data = encrypt_data(data, key)
print("暗号化されたデータ:", encrypted_data)

# 復号化
decrypted_data = decrypt_data(encrypted_data, key)
print("復号化されたデータ:", decrypted_data.decode())

RSA暗号

from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes

# 秘密鍵の生成
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048
)
# 公開鍵
public_key = private_key.public_key()

# データを暗号化する関数
def encrypt_data(data, public_key):
    encrypted_data = public_key.encrypt(
        data,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return encrypted_data

# データを復号化する関数
def decrypt_data(encrypted_data, private_key):
    decrypted_data = private_key.decrypt(
        encrypted_data,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return decrypted_data

# データ
data = b"otupy"

# 暗号化
encrypted_data = encrypt_data(data, public_key)
print("暗号化されたデータ:", encrypted_data)

# 復号化
decrypted_data = decrypt_data(encrypted_data, private_key)
print("復号化されたデータ:", decrypted_data.decode())

SHA-256

import hashlib

# データをハッシュ化する関数
def hash_data(data):
    hash_object = hashlib.sha256()
    hash_object.update(data)
    hash_value = hash_object.hexdigest()
    return hash_value

# データ
data = b"otupy"

# ハッシュ値を計算
hashed_value = hash_data(data)
print("計算されたSHA-256ハッシュ値:", hashed_value)

RSA暗号を破るとしたら・・・

ショアのアルゴリズム

量子コンピューターを使用して素因数分解問題を解くためのアルゴリズム

古典コンピューターでは大きな合成数の素因数分解は効率的に解くことが難しい

ショアのアルゴリズムは、1994年にPeter Shorによって提案

素因数分解問題を効率的に解くことができるという特性を持ち
RSA暗号や他の公開鍵暗号方式のセキュリティを脅かす可能性がある

ショアのアルゴリズムの基本的な手順

量子フーリエ変換
　入力として素因数分解したい合成数をエンコードし、量子フーリエ変換を行う

位相推定
　位相推定アルゴリズムを使用して、周期性を持つ関数の周期を見つける

因数分解
　見つかった周期性を利用して、元の合成数の素因数を見つける

ショアのアルゴリズムのコード例

import numpy as np
from qiskit import Aer, QuantumCircuit, transpile, assemble
from qiskit.circuit.library import QFT
from qiskit.visualization import plot_histogram
from math import gcd
from numpy.random import randint

def a_to_the_power_mod(a, power, N):
    result = 1
    for _ in range(power):
        result = (result * a) % N
    return result

def qpe_amod15(a):
    # 位相推定に使用する量子ビットの数
    n_count = 8
    # 量子回路を初期化
    qc = QuantumCircuit(4 + n_count, n_count)
    
    for q in range(n_count):
        qc.h(q)
    qc.x(3 + n_count)
    
    for q in range(n_count):
        # 各位相推定用の量子ビットに対して、逆量子フーリエ変換 QFT を適用
        qc.append(QFT(num_qubits=n_count, inverse=True).to_gate(), range(n_count))
        # a_to_the_power_mod 関数を使用してモジュラエクスポネンシエーションを計算し、その結果を量子回路に追加
        qc.append(a_to_the_power_mod(a, 2**q, 15), [q + n_count, n_count + 1, n_count + 2, n_count + 3])
    # 全ての位相推定用の量子ビットに対して再度逆量子フーリエ変換 QFT を適用
    qc.append(QFT(num_qubits=n_count, inverse=True).to_gate(), range(n_count))
    qc.measure(range(n_count), range(n_count))

    # Aer シミュレーターを使用して量子回路をシミュレーションし、結果を取得
    aer_sim = Aer.get_backend('qasm_simulator')
    t_qc = transpile(qc, aer_sim)
    qobj = assemble(t_qc)
    result = aer_sim.run(qobj).result()
    # 測定結果のカウントを返す
    counts = result.get_counts()
    return counts

N = 15
a = 7
counts = qpe_amod15(a)
plot_histogram(counts)

RSA暗号への影響

RSA暗号は素因数分解の困難さに基づいて安全性が保証されている

しかし、ショアのアルゴリズムを用いる量子コンピューターが実用化されると
現在のRSA暗号の鍵長が十分に安全でなくなる可能性がある

量子コンピューターを用いたショアのアルゴリズムによって
RSA暗号の破綻が懸念されてる

ショアのアルゴリズムは量子コンピューターの登場による
セキュリティ上の脅威として注目されており

RSA暗号を含む多くの暗号方式の安全性に影響を与える可能性がある

もしRSA暗号が破られた場合は

通信の機密性の喪失

デジタル署名の信頼性の喪失

金融取引やオンラインショッピングの脆弱性

国家機密や軍事情報の漏洩

RSA暗号を用いたランサムウェアの取引が成立しなくなる

今後の暗号技術はどうなるか

ポスト量子暗号 (Post-Quantum Cryptography):

量子コンピューターの発展に伴い、RSAやECCなどの
従来の暗号方式が量子コンピューターによって破られる可能性が出てきている

ポスト量子暗号は、量子コンピューターが存在しても
安全性が確保されるように設計されている

例として、NTRU暗号や格子(Lattice)ベース暗号方式が挙げられる

終わりに

量子コンピューターがいつ実用化されるのか
RSA暗号がいつ破られるのか
新しい暗号技術がどうなるのか

今後もセキュリティー上の観点から
暗号関連は見逃せない展開になっていくと思われます

それでは

タグ：: #Python; #プログラミング; #暗号; #量子コンピューター

乙Py先生のプログラミング教室