#!/usr/bin/env python3

# Imports
from pwn import *
import arrow
import random
import numpy as np

def legendre_symbol(a, p):
    """
    Legendre symbol
    Define if a is a quadratic residue modulo odd prime
    http://en.wikipedia.org/wiki/Legendre_symbol
    """
    ls = pow(a, (p - 1)//2, p)
    if ls == p - 1:
        return -1
    return ls

def prime_mod_sqrt(a, p):
    """
    Square root modulo prime number
    Solve the equation
        x^2 = a mod p
    and return list of x solution
    http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm
    """
    a %= p

    # Simple case
    if a == 0:
        return [0]
    if p == 2:
        return [a]

    # Check solution existence on odd prime
    if legendre_symbol(a, p) != 1:
        return []

    # Simple case
    if p % 4 == 3:
        x = pow(a, (p + 1)//4, p)
        return [x, p-x]

    # Factor p-1 on the form q * 2^s (with Q odd)
    q, s = p - 1, 0
    while q % 2 == 0:
        s += 1
        q //= 2

    # Select a z which is a quadratic non resudue modulo p
    z = 1
    while legendre_symbol(z, p) != -1:
        z += 1
    c = pow(z, q, p)

    # Search for a solution
    x = pow(a, (q + 1)//2, p)
    t = pow(a, q, p)
    m = s
    while t != 1:
        # Find the lowest i such that t^(2^i) = 1
        i, e = 0, 2
        for i in range(1, m):
            if pow(t, e, p) == 1:
                break
            e *= 2

        # Update next value to iterate
        b = pow(c, 2**(m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i

    return [x, p-x]


# Connection
host = "chall.nitdgplug.org"
port = 30209

s = remote(host,port)

context.log_level = 'debug'


# Get the encrypted time (contains the offset)
s.recv()
s.sendline('1')

s.recvuntil('\n')
s.recvuntil('\n')

enc_time = int(s.recvuntil('\n', drop=True).decode('ascii'))


# Send our guess based on seed derived from the decrypted time
s.recv()
s.sendline('2')

s.recvuntil('\n')

# Largest prime of N, which > m
p = 50700462220707155573

# Decrypt enc_time
time = min(np.array([prime_mod_sqrt(i,p) for i in prime_mod_sqrt(enc_time,p)]).flatten())

# Set seed
random.seed(time)

# Our guess
guess = random.randint(0, 99999999999)

s.sendline(str(guess))


s.interactive()