Problem A
Shanks' Baby Step Giant Step

Languages en is

Implement the baby-step giant-step algorithm to solve $g^{x} \equiv h (\mod p)$ for $x$ .

Input

Input is three lines. The first line contains the prime $p$ where $3 \leq p < 2^{40}$ . The second line contains the integer $g$ where $2 \leq g < p$ of order at least 2. The third line contains the integer $h$ where $0 \leq h < p$ .

Output

Output one line with any valid solution $0 \leq x < p - 1$ or no solution if no solution exists.

Sample Input 1	Sample Output 1
367 2 137	75

Sample Input 2	Sample Output 2
367 2 179	no solution

Hide

Please log in to submit a solution to this problem

Log in

CPU Time limit5 seconds

Memory limit1024 MB

?

DifficultyNot Available

LinksStatistics

DownloadsSample data files

Source & LicenseJón Steinn ElíassonT-513-Cryptography and Number Theory

You haven't made any submissions on this problem yet.

Editor:

Problem AShanks' Baby Step Giant Step

Input

Output

Problem A
Shanks' Baby Step Giant Step