View Single Post
Old 2018-05-11, 02:49   #1
carpetpool's Avatar
Nov 2016

5108 Posts
Post Complexity of Finding a Principal Ideal

Question made simple.

Suppose we are given a number field (hence an algebraic number field), K, an Principal ideal P in K which is the product of two non-principal prime ideals Q and Q', (that is P = Q*Q'), and the norms the ideals Q, and Q' in the field of rational integers, which are correspondingly t and t' (norm of Q is t and norm of Q' is 't). Note that prime is bold, this means that both t and t' are prime. Lastly t and t' are not the same, therefore the corresponding ideals Q and Q' are not identical.

Suppose now, we are given exactly one of these ideals Q and the norm of Q which is t (we know what Q and t are, more importantly, t). How hard is it to find a corresponding ideal Q' with norm t' which is not identical to the ideal Q with norm t' such that P = Q*Q' is a principal ideal with norm t*t'? Also assume that the class number h of K is significantly large (say, h > 10000).

To better understand my question, consider the following problem. The imaginary quadratic field Q(i*sqrt(199)) has class number 9 (really this concept is applied to much larger number fields, with much larger class numbers). One finds that

Q = <i*sqrt(199)+862,3851> is a prime ideal with norm t = 3851, which is prime.

Now the goal is, to find a corresponding ideal Q' with prime norm t' (t' and t should be roughly about the same size) such that P = Q*Q' is a principal ideal. Obviously this is too easy, because of the relatively small class number, and degree of the field, but what about for significantly larger class number, and larger degree of the number field? Assuming dealing with larger number fields, what is the complexity of this problem?

Thanks for help
carpetpool is offline   Reply With Quote