Python gcd calulation of rsa

Question

def gcd(e, z):

    if z == 0:
        return e
    else:
        return gcd(z, e % z)

e = int(input("Please enter the first number:"))
z = int(input("Please enter the second number:"))

print ("The GCD of ",e," and ",z," is ",gcd(e,z))
d = 1
while d < e:

    if d * e == 1 % z:
        print (d," * ",e," = 1 (mod ",z,")")
        d = d + 1
    else:
        d = d + 1

I am trying to use this code to find candidates for rsa by brute force it seems like it should work but it doesn't can anyone help me out?

z = (p − 1)(q − 1) for the calculation of z is used prior to this with p = 47 and q = 59, e = 17 and d = 157 but after the program runs it finds no matches but it should.

Answer 1

Where you have

if d * e == 1 % z:

you seem to want to check "Is d*e equal (mod z) to 1"

But what you're doing is performing 1 % z (which gives 1) and checking if d * e is equal to 1.

Change it to:

if (d*e) % z == 1:

and it should do the calculation you intend.

Answer 2

some problems from your code:

1) if z = (p-1)(q-1), d*e = 1 (mod z), then z and e are coprime, gcd(e, z) will always equal 1, see

2) if you say d*e = 1 (mod z), the code should be if d * e % z == 1