``````def egcd(a,b):
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a
def gcd(a,b):
a,b=(b,a) if a<b else (a,b)
while b:
a,b=b,a%b
return a
def modInverse(e,n):#will help me find the private key!
return egcd(e,n)[0]%n
def totient(p,q):
return (p-1)*(q-1)
#e=int(raw_input())
#ct=1520
#n=int(raw_input())
def encode(ct,n,e):
ans=(ct**modInverse(e,n))%n
return ans
def decode(n,e):
ans=(encode(ct,n,e)**modInverse(e,n))%n
return ans
e = 2667263
n = 118161264594682552213478835740008518638148382236836652791249450378665869820660982155245457006168819364532380817733
ct=4972012305304213038212726495362
#d=modInverse(e,n)
#print encode(ct,n,e)
#print decode(n,e)
print decode(n,e)``````

Please help me solve this problem, when I run this program with small integers it does run, but for the one given above it doesn't. it's RSA Cryptography related

Edited by Nick Evan: Added CODE-tags

5
Contributors
4
Replies
5
Views
7 Years
Discussion Span
Last Post by Schol-R-LEA

soft brian (es): "it doesn't run" isn't enough info, (and no one is going to waste their time trying to properly indent the code you posted so they can run it). Also, try a more descriptive title. There are people who won't even look at threads with titles like "Please Help".

Edited by woooee: n/a

CODE-tags would also help.

Edited by mike_2000_17: Fixed formatting

As a one-time service to the OP, here's the code (extracted by quoting the post) with the original indentation:

``````def egcd(a,b):
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a

def gcd(a,b):
a,b=(b,a) if a<b else (a,b)
while b:
a,b=b,a%b
return a

def modInverse(e,n):#will help me find the private key!
return egcd(e,n)[0]%n

def totient(p,q):
return (p-1)*(q-1)

#e=int(raw_input())
#ct=1520
#n=int(raw_input())
def encode(ct,n,e):
ans=(ct**modInverse(e,n))%n
return ans

def decode(n,e):
ans=(encode(ct,n,e)**modInverse(e,n))%n
return ans

e = 2667263
n = 118161264594682552213478835740008518638148382236836652791249450378665869820660982155245457006168819364532380817733
ct=4972012305304213038212726495362
#d=modInverse(e,n)
#print encode(ct,n,e)
#print decode(n,e)
print decode(n,e)``````

Please use [code] tags in the future for any code samples you post.

Having tried running the code, I would say that the issue is a simple one: you are trying to factor a very large number, a process that takes a very long time - on the order of years even with modern hardware - and the factoring simply isn't finishing in a reasonable amount of time. Given that this is the whole basis of this sort of encryption's security, this should not be surprising.

Edited by Schol-R-LEA: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.