all images are clickable

## Challenge information ## 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}
``````