Квадраттық Фробениус тесті - Quadratic Frobenius test

The квадраттық Фробениус сынағы (QFT) Бұл ықтималдық бастапқы тест санның а екенін тексеруге ықтимал қарапайым. Оған байланысты Фердинанд Георг Фробениус. Тестте. Ұғымдары қолданылады квадрат көпмүшелер және Фробениус автоморфизмі. Мұны неғұрлым жалпы деп шатастыруға болмайды Фробениус сынағы квадраттық көпмүшені қолдану - QFT кіріс негізінде рұқсат етілген көпмүшелерді шектейді, сонымен қатар басқа да шарттар орындалуы керек. A құрама бұл сынақты тапсыру а Фробениус псевдопримі, бірақ керісінше болуы міндетті емес.

Тұжырымдама

Алгоритмді құру кезінде Грантемнің мақсаты жай бөлшектер әрдайым өтіп, композиттер 1/7710 ықтималдығымен өтетін тест ұсыну болды.^[1]^:33

Кейінірек тест ұзартылды Дамгард және Франдсен шақырылған сынаққа кеңейтілген квадраттық Фробениус тесті (EQFT).^[2]

Алгоритм

Келіңіздер $n$ оң бүтін сан болуы керек $n$ тақ, ${ displaystyle left ({ frac {b ^ {2} + 4c} {n}} right) = - 1}$ және ${ displaystyle left ({ frac {-c} {n}} right) = 1}$ , қайда ${ displaystyle сол жақ ({ frac {x} {n}} оң)}$ дегенді білдіреді Якоби символы. Орнатыңыз ${ displaystyle B = 50000}$ . Сонда а QFT қосулы $n$ параметрлерімен ( $б$ , $c$ ) келесідей жұмыс істейді:

(1) Жай санның біреуі екі мәннен кіші немесе тең екенін тексеріңіз

{ displaystyle B}

және

{ displaystyle { sqrt {n}}}

бөледі

n

. Егер иә болса, онда тоқтатыңыз

n

құрама болып табылады.

(2) Мұны тексеріңіз

{ displaystyle { sqrt {n}} in mathbb {Z}}

. Егер иә болса, онда тоқтатыңыз

n

құрама болып табылады.

(3) Есептеу

{ displaystyle x ^ {n + 1 2} ден жоғары , { bmod {,}} { big (} n, x ^ {2} -bx-c)}

. Егер

{ displaystyle x ^ {n + 1 over 2} notin mathbb {Z} { big /} n mathbb {Z}}

содан кейін тоқтаңыз

n

құрама болып табылады.

(4) Есептеу

{ displaystyle x ^ {n + 1} , { bmod {,}} { big (} n, x ^ {2} -bx-c)}

. Егер

{ displaystyle x ^ {n + 1} not equiv -c}

содан кейін тоқтаңыз

n

құрама болып табылады.

(5) Келіңіздер

{ displaystyle n ^ {2} -1 = 2 ^ {r} s}

бірге

с

тақ. Егер

{ displaystyle x ^ {s} not equiv 1 { bmod {,}} { big (} n, x ^ {2} -bx-c)}

, және

{ displaystyle x ^ {2 ^ {j} s} not equiv -1 { bmod {,}} { big (} n, x ^ {2} -bx-c)}

барлығына

{ displaystyle 0 leq j leq r-2}

, содан кейін тоқтаңыз

n

құрама болып табылады.

Егер QFT (1) - (5) қадамдарында тоқтамайды, содан кейін $n$ ықтимал қарапайым.

(Белгілеу ${ displaystyle A equiv B { bmod {,}} (n, , f (x))}$ дегенді білдіреді ${ displaystyle A-B = H (x) cdot n + K (x) cdot f (x)})$ , мұндағы H және K - көпмүшелер.)

Сондай-ақ қараңыз

Әдебиеттер тізімі

^ Grantham, J. (1998). «Жоғары сенімділіктің ықтимал негізгі сынағы». Сандар теориясының журналы. 72 (1): 32–47. CiteSeerX 10.1.1.56.8827. дои:10.1006 / jnth.1998.2247.
^ Дамгард, Иван Бьерре; Франдсен, Гудмунд Сковберг (2003). Орташа және нашар жағдайлардың қателіктерін бағалайтын кеңейтілген квадраттық фробениустың басымдылығы тесті (PDF). Информатика пәнінен дәрістер. Есептеу теориясының негіздері. 2751. Springer Berlin Heidelberg. 118–131 бет. дои:10.1007/978-3-540-45077-1_12. ISBN 978-3-540-45077-1. ISSN 1611-3349.

[Grantham-1] Grantham, J. (1998). «Жоғары сенімділіктің ықтимал негізгі сынағы». Сандар теориясының журналы. 72 (1): 32–47. CiteSeerX 10.1.1.56.8827. дои:10.1006 / jnth.1998.2247.

[DamFran-2] Дамгард, Иван Бьерре; Франдсен, Гудмунд Сковберг (2003). Орташа және нашар жағдайлардың қателіктерін бағалайтын кеңейтілген квадраттық фробениустың басымдылығы тесті (PDF). Информатика пәнінен дәрістер. Есептеу теориясының негіздері. 2751. Springer Berlin Heidelberg. 118–131 бет. дои:10.1007/978-3-540-45077-1_12. ISBN 978-3-540-45077-1. ISSN 1611-3349.

[1]

[2]

Сандық-теориялық алгоритмдер
Бастапқы тесттер	AKS Сәуір Baillie – PSW Эллиптикалық қисық Поклингтон Ферма Лукас Лукас –Леммер Лукас – Леммер – Ризель Прот теоремасы Пепиндікі Квадраттық Фробениус Соловай – Страссен Миллер – Рабин
Бастапқы генератор	Аткин елегі Эратосфен елегі Сундарам елегі Дөңгелектерді факторизациялау
Бүтін факторизация	Жалғастырылған фракция (CFRAC) Диксондікі Lenstra эллиптикалық қисығы (ECM) Эйлер Поллард Ро б − 1 б + 1 Квадрат елеуіш (QS) Жалпы өрісті елеуіш (GNFS) Арнайы нөмірлі елеуіш (SNFS) Рационалды елек Ферма Шенкстің квадрат формалары Сынақ бөлімі Шордың
Көбейту	Ежелгі Египет Ұзақ Карацуба Toom – Cook Шенхаг-Страссен Фюрер
Евклид бөлу	Екілік Бөлшектеу Фурье Голдшмидт Ньютон-Рафсон Ұзақ Қысқа SRT
Дискретті логарифм	Сәби қадамы алып қадам Поллард ро Поллард кенгуру Похлиг-Хеллман Индексті есептеу Өріс елеуіші
Ең үлкен ортақ бөлгіш	Екілік Евклид Кеңейтілген евклид Леммердікі
Модульдік квадрат түбір	Циполла Поклингтонның Тонелли –Шенкс Берлекамп
Басқа алгоритмдер	Чакравала Корнакия Квадрат арқылы квадраттау Бүтін квадрат түбір Бүтін қатынас (LLL ) Модульдік дәрежелеу Монтгомеридің қысқаруы Шоф
Көлбеу алгоритм арнайы формалардың сандарына арналғанын көрсетіңіз