Кіріспе
Шуф алгоритмі – шекті өрістердегі эллиптік қисықтардағы нүктелерді санаудың тиімді алгоритмі. Алгоритм эллиптік қисық криптографиясында қолданылады, онда эллиптік қисықтың нүктелер тобындағы дискретті логарифмдік есепті шешудің қиындығын бағалау үшін нүктелер санын білу маңызды. Алгоритмді 1985 жылы Рене Шуф жариялаған, және ол эллиптік қисықтардағы нүктелерді санау үшін жасалған алғашқы детерминистік полиномиалдық уақыт алгоритмі болғандықтан, теориялық тұрғыдан маңызды жаңалық болды. Шуф алгоритмінен бұрын эллиптік қисықтардағы нүктелерді санауға қолданылған қарапайым және «кішкентай қадам – үлкен қадам» сияқты әдістер көбінесе қиынға соғып, экспоненциалды уақыт талап ететін. Осы мақалада Шуф әдісі түсіндіріледі, алгоритмнің құрылымын анықтайтын математикалық идеяларға ерекше назар беріледі.
Кіріспе
Бұл – жай өріс үстінде анықталған эллиптік қисық, мұнда *p* – жай сан және *m* – бүтін сан. Сипаттамасы *p*-ға тең өріс үстінде эллиптік қисықты (қысқа) Вейерштрасс теңдеуі арқылы беруге болады:
with The set of points defined over consists of the solutions satisfying the curve equation and a point at infinity Using the group law on elliptic curves restricted to this set one can see that this set forms an abelian group, with acting as the zero element. In order to count points on an elliptic curve, we compute the cardinality of Schoof's approach to computing the cardinality makes use of Hasse's theorem on elliptic curves along with the Chinese remainder theorem and division polynomials.
y² = x³ + ax + b.
with The set of points defined over consists of the solutions satisfying the curve equation and a point at infinity Using the group law on elliptic curves restricted to this set one can see that this set forms an abelian group, with acting as the zero element. In order to count points on an elliptic curve, we compute the cardinality of Schoof's approach to computing the cardinality makes use of Hasse's theorem on elliptic curves along with the Chinese remainder theorem and division polynomials.
Бұл жерде анықталған нүктелер жиыны қисық теңдеуін қанағаттандыратын шешімдерден және шексіз нүктеден тұрады. Эллиптік қисықтардағы топтық заңдылықты осы жиынға шектеу арқылы, бұл жиынның нөлдік элементі ретінде әрекет ететін абельдік топ құрайтынын көруге болады. Эллиптік қисықтағы нүктелер санын есептеу үшін Schoof әдісімен кардиналдылықты есептейміз. Schoof әдісі кардиналдылықты есептеу үшін Хассе теоремасын, қытайлық қалдық теоремасын және бөлу полиномдарын қолданады.
with The set of points defined over consists of the solutions satisfying the curve equation and a point at infinity Using the group law on elliptic curves restricted to this set one can see that this set forms an abelian group, with acting as the zero element. In order to count points on an elliptic curve, we compute the cardinality of Schoof's approach to computing the cardinality makes use of Hasse's theorem on elliptic curves along with the Chinese remainder theorem and division polynomials.
Есептеу модульді алғашқы сандар
L-ші бөлініс полиномының түбірлері дәл l-ретті нүктелердің x-координаттарымен анықталады. Осылайша, есептеуді l-ретті бұрылыс нүктелерімен шектеу, бұл өрнектерді E эллиптік қисығының координаттық сақинасындағы функциялар ретінде есептеу және оларды l-ші бөлініс полиномы бойынша модульдеуді білдіреді. Яғни, біз осы ортада жұмыс істейміз. Бұл, атап айтқанда, X және Y-дің дәрежесі y бойынша 1-ден аспайды және x бойынша да 1-ден аспайды дегенді білдіреді. Скалярлық көбейтуді екі еселеу және қосу әдісімен немесе l-ші бөлініс полиномын пайдалану арқылы жүзеге асыруға болады. Соңғы тәсіл мынадай:
in x. The scalar multiplication can be done either by double and add methods or by using the th division polynomial. The latter approach gives:
, мұндағы – n-ші бөлініс полиномы. Бұл функция тек x-ке тәуелді екенін және оны арқылы белгілейтінімізді ескеріңіз. Мәселені екі жағдайға бөлу керек: жағдайы және жағдайы. Бұл теңдіктер модуль бойынша тексеріледі.
is a function in x only and denote it by
We must split the problem into two cases: the case in which , and the case in which Note that these equalities are checked modulo .
2-ші жағдай:
Біз l – тақ сан, сондықтан ол тең болмайды деп бастаймыз. Осыдан сипаттамалық теңдеу мынаны береді: және осының салдарынан . Бұл q санын l модулі бойынша квадраттық қалдық екенін білдіреді. Енді q санын есептеп, оны l модулі бойынша тексеріп көрейік. Егер осы шарт орындалса, онда y координатасына байланысты . Егер q санын l модулі бойынша квадраттық қалдық емес екені анықталса немесе теңдеу w және ешқайсысы үшін де орындалмаса, онда біздің болжамымыз жалған, демек сипаттамалық теңдеу мынаны береді.
This implies that q is a square modulo l. Let Compute in and check whether If so, is depending on the y coordinate. If q turns out not to be a square modulo l or if the equation does not hold for any of w and , our assumption that is false, thus The characteristic equation gives .
Қосымша жағдай
Егер естеріңізде болса, біздің бастапқы қарастыруларымыз жағдайды қамтымайды. Біз q-ның тақ сан екенін болжаймыз, және әсіресе, егер және тек қана егер топта 2-ретті элемент болса ғана. Топтағы қосудың анықтамасы бойынша, 2-ретті кез келген элемент міндетті түрде мынадай формада болады. Демек, егер және тек қана егер көпмүше түбірі болса, егер және тек қана егер .
Since we assume q to be odd, and in particular, if and only if has an element of order 2. By definition of addition in the group, any element of order 2 must be of the form Thus if and only if the polynomial has a root in , if and only if .
Күрделілігі
Есептеудің басым бөлігі әрбір жай сан үшін және есептеу арқылы жүзеге асырылады, яғни әрбір жай сан үшін , , , есептеу. Бұл сақинадағы дәрежелеуді және көбейтуді қажет етеді. сақинасының дәрежесі болғандықтан, сақинадағы әрбір элемент дәрежелі полином болып табылады. Жай сандар теоремасы бойынша, шамамен өлшемді жай сандар бар, сондықтан және осыдан келеді. Осылайша, сақинадағы әрбір көбейту үшін көбейту қажет, ал ол өз кезегінде биттік операцияларды қажет етеді. Жалпы, әрбір жай сан үшін биттік операциялардың саны болады. Бұл есептеуді барлық жай сан үшін орындау қажет болғандықтан, Шоуф алгоритмінің жалпы күрделілігі болып табылады. Жылдам полиномдық және бүтін сан арифметикасын қолдану бұл көрсеткішті дейін төмендетеді.
Schoof алгоритмінің жетілдірілуі
1990 жылдары Ноам Элкис, одан кейін А. О. Л. Аткин, бұрын қарастырылған жай сандар жиынын белгілі бір түрдегі жай сандармен шектеу арқылы Шоуфтың негізгі алгоритмін жетілдірді. Бұлар тиісінше Элкис жай сандары және Аткин жай сандары деп аталды. Егер сипаттамалық теңдеу жақымдылықпен бөлінсе, онда ол Элкис жай саны деп аталады, ал Аткин жай саны – Элкис жай саны емес жай сан. Аткин, Аткин жай сандарынан алынған мәліметтерді Элкис жай сандарынан алынған мәліметтермен біріктіре отырып, тиімді алгоритм жасауға болатынын көрсетті, ол Шоуф–Элкис–Аткин алгоритмі деп аталды. Бірінші мәселе – берілген жай санның Элкис немесе Аткин екенін анықтау. Мұны істеу үшін модульдік формаларды зерттеуден және күрделі сандардағы эллипстік қисықтарды торлар ретінде қарастырудан туындайтын модульдік полиномдар қолданылады. Біз қай жағдай екенін анықтағаннан кейін, бөлу полиномдарын пайдаланудың орнына, тиісті бөлу полиномынан төмен дәрежелі полиноммен жұмыс істей аламыз: . Тиімді іске асыру үшін ықтималдық түбір табу алгоритмдері қолданылады, бұл оны детерминистік емес, Лас-Вегас алгоритміне айналдырады. Егер белгілі бір шекке дейінгі жай сандардың шамамен жартысы Элкис жай сандары болса деп есептесек, онда бұл Шоуф алгоритмінен тиімдірек алгоритмді береді, ал оның күтілетін жұмыс уақыты қарапайым арифметиканы қолданғанда және жылдам арифметиканы қолданғанда болады. Бұл эвристикалық болжам көптеген эллипстік қисықтар үшін дұрыс деп танылса да, тіпті GRH жағдайында да, ол әрбір жағдайда дұрыс екені белгілі емес.
Қолданылу
Бірнеше алгоритмдер Майк Скотт тарапынан C++ тілінде іске асырылды және бастапқы кодымен бірге қолжетімді. Бұл іске асырылымдар тегін (ешқандай талаптарсыз, ешқандай шарттарсыз) және AGPLv3 лицензиясымен таратылатын MIRACL кітапханасын пайдаланады. Schoof алгоритмінің жай сан p үшін іске асырылымы, Schoof алгоритмінің жай сан үшін іске асырылымы.