# m0leCon CTF 2021 Teaser — Giant log

*all images are clickable*

## Challenge information

## Files

**chall.py**:

## Solution

The main goal of the challenge is simple: we just need to calculate a discrete logarithm in *very huge* numbers. The challenge server generates a random number `x ∈ [1, p]`

, calculates `y = g ^ x (mod p^1000)`

and prints `y`

, then we need to find `x`

in 60 seconds. It’s obvious that running the discrete logarithm directly will be inefficient, so we need to use a different approach.

When you see a prime power (such as `p^1000`

in our case), you might think of p-adic numbers. I’ll try to briefly explain what it is.

Suppose you have a prime `p`

and an integer `x`

. You always can write `x`

as sum:

```
x = a0 * p^0 + a1 * p^1 + a2 * p^2 + ...
```

And `x`

represented that way is a p-adic number. You could use something similar when you wrote a number in a binary representation (`2-adic`

). p-adic numbers extend the ordinary integer arithmetic and also have its exponential and logarithm functions. As you know, the logarithm function for numbers has the property: `log_a(b) = log(b) / log(a)`

, so we can express `x`

:

```
y = g ^ x => x = log_g(y) = log(y) / log(g)
```

Let’s write come `sage`

code:

Note that the numbers are really huge, for example `y`

has about 150k decimal digits.

## Flag

```
ptm{p_4d1cs_ar3_t00_op}
```