Re: how to factor gaussian integers ?

magadin@math wrote:

In article
<8970362.1189855862584.JavaMail.jakarta@xxxxxxxxxxxxxx
orum.org>,
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}*
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.

thanks for the reply.
it seems intresting.
and i like berkeley :-)

but somewhere you lost me ...

im sorry its weekend :-)

could you give an example maybe to factor

89703621729 + 11898558625841729 i



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.

i meant efficient rather than easily ...



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

i like that quote :-)


Arturo Magidin
magidin-at-member-ams-org


regards
tommy1729
.

Relevant Pages

  • Re: how to factor gaussian integers ?
    ... but despite knowing about gaussian primes, ... gaussian integers, then by letting a be a rational integer, factor it ... If you have a method for factoring regular integers, ...
    (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