Can we fast generate perfectly uniformly mod 3 or solve NP problem? To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model:
We can get integers uniformly random from $[1,2^n]$ and our goal is to output an integer uniformly random from [1,3].

A simple solution whose expected running time is polynomial is the following. Discard $2^n$ (and possibly also $2^n-1$) from $[1,2^n]$ so that the number of remaining integers is divisible by $3$ so we can take $\bmod 3$ of the generated integer.
If we get a discarded number, we generate another number, until we get a non-discarded one.

But what if we want to terminate surely in polynomial time?
Because of divisibility issues, the problem becomes unsolvable.
However, I wonder if we can solve the following.


  Suppose we can generate integers uniformly random from $[1,2^n]$ and we are given a computationally hard problem.
  Our goal is to output an integer uniformly random from [1,3] or solve the hard problem.


Here the hard problem can be factoring an integer, solving a SAT instance or anything similar.
For example, we can decode a one-way permutation $f$ as follows, if we are given some $f(x)$ (and supposing $n$ is even):
If for our random string $f(r)&lt;f(x)$, then take $f(r) \bmod 3$, if $f(r)&gt;f(x)$, then take $f(r)-1\bmod 3$.
Finally, if $f(r)=f(x)$, then we are done, as $r=x$.
(If $n$ is odd, then something similar works, just we also have to check if $f(r+1)=f(x)$ and subtract $2$ if $f(r)&gt;f(x)$.)

Summary of answers.
Emil Jeřábek has shown that unless we can generate perfectly uniformly, we can solve any single-valued search problem from TFNP, and also from PPA-3.
On the other hand, daniello has shown that we cannot solve NP-complete problems the above way, unless NP=co-NP.
I will use numbers starting from $0$ rather than $1$, as I find it much more natural.
Here are two classes of problems we can solve in this way:

Functions in TFNP (i.e., single-valued total NP search problems)
(This generalizes the example with one-way permutations. It includes as a special case decision problems from $\mathrm{UP\cap coUP}$.)
The setup is that we have a polynomial-time predicate $R(x,y)$, and a polynomial $p(n)$ such that for every $x$ of length $n$, there exists a unique $y$ of length $m=p(n)$ such that $R(x,y)$ holds. The computational task is, given $x$, find $y$.
Now, I will assume wlog that $m$ is even, so that $2^m\equiv 1\pmod3$. The algorithm is to generate a uniformly random $y\in[0,2^m)$, and output

$y$ (as a solution of the search problem) if $R(x,y)$;

$y-y'$ (as a random element of $\{0,1,2\}$) if $y-y'\in\{1,2\}$, and $R(x,y')$;

$y\bmod3$ (as a random element of $\{0,1,2\}$) if no $y'\in\{y,y-1,y-2\}$ solves $R(x,y')$.


If there were no solution of the search problem, the $2^m$ random choices would give $1$ and $2$ $(2^m-1)/3$ times, and $0$ $(2^m+2)/3$ times (one more). However, if $y$ solves the search problem, we tinkered with the elements $y,y+1,y+2$ (which hit all three residue classes) so that they only produce residues $1$ and $2$, which evens out the advantage of $0$. (I am assuming here wlog that $y&lt;2^m-2$.)

PPA-$3$ search problems
A convenient way to define PPA-$3$ is as NP search problems many-one reducible to the following kind of problems. We have a fixed polynomial-time function $f(x,y)$, and a polynomial $p(n)$, such that for any input $x$ of length $n$, the induced mapping $f_x(y)=f(x,y)$ restricted to inputs $y$ of length $m=p(n)$ is a function $f_x\colon[0,2^m)\to[0,2^m)$ satisfying $f_x(f_x(f_x(y)))=y$ for every $y$. The task is, given $x$, find a fixpoint $y$ of $f_x$: $f_x(y)=y$.
We can solve this in the way in the question as follows: given $x$ of length $n$, we generate a random $y$ of length $m=p(n)$, and output

$y$ if it is a fixpoint of $f_x$;

otherwise, $y$, $f_x(y)$, and $f_x(f_x(y))$ are distinct elements. We can label them as $\{y,f_x(y),f_x(f_x(y))\}=\{y_0,y_1,y_2\}$ with $y_0&lt;y_1&lt;y_2$, and output $i\in\{0,1,2\}$ such that $y=y_i$.


It is clear from the definitions that this gives a uniform distribution on $\{0,1,2\}$, as the non-fixpoint $y$'s come in triples.



Let me show for the record the equivalence of the problem above with Papadimitriou’s complete problem for PPA-$3$, as this class is mostly neglected in the literature. The problem is mentioned in Buss, Johnson: “Propositional proofs and reductions between NP search problems”, but they do not state the equivalence. For PPA, a similar problem (LONELY) is given in Beame, Cook, Edmonds, Impagliazzo, and Pitassi: “The relative complexity of NP search problems”. There is nothing special about $3$, the argument below works mutatis mutandis for any odd prime.

Proposition: The following NP search problems are poly-time many-one reducible to each other:

Given a circuit representing a bipartite undirected graph $(A\cup B,E)$, and a vertex $u\in A\cup B$ whose degree is not divisible by $3$, find another such vertex.

Given a circuit representing a directed graph $(V,E)$, and a vertex $u\in V$ whose degree balance (i.e., out-degree minus in-degree) is not divisible by $3$, find another such vertex.

Given a circuit computing a function $f\colon[0,2^n)\to[0,2^n)$ such that $f^3=\mathrm{id}$, find a fixpoint of $f$.



Proof:
$1\le_p2$ is obvious, as it suffices to direct the edges from left to right.
$2\le_p1$: First, let us construct a weighted bipartite graph. Let $A$ and $B$ be copies of $V$: $A=\{x^A:x\in V\}$, $B=\{x^B:x\in V\}$. For each original edge $x\to y$, we put in an edge $\{x^A,y^B\}$ of weight $1$, and an edge $\{x^B,y^A\}$ of weight $-1$. This makes $\deg(x^A)=-\deg(x^B)$ equal to the degree balance of $x$ in the original graph. If $u$ is the given vertex of balance $b\not\equiv0\pmod3$, we add an extra edge $\{u^A,u^B\}$ of weight $b$, so that $\deg(u^A)=2b\not\equiv0\pmod3$, and $\deg(u^B)=0$. $u^A$ will be our chosen vertex.
In order to make the graph a plain unweighted undirected graph, we first reduce all weights modulo $3$, and drop all edges of weight $0$. This leaves only edges of weights $1$ and $2$. The latter can be replaced with suitable gadgets. For example, instead of a weight-$2$ edge $\{x^A,y^B\}$, we include new vertices $w_i^A$, $z_i^B$ for $i=0,\dots,3$, with edges $\{x^A,y^B\}$, $\{x^A,z^B_i\}$, $\{w^A_i,y^B\}$, $\{w^A_i,z^B_i\}$, $\{w^A_i,z^B_{(i+1)\bmod4}\}$: this makes $\deg(w_i^A)=\deg(z_i^B)=3$, and contributes $5\equiv2\pmod3$ to $x^A$ and $y^B$.
$3\le_p2$: Let me assume for simplicity $n$ is even so that $2^n\equiv1\pmod3$. We construct a directed graph on $V=[0,2^n)$ as follows:

We include edges $3x+1\to3x$ and $3x+2\to3x$ for each $x&lt;2^n/3-1$.

If $x_0&lt;x_1&lt;x_2$ is a non-fixpoint orbit of $f$, we include edges $x_0\to x_1$ and $x_0\to x_2$.


The chosen vertex will be $u=2^n-1$. The first clause contributes balance $1$ or $-2\equiv1\pmod3$ to each vertex $\ne u$. Likewise, the second clause contributes balance $-1$ or $2\equiv-1\pmod3$ to vertices that are not fixpoints. Thus, assuming $u$ is not already a fixpoint, it is indeed unbalanced modulo $3$, and any other vertex unbalanced modulo $3$ is a fixpoint of $f$.
$1\le_p3$: We may assume that $A=B=[0,2^n)$ with $n$ even, and the given vertex $u\in A$ has degree $\equiv2\pmod3$.
We can efficiently label edges incident with a vertex $y\in B$ as $(y,j)$, where $j&lt;\deg(y)$. In this way, $E$ becomes a subset of $[0,2^n)\times[0,2^n)$, which we identify with $[0,2^{2n})$. We define a function $f$ on $[0,2^n)\times[0,2^n)$ as follows.

On the complement of $E$: for each $y\in B$, and $j$ such that $\deg(y)\le 3j&lt;2^n-1$, we make $f(y,3j)=(y,3j+1)$, $f(y,3j+1)=(y,3j+2)$, $f(y,3j+2)=(y,3j)$. Also, $f(3i,2^n-1)=(3i+1,2^n-1)$, $f(3i+1,2^n-1)=(3i+2,2^n-1)$, $f(3i+2,2^n-1)=(3i,2^n-1)$ for $3i&lt;2^n-1$. This leaves out the point $(2^n-1,2^n-1)$, and $3-(\deg(y)\bmod 3)$ points $(y,i)$ for each $y\in B$ whose degree is not divisible by $3$.

On $E$: for each $x\in A$, we fix an efficient enumeration of its incident edges $(y_0,j_0),\dots,(y_{d-1},j_{d-1})$, where $d=\deg(x)$. We put $f(y_{3i},j_{3i})=(y_{3i+1},j_{3i+1})$, $f(y_{3i+1},j_{3i+1})=(y_{3i+2},j_{3i+2})$, $f(y_{3i+2},j_{3i+2})=(y_{3i},j_{3i})$ for $i&lt;\lfloor d/3\rfloor$. This leaves out $\deg(x)\bmod3$ points for each vertex $x\in A$ whose degree is not divisible by $3$.


Since $\deg(u)\equiv2\pmod3$, two of its incident edges were left out; we make them into yet another $f$ cycle using $(2^n-1,2^n-1)$ as the third point. The remaining points are left as fixpoints of $f$. By construction, any of them will give rise to a solution of (1).