http://yosida95.hatenablog.com/entry/20120530/1338365377

gistfile1.py

#!/usr/bin/env python
#-*- coding: utf-8 -*-

from random import randrange


LENGTH_OF_INT = 5


def prime_list(limit):
    primes = []
    tmp = [True for _ in range(0, limit + 1)]
    tmp[0] = tmp[1] = False

    for number, is_prime in enumerate(tmp):
        if is_prime:
            primes.append(number)
            for _ in range(number * 2, limit + 1, number):
                tmp[_] = False

    return primes


def prime_range(offset, limit=None):
    _offset = 1 if limit is None else offset
    _limit = offset if limit is None else limit
    primes = prime_list(_limit)

    begin, end = 0, len(primes) - 1
    while (end - begin) > 1:
        middle = (begin + end) // 2
        if primes[middle] > _offset:
            end = middle
        elif primes[middle] <= offset:
            begin = middle

    return primes[end - 1 if primes[end - 1] >= offset else end:]


def ex_euclid(a, b):
    x0, x1 = 0, 1
    y0, y1 = 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1 - q * x0, x0
        y0, y1 = y1 - q * y0, y0

    return x1, y1, a


def generate_key_pair(prime_table):
    p = q = prime_table[randrange(0, len(prime_table))]
    while(p == q):
        q = prime_table[randrange(0, len(prime_table))]

    n = p * q

    modulo = (p - 1) * (q - 1)
    int_gen = lambda: randrange(10 ** (LENGTH_OF_INT - 1), 10 ** LENGTH_OF_INT)

    e = int_gen()
    d, y, gcd = ex_euclid(e, modulo)
    while gcd is not 1:
        e = int_gen()
        d, y, gcd = ex_euclid(e, modulo)

    return e, d, n


def main():
    prime_table = prime_range(10 ** (LENGTH_OF_INT - 1), 10 ** LENGTH_OF_INT)
    e, d, n = generate_key_pair(prime_table)

if __name__ == '__main__':
    main()