factorization of integers in quadratic norm-Euclidean fields
FactorNormEuclidean(z, d, output_opt)
integral element of Q⁡d
rational integer such that Q⁡d is a norm-Euclidean field
(optional) equation of the form output = product or output = list; the default is output = product
If output_opt is set to output = product, then the return value is of the form ±ua⁢p1b1⋯pnbn where the pi are distinct prime factors and the bi are positive integers.
If d>0, then u is either w or w&conjugate0; where w is the fundamental unit in Z⁡d and a is a non-negative integer.
If d<0, then u is a unit in Z⁡d and a=1.
If output_opt is set to output = list, then the return value is of the form s,x,y,a,f1,…,fn where s=±1 and each fi is a three element list of the form p,q,k. Each p+q⁢d is a distinct prime and k is a positive integer.
If d>0, then u=x+y⁢d where u is as previously described and a is a non-negative integer.
If d<0, then x+y⁢d is a unit in Z⁡d. Let t=x+y⁢d. If t=±1 then t=s and x,y,a=1,0,0. Otherwise, s,a=1,1.
The FactorNormEuclidean function computes the integer factorization of z in the ring of integers Z⁡d of the quadratic field Q⁡d.
Consider the absolute value of the field norm of Q⁡d as a field extension of Q, denoted by N. If d is one of −11,−7,−3,−2,−1,2,3,5,6,7,11,13,17,19,21,29,33,37,41,57,73, then N satisfies the following property. If a and b are in Q⁡d and b≠0, then there exists q and r in Q⁡d such that a=b⁢q+r and N⁡r<N⁡b. In this case, N is said to be a Euclidean function on Q⁡d and Q⁡d is said to be a norm-Euclidean field.
When d=2,3mod4, integers in Z⁡d have the form a+b⁢d and when d=1mod4 they have the form a+b⁢12+12⁢d, where a and b are rational integers. Alternatively for when d=1mod4, integers have the form a2+b2⁢d where a and b are rational integers of the same parity.
expand may be used to multiply together the terms.
If output_opt option is explicitly set to output = product, the return value will be in product form.
If the output_opt is set to output = list, the return value will be in list form.
FactorNormEuclidean(z, d) displays an error message if z is not an integer in Q⁡d.
Error, (in NumberTheory:-FactorNormEuclidean) 3/2 is not an integer in Q(sqrt(2))
The NumberTheory[FactorNormEuclidean] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
Download Help Document