    16.   

            N      
      N       
      ,   <?. N.   
         . 

    250 . 3.           

          ,   
      .    
,    ,    
   .    8   /, 
 ,    28 = 256  ,   
  0  255.  ,      0 .. 255. 
     ,    ,   , 
     .      
   ,  ,  1  512.      
  ,           
   ,  . 
              
 ,   ( , cache  )    
  .           
  , ; . 
    ,        , 
       ,   
 :       .   
   ,        
    . [, ,  
 :  .      
  ,       
   . 
                     
  ,            ,       
              .   
        
   .   ,          
      .     
          
.  :   ? ,          
   ,   :       ,         
           (       
0   1),   ,               
      (  ,  virtual  )   
   (        AQ N sa.l), ,   . 

    /16.   251 

           .    
       ,   
   . 
    ,  .       
       ,  
         
 ,    ,     .  
       ,    ,   
. , ,   , 
,.,., N1-   , (      
,  ,  ,    . 
 ,       
  . 
                 : 
    )      ,     
 ( =).      ( 
  )        
  V(B  )     ; 
    )   (,   , -    
, pool   )    , . .  
,       (,    
, ) .      , 
 <    ,     ,    
      .      
       ,     ( 
  )   . 
            
 (  )    /,   . 
            
 ,   ,       
            
   *   : 
    1.   
    2.    < : 1>     : 
    3.  < : >;     < : 1} 
    4.   

    252	. 3.           

    .         . 
           
 ,   ,      
     . 
    -.      () 
   (   )    (=)  
  0  N  1          
0    1         0  N-1. 
   :       
   ,      
 .      0 . . N  1 
- h(i)=imodn   0 ,.   1.      
1      ,       h(i)i   
  ,         . 
 ,        (     
   ).      ,     
         
           ,    
           , 
 ,   .  ,     
         . 
, ,      ,       
  .      .   
1,5  2 , 

       . : 
    1.   ,     2.    ( : 1)      :  
    3.  ( : )     ( : i) 
    4.   
    4. : 
    .      N = 65636 .      .= 2048 
    : 
    . 
    

    16    ' 263 
    

    _ = 0 ..    1 : 
       :   (-)  : 
           :   (-) 
     :   () 
      
       .         : . : 
    i	.  
    ;	  .  
    .	.  
    .	 V _  
    .	,     (k) :=  (k) 
    .	.       (k) := k 
    .	  
     	
        (: i: ):  .         : . : 
    .	k := i mod n 
    .	    (k) 
    .	.     Ksm (k) :  (i) 
    .	,         (k) : 1 
    .	  
    .	 :-  (k) 
     	; 
      (::)  .         : . : 
    i   TO 
    'SSgWWKCOM 
    ':.)<      ( 
    ,   k := i mod n .    (k) := e .      (k) .     (i) 
:= e   
       .        ; 


    254 . 3.        


    , : 
    .   .   .     .   .   . 
  
  
      

    ,   -  ,     
     ;(  )  
   ,        ,  
       . , ,  
      ,     
,      ,      
   $   . 
     .    ).        , 
          , 
           
.  ,     ,   
 ,      
    ,    ; 
    1.   
    2.   < 1 1 1  )  < :  : ) 
    3.  < :  ; )   < : i i  ) 
    4.   
          . 16.1.  
     .   
 -       !  
  ,    ,     , 
         # (    ,  
, ,   .)      , . ,   
       , 
        : 
    ,      1,   
         2,    ( : i)     \ E 
    > .. 3.  (uxiesE)     () 
    ".       (:1)   (!) 
        {: ) .      4.   
    **	t 
    .	: 
    .	N                   = 2048 
    .	                   =   128 
    	 =  512 |  
     
    .	: 
    .	          =0 .. N  1 |    
    .	  = 0 ..   1 
    ,	 =    =   (0 ..    
    

    ' 16.   253 

      
     
     
     

    .   16.1 

     .     (  
  O..N  1)         
^?____, KOTOpjgu^      , 
  .        
     .       
         , . 
      ,     
 ,     ,  

    256	1'. 3.         -   

            (,  16.1).   
       ,     , 
     , ,       
 , -   /    /  
         (   
,     )      . 
(        .)    
          
    -      
     ,    
 ,          , , 
    .  : 
    .     
    .   :            
    .      
    * 
      | ----_-_-   .       
  : . : 


    15.   

    .    .  
    .   .  
    .     .  
      
        (: i: ):  
    .         : 
    . : 
    '. "  (ex:i>   (:> .    :=  (k)   
             
 1-      (  ?   )  
    k    . 
      <::>     <:1> 0         : i: 
  , ; 
    .     (: 1}   {: k) .   () :=    
       <: i)   (: k) 
    ,         :  I:   
    . : k:    
    .	k :=  .    (ex:i) 
    .	 k =   |    
    .	.       ( : k) 
    .	.     .  (ex:i)  (: (k)) 
    .	.      .  (ex:k,i)                   * 
    .	  
      
      .       
     ,    i-  
 ,  ,  1-      
    (, .        (k, i)  
 i). 
        (:) 
    .         : 
    . : k:  	;   .V;' 
    .    .  (:1<,1) 
    .    IT^  [    
    .    .      . ( :  (k))   (ex:i) 
    .      
     iipoi  
     ,     .    
 -  (k, i)  ,   k  i   
  ,     (k, ),  k  
   (     ).  ,  
 (     ),   
          
  , 
       .        : . : 
       | . .     


     9    . . , . .  
    258 . 3.           


    .	    
    .	        (:1) 
    .	  
    ,	 .  
    .	.  
    ,	 .  
      
      
    | =, = =, = = = = = = = -_-=1 = =,=, = =, =  = = = --=, ==
       , . .      
     , ,   
          
 -   . ,     
 ,     .      
    ,   ,    
     ,    , 
. .  -  .      
         
   :  / (  )        
   ,       
     : 
      (: : )     (:!) 
    .        : i:   
    . : 
    .     (: 1)   (: k) .   () :==  .    
 (k) :=    
       (ix:i)   (:1) 
    .        :  i:   
    . : k:    
    .	k :=  .    (: i) 
    .	 k =   |    
    .	.       ( : k) 
    .	.     ,   (: i)  (:  (k)) 
    .	.     .  (flx:k,i) 
    .	.      (k) :=  
           
        ( i k) 
    .         i 
    . : k:^   


    ,    259 


    .    .  (ebixlk,i) 
    .    1^    (k)  
    ,    .     . (|(^)   (BXI!) 
    ,      
      
    * 
      .     
 >,      : 
       . : 
    1.   
    2.   ( ! k!   , 1:  ) .     3.  
 (: k i   , 4 i  ) .     4.     ( i i 
I )  i    
    .   
    : 
    N  
    = 2048    128 
    ! 
               0 ,, N  i  ->  0      
      nap (k, I)     -   k 
   ,      ,  
    (k, i)  -  
      ;   { ), 
         (k)  1,   (k, 1)    
,  ,   {k, i)   k   .  
 ,  -       
  k,   ,     
 v k => ,   k = 1, k = 2, ,.,, k =  1,    

    260 . 3,            

    k = , k = 1  . . ,     - (k, i) 
k       (    
  ),          
    ,      .  
        
       0..   1   . 
        
      :  . 
       ,             
  : 
    . : 
    .   :    (  ) 
    .    :    
      |_________ _________ 
       ==    : = 1  
  (:k:  , 1:) .  . : 
    18.   ?31 
    .   k := (  -f- l)mod n 
    .    i  :=   (k) 
    .     (k) :=  
    .   41=   ;= k 
      
       <: k:   , 1: ) .        : 
  (k) =  . : 
    .     (k) := 1   
         (: i:  ):    
    .    : 
    . :  =  |   i    
    .           ()= i 
    .	 V k &       (k) =?& L 
    ,	.  
    .	.        
    .     .     := k   
         ]=, = = = , 
       


    -  ,   *  
  ( ,   )   
     *     ,   
     (  .   
)    ,    -1 
     ,     
,    , . , _1>  
  ,       D .   
     =  |  -    
    _ :    (0  ..  1) . :    
 (  ) 
          I    
 :   , *   ,   
,  *   - h(i)=imodp. 
        @    
 .  -   
      (..   ) .  -(h),  h--*  
    .'..    
      ll       (vicmon     -,  
             h    ; 
       
    i (.11: 
    ,  1.   
    ,  2.   ( : k :   , J:  ) 
    ,  3.   ( : k i   , 1:  ) 
    ,  4.     ( : i:  ) :    
      5.   
    : 
    N  
     = 2048 = 128 =  |  - 


    262 , 3,        


    : 
         '    
     
    . 
    N-1 1 
    .    : 
      :    ( ' ); .         
S    .     _ :    (0' .,   1) 
    @, !    ( )1 
      |-    -  --- 
     -  ==. ^'  s=*  1:  
-  : k:.  ,, 1:;-), .         : . : 
    ,	k := (41=   + 1) mod n 
    .	i :=   (k) 
    .	  (k): := ; 
    ,	   := k 
      , ,  ,     (i _ 
),  *  - * : 
    .  t *f=   
    !, .     (@npeA(k), @(^) 
     ,     '    ,   
-    1 , >   -: 
    . .    h := i mod p . .     
    ..    .    (k) = k	^  _ ('h)):;  
    . .    ,    _ (ih)'-"o;k =>_ (1:,=  (k) 
    . .      
    .   
      
       (: k:   , i!  ) 
    .         :   (k) =  
    . ; 
      (k) := I 


    16. -  	?6i 

       ,              .  - 
,     (. ,  - (h)  ),, . 
   . .,     ? . h := i mod 
p	 . kl: *='_!('1) 
    .  kl = 	' . .    |   _ h    . . 
      <k,k) . .    _( h) := k . .    |    
  . .      (@(), k   > . .      (k,            
     kl)                                          

         . , ,    
cifipmm'iimi        ,      , 
   ,   -     
  ,       .  
,   -   ,    
,        ,    
        - -    
  '.  -rraiiicM  
    . . _ (h) := k .     
      .   .(*-:-1: }:   
    -----       .: 
    : *  |> (  I -     ()=i 
      -      |in*    
         .    
   k    ! , h : - -  mod p , 1>        
_ (h)      >            
 0;ini..i     ,       (  *  
I    ),     : ,  It /^  (      
  - . ,    kl := k 
    , .        (k)^!  @ (k)=^=k2 , .    ,      


    264	. 3.        


          k :=  (k) . .      
    . .       (k)=?M  k i    .   
    .     : k =  |  i-ro     .	   (k) 
*= i ,  := k   
         ,  : 
      (exika.kb) = ) := kb', 
    @  (kb) := ka 
       ==      | ^,-, = 
__^ = =. = = = = = = = =, = = =,=,=, = . = =.--===.= =. 

      -    -   
,   ,   ,  ,  -  
(, ,        , 
       ).    - 
 ,    ,    2,  
    ,  ,     ( 
   )     . 
    .   ,  ,   
      .    
           
 , ,   (, 256) 
 ,        
,         0  N  
1        0  1,   - N.  
 , ,     N ,   
           .   
,         ,     
      , 
    ., 

       

             
      ,   . 

    17.   	265 

    1.          
    . 
    2.        Case  
 . 
    3.        . 
        . 
    4.     ,     
 ,     ,    ==,   (1..)  
     . 
