Түпнұсқа болу (немесе болмау) қасиетін түпнұсқалық деп атайды. Кез келген n санының түпнұсқалығын қарапайым, бірақ баяу растау сынақ бөлінісі деп аталады. Сынақты бөлу - бұл n санының 2 мен оның арасындағы барлық бүтін сандардың коэффициенті бар ма, жоқ па деген сынақтан өту. Алгоритмдер үлкен сандардың түпнұсқалығын тексеру үшін жасалған, олар сынақ бөлуден әлдеқайда тиімді. Бұл алгоритмдерде жылдам, бірақ қателік мүмкіндігі аз Миллер-Рабин тұқым қуалау тесті бар, ал AKS тұқым қуалау тестісі бар, ол полиномиалды уақытта әрқашан дұрыс жауап береді, бірақ іс жүзінде өте баяу. Әсіресе, арнайы формадағы сандар үшін жылдам әдістер, мысалы, Мерсен сандары бар. 2016 жылғы қаңтарда ((жаңарту) ең үлкен белгілі алғашқы саны 22.338.618 ондық санға ие.
Үлкен сандардың түпнұсқалығын дұрыс тексеруге арналған алгоритмнің аты қандай?
Миллер-Рабин тұқым қуалау тесті