pythonでたまに使う用法（リスト・内包表記・三項演算子・lambda…）

pythonのちょっと特殊だけどたまに使う記法について備忘録。
※2.7系で動かしているので3系では動かないかもしれない。要調査。

リスト操作

リストの重複削除

a = [1,1,4,4,3,3,2,2,5,5]
list(set(a))
# >>[1,2,3,4,5]

※この書き方だと順序は保持されない

順序を保持するリストの重複削除はこうする

sorted(set(a), key=a.index)
# >>[1,4,3,2,5]

リストの結合

a = [1,2,3]
b = [4,5,6]
c = a + b
# >>[1,2,3,4,5,6]

リストのソート

sorted(a)　# 1
a.sort()   # 2

1の場合はソートされたリストが返されるが、引数のリストは元の状態を保持。
2の場合は値が返ってこないが、ソートされた状態になるので注意が必要。
いわば2は a = sorted(a) と同じ

リスト内包表記

基本

[i*i for i in range(10)]
# >>[0,1,4,9,16,25,36,49,64,81,100]

応用

ユークリッド距離を求めるのに使ったり

import numpy as np
c1 = [1, 2, 3]
c2 = [0, 0, 0]
distance = np.sqrt(sum([(a - b)**2 for a, b in zip(c1, c2)]))

三項演算子

x = "Fizz" if True else "Buzz"

実は結構新しくて、2.5以降からできたらしい。
それ以前はめっちゃ不便だっただろうな…

リスト内包表記との合わせ技

[0 if i%3==0 else i for i in range(10)]
# >>[0, 1, 2, 0, 4, 5, 0, 7, 8, 0]

lambda式

map, filterとの組み合わせ

map(lambda x:x*x ,range(10))
# >>[0,1,4,9,16,25,36,49,64,81,100]

※リスト内包表記の上の例と同じ。

filterを使ってある文字列を含む要素を取り出すことができる

keyword = ["windows","linux","mac","android"]
filter(lambda x:"win" in x, keyword)
# >>['windows']

sortedやmaxなどとの組み合わせ

要素に注目してソートしたり、距離の最大値を求めたりできる。

import random
a = [[random.random() for i in range(2)] for j in range(20)]
sorted(a, key=lambda x:x[0])
max(a, key=lambda x:x[0]**2+x[1]**2)

可読性が悪いのであまりに複雑な処理なら関数にした方がいいかもしれない

