Кіріспе

Математикалық алгоритм. Сынақ бөлу – бүтін сандарды жіктеу алгоритмдерінің ең еңбектеп атқарылатыны, бірақ түсінуге ең оңайы. Сынақ бөлудің негізгі идеясы – жіктеуге жататын n бүтін санын n-нің квадрат түбірінен кіші әрбір санға бөлінетінін тексеру. Мысалы, 12 саны үшін оны бөлетін сандар – 1, 2, 3, 4, 6, 12. Осы тізімдегі жай сандардың ең жоғары дәрежелерін таңдасақ, Сынақ бөлуді алғаш рет Фибоначчи өзінің "Liber Abaci" (1202) кітабында сипаттаған.

Жылдамдық

Ең нашар жағдайда, сынаққа бөлу – еңбекке толы алгоритм. 2ⁿ цифрлы a саны үшін, егер ол 2-ден басталып, a-ның квадрат түбіріне дейін ғана жұмыс істесе, алгоритмге сынақ бөлінісі қажет болады, мұнда – жай сандарды санау функциясы, яғни x-тен кіші жай сандардың саны. Бұл кандидат-факторлар ретінде жай сандарды алу үшін жайлылықты тексеруге кеткен қосымша уақытты ескермейді. Пайдалы кесте үлкен болуы қажет емес: P(3512) = 32749, он алты биттік таңбалы бүтін санға сыятын соңғы жай сан, ал P(6542) = 65521 – таңбасыз он алты биттік бүтін сандар үшін. Бұл 655372 = 4,295,098,369 дейінгі сандардың жайлылығын тексеру үшін жеткілікті. Мұндай кесте жасау (әдетте Эратоспенің елегі арқылы) тек көптеген сандарды тексеру қажет болғанда ғана тиімді. Егер жайлылықты тексермейтін нұсқа қолданылса, бірақ жай ғана 2ⁿ цифрлы a санын, жай сан болсын болмасын, квадрат түбірінен кіші әр тақ санға бөлу жүргізілсе, онда шамамен:

Екі жағдайда да, қажетті уақыт санының цифрларымен бірге экспоненциалды түрде өседі. Дегенмен, бұл өте қанағаттанарлық әдіс, себебі тіпті ең жақсы белгілі алгоритмдердің де уақыт өсуі экспоненциалды. Белгілі бір ұзындығы бар бүтін сандардың арасынан кездейсоқ таңдалған a үшін, 2-нің a-ның көбейткіші болу ықтималдығы 50%, ал 3-тің – 33% және т.б. Барлық оң бүтін сандардың 88%-ы 100-ден кіші көбейткішке ие, ал 92%-ы – 1000-нан кіші көбейткішке ие. Сондықтан, кездейсоқ үлкен a санымен кездескенде, оны кіші жай сандарға бөлінетінін тексеруге тұрарлық, себебі 2 негізіндегі ,

Дегенмен, кіші жай сандарда көбейткіштері жоқ көптеген цифрлы сандарды сынаққа бөлу арқылы факторлауға бірнеше күн немесе айлар қажет болуы мүмкін. Мұндай жағдайларда, басқа әдістер қолданылады, мысалы, квадраттық елеу және жалпы сандық өріс елегі (GNFS). Бұл әдістердің де уақыт өсуі суперполиномиалды болғандықтан, n цифрының практикалық шегіне өте жылдам жетеді. Осы себепті, ашық кілтті криптографияда a-ның мәндері ұқсас өлшемдегі үлкен жай көбейткіштеріне ие болу үшін таңдалады, осылайша оларды кез келген қол жетімді компьютерлік жүйеде немесе суперкомпьютерлер мен компьютерлік кластерлер сияқты компьютерлік кластерде пайдалы уақыт ішінде ешқандай жалпыға белгілі әдіспен факторлау мүмкін болмайды. Криптографиялық деңгейдегі ең үлкен факторланған сан – RSA 250, 250 цифрлы сан, ол GNFS және бірнеше суперкомпьютерлердің ресурстарын пайдалана отырып факторланды. Оның жұмыс істеу уақыты 2700 ядролық жылды құрады.