code_iq: rsa

rsa.py

# -*- coding: utf-8 -*-

class code_iq:

    def do(self, n = 100):
        prime_numbers = self.prime_numbers(n)
        for p in prime_numbers:
            for q in prime_numbers:
                if p >= q:
                    continue
                e = []
                for k in range(1, (p - 1) * (q - 1)):
                    if self.is_coprime(k, (p - 1) * (q - 1)):
                        e.append(k)
                        if len(e) >= p + q:
                            continue
                if len(e) == p + q:
                    print "(p, q) = (%d, %d)" % (p, q)

    def is_coprime(self, a, b):
        if a > b:
            big, small = a, b
        else:
            big, small = b, a
        while big % small:
            big, small = small, big % small
        return True if small == 1 else False

    def prime_numbers(self, n):
        prime_numbers = []
        numbers = range(2, n + 1)
        for i in range(2, n + 1):
            if(i not in numbers):
                continue
            prime_numbers.append(i)
            for j in range(i, n + 1, i):
                if j in numbers:
                    numbers.remove(j)
        return prime_numbers

if __name__ == '__main__':
    code = code_iq()
    code.do()