What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.



Number theory and NP-complete
You can take a look at the papers by Adleman and Manders (not always in this order) from the 70s (at least "Computational complexity of decision procedures for polynomials", "NP-complete decision problems for quadratic polynomials", "Diophantine complexity"), and the references therein. 


One example of the problems they show to be NP-complete is the following decision problem. 


* Input: three natural numbers $a,b,c$ (in base $2$),
* Output: YES/NO depending whether the equation $ax^2 + by = c$ has solutions (for $x,y$) in the natural numbers.


