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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.