Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Сандар теориясында Фробениус псевдопримі – псевдоприм, оның анықтамасы Джон Грантхэмнің 1998 жылғы препринтінде және 2000 жылы жарияланған квадраттық Фробениус тестісінен шабыттанды. Фробениус псевдопримдері кем дегенде 2 дәрежелі полиномдарға қатысты анықталуы мүмкін, бірақ олар ең көп зерттелгені квадратық полиномдар жағдайында.
In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000. Frobenius pseudoprimes can be defined with respect to polynomials of degree at least 2, but they have been most extensively studied in the case of quadratic polynomials.
Псевдопримальдық сынақтар
Фробен псевдопримі анықтайтын шарттар берілген n санын ықтимал жай сан екенін тексеру үшін қолданылуы мүмкін. Көбінесе мұндай тесттер белгілі бір параметрлерге сүйенбейді, керісінше, жалған оң нәтижелердің – яғни, жай емес сандардың – тесттен өту үлесін азайту үшін оларды кіріс саны n-ге байланысты белгілі бір тәсілмен таңдайды. Кейде мұндай жай емес сандар, әр түрлі параметрлерге сәйкес келсе де, Фробен псевдопримі деп аталады. Бейли мен Вагстафф (1980) алғаш ұсынған параметрлерді таңдау идеяларын, Бейли-PSW жай сан тестінің бір бөлігі ретінде және Грантамның квадратық Фробен псевдопримі тестінде пайдаланған, одан да жақсы квадратық тесттер жасауға болады. Атап айтқанда, n модулі бойынша квадратық қалдық емес параметрлерді таңдау (Джакоби символына негізделген) әлдеқайда күшті тесттерді жасауға мүмкіндік береді, және бұл Бейли-PSW жай сан тестінің табысының бір себебі болып табылады. Мысалы, (P,2) параметрлері үшін, мұнда P – бірінші тақ бүтін сан, белгілі теңсіздікті қанағаттандыратын болса, 264-тен төмен псевдопримдер жоқ. Тағы бір тестті Хашин ұсынады. Берілген жай емес n саны үшін, ол алдымен c параметрін ең кішкентай тақ жай сан ретінде есептейді, оның Джакоби символы белгілі шартты қанағаттандырады, содан кейін келесі сәйкестікті тексереді: Барлық жай n сандары осы тесттен өтеді, ал жай емес n саны оны тек және тек n Фробен псевдопримі болса ғана өтеді. Жоғарыдағы мысалға ұқсас, Хашин өзінің тесті үшін псевдопримдер табылған жоқ екенін атап өтеді. Ол сондай-ақ, 260-тан төмен кез келген псевдопримнің 19-дан кішкентай бөлгіші болуы немесе c > 128 болуы керек екенін көрсетеді.
The conditions defining Frobenius pseudoprime can be used for testing a given number n for probable primality. Often such tests do not rely on fixed parameters , but rather select them in a certain way depending on the input number n in order to decrease the proportion of false positives, i. e., composite numbers that pass the test. Sometimes such composite numbers are commonly called Frobenius pseudoprimes, although they may correspond to different parameters. Using parameter selection ideas first laid out in Baillie and Wagstaff (1980) as part of the Baillie–PSW primality test and used by Grantham in his quadratic Frobenius test, one can create even better quadratic tests. In particular, it was shown that choosing parameters from quadratic non residues modulo n (based on the Jacobi symbol) makes far stronger tests, and is one reason for the success of the Baillie–PSW primality test. For instance, for the parameters (P,2), where P is the first odd integer that satisfies , there are no pseudoprimes below 264. Yet another test is proposed by Khashin. For a given non square number n, it first computes a parameter c as the smallest odd prime having Jacobi symbol , and then verifies the congruence: While all prime n pass this test, a composite n passes it if and only if n is a Frobenius pseudoprime for Similar to the above example, Khashin notes that no pseudoprime has been found for his test. He further shows that any that exist under 260 must have a factor less than 19 or have c > 128.
Қасиеттері
Фробениус псевдоперделік сынағының квадраттық полиномиалдарға қатысты есептеу құны мықты псевдоперделік сынақтан (яғни Миллер-Рабин перделік сынағының бір раундынан) шамамен үш есе, Лукастың псевдоперделік сынағынан 1,5 есе және Бейли-PSW перделік сынағынан сәл көп. Квадраттық Фробениус сынағы Лукас сынағынан күштірек екенін ескеріңіз. Мысалы, 1763 саны (P, Q) = (3, –1) үшін Лукас псевдоперделігі болып табылады, өйткені U1764(3,–1) ≡ 0 (mod 1763) (U(3,–1) формуласында келтірілген), сонымен қатар ол Якоби қадамын да өтеді, бірақ x² – 3x – 1 бойынша Фробениус сынағынан өтпейді. Бұл қасиет алгоритм Крандл мен Померанс алгоритмі 3.6.9 көрсетілгендей құрастырылғанда анық көрінеді. Дамгард пен Франдсен 2003 жылы негізінен Сейсеннің шекарасы бар EQFT сынағын ұсынды. 2005 жылы Сейсен SQFT сынағын шектеуімен және SQFT3 сынағын шектеуімен ұсынды. Бірдей есептеу күшін қолдана отырып, бұл сынақтар жиі қолданылатын Миллер-Рабин перделік сынағынан жақсырақ ең нашар жағдай шектерін ұсынады.
The computational cost of the Frobenius pseudoprimality test with respect to quadratic polynomials is roughly three times the cost of a strong pseudoprimality test (i. e. a single round of the Miller–Rabin primality test), 1.5 times that of a Lucas pseudoprimality test, and slightly more than a Baillie–PSW primality test. Note that the quadratic Frobenius test is stronger than the Lucas test. For example, 1763 is a Lucas pseudoprime to (P, Q) = (3, –1) since U1764(3,–1) ≡ 0 (mod 1763) (U(3,–1) is given in ), and it also passes the Jacobi step since , but it fails the Frobenius test to x2 – 3x – 1. This property can be clearly seen when the algorithm is formulated as shown in Crandall and Pomerance Algorithm 3.6.9 Damgård and Frandsen in 2003 proposed the EQFT with a bound of essentially Seysen in 2005 proposed the SQFT test with a bound of and a SQFT3 test with a bound of
Given the same computational effort, these offer better worst case bounds than the commonly used Miller–Rabin primality test.