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.

Westernize

1 % z is always 1 ... what did you expect this to mean? – Steiger

i was expecting de = 1 (mod z) – Westernize

Then you want (d*e)%z==1 – Steiger

If @khelwood's comment isn't obvious: 1 (mod z) is always 1 (for z > 1). But de (mod z) is not always de. So you're doing the modulus remainder on the wrong side. (Of course technically speaking, you should do it on both sides, but the point is, you can skip the right, and you can't skip the left.) – Nobile

if z = (p-1)(q-1), then gcd(e, z) is always 1, what is the point of your first function? – Compeer

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.

Steiger

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

Compeer

Your (3) isn't necessary. If you pass them in the wrong order, then e%z will be e, as you say, but that just means the return gcd(z, e%z) is the same as return gcd(z, e). In other words, it automatically swaps them for you. – Nobile

that is what I meant, he would never get the greatest common divisor@Nobile – Compeer

Then you meant wrong. If you call gcd(e, z) when you should have called gcd(z, e), that's fine, because the first thing it will do is return gcd(z, e). Try running it; gcd(4, 18) and gcd(18, 4) both return 2. – Nobile