Re: how to factor gaussian integers ?

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

Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
.

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)
  • 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)
  • 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 ?
    ... 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)