# How do you get $d$ in textbook RSA

So people say to choose $$d$$ such that $$e*d=1(mod((p-1)*(q-1)))$$.

However, $$1\%$$ anything always equals $$1$$. Maybe I am not understanding it correctly, but the only way to get $$e \cdot d=1$$ is just by doing $$e^{-1}$$ which leads into a very very small number $$\lll 1$$ because $$e$$ is large.

How are people getting $$e$$ and $$d$$ such that they are both large numbers?

My main confusion really just comes from that $$1\%$$ anything always equals $$1$$.

• You appear to be conflating two notations: a mod n (no parentheses) including x = a mod n means, for positive numbers, the remainder of a divided by n, the same as the % operator in some programming languages. (For negative numbers remainder and modulo are not always the same, but in crypto we mostly don't care about negative numbers.) $a \equiv b$ (mod n) with triple-bar and parentheses means the difference $a-b$ is a multiple of n, also said as a and b are equivalent modulo n. – dave_thompson_085 Feb 3 at 9:01

## 1 Answer

There are no percentages, fractions, real or floating point numbers involved.

When using modular arithmetic, the "division" operation is defined differently. If you have some values $$a, b$$ that have been multiplied together into $$ab$$, what you want from division is that $$\frac{ab}{b} = a$$, or stated alternatively that $$\frac{a}{a} = 1$$.

When working with modular arithmetic, you need a different division operation than the "normal" one taught in basic math classes. This is easy to see with an example. Suppose that you have $$a=5\\b=7\\N=19\\ab \equiv 16 \bmod N$$ It is easy to see that dividing (in the traditional sense) $$16$$ by $$7$$ is not going to yield $$5$$.

Instead, you can multiply $$16$$ by $$11$$, which happens to be equivalent to $$5$$ modulo $$19$$. This fulfills the behavior expected of the division operation, which is what we really care about.

A value $$\frac{1}{b}$$ such that $$\frac{ab}{b} \equiv a \bmod N$$ is called a modular multiplicative inverse.

## Back to the specific question

In the case of RSA, $$e$$ and $$d$$ are modular multiplicative inverses: $$ed \equiv 1 \bmod \lambda(N)$$.

Alternatively, you can denote $$d$$ by $$\frac{1}{e}$$ or $$e^{-1}$$; These are different ways of writing the same value.

A multiplicative inverse exists if the element is coprime to the modulus $$N$$. To actually find a modular multiplicative inverse of an element, you can use the extended euclidean algorithm.