Re: how to factor gaussian integers ?

In article <8970362.1189855862584.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
tommy1729 <tommy1729@xxxxxxxxx> wrote:
how does one efficiently factor a gaussian integer ??

plz dont tell me what a gaussian prime is and how to find them ; i
already know this.

but despite knowing about gaussian primes, no efficient factoring
method for gaussian integers ??

No more efficient method than for integers, because if you can factor
gaussian integers, then by letting a be a rational integer, factor it
as a gaussian integer, and by pairing off the conjugate non-rational
gaussian primes, which can be done easily, you get a factorization of
a into rational primes.

If you have a method for factoring regular integers, then do the
following to factor Gaussian integers: Given a+bi.

(i) Compute d = gcd(a,b); factor d into integers, then factor the
rational primes (by writing them as sums of two squares) that are not
gaussian primes to get a factorization of this factor. So we may
assume that gcd(a,b)=1.

(ii) If gcd(a,b)=1, then compute a^2+b^2, and factor it into rational
primes. Divide the primes into three groups: 2, those congruent to 1
modulo 4, and those congruent to 3 modulo 4:

a^2 + b^2 = 2^r * p_1^{s_1}*...*p_n^{s_n}* q_1^{t_1}*...*q_m^{t_m}.

with r>=0, s_i,t_j positive integers, p_i pairwise distinct primes
congruent to 1 modulo 4; q_i pairwise distinct primes congruent to 3
modulo 4.

(iii) The exponents t_i will all be even. Write each p_i as a sum of
two squares, p_j = (d_j^2 + f_j^2). Then p_i factors in Gaussian
primes as (d_j + i*f_j)(d_j - i*f_j).

(iv) (a+bi)(a-bi) = a^2+b^2. Each of a+bi and a-bi will be exactly
divisible by q_j^{t_j/2}. 2 will not divide a+bi (since gcd(a,b)=1),
but 1+i may; check.

(v) The remaining factors will be up to s_i factors of d_j + if_j or
d_j - if_j in some combination. Again, not hard to figure out which
and how many.

does any integer domain factor easily ?

Oh, yes. Any integral domain with finitely many primes has very easy
factoring algorithms, and there are plenty of those.

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: how to factor gaussian integers ?
    ... but despite knowing about gaussian primes, ... If you have a method for factoring regular integers, ... modulo 4, and those congruent to 3 modulo 4: ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... But if the idea turns out to be a brilliant one which means factoring ... No one has said math journals routinely publish ... current methods in speed for counting primes. ... about being a genius. ...
    (sci.math)
  • Re: JSH: Now were golden!
    ... factoring problem, and I want to definitely thank Enrico and would ... which the negative of the quadratic residue is a quadratic residue and ... they are the primes for which the negative of their quadratic residue ... It's a duty. ...
    (sci.crypt)
Loading