参考サイト：
Pythonで配列内の重複する値を抽出する方法 - Pashango’s Blog
[Pythonの無名関数（lambda）の使い方 - Life with Python

ポモドーロテクニックという時間管理術

ポモドーロテクニックという時間管理術を知った。
一部ではもてはやされているようだけどどうなんだろう。

ポモドーロテクニックとは
1.　25分＋5分の休憩を1ポモドーロとする。
２．1ポモドーロ内には自分の決めたタスクだけに集中する。
３．4ポモドーロごとに長めの休憩を取る。
というもの、ポイントは25分間だけは他のことを考えず決めたことだけに集中するというところらしい。
そうすることで長時間かかるタスクでも効率よく集中して取り組むことができるのだとか。

そのためのTodo管理サービスを見つけたのでちょっと試してみようと思う。

参考サイト：
誤解していたポモドーロテクニックと本当の威力 | RickyNews
今日から始める生産性アップ術。ポモドーロ・テクニック再入門ガイド | ライフハッカー［日本版］
長時間作業を短時間で済ませるために有効的な「ポモドーロ・テクニック」 - GIGAZINE
The Ultimate Guide to the Pomodoro Technique

RSA暗号を実装してみる（プログラム編）

前回まではRSA暗号の原理を説明してきたけれど、いよいよ本題。実際コーディングに取り掛かる。理論では簡単に説明されるところでも実際にコーディングしてみると難しいところがある。
RSA暗号を実装してみる（知識編） - 技術メモ
RSA暗号を実装してみる（理論編） - 技術メモ

RSA暗号の暗号化復号化の手順（復習）

(A1) A は異なる２つの巨大な素数 p, q を選ぶ。そして、n = pq を計算する。
(A2) n に対するオイラー数 ϕ(n) = (p − 1)(q − 1) を計算する。
(A3) ϕ(n) 以下で、ϕ(n) と互いに素となる自然数 e を探す。
(A4) ϕ(n) 以下で、ed ≡ 1 (mod ϕ(n))を満たす自然数 d を求める。
(A5) p, q, ϕ(n), d を秘匿して、n と e のみを公開する。
(B1) B が A に送りたい平文を P (＜ｎ)とする。B は を計算して、C を A へ送る。
(A6) 暗号文 C を受信した A は によって復号化する。

D=Pとなる理由は理論編で。

実際のコード

from math import sqrt, log10
import random

class RSA:
    def __init__(self,
                 upper_limit,
                 randomseed=None):
        random.seed(randomseed)
        primes = self.prime_list(upper_limit)
        self.p = [0,0]
        p = [int(pow(10, random.random() + log10(upper_limit) - 1)) - 1 for i in range(2)]
        for i,x in enumerate(p):
            while not primes[x-2]:
                x = x-1
            self.p[i] = x
        self.n = self.p[0] * self.p[1]
        self.euler = (self.p[0] - 1) * (self.p[1] - 1)
        x = int(pow(10, random.random() + log10(upper_limit) - 1)) - 1
        while not primes[x-2]:
            x = x-1
        self.e = x
        self.d = self._set_public_key()

    @staticmethod
    def prime_list(n):
        def mark(primes,x):
            for i in xrange(2*x, n, x):
                primes[i-2] = False
        primes = [(i%2!=0 and i%3!=0 and i%5!=0) for i in range(2,n)]
        primes[0] = primes[1] = primes[3] = True
        for x in xrange(7, int(sqrt(n))+1):
           if primes[x-2]: mark(primes,x)
        return primes

    @staticmethod
    def pow_mod(x, y, z):
        n = 1
        while y:
            if y & 1:
                n = n * x % z
            y >>= 1
            x = x * x % z
        return n

    def _set_public_key(self):
        def xgcd(b, n):
            x0, x1, y0, y1 = 1, 0, 0, 1
            while n != 0:
                q, b, n = b // n, n, b % n
                x0, x1 = x1, x0 - q * x1
                y0, y1 = y1, y0 - q * y1
            return  b, x0, y0
        g,x,_ = xgcd(self.e, self.euler)
        d = x % self.euler
        return d

    def encrypt(self, plain):
        cipher = self.pow_mod(plain, self.e, self.n)
        return cipher

    def encrypt_with_external_pubkey(self, plain, e, n):
        cipher = self.pow_mod(plain, e, n)
        return cipher

    def decrypt(self, cipher):
        plain = self.pow_mod(cipher, self.d, self.n)
        return plain

    def decrypt_with_external_seckey(self, cipher, d, n):
        plain = self.pow_mod(cipher, d, n)
        return plain

    def get_secret_keys(self):
        return [self.p, self.euler, self.d]

    def get_public_keys(self):
        return [self.n, self.e]


def decrypt_test():
    rsa = RSA(1000000)
    plain = int(random.random()*100000000)
    print("plain:%d"%plain)
    cipher = rsa.encrypt(plain)
    print("cipher:%d"%cipher)
    replain = rsa.decrypt(cipher)
    print("replain:%d"%replain)
    pubkeys = rsa.get_public_keys()
    seckeys = rsa.get_secret_keys()
    print("public keys -- n:%d, e:%d"%(pubkeys[0],pubkeys[1]))
    print("secret keys -- (p, q):(%d, %d), euler:%d, d:%d"%(seckeys[0][0], seckeys[0][1], seckeys[1], seckeys[2]))

if __name__=="__main__":
    decrypt_test()

実行結果

plain:94192148
cipher:805896119
replain:94192148
public keys -- n:71467294553, e:415111
secret keys -- (p, q):(343393, 208121), euler:71466743040, d:28686310711

ちゃんと元の平文が再現されていることがわかる。うまくいったネ。
たしかに71467294553の素因数分解は難しそう…。実際には300桁くらいの素数ペアを使うので、600桁以上の数を素因数分解しなければいけなくなるらしい。
そりゃ安全なわけだ…

解説

素数リストの作成

素数のリスト作成にはエラトステネスの篩を使った。※参考サイトの欄に載せておきます。
実際にSSHなどで使われている素数は300桁ほどあり、こんな方法じゃ余裕でオーバーフローしてしまう。そこで素数を探し出すには確率的素数判定法なるものを使うのだが、自分自身よくわかっていないので、解説はまたいつかということで。確率的素数判定法 vs. エラトステネスの篩 - 技術メモ

素数ペアの選定

素数のペアを出してくる際には、2つともできるだけ大きい素数であることが望ましい。そこで、桁数を絞る工夫をしてある。上限値の対数を取って±1以内に収まるようにした。末尾で１を引く処理をしいるのは、万が一乱数が0.999999999999...となった場合インデックス外になってしまってエラーを吐くから。
秘密鍵のeにはある程度大きい数を使った方が良いらしいが、直接互いに素な大きい数を探し出す高速な方法がわからず、予め求めた素数リストから抜き出すようにした。

公開鍵の作成

公開鍵の作成には拡張ユークリッド互除法を使う。※参考サイトの欄に乗せておきます。

暗号化復号化

暗号化復号化には馬鹿でかい数の指数を扱うのでpow(e,d)%nじゃ時間もメモリも足りない。そこでベースを掛けるたびに剰余を計算する方法をとる。
※参考サイトをそのまま参考にしたので下の欄に乗せておきます。
※pythonではどうやらx^y%zの計算はpow(x,y,z)でできるらしい！さすがpython！

関連記事：

参考にしたサイト：

• 素数リストの作成 -- Pythonでエラトステネスの篩 - むしゃくしゃしてやった，今は反省している日記
• 冪剰余 -- Fastest modular exponentiation - Code Golf Stack Exchange
• 拡張ユークリッド互除法 -- Algorithm Implementation/Mathematics/Extended Euclidean algorithm - Wikibooks, open books for an open world

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html
2014-06-10
http://blanktar.jp/blog/2013/10/python-modular-exponentiation.html