Գծային համընկման գեներատոր

Գծային համընկման գեներատոր - ալգորիթմներից մեկը՝ կեղծ պատահական թվերի գեներատորը, օգտագործվում է սովորական դեպքերում։


== Նկարագրություն ==
Գծային համընկման գեներատորը հիմնվում է անդամների հաշվարկման գծային հետևողականությամբ որոշ բնական թվի m մոդուլով, հետևյալ ֆորմուլայի տեսքով։

  
    
      
        
          X
          
            k
            +
            1
          
        
        =
        (
        a
        
          X
          
            k
          
        
        +
        c
        )
         
         
        
          mod
          
             
          
        
         
        m
        ,
      
    
    {\displaystyle X_{k+1}=(aX_{k}+c)~~{\bmod {~}}~m,}
  որտեղ a և c-ն որոշ ամբողջ թվերի գործակիցներ են։ Ստացված հետևողականությունը կախված է մեկնարկային թվի ընտրությունից X0 և նրա տարբեր նշանակությունների դեպքում ստացվում է պատահական թվերի տարբեր արդյունք։ Միաժամանակ այս արդյունքների շատ հատկություններ որոշվում են ֆորմուլայի գործակիցների ընտրությամբ և կախված չեն մեկնարկային թվերի ընտրությունից։


== Հատկություն ==
Թվերի հետևողականությունը, որը ստացվում է գծային համընկման մեթոդով, պարբերաբար չգերազանցվող m է։ Հատվածի երկարությունը ճիշտ հավասար է m միայն այն դեպքում, երբ։

Ամենամեծ ընդհանուր բաժանարար, այսինքն՝c, m = 1 փոխադարձ հասարակ թվեր;
a-1 բոլոր հասարակ թվի բաժանարար ;Ստացված արդյունքի պատահական թվերի վիճակագրական հատկությունները ամբողջովին որոշվում են a և c գործակիցների ընտրությամբ։ Այս հաստատունների համար դուրս են գրված պայմաններ, որոնք երաշխավորում են ստացված պատահական թվերի բավարար որակ։


== Հաճախ օգտագործվող պարամետրեր ==
Իրացման ժամանակ ճիշտ է ընտրել 
  
    
      
        m
        =
        
          2
          
            e
          
        
      
    
    {\displaystyle m=2^{e}}
  , որտեղ e - որտեղ e բիթերի քանակը, քանի որ դա թույլ է տալիս ազատվել համեմատաբար դանդաղ հետազոտություններից։
Փոքր երկրորդական կարգի գեներացված պատահական թվերը ցուցադրում են վարմունք, որը շատ հեռու է պատահականից, դրա համար խորհուրդ է տրվում օգտագործել միայն բարձր կարգեր։ Բացի դրանից այս գեներատորի օգտագործման ժամանակ կետերի ընտրման համար d-տարածությունում, կետերն ընկնում են ոչ ավել գիպերհարթություններում, 
  
    
      
        
          m
          
            1
            
              /
            
            d
          
        
      
    
    {\displaystyle m^{1/d}}
  , ինչը սահմանափակում է m1 / d գեներատորի կիրառումը Մոնթե-Կառլի մեթոդով։
Աղյուսակում բերված են առավել հաճախ օգտագործվող գծային համընկման գեներատորների պարամետրերը, հատկապես տարբեր
կազմված միօրինակ գրադարաններում։


== Ծածկագրերի վերլուծություն ==
Գծային մեթոդի առավելությունն այն է, որ գործոնը և մոդուլը համապատասխան ձևով ընտրվում են, ապա ստեղծված թվերի արդյունքը կլինի վիճակագրապես անտարբերելի պատահական արդյունքների բազմաթիվ էլեմենտներից։ { 0, 1, 2, …, m-1 }. Սակայն բոլոր արդյունքային այն էլեմենտները միանշանակ որոշվում են 4 պարամետրերով՝ X_0, a, c, m.
Եթե ծածկագրերի վերլուծությունը գիտի հայտնի պարամետրերով գծային համընկման մեթոդի օգտագործումը, ապա հայտնի է դառնում թվերի ամբողջ արդյունքը։ Միաժամանակ, անգամ եթե ծածկագրությունը գիտի միայն գծային համընկամն մեթոդի օգտագործումը, ապա արդյունքի փոքր հատվածի տեղեկատվությունը բավական է մեթոդի պարամետրերի և արդյունքների բոլոր հաջորդող էլեմենտների հայտնաբերումը։ Մասնավորապես, եթե ծածկագրերի վերլուծությանը հայտնի են նշանակությունները 
  
    
      
        
          
            X
            
              0
            
          
        
        ,
        
          
            X
            
              1
            
          
        
        ,
        
          
            X
            
              2
            
          
        
        ,
        
          
            X
            
              3
            
          
        
      
    
    {\displaystyle {X_{0}},{X_{1}},{X_{2}},{X_{3}}}
  , ապա նրանք բավարարում են հավասարության համակարգին։

  
    
      
        
          
            {
            
              
                
                  
                    X
                    
                      1
                    
                  
                  =
                  (
                  a
                  ⋅
                  
                    X
                    
                      0
                    
                  
                  +
                  c
                  )
                   
                  
                    mod
                    
                       
                    
                  
                  m
                
              
              
                
                  
                    X
                    
                      2
                    
                  
                  =
                  (
                  a
                  ⋅
                  
                    X
                    
                      1
                    
                  
                  +
                  c
                  )
                   
                  
                    mod
                    
                       
                    
                  
                  m
                
              
              
                
                  
                    X
                    
                      3
                    
                  
                  =
                  (
                  a
                  ⋅
                  
                    X
                    
                      2
                    
                  
                  +
                  c
                  )
                   
                  
                    mod
                    
                       
                    
                  
                  m
                
              
            
            
          
        
      
    
    {\displaystyle {\begin{cases}X_{1}=(a\cdot X_{0}+c)~{\bmod {~}}m\\X_{2}=(a\cdot X_{1}+c)~{\bmod {~}}m\\X_{3}=(a\cdot X_{2}+c)~{\bmod {~}}m\end{cases}}}
  որից կարելի է ստանալ а, с և m.
Դրա համար, թեև գծային համընկման մեթոդը տալիս է վիճակագրապես լավ թվերի արդյունք, նա չի համարվում ծածկագրության դիմացկուն։


== Նշումներ ==