# Why does the challenge need to be prime in Wesolowski's succinct argument of $y=x^{e}$?

In Wesolowski's VDF (verifiable delay function) a prover produces a pair $$(x, y)$$ and needs to argue to the verifier that the pair satisfies $$y = x^e \pmod N$$ for some $$e$$ computable to both. The verifier is compute limited and $$e$$ is really large, so cannot compute $$x^e\pmod N$$ herself. The prover needs to convince the verifier with the verifier doing little work.

To achieve this, the verifier generates a challenge $$c$$ which is prime, and the prover responds with $$\pi = x^{\lfloor e/c\rfloor}\pmod N$$. Now the verifier can be convinced if $$y = \pi^c x^{r}\pmod N$$, where $$r$$ is the remainder of $$e$$ divided by $$c$$.

How does the primality of $$c$$ come into play? Is there a forged proof attack for composite challenges?

In [1] the base difficulty assumption is this game:

Game 1: We are given an $$N$$ guaranteed to be a product of two primes . We choose $$u\neq 1$$. After this we're given a uniform random k-bit prime $$c$$. We win if we output $$v$$ such that $$v^c = u\pmod N$$.

Does this game become easier if instead we're given just a random k-bit number? The reduction from the VDF problem to Game 1 does not seem to use the fact that $$c$$ is a prime either.

Later on [2] names the statement "Game 1 is hard" the adaptive root assumption. They also work with primes only, with no justification.

The reason we cannot choose $$c$$ uniformly in some interval, but must choose it from $$\mathrm{Primes}(k)$$, is because a random $$c$$ in $$\{1, \ldots, 2^k\}$$ has a reasonable chance of being a smooth integer. The adversary can then win by outputting $$u= a^B$$ where B is the product of small prime powers up to some bound k, and later chosing $$v = a^{B/c}$$. Choosing $$c$$ as a prime number eliminates this attack.
So Game 1 does become easier if we give the player a random $$k$$ bit integer instead.