# Factorizing N to derive D [duplicate]

So I have the value of N. I have to use this value of N to find the value of D.

N = 265291078722948385089717069136983657793

N=PQ | where P and Q are prime factors

I found -
P - 14716976826788780483
Q - 18026193955816294571

1. The following is an example of what I've approached

Choose p = 3 and q = 11
Compute n = p * q = 3 * 11 = 33
Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]

2. We have

P = 14716976826788780483
Q = 18026193955816294571
N = 265291078722948385089717069136983657793
E = 65537 (given)
φ(n) = 265291078722948385056973898354378582740 [using (p-1)(q-1)]

I'm unable to solve the equation (d * e) % φ(n) = 1 for the above values. We need to find/derive D.

I tried using this online calculator Princeton Extended Calc But it doesn't accept large values

Any help is appreciated

Wolfram alpha can do this:

http://www.wolframalpha.com/input/?i=multiplicative+inverse+of+65537+mod+265291078722948385056973898354378582740

yields

d = 240894030773496778838526583320400223673

The alternative is to write a small C program using gmp or using python, e.g.

• More than answer the question giving the number, I feel it would be better to explain the process and how to find the result. This would be useful for all other people having a similar problem with a different number. – ddddavidee Nov 16 '15 at 20:19
• The OP used an online calculator so I referred him to another one that does work – Henno Brandsma Nov 16 '15 at 20:21
• "Give a man a fish and you feed him for a day; teach a man to fish and you feed him for a lifetime." Generally, for homework questions like this pointers towards the correct way are much more useful than just handing over the result. – tylo Nov 17 '15 at 13:30

Seeing code might help you, it should be this if I remember correctly. For large numbers you should use an NTL library.

/*
Recursive version of the euclidean algorithm, because it's much faster.
*/
void extendedEuclid(long a, long b, long& x, long& y)
{
if (a%b== 0)
{
x = 0;
y = 1;
return;
}
extendedEuclid(b,(a%b), x, y);
long temp = x;
x = y;
y = temp - (y*(a//b));
}
/*
Mudular inverse of a x = 1 mod m;
returns x in this case.
*/
long modInverse(long a, long d)
{
long x, y;
extendedEuclid(a, d, x, y);
if (!(x > zero()) && !(x ==0))
x =(x+d);
return x;
}

• long is also not big enough. Use gmp or some other bignum library, if you want C. Of course Python will do this OK, as it has bignums built in. – Henno Brandsma Dec 17 '15 at 21:36

If you want to try with some Python code:

   def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m