> For the complete documentation index, see [llms.txt](https://www.ctfrecipes.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/modular-binomial.md).

# Modular binomial

A modular binomial problem is a mathematical problem in which a binomial expression of the form :

$$
x = (a + b)^e \bmod N
$$

where :

* a and b are integers,
* e is a positive integer (the exponent),
* and N is a positive integer (the modulus).

{% hint style="info" %}
In cryptography, the modular binomial problem is used in RSA encryption, where the integers a, b, and N are related to the encryption and decryption keys, and the exponent e is used to encrypt a message. Solving the modular binomial problem for a given c, e, and N is considered to be a hard problem and is the basis of RSA encryption's security.
{% endhint %}

## Searching p and q

The modular binomial problem can have the following form :

$$
c\_1 = (a\_1 \cdot p + b\_1 \cdot q)^{e\_1} \bmod N\ c\_2 = (a\_2 \cdot p + b\_2 \cdot q)^{e\_2} \bmod N\\
$$

Given the value of `c1, c2 a1, a2, e1, e2 and N` and where `N = p*q` it's possible to retrieve p and q as follow :

{% hint style="info" %}
The main idea is to :

* upper `c1` using the exponent used in the `c2` equation : `e2`
* upper `c2` using the exponent used in the `c1` equation : `e1`

Doing that, `c1` and `c2` are on the same exponent : `e1.e2`

In order to retrieve `q` it's needed to isolate it, so it's needed to make the two equation to had the same p value

* Multiply by `a1**(-e1*e2)` in the c1 equation reduce P factor to 1
* Multiply by \`a2\*\*(-e1\*e2) in the c2 equation reduce P factor to 1

Then, by substrat `c1` to `c2` there is a `p**(e1*e2) - p**(e1*e2)` which is 0 so they can be remove of the equation
{% endhint %}

$$
c\_1^{e\_2} = (a\_1 \cdot p + b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\ c\_1^{e\_2} = (a\_1 \cdot p)^{e\_1 \cdot e\_2} + (b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\ a\_1^{-e\_1 \cdot e\_2} \cdot c\_1^{e\_2} = a\_1^{-e\_1 \cdot e\_2} \cdot (a\_1 \cdot p)^{e\_1 \cdot e\_2} + a\_1^{-e\_1 \cdot e\_2} \cdot (b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\ a\_1^{-e\_1 \cdot e\_2} \cdot c\_1^{e\_2} = p^{e\_1 \cdot e\_2} + a\_1^{-e\_1 \cdot e\_2} \cdot(b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\\
$$

Make the same with `c2`

$$
c\_2^{e\_1} = (a\_2 \cdot p + b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\ c\_2^{e\_1} = (a\_2 \cdot p)^{e\_2 \cdot e\_1} + (b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\ a\_2^{-e\_2 \cdot e\_1} \cdot c\_2^{e\_1} = a\_2^{-e\_2 \cdot e\_1} \cdot (a\_2 \cdot p)^{e\_2 \cdot e\_1} + a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\ a\_2^{-e\_2 \cdot e\_1} \cdot c\_2^{e\_1} = p^{e\_2 \cdot e\_1} + a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\\
$$

Then

$$
a\_2^{-e\_2 \cdot e\_1} \cdot c\_2^{e\_1} - a\_1^{-e\_1 \cdot e\_2} \cdot c\_1^{e\_2} = p^{e\_2 \cdot e\_1} + a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} - p^{e\_1 \cdot e\_2} - a\_1^{-e\_1 \cdot e\_2} \cdot(b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N \\= a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} - a\_1^{-e\_1 \cdot e\_2} \cdot(b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N
$$

So, q = `gcd(pow(a2,(-e2 * e1),N) * pow(c2, e1, N) - pow(a1, (-e1 * e2), N) * pow(c1, e2, N), N)`

Do the same to get `p`