# 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`


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/modular-binomial.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.