Re: how to factor gaussian integers ?


Bill Dubuque wrote:
Arturo Magidin <magidin@xxxxxxxxxxxxxxxxx> wrote:

There are very efficient algorithms for factoring in integral domains
with only finitely many primes.

Most certainly not. If that were true then one could factor
any integer N "efficiently" in the localization of Z whose
primes are precisely those integer primes smaller than N.

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.

That's simply trial division. Certainly easy, but hardly efficient.


Huh? The method is polynomial in the length of x. This is
efficient
in any measure of complexity.

.

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 ?
    ... Bill Dubuque wrote: ... There are very efficient algorithms for factoring ... many primes, ...
    (sci.math)
  • Re: Notes on irreducibles, reducibles in Integral Domains
    ... One definition of a UFD is ... A UFD is an integral domain in which every nonzero nonunit can ... A UFD is an integral domain in which every nonzero nonunit can ... factored into primes. ...
    (sci.math)
  • Re: how to factor gaussian integers ?
    ... plz dont tell me what a gaussian prime is and how to ... but despite knowing about gaussian primes, ... If you have a method for factoring regular integers, ... This is an integral domain. ...
    (sci.math)
Loading