Кіріспе
Математикада күшті жай сан – нақты бір ерекше қасиеттері бар жай сан. Криптография және сандар теориясында күшті жай сандардың анықтамалары әртүрлі.
Криптографиядағы анықтамасы
Криптографияда p жай саны келесі шарттар орындалса "күшті" деп аталады. p криптографияда пайдалы болу үшін жеткілікті үлкен болуы керек; әдетте, бұл криптоанализге p-нің өнімдерін басқа күшті жай сандармен көбейткіштерге жіктеуге мүмкіндік беретін нақты есептеу ресурстары үшін p өте үлкен болуын талап етеді. p – 1 үлкен жай көбейткіштерге ие. Яғни, p = aq + 1, мұнда a – кез келген бүтін сан, ал q – үлкен жай сан. q – 1 үлкен жай көбейткіштерге ие. Яғни, q = aq + 1, мұнда a – кез келген бүтін сан, ал q – үлкен жай сан. p + 1 үлкен жай көбейткіштерге ие. Яғни, p = aq – 1, мұнда a – кез келген бүтін сан, ал q – үлкен жай сан. Жай сан криптографиялық және сандық теориялық мағынада да күшті болуы мүмкін. Мысал ретінде, 439351292910452432574786963588089477522344331 саны сандық теория тұрғысынан күшті жай сан, себебі оның екі көрші жай санының арифметикалық ортасы 62-ге кем. Компьютердің көмегісіз, бұл сан криптографиялық мағынада күшті жай сан болар еді, өйткені 439351292910452432574786963588089477522344330 санының үлкен жай көбейткіші 1747822896920092227343 (ал одан бір кем санның үлкен жай көбейткіші 1683837087591611009), 439351292910452432574786963588089477522344332 санының үлкен жай көбейткіші 864608136454559457049 (ал одан бір кем санның үлкен жай көбейткіші 105646155480762397). Тіпті сынаққа бөлуден артық алгоритмдерді қолданғанда да, бұл сандарды қолмен көбейткіштерге жіктеу қиын. Дегенмен, қазіргі заманғы компьютерлік алгебра жүйесі үшін бұл сандарды дерлік бірден көбейткіштерге жіктеуге болады. Криптографиялық тұрғыдан күшті жай сан осы мысалдан әлдеқайда үлкен болуы керек.
q − 1 has large prime factors. That is, q = aq + 1 for some integer a and large prime q.
p + 1 has large prime factors. That is, p = aq − 1 for some integer a and large prime q. It is possible for a prime to be a strong prime both in the cryptographic sense and the number theoretic sense. For the sake of illustration, 439351292910452432574786963588089477522344331 is a strong prime in the number theoretic sense because the arithmetic mean of its two neighboring primes is 62 less. Without the aid of a computer, this number would be a strong prime in the cryptographic sense because 439351292910452432574786963588089477522344330 has the large prime factor 1747822896920092227343 (and in turn the number one less than that has the large prime factor 1683837087591611009), 439351292910452432574786963588089477522344332 has the large prime factor 864608136454559457049 (and in turn the number one less than that has the large prime factor 105646155480762397). Even using algorithms more advanced than trial division, these numbers would be difficult to factor by hand. For a modern computer algebra system, these numbers can be factored almost instantaneously. A cryptographically strong prime has to be much larger than this example.
Факторингке негізделген крипто жүйелері
Кейбір адамдар RSA криптожүйелерінде кілт жасау процесінде n модулін екі күшті жай санның көбейтіндісі ретінде таңдау керек деп ұсынады. Бұл Pollard-тың p-1 алгоритмін қолдану арқылы n = pq-ны факторлауды есептеу тұрғысынан мүмкін емес етеді. Осы себепті, ANSI X9.31 стандарты цифрлық қолтаңбалар үшін RSA кілттерін жасауда қолдану үшін күшті жай сандарды талап етеді. Дегенмен, күшті жай сандар Lenstra эллипстік қисық факторлау және Сандық өріс Елегі алгоритмі сияқты жаңа алгоритмдерді қолдана отырып, модульді факторлаудан қорғамайды. Күшті жай сандарды жасаудың қосымша құнына байланысты, RSA Security қазіргі таңда кілт жасауда оларды қолдануды ұсынбайды. Осыған ұқсас (және көбірек техникалық) аргументтерді Rivest және Silverman да келтіреді.
Дискрет-логрифимге негізделген крипто жүйелері
1978 жылы Стивен Полиг пен Мартин Хеллман көрсеткендей, егер p-1 санының барлық көбейткіштері log p-ден кіші болса, онда p модулі бойынша дискретті логарифмді шешу мәселесі P класында болады. Сондықтан, DSA сияқты дискретті логарифмге негізделген криптожүйелер үшін p-1 санының кем дегенде бір үлкен жай көбейткіші болуы керек.
Түрлі фактілер
Есептеулік жағынан үлкен қауіпсіз жай сан криптографиялық тұрғыдан берік жай сан болуы мүмкін. Псевдожай санның мықты псевдожай сан екенін анықтау критерийлері негіздің дәрежелеріне қатысты сәйкестіктер арқылы, ал көршілес псевдожай сандардың арифметикалық орташасымен теңсіздік арқылы емес, анықталады. Егер жай сан өзінің көршілес жай сандарының орташасына тең болса, онда ол теңгерілген жай сан деп аталады. Егер ол кіші болса, онда ол әлсіз жай сан деп аталады (әлсіз жай санмен шатастырмау керек).