Must an algorithm that decides a problem in NP also produce a solution?

If you could decide SAT problems in polynomial time, then you could also find a solution (for those instances that have them) in polynomial time.
Namely, if Boolean expression $A$ is satisfiable and $x$ is a variable appearing in $A$, choose one of the expressions $A|_{x=T}$ and $A|_{x=F}$ (obtained by setting $x$ to "true" or "false" respectively) that is satisfiable (at least one must be). Recurse until assignments for all variables have been found.

This extends to all problems in NP that can be reduced to SAT in such a way that a solution to the SAT problem generates (in polynomial time) a solution to the original problem. Most of the classical cases of NP-completeness are of this type.

In your example, we need to generalize a little bit, from the problem

Given $A,B,g,p$, do there exist $a,b$ such that ...

to

Given $A,B,g,p$ and $a_0, b_0, n$, do there exist $a,b$ such that $a \equiv a_0 \mod 2^n, b \equiv b_0 \mod 2^n$, and ...

Must an algorithm that decides a problem in NP also be able to construct a solution for that problem which can then be verified in polynomial time?

No, but a solution can be easily derived using the decision procedure for NP problems because all "natural" NP-complete problems seem to be downward self-reducible and all NP problems can be reduced to NP-complete problems.

Would an algorithm that decides (but does not construct a "solution") an NP-complete problem in polynomial time be sufficient to prove P=NP?

Yes. P and NP are classes of decision problems. A binary yes/no answer is all that is required for decision problems. Thanks to self-reducibility a decision procedure is all that's needed to construct a solution as well.

Would such a proof have any impact on cryptography at all?

Maybe. If the degree of the polynomial degree required to solve NP-complete problems is large in the worst case, then decrypting conventionally encrypted strings might still turn out to be hard, just not exponentially so. If the degree required is small then one-time pads are going to enjoy a renaissance.