The average behavior of nine algorithms derived from the Euclidean Algorithm is analysed. Some of them are useful in computing the Jacobi symbol. It is shown that these algorithms form two classes: the fast and the slow algorithms (Q(ln N)) versus Q(ln^{2} N)). The author suggests a general method, in which the algorithm and the set of its data are viewed as a dynamical system. The Ruelle operator and functional analysis are key tools. This unified approach gives not only the previously known results for classical Euclidean algorithms but also new results about the binary GCD and Jacobi symbol algorithms. In particular, conjectures due to Brent, Bach and Shallit are solved. The average behavior is linked to the entropy of the dynamical system, thus new universal constants (explicit for classical cases, computed numerically in the other cases) are exhibited.
( 

)= 

J(u,v):= 

( 

) 

for  v= 

v 

with odd primes v_{i}. 
Quadratic reciprocity law:  J(u,v)  =(1)^{(u1)(v1)/4}J(v,u) for u,v odd positive integers,  
Modulo law:  J(v,u)  =J(vbu,u),  
Multiplicativity law:  J(vw,u)  =J(v,u)J(w,u),  
Special values:  J(2,v) 

Classical with positive remainders  
v=cu+r, 0£ r<u  13/75=1/5+1/1+1/3+1/3+0 
Subtractive classical  
v=u+(vu)  13/75=1/1+1+1+1+1+1/1+1/1+1+1+1/1+1+1 
Classical with negative remainders  
v=cur  
0£ r <u  13/75=1/61/51/21/2+0 
Classical with centred remainders  
v=cu+e r  
c³ 2, e=±1, (c,e)¹ (2,1)  
0£ r £ u/2  13/75=1/61/4+1/3 
Even CF  
v=cu+e s,  
c even, e=± 1 s odd, 0<s<u  13/75=1/61/4+1/41 
Odd CF  
v=cu+e 2^{k} s,  
c odd, e=± 1,  
s odd, k³ 1, 0£ 2^{k}s <u  13/75=1/5+2/32/5+0 
Ordinary CF  
v=cu+2^{k}s, s=0 or s odd,  
k³ 0,  
0£ 2^{k}s<u  13/75=1/5+2/2+1/1+2/3+0 
Centred CF  
v=cu+e2^{k}s,  
s=0 or s odd, k³ 0,  
0£ 2^{k} s<u/2  13/75=1/61/4+1/3+0 
Binary GCD  
v=au+2^{k}r,  
a odd,  
a<2^{k}, r£ u  13/75=1/1+2+2^{2}/1+2^{2}/1+2^{3} 
S(s,w):= 



w^{l} 
S(s,1)=: 


and 

S(s,w)_{w=1}=: 


S_{N}= 

= 

. 

a_{n}= 

N 

ln 

N (1+o(N)). 
A_{s}(f)= 


. 
positive remainders  12ln 2/p^{2}ln N  .842 ln N  Heilbron & Dixon 70  
subtractive  6/p^{2}(ln N)^{2}  .607(ln N)^{2}  Knuth & Yao 75  
negative remainders  3/p^{2} (ln N)^{2}  .303(ln N)^{2}  Vardi 92  
centred remainders  12ln f/p^{2}ln N  .585ln N  Rieger 80  
even  2/p^{2}(ln N)^{2}  .202(ln N)^{2}  Vallée & Lemée 98  
odd  A_{O}ln N  .435 ln N  Vallée & Lemée 98  
ordinary  A_{U}ln N  .535 ln N  Vallée & Lemée 98  
centred  A_{C}ln N  .430 ln N  Vallée & Lemée 98  
binary GCD  A_{B}ln N  .555 ln N  Vallée 98  
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.