Re: how to factor gaussian integers ?

Phil Carmody <thefatphil_demunged@xxxxxxxxxxx> writes:
Bill Dubuque <wgd@xxxxxxxxxxxxxxxxxxxx> writes:
Pubkeybreaker <pubkeybreaker@xxxxxxx> wrote:
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.

Perhaps their is some confusion due to imprecision.
Precisely what algorithm do you believe is efficient?

The same as everyone else. It's just that he's viewing efficiency
to mean the assymptotic Big-Oh of the algorithm. As the trial division
factor list never changes size, the algorithm complexity is barely worse
than a GCD computation, i.e. poly in the input size (number to be
factored).

This assymptotic behaviour in no way corresponds to whether
the algorithm is efficient to implement in the real world.

A simple equivocation on 'efficient'.

That was precisely my point - to highlight the artificiality of
this particular interpretation of "very efficient algorithms",
lest a novice be misled to believe that localizations possess
some nontrivial innate structure that simplifies factorization.

--Bill Dubuque
.

Relevant Pages

  • 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)
  • A Factoring Algorithm
    ... A Factoring Algorithm ... This is a different algorithm than that one. ... IF H is divisible by ANY of the primes ... constructing a NEW Base G, from the primes that follow P: ...
    (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 ?
    ... 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)