Сызықты конгруэнттік әдіс.

Бү гінгі кү ні кездейсоқ сандарды ұ қ састыру жө ніндегі ә дістер 1948 жылы Д.Х.Лемер ұ сынғ ан дербес жағ дайлар болып есептелінеді.

Ә дістің мә ні: тө рт «сиқ ырлы сан» таң дап алынады.

– алғ ашқ ы мә н,

а - кө бейткіш,

с - ө сімше,

m – модуль,

сонда ізделінді кездейсоқ сандардың тізбегі тө мендегі қ атынастан алынады:

(1)

басқ аша айтқ анда ә рбір кездейсоқ сан санын m - ге бө лгендегі қ алдық (Mod операциясы «қ алдық ты анық тау» деген сө зден шығ ады, «modulo» - аударғ анда «қ алдық» деген сө з).

Мысалы: болсын, сонда тізбектің тү рі мынадай болады:

7, 6, 9, 0, 7, 6, 9, 0,...

Кө ріп отырғ анымыздай «cиқ ырлы сандарды» таң дап алғ анда тізбек қ айталанып қ алды, оның периоды 4 - ке тең.

Бұ л мысалдан «cиқ ырлы сандарды» кез-келген тү рде алуғ а болмайтынын кө реміз. Кө птеген зерттеулер жү ргізілді жә не «cиқ ырлы сандарды» қ алай таң дап алу жө ніндегі кө птеген теориялар дә лелденді.

с = 0 болғ андағ ы кездейсоқ сандарды таң дап алу ә дісі «мультипликативті конгруэнттік» ә діс деп аталады. с = 0 болғ анда тізбекті табу тезірек болады, бірақ бұ л жерде тізбектің периодының ұ зындығ ы қ ысқ арады.

Ең алдымен Лемер ә дісінде с = 0 деп есептелінді. с ≠ 0 болғ анда ұ зынырақ тізбекті алу идеясы Томпсонғ а жә не одан бө лек Ротенбергке жатады.

m модульді таң дау. Ұ зын тізбекті алу ү шін жә не есептеу жылдамдығ ын арттыру ү шін m - ді машиналық сө здің ұ зындығ ына сә йкес таң дау керек. 32 – разрядты машиналық сө з ү шін m = 231=2147483648 деп алу керек (сө здің сол жақ нө лдік биті санның белгісіне енгізілген).

Сонда 32 разрядты машиналық сө зде орналасатын бү тін сан

Сонда болады.

Кө бейткіштің мә ні тізбектердің периодының ұ зындығ ына ә сер етеді. Осы мә селе бойынша да кө птеген зерттеулер жү ргізілген.

Сызық тық конгруэнттік тізбектер кездейсоқ сандар шығ атын кө здің бірі ғ ана емес, мысал ү шін оны

квадраттық конгруэнттік ә діске жалпылауғ а болады.

Р.Ковью ұ сынғ ан квадраттық ә діс белгілі, ол

Фибоначчи тізбегін алуғ а болатын

ә діс те белгілі.

Грин ұ сынғ ан кездейсоқ сандарды алу ә дісі белгілі, ол

,

мұ нда, k ү лкен сан. Осы сияқ ты аддитивтік ә дістер деп аталатын кө бейту жә не бө лу операцияларын қ ажет етпейтін ә дістер, т.с.с. ә дістер де белгілі.