Re: Complexity of Discrete Log Algorithms

tomstdenis_at_gmail.com
Date: 06/08/05 

Date: 8 Jun 2005 11:04:23 -0700

Gregory G Rose wrote:
> You measure complexity in terms of the *length* of
> the input. Since the number n has length log(n),
> this complexity is O(e^(log n)) and hence it is
> fully exponential.

Just adding two bits here to help clarify the picture for the OP.

The big-O time/space is for the circuit time/size of the solution to
the problem. This stems from the classical theoretical view of
computing where programs are essentially combination of NAND gates
[though really they never specify hardware gates]. The idea is there
is some circuit of if/then/else statements which evaluate your problem.

Let's take a simple problem, adding two n-bit numbers. The circuit has
2n bits of input and produces n bits of output, each bit [after the
first] is dependent [and only computable] after the preceding bit has
been determined. This means the space is O(n) since we drop the
constant "2" and the time is O(n) since the result is only stable after
a linear number of gates have stabalized.

Now consider multiplication with double-add. Both double and add are
O(n) which means you take 2*O(n) = O(n) space but you pass through the
adder O(n) TIMES [once for each of the n bits] so you have a time
complexity of n additions which is O(n^2). Note that even if we move
up from bits to words [e.g. a typical BigNum library] the time is still
O(n^2) since we drop the constant.

Now consider a factoring sieve [e.g. Fermat]. The circuit is very
small at iirc roughly O(n) space but the time complexity is exponential
at q - p ~ 2^k [for some primes p and q of your modulus where q > p]
where the average k grows linearly as the size of the modulus [in bits]
grows linearly. so the time is O(2^k).

Note how in each case the time is dependent on the *length* of the
input not it's actual value, for example multiplying 127 * 65 takes the
same amount of time as 123*111 through a 8x8 multiplying circuit [as
far as big-oh is concerned]. E.g. double the bits, quadruple the
multiplication time or in the case of Fermat you essentially make the
problem intractable.

Quick ref of the Big ohs...

constant - O(1)
linear - O(n)
log - O(log n)
polynomial - O(n^k) for some constant k
sub-exp - O(e^logn)
exp - O(e^n)

It helps to graph them to see the difference and see how they grow.

Tom

Relevant Pages

  • Re: Complexity science meets geology, some recent research papers
    ... Looking at the world through a non linear perspective takes ... It's also in how the word complexity is now defined. ... state is considered to be at criticality. ... For a cloud the opposite extremes are simply ...
    (sci.geo.geology)
  • Re: Jeff Hawkins Q&A
    ... >>>brain is responsible. ... Certainly Dan's arguments have all been about linear ... >> complexity, that is simple numerical terms and combinations. ... >the nonlinear, ...
    (comp.ai.philosophy)
  • Re: Jeff Hawkins Q&A
    ... >> features and aspects of complexity and non linearity but don't really ... Computer power isn't the issue for nonlinear complexity. ... But linear complexity of itself has nothing to ... to the mechanization of intelligence for that reason. ...
    (comp.ai.philosophy)
  • Re: Complexity of BWT, PPM, LZ77/LZ78
    ... BWT based compressor to be considered linear. ... It has N^2 complexity. ... a certain size, eg the block size, as the sort algos involved may not ...
    (comp.compression)
  • Re: Why Is High Feedback Considered Bad In Audio? In Simple Terms
    ... Can someone explain, in simple terms, why high feedback is considered ... To me, linear is linear and ... a high feedback op-amp circuit is linear. ... the cd player's laser and electronics will more easily reproduce ...
    (sci.electronics.design)