Re: how to factor gaussian integers ?

In article <21860870.1189884618154.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
tommy1729 <tommy1729@xxxxxxxxx> wrote:
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

Hardy har har.

Did you notice where it said that you need to be able to factor an
integer to start? Given a+bi, you first compute a^2+b^2, then you
factor ->that<-, and once you have that factorization then you can
obtain a factorization for the original.

This is why I said that factoring in the Gaussians is as hard as
factoring in the integers. If you can do one efficiently, then you can
do the other efficiently.

So, no. I will not play your little game. Go play with yourself if you
are so starved for entertainment. Just shut the bathroom door before
you start.


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 ...

There are very efficient algorithms for factoring in integral domains
with only finitely many primes. You can even figure them out if you
think about them and stop trying to be a clown.

Let D be the set of all rational numbers that can be written as a/b,
with a and b integers, and b relatively prime to, say, 2, 3, and 5.

This is an integral domain. The only primes in this domains are 2, 3,
and 5.

Given any element x/y of D, with gcd(x,y)=1, find the highest power of
2, of 3, and of 5 that divide x (which can be done both easily and
efficiently). Write x = 2^a*3^b*5^c*e, with gcd(e,30)=1. Then x/y
factors in D as (e/y)*2^a*3^b*5^b. Both easy and efficient.

Same idea if you have an integral domain with only finitely many
primes.

--
======================================================================
"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 ?
    ... There are very efficient algorithms for factoring ... in integral domains with only finitely many primes. ... Same idea if you have an integral domain with only finitely many ... Precisely what algorithm do you believe is efficient? ...
    (sci.math)
  • Re: how to factor gaussian integers ?
    ... There are very efficient algorithms for factoring in integral domains ... with only finitely many primes. ... Same idea if you have an integral domain with only finitely many ... efficiency to mean the assymptotic Big-Oh of the algorithm. ...
    (sci.math)
  • Re: how to factor gaussian integers ?
    ... There are very efficient algorithms for factoring in integral domains ... with only finitely many primes. ... Same idea if you have an integral domain with only finitely many ...
    (sci.math)
  • Re: how to factor gaussian integers ?
    ... There are very efficient algorithms for factoring in integral domains ... with only finitely many primes. ... Same idea if you have an integral domain with only finitely many ...
    (sci.math)
  • getting more familiar with gaussian primes
    ... by trying to get more familiar with gaussian primes- ... using gaussian primes? ... Gottfried Helms ... Prev by Date: ...
    (sci.math)
Loading