RSA nulauzimas

from math import*
import string

def number2phrase(number):
    '''skaiciu pavers i fraze'''
    dictionary = dict(zip(range(27)," "+string.lowercase))
    ans = ""
    while number > 0:
        ans = dictionary[number % 27] + ans
        number = number // 27
    return ans

def count_pow(a,n,modulus):
    '''suskaiciuos rezultata a^n (mod modulus)'''
    def get_binary(n):
        '''n pavers i dvejetaine forma ir parasys gautos formos skaitmenu sarasa (atbula tvarka)'''
        ls=[]
        while n>0:
            ls.append(n%2)
            n/=2
        return [n for n in ls]

    def binary_residues(base,length, modulus):
        '''pagrindas base bus keliamas kvadratu tiek kartu, kiek reikalauja length ir bus grazinamas rezultatu (mod modulus) masyvas '''
        array=[]
        for i in range(length):
            array.append(base)
            base=(base**2)%modulus
        return array
    binary_pow=get_binary(n)
    multipliers=binary_residues(a,len(binary_pow), modulus)
    result=1
    for i in range(len(binary_pow)):
        if binary_pow[i]: result=(result*multipliers[i])%modulus
    return result

def gcd(a,b,M=[[1,0],[0,1]]):
    '''ispresime lygti ax=1 (mod b) taip, kad x butu teigiama liekana'''
    A,B=a,b
    while a<>0:
        factor=b/a
        a,b=b-a*factor,a
        M=[[M[1][0]-factor*M[0][0],M[1][1]-factor*M[0][1]],[M[0][0],M[0][1]]]
    if M[1][0]>0: return M[1][0]
    else: return M[1][0]+B

n=int('107150860718626732094842504906000181056140481170553360744375038'+\
'8370351051124936122493198378815695858127594672917553146825187145285'+\
'6923140435984577575320519019434834730126737027818318443983533130626'+\
'1364921548718349218473625842869329869868614879988527732396664619229'+\
'55659411708575370849066969625910058241')

m=int('5891891362324618801516625276689753892986599946617538963411230332134'+\
'2112190514713843777222238924868922623498834914053875551248418228253'+\
'1197092733993097827467708018501761089296474369148392207940371165257'+\
'7298170507933443719740542805570094855295089660630892981913643413045'+\
'581501376437077203633106798985884')

#Kodo dalis, kuri tikrina, ar salia n spinduliu 100 nera kokio nors kvadrato X, kad X^2-n yra kvadratas
for i in range(-100, 100):
    A=(int(sqrt(n))+i)**2-n
    if A>0 and A==(int(sqrt(A)))**2:
        print 'suradome: (int(sqrt(n)) +', i,'- n)^2 yra', int(sqrt(A)), 'kvadratas'
        break

p_plus_q_div2 = int(sqrt(n))+i
p_minus_q_div2 = int(sqrt(A))
p=p_plus_q_div2+p_minus_q_div2
q=p_plus_q_div2-p_minus_q_div2

d=17 #public key
e=gcd(d,(p-1)*(q-1)) #private key
meaning=count_pow(m,e,n)
print 'public key d=', d
print 'private key e=', e
print 'encrypted text:', meaning
print 'text:', number2phrase(meaning)