ebook img

Computer algebra PDF

67 Pages·2005·0.51 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Computer algebra

Computer algebra Friedrich-Schiller-Universit¨at Jena, SS 2005 Ju¨rgen Mu¨ller Contents 1 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Integer arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Fast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Resultants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5 Lattice base reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6 Polynomial factorization over finite fields . . . . . . . . . . . . . . . . 39 7 Polynomial factorization over the integers . . . . . . . . . . . . . . . . 47 8 Exercises (in German) . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 1 1 Computational complexity Weintroducethestandardmodelofalgorithmiccomputing,namelyperforming operationsonfinitestringsofsymbolsoutofafinitealphabet,whicharethought ofasbeingwrittenontoaninfinitetape,usingamachinerunningbackandforth on the tape, reading and writing symbols according to a specified program. By Church’s Hypothesis this idea precisely covers the intuitive notion of algorithmiccomputability. Oneoftheearlyoccurrencesofthistypeofquestions isHilbert’s 10th problemonthedecidabilityofthesolubilityofDiophantine equations, see [6]; it was solved to the negative by Matijasevich (1972). (1.1) Definition. An alphabet is a finite set X =(cid:54) ∅. The free monoid X∗ := Xn is called the set of words over X. A subset L ⊆ X∗ is called a (cid:83)(fon∈rmN0al) language. For w ∈ Xn let l(w) = n ∈ N be the length of w. We 0 have X0 ={(cid:15)}, where (cid:15) is the empty word. (1.2) Definition. See [16]. A (deterministic) Turing machine over an alphabet X is a triple T := . [X ∪Y,S,τ], whereY isaworkingalphabet, inparticularcontainingablank symbol ∈ Y, an accepting symbol 1, a rejecting symbol 0, and a failure symbol∅. Moreover,S isafinitesetofstates,inparticularcontaininganinitial state s0 and a halting state s∞, and there is the transition function . . τ: (X ∪Y)×(S\{s∞})−→(X ∪Y)×{←,↑,→}×S. T acts on the set (X ∪. Y)∗×S×(X ∪. Y)∗ of configurations as follows: The initial configurations are given as [ ,s ,u], where u∈X∗ is called an input; an input of several u ,...,u ∈X∗ is enc0oded as u u ... u ∈(X ∪. Y)∗. 1 n 1 2 n Let [v,s,w] be a configuration, where s∈S\{s∞}. If (cid:15)(cid:54)=v,w ∈(X ∪. Y)∗, let v = v(cid:48)x and w = yw(cid:48), where x,y ∈ X ∪. Y; if v = (cid:15), let v(cid:48) := (cid:15) and x := ; if w =(cid:15), let w(cid:48) :=(cid:15) and y := . Then T induces the transition [v, s(cid:48), zw(cid:48)], if τ(y,s)=[z,↑,s(cid:48)], [v,s,w](cid:55)→ [vz, s(cid:48), w(cid:48)], if τ(y,s)=[z,→,s(cid:48)],  [v(cid:48), s(cid:48), xzw(cid:48)], if τ(y,s)=[z,←,s(cid:48)].  For a configuration [v,s∞,w] no transition is defined and T halts. We assume that for all inputs leading to such a halting configuration we are in one and the same of the following cases, depending on whether we consider decision problems or function problems: Either we have w ∈ 1(X ∪. Y)∗ or w ∈ 0(X ∪. Y)∗, i. e. T accepts or rejects the input, respectively; or we have w ∈ ∅(X ∪. Y)∗ or w ∈ w(cid:48) (X ∪. Y)∗, where w(cid:48) ∈ X∗, i. e. T fails or outputs w(cid:48). 2 (1.3) Example. Let X := {1} and S := {s0,s1,s∞}, and let T be given by the following transition function τ: τ 1 s [1,←,s ] [1,→,s ] 0 1 0 s1 [ ,→,s∞] [1,←,s1] Hence e. g. upon input 11∈X2 we obtain: s 11 (cid:55)→ 1 s 1 (cid:55)→ 11 s (cid:55)→ 0 0 0 1 s1 11 (cid:55)→ s1 111 (cid:55)→ s1 111 (cid:55)→ s∞ 111 , and for (cid:15)∈X0 we obtain: s0 (cid:55)→ s1 1 (cid:55)→ s∞ 1 . ThusitiseasilyseenthatT computesthesuccessorfunctionN →N: n(cid:55)→n+1, 0 where N is given in unary encoding. For the successor function in binary 0 encoding, see Exercise (8.1). (1.4) Definition. a) A language L ⊆ X∗ is called decidable (recursive), if there is a Turing machine T deciding L, i. e. T halts for all w ∈ X∗, and accepts w if and only if w ∈L, otherwise rejects w. A language L ⊆ X∗ is called recursively enumerable, if there is a Turing machine T accepting L, i. e. T halts for w ∈X∗ if and only if w ∈L. Note that if L is decidable, then it is recursively enumerable: Let T decide L, then T(cid:48) accepting L is a copy of T, except that whenever T rejects an input, then T(cid:48) enters an infinite loop. b) A Turing machine T deciding a language L ⊆ X∗ is called to run in time f: {N,N +1,...} → R , if T halts after at most f(l(w)) transitions, for all >0 w ∈ X∗ such that l(w) ≥ N. The complexity class TIME(f) ⊆ Pot(X∗) is the set of all languages being decidable in time f. In particular, we have the complexity class P := TIME(n (cid:55)→ nk) of lan- (cid:83)k∈N guages being decidable in polynomial time, and the complexity class EXP:= TIME(n(cid:55)→cnk)oflanguagesbeingdecidableinexponentialtime,where (cid:83)k∈N c>1; note that this does not depend on the choice of c>1. (1.5) Definition. a) A non-deterministic Turing machine over an alpha- . . bet X is a triple T := [X ∪ Y,S,τ], where X ∪ Y and S are as in (1.2), while the transition function . . τ: (X ∪Y)×(S\{s∞})−→Pot(cid:16)(X ∪Y)×{←,↑,→}×S(cid:17) allows for choices and thus branching. Let the non-determinateness be . defined as dT := max{|τ(x,s)|;x ∈ X ∪ Y,s ∈ S \{s∞}} ∈ N. The machine 3 T halts if no further transition in either branch is possible. We assume that for all inputs T on halting either accepts or rejects, or outputs; for acceptance, rejection or the output one of the branches is chosen randomly. b) A language L⊆X∗ is called non-deterministically decidable, if there is anon-deterministicTuringmachineT decidingL,i.e. T haltsforallw ∈X∗, and we have w ∈ L if and only if there is a branch accepting w, otherwise all branches reject w; note the asymmetry in the treatment of acceptance and rejection. The complexity class NTIME(f) is the set of all languages being non-deterministically decidable in time f. Inparticular,wehavethecomplexityclassNP:= NTIME(n(cid:55)→nk)oflan- (cid:83)k∈N guagesbeingdecidableinnon-deterministic polynomial time. LetcoNPbe thecomplexityclassoflanguagesL⊆X∗ suchthat(X∗\L)∈NP. Analogously, let coP be the complexity class of languages L ⊆ X∗ such that (X∗ \L) ∈ P. Obviously we have coP=P⊆NP∩coNP. The most outstanding open problem of computational complexity theory is the Conjecture: We have P(cid:54)=NP and NP(cid:54)=coNP as well as P(cid:54)=NP∩coNP. (1.6) Proposition. We have NTIME(f) ⊆ TIME(n (cid:55)→ cf(n)). Thus in particular we have NP⊆EXP. (cid:83)c>1 Proof. See [13, Thm.2.6] or Exercise (8.3). (cid:93) (1.7) Proposition. Given a language L ⊆ X∗, where |X| ≥ 2, then we have L∈NP if and only if there is a relation R⊆X∗×X∗ such that: i) We have L={w ∈X∗;[w,v]∈R for some v ∈X∗}. ii) There is k ∈N such that l(v)≤l(w)k, for all [w,v]∈R. iii) Letting LR :={w v;[w,v]∈R}⊆X∗ X∗, we have LR ∈P. Given w ∈ L, an element v ∈ X∗ such that [w,v] ∈ R is called a polynomial certificate for w. Proof. Let R be as in the assertion. Then L is decided by a non-deterministic Turing machine, which for w ∈X∗ first finds a certificate v ∈X∗ of polynomial length l(v) ≤ l(w)k, hence in polynomial time, and then decides in polynomial time whether [w,v]∈R. Hence we have L∈NP. Conversely, let L∈NP be decided by the non-deterministic Turing machine T, running in polynomial time and having non-determinateness dT. Each finite sequence choices of T can be encoded dT-adically into an element of N0, and hence |X|-adically into an element of X∗. Thus we define R ⊆ X∗ ×X∗ by letting [w,v]∈R if and only if v ∈X∗ is the encoding of a sequence of choices of an accepting computation for w ∈ X∗. Hence by construction of R we have i) and ii). Moreover, for w v it can be checked in linear time whether v indeed encodes an accepting computation for w, hence we also have iii). (cid:93) 4 (1.8) Definition. a) A (one-sided) Monte-Carlo machine for a language L⊆X∗ isanon-deterministicTuringmachineT haltingforallw ∈X∗, having an error bound 0<(cid:15)<1 such that T accepts w ∈L in at least a fraction of (cid:15) of the branches, while T rejects w (cid:54)∈L in all branches. Hence acceptance is correct, but rejection might be incorrect with an error probability 1−(cid:15). Note that we may fix an error bound 0<(cid:15) <1 a priorly: If 0 (cid:15)<(cid:15) , then T is repeated k times, until (1−(cid:15))k ≤(1−(cid:15) ). 0 0 b)ThecomplexityclassRPoflanguagesbeingdecidableinrandomized poly- nomial timeisthesetoflanguagespossessingaMonte-Carlomachinerunning in polynomial time. Hence we have P⊆RP⊆NP. LetcoRPbethecomplexityclassoflanguagesL⊆X∗ suchthat(X∗\L)∈RP. Let ZPP:=RP∩coRP be the complexity class of languages being decidable in randomized polynomial time with zero probability error: For L ∈ ZPP let T(cid:48) and T(cid:48)(cid:48) be Monte-Carlo machines for L and X∗ \L, re- spectively, both with error bound 0<(cid:15)<1. A Las-Vegas machine for L is a non-deterministicTuringmachineT definedasfollows: T runsbothT(cid:48) andT(cid:48)(cid:48), ifT(cid:48) acceptsthenT accepts,ifT(cid:48)(cid:48) acceptsthenT rejects,andotherwiserepeats this. Hence it is not guaranteed that T halts, but if it halts then the answer is correct. Moreover, T halts after at most k repetitions with a probability of at least 1−(1−(cid:15))k. c) The complexity class BPP of languages being decidable in polynomial time with bounded probability error is the set of languages possessing a non- deterministic Turing machine T, called a two-sided Monte-Carlo machine, running in polynomial time halting for all w ∈ X∗, having an error bound 1 <(cid:15)<1 such that T accepts w ∈L in at least a fraction of (cid:15) of the branches, 2 and T rejects w (cid:54)∈L in at least a fraction of (cid:15) of the branches. Note that we may fix an error bound 1 < (cid:15) < 1 a priorly, by running T 2 0 repeatedly, k times say, and accepting an input if and only if it is accepted by a strict majority of the runs. This is seen as follows: The i-th run of T on w ∈ L is considered as a random variable X assuming the values 1 and 0 i with probability (cid:15) and 1−(cid:15), respectively. Letting X := k X be the sum of the independent random variable X , rejection is equiv(cid:80)alie=n1t toi X ≤ k, or i 2 equivalently k (1−X ) = k −X ≥ k; note that E(1−X ) = 1−(cid:15). Let ϑ:=min{1, (cid:80)2(cid:15)−i=11}, hencei 0<ϑ≤1; not2e that 2(cid:15)−1 ≥1 if anid only if (cid:15)≥ 3. 2(1−(cid:15)) 2(1−(cid:15)) 4 Thisyields(1+ϑ)(1−(cid:15))≤ 1,andthusbyChernoff’sbound,seeExercise(8.4), 2 we have P[k−X ≥ k]≤P[k−X ≥(1+ϑ)(1−(cid:15))k]≤e−12ϑ2(1−(cid:15))k. Hence we 2 have P[k−X ≥ k]≤1−(cid:15) whenever k ≥ −2ln(1−(cid:15)0). 2 0 ϑ2(1−(cid:15)) Finally, we have BPP = coBPP and RP∪coRP ⊆ BPP, while it is conjectured that BPP(cid:54)⊆NP holds. (1.9) Definition. a)LetX beanalphabetandletR⊆X∗×X∗ bearelation. The function problem associated to R is, given w ∈ X∗, find a solution 5 v ∈ X∗ such that [w,v] ∈ R, if such a v exists at all, otherwise report failure. A Turing machine T solves the function problem R, if T halts for all w ∈X∗, and outputs a solution, if any solution exists at all, and fails otherwise. Therearestraightforwardnotionsofrunningtimeandcomplexityclasses. More- over, this immediately generalizes to non-deterministic Turing machines, and thereisastraightforwardnotionofMonte-Carlo machinesforfunctionprob- lems. NotethatthelatterareusuallycalledLas-Vegas machinesforfunction problems, which does not seem appropriate, since the straightforward notion of Las-Vegas machines does not make sense. b) The function problems associated to L ∈ NP are the function problems associatedtothepolynomialcertificaterelationsRforL. LetFNPbethecom- plexity class of function problems associated to languages in NP. In particular, function problems in FNP are solvable by non-deterministic Turing machines running in polynomial time. Let FP⊆FNP be the complexity class of function problems being solvable by Turing machines running in polynomial time; it is conjectured that FP(cid:54)=FNP holds. c) A language L⊆X∗ reduces in polynomial time to a language L(cid:48) ⊆X∗, ifthereisafunctionprobleminFP,associatedtoarelationR⊆X∗×X∗,such that for all w ∈ X∗ there is v ∈ X∗ such that [w,v] ∈ R, i. e. failure does not occur, and for all [w,v]∈R we have w ∈L if and only if v ∈L(cid:48). A Turing machine deciding L(cid:48) is called an oracle for L. Languages L and L(cid:48) are called polynomial time equivalent, if L reduces in polynomial time to L(cid:48) and vice versa. Given a complexity class C of languages, L(cid:48) ∈C is called C- complete if each L∈C reduces in polynomial time to L(cid:48). Given a complexity class C of languages, a function problem is called C-hard if each L∈C reduces in polynomial time to that function problem. 2 Integer arithmetic (2.1) Definition. LetD ⊆N suchthat{N,N+1,...}⊆D forsomeN ∈N , 0 0 andletf: D →Rbeaneventually positive function,i.e. wehavef(n)>0 for all n≥N. Let O(f) be the set of eventually positive functions g: D → R such that the sequence [g(n);n ≥ N] ⊆ R is bounded. Let o(f) be the set of eventually f(n) >0 positivefunctionsg: D →Rsuchthatlimn→∞ fg((nn)) =0;henceg ∈O(f). These symbols are also called Landau symbols. Let g: D → R be an eventually positive function. Then the functions g and f are called asymptotically equivalent g ∼ f, if limn→∞ fg((nn)) = 1; hence f ∈O(g) and g ∈O(f). For h: R → R let h(O(f)) := {h ◦ g: D → R;g ∈ O(f)} and h(o(f)) := {h◦g: D → R;g ∈ o(f)}. Moreover, we use a straightforwardly generalized 6 notationforfunctionsinseveralvariables, orforfunctionsdefinedonsubsetsof R unbounded to the right. E.g. wehaveSt√irling’sformulalimn→∞ nnn·!√·e2nπn =1,see[5,Formula96.2√],and thusn!∼(n)n· 2πn. Hencewehaveln(n!)∼n(ln(n)−1)+1·ln(n)+ln( 2π), e 2 and thus ln(n!)∼nln(n). E. g. letting π(n) := |{p ∈ N;p ≤ n,p prime}| ∈ N , for n ∈ N, by the Prime 0 Number Theorem, see [4, Ch.22], we have π(n)∼ n . ln(n) (2.2) Definition. The number of digits to the base 1 (cid:54)= z ∈ N necessary to represent n = b n zi ∈ N, where n ∈ {0,...,z −1}, is given as the (cid:80)i=0 i i bit length b (n) := 1+b = 1+(cid:98)log (n)(cid:99) = 1+(cid:98)ln(n)(cid:99), where (cid:98)·(cid:99) denote z z ln(z) lower Gaussian brackets. Note that for n ∈ Z we only need an additional sign. Hence for the input length of n ∈ Z into a Turing machine we have 1+b (|n|)∈O(ln(n)). z The computational complexity of integer arithmetic is counted in bit opera- tions, i. e. and, or, exclusive or, not and shift on bit strings, hence for the base z = 2. More generally, typical generalized bit operations could be Byte op- erations, word operations and long word operations with respect to the bases z = 28, z = 232 and z = 264, respectively. Using multiple string Turing machines, see Exercise (8.2), it is easily seen that the time needed for these operations indeed is polynomial in the input length 1+b (|n|). z Hencewetreatbitoperationsasoracles. Analgorithmusingintegerarithmetic, whoseinputuptosignisn∈N,iscalledanL -timealgorithm,for0≤α≤1 α,c and c > 0, if it needs L := O(ec(ln(n))α(ln(ln(n)))1−α) bit operations. Hence α,c for α = 0 we have L = O(lnc(n)), thus the algorithm runs in polynomial α,c time with respect to bit operations, and thus is a polynomial time algorithm. Moreover,forα=1wehaveL =O(ecln(n))=O(nc),thusthealgorithmruns α,c inexponentialtimewithrespecttobitoperations,andthusisaexponentialtime algorithm. Finally, for 0 < α < 1 we have cxαln1−α(x) ∈ o(x), see Exercise (8.5), thus the algorithm runs in subexponential time with respect to bit operations,i.e. itneedsO(eh(ln(n)))bitoperations,forsomeeventuallypositive function h(x)∈o(x). (2.3) Algorithm: Ring operations. Theseingeneralareaddition,subtractionandmultiplication,aswellasdivision by units; the latter of course do not play a role for integers. a) Addition is described as follows: Let n ≥ m ∈ N and b := b (n), for some z 1(cid:54)=z ∈N. Hencewehaven= b−1n zi,andwemayassumem= b−1m zj, by letting m :=0 for j ∈{b (m(cid:80))i,=.0..,ib−1}: (cid:80)j=0 j j z 1. δ ←0. 2. for k ∈[0,...,b−1] do s ←n +m +δ k k k 7 if s ≥z then k s ←s −z k k δ ←1 else δ ←0 3. s ←δ b 4. return [s ,...,s ] 0 b Hencewehaven+m= b s zk. Foreachk thisneedsafixednumberofbit (cid:80)k=0 k operations, and hence needs O(b (n)) = O(ln(n)) bit operations. For subtrac- z tion see Exercise (8.7); again this needs O(max{b (n),b (m)}) bit operations. z z b) Multiplication is described as follows: Let n,m ∈ N and b := b (n) n z as well as b := b (m). Hence we have nm = bn−1 bm−1n m zi+j = m z (cid:80)i=0 (cid:80)j=0 i j (cid:80)bkn=+0bm−1((cid:80)ml=imn{abxn{−0,1k,−k}bm+1}nlmk−l)·zk. Using the former formula yields: 1. for k ∈[0,...,b +b −1] do s ←0 n m k 2. for i∈[0,...,b −1] do n δ ←0 for j ∈[0,...,b −1] do m s←s +n m +δ # s=(s mod z)+(cid:98)s(cid:99)·z i+j i j z s ←s mod z i+j δ ←(cid:98)s(cid:99) z s ←δ i+bm 3. return [s0,...,sbn+bm−1] Hencewehavenm= bn+bm−1s zk. Foreachiandjthisneedsafixednumber (cid:80)k=0 k of bit operations, thus needs O(b (n)b (m))=O(ln(n)ln(m)) bit operations. z z (2.4) Algorithm: Karatsuba (1962). Let k ∈N and b=2k, as well as 1(cid:54)=z ∈N and m,n∈N such that m,n<zb, 0 hence we have bz(m),bz(n) ≤ b. Let m = m(cid:48)·z2b +m(cid:48)(cid:48) and n = n(cid:48)·z2b +n(cid:48)(cid:48), where 0≤m(cid:48),m(cid:48)(cid:48),n(cid:48),n(cid:48)(cid:48) <z2b. Then we have m·n=m(cid:48)n(cid:48)zb+(m(cid:48)n(cid:48)(cid:48)+m(cid:48)(cid:48)n(cid:48))· z2b +m(cid:48)(cid:48)n(cid:48)(cid:48), where m(cid:48)n(cid:48)(cid:48)+m(cid:48)(cid:48)n(cid:48) =m(cid:48)n(cid:48)+m(cid:48)(cid:48)n(cid:48)(cid:48)+(m(cid:48)−m(cid:48)(cid:48))(n(cid:48)(cid:48)−n(cid:48)), and in particular |m(cid:48)−m(cid:48)(cid:48)|,|n(cid:48)−n(cid:48)(cid:48)|<z2b. Let K(m,n,b) be defined as follows: 1. if b=1 then return mn 2. if b>1 then r ←K(m(cid:48),n(cid:48), b) 2 s←K(m(cid:48)(cid:48),n(cid:48)(cid:48), b) 2 t←K(|m(cid:48)−m(cid:48)(cid:48)|,|n(cid:48)−n(cid:48)(cid:48)|, b) 2 3. return rzb+(r+s±t)·z2b +s Hence by induction with respect to b ∈ N we have K(m,n,b) = mn. We show that this divide and conquer technique needs O(blog2(3)) bit opera- tions. Since we may assume that n ≥ m and b < b (n) ≤ b, this amounts to 2 z O((2ln(n))log2(3))=O((ln(n))log2(3)) bit operations; note that log2(3)< 115090: Let κ(b) ∈ N be the number of bit operations needed to compute K(·,·,b). 8 Then we have κ(1) = 1, and for b > 1 we have 3 calls of K(·,·, b) as well as 2 additions and shifts, thus κ(b) = 3κ(b)+γb, for some γ > 0. By induction we 2 get κ(b) = 3k ·κ( b )+γb· k−1(3)i = 3k +γ2k · (23)k−1 = 3k +2γ ·(3k − 2k (cid:80)i=0 2 32−1 2k) = (2γ + 1) · 3k − γ2k+1. Hence we have κ(b) ∈ O(3k) = O(3log2(b)) = O((2log2(3))log2(b))=O(blog2(3)). (cid:93) (2.5) Algorithm: Quotient and remainder. Letm≥n∈N,hencethereareuniqueq,r ∈N suchthatr <nandm=qn+r. 0 Note that in particular to compute in the ring Z/(cid:104)n(cid:105) we need the computation of remainders. Let b(cid:48) := b (m) and b(cid:48)(cid:48) := b (n), for some 1 (cid:54)= z ∈ N. Replacing [m,n] by a z z suitable multiple [km,kn], for some 1 ≤ k < z, we may assume that nb(cid:48)(cid:48)−1 ≥ (cid:98)z(cid:99). Moreover, after replacing n by nzl for some l ∈ N , i. e. after a suitable 2 0 shift, we may assume that we have b (n) = b and b (m) ∈ {b,b+1}, where z z b ∈ {b(cid:48),b(cid:48)+1}. To compute q, we compute q(cid:48) := min{(cid:98)mbz+mb−1(cid:99),z−1}. We show that q(cid:48)−2≤q ≤q(cid:48): nb−1 Wehavenb−1q(cid:48) ≥mbz+mb−1−(nb−1−1). Hencem−q(cid:48)n≤m−q(cid:48)nb−1zb−1 ≤ m − (mbz + mb−1)zb−1 + (nb−1 − 1)zb−1 = (nb−1 − 1)zb−1 + (cid:80)bj−=20mjzj < nb−1zb−1 ≤n. As we have q ≤z−1 anyway, we conclude q ≤q(cid:48). Moreover, we haveq(cid:48) ≤ m < m andq =(cid:98)m(cid:99)> m−1. Assumetothecontrarythat nb−1zb−1 n−zb−1 n n 3≤q(cid:48)−q < n−mzb−1−(mn −1)= n(mn−·zzb−b−11)+1. Thuswehave mn >2·(nb−1−1), and hence z−4 ≥ q(cid:48)−3 ≥ q = (cid:98)mn(cid:99) ≥ 2·(nb−1−1) ≥ z−3, a contradiction. Thus q(cid:48)−2≤q. (cid:93) Computing[km,kn]needsO(b(cid:48))bitoperations,theshiftsneedO(b(cid:48)(cid:48)(b(cid:48)−b(cid:48)(cid:48)))bit operations. Tocomputethequotientqatmost3trialsarenecessary,asb (q(cid:48))= z 1thetrialmultiplicationtocomputeq(cid:48)nneedsO(b)=O(b(cid:48))bitoperations,and the addition r := m−qn as well needs O(b(cid:48)) bit operations. This amounts to O(max{b(cid:48),b(cid:48)(cid:48)(b(cid:48)−b(cid:48)(cid:48))}) bit operations, where b(cid:48)(cid:48)(b(cid:48)−b(cid:48)(cid:48))≥b(cid:48) whenever b(cid:48) >b(cid:48)(cid:48); as m≥n this hence needs O(ln(m)ln(n))⊆O(ln2(m)) bit operations. (2.6) Algorithm: Binary modular exponentiation. Let e,n∈N and m∈{0,...,n−1}. 1. r ←1 2. while e>0 do if 1≡emod2 then r ←rmmodn e←(cid:98)e(cid:99). 2 m←m2 modn. 3. return r. Using the binary representation of e ∈ N shows that r ∈ {0,...,n−1} such that r ≡ me modn. Moreover, as b (e) ∈ O(ln(e)) and both multiplication 2 and computing remainders need O(ln2(n)) bit operations, we need O(ln(e) · 9 ln2(n)) bit operations; note that the classical exponentiation algorithm needs O(e·ln2(n)) bit operations, and hence needs exponential time. (2.7) Algorithm: Extended Euclidean algorithm. Let m,n∈N. 1. r ←m, s ←1, t ←0 0 0 0 2. r ←n, s ←0, t ←1 1 1 1 3. i←1 4. while r (cid:54)=0 do i ri+1 ←ri−1 modri q ←(cid:98)ri−1(cid:99) # quotient and remainder sii+1 ←rsii−1−qisi ti+1 ←ti−1−qiti i←i+1 5. return [ri−1,si−1,ti−1] Wehaver =s m+t nandr =s m+t n,andbyinductiononi≥1wehave 0 0 0 1 1 1 ri+1 =ri−1−qiri =(si−1m+ti−1n)−qi·(sim+tin)=si+1m+ti+1n. Aswehave ri < ri−1 for all i ≥ 1, the algorithm halts, after step i := l+1 say, returning [r ,s ,t ]=:[d,s,t]. ThenumberlofstepsneededisdiscussedinExercise(8.10). l l l Thus we have d = sm+tn, and hence gcd(m,n) | d. Conversely, running the algorithm reversely shows that d | r for all i ≥ 0, hence d | m,n and thus i d | gcd(m,n). Thus [d,s,t] ⊆ Z such that 0 < d = gcd(m,n) = sm+tn; the elements s,t ∈ Z are called Bezout coefficients. Note that the computation ofthecoefficientss andt canbeleftout,theremainingalgorithmiscalledthe i i Euclidean algorithm. Let 1 (cid:54)= z ∈ N. For i ∈ {1,...,l} we need O(b (r )b (q )) bit operations z i z i to compute [q ,r ]. As b (q ) = 1 + (cid:98)log (q )(cid:99), we have O( l b (q )) = i i z i z i (cid:80)i=1 z i O(b ( l q )) ⊆ O(b (r )). Hence computing the quotients and remainders z (cid:81)i=1 i z 0 needs O( l b (r )b (q )) ⊆ O(b (r )· l b (q )) ⊆ O(b (r )b (r )) bit op- (cid:80)i=1 z i z i z 1 (cid:80)i=1 z i z 1 z 0 erations. TocomputethelinearcombinationneedsO( l b (q )b (s ))bitop- erations, where in turn bz(si)∈O(bz(si−1)+bz(qi−1)(cid:80)), hi=e1ncze wie hzavie bz(si)∈ O( i−1b (q )), yielding O( l i−1b (q )b (q )) bit operations. As above (cid:80)j=1 z j (cid:80)i=1(cid:80)j=1 z i z j we from this obtain O( l−1 l b (q )b (q )) ⊆ O( l−1 b (q )b (r )) ⊆ (cid:80)j=1(cid:80)i=j+1 z j z i (cid:80)j=1 z j z j O(b (r ) · l−1 b (q )) ⊆ O(b (r )b (r )) bit operations. Thus this needs O(bz(r1)b ((cid:80)r j)=)1=zOj(b (m)b (nz)) 1bitzop0erations; if m ≥ n this hence needs z 1 z 0 z z O(ln2(m)) bit operations. (2.8) Remark: Polynomial arithmetic. LetRbeacommutativeringandletR[X]bethepolynomialringoverRinthe indeterminateX. For0(cid:54)=f = d f Xi ∈R[X], wheref ∈R andf (cid:54)=0, let (cid:80)i=0 i i d deg(f) := d denote its degree. The computational complexity of polynomial arithmeticisusuallymeasuredinringoperationsinR, relatedtothedegreesof the polynomials in R[X] involved. Hence in general this is not directly related

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.