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 6 Years Ago by Nick Evan: Added CODE-tags

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 6 Years Ago by woooee: n/a

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 6 Years Ago by Schol-R-LEA: n/a

This article has been dead for over six months. Start a new discussion instead.