Schoof's algorithm

Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve.

The algorithm was published by René Schoof in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm for counting points on elliptic curves. Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive and baby-step giant-step algorithms were, for the most part, tedious and had an exponential running time.

This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm.

Introduction

Let be an elliptic curve defined over the finite field , where for a prime and an integer . Over a field of characteristic an elliptic curve can be given by a (short) Weierstrass equation

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.

Hasse's theorem

Hasse's theorem states that if is an elliptic curve over the finite field , then satisfies

This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down to a finite (albeit large) set of possibilities. Defining to be , and making use of this result, we now have that computing the value of modulo where , is sufficient for determining , and thus . While there is no efficient way to compute directly for general , it is possible to compute for a small prime, rather efficiently. We choose to be a set of distinct primes such that . Given for all , the Chinese remainder theorem allows us to compute .

In order to compute for a prime , we make use of the theory of the Frobenius endomorphism and division polynomials. Note that considering primes is no loss since we can always pick a bigger prime to take its place to ensure the product is big enough. In any case Schoof's algorithm is most frequently used in addressing the case since there are more efficient, so called adic algorithms for small-characteristic fields.

The Frobenius endomorphism

Given the elliptic curve defined over we consider points on over , the algebraic closure of ; i.e. we allow points with coordinates in . The Frobenius endomorphism of over extends to the elliptic curve by .

This map is the identity on and one can extend it to the point at infinity , making it a group morphism from to itself.

The Frobenius endomorphism satisfies a quadratic polynomial which is linked to the cardinality of by the following theorem:

Theorem: The Frobenius endomorphism given by satisfies the characteristic equation

where

Thus we have for all that , where + denotes addition on the elliptic curve and and denote scalar multiplication of by and of by .

One could try to symbolically compute these points , and as functions in the coordinate ring of and then search for a value of which satisfies the equation. However, the degrees get very large and this approach is impractical.

Schoof's idea was to carry out this computation restricted to points of order for various small primes . Fixing an odd prime , we now move on to solving the problem of determining , defined as , for a given prime . If a point is in the -torsion subgroup , then where is the unique integer such that and . Note that and that for any integer we have . Thus will have the same order as . Thus for belonging to , we also have if . Hence we have reduced our problem to solving the equation

where and have integer values in .

Computation modulo primes

The lth division polynomial is such that its roots are precisely the x coordinates of points of order l. Thus, to restrict the computation of to the l-torsion points means computing these expressions as functions in the coordinate ring of E and modulo the lth division polynomial. I.e. we are working in . This means in particular that the degree of X and Y defined via is at most 1 in y and at most 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:

where is the nth division polynomial. Note that 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 .

Case 1:

By using the addition formula for the group we obtain:

Note that this computation fails in case the assumption of inequality was wrong.

We are now able to use the x-coordinate to narrow down the choice of to two possibilities, namely the positive and negative case. Using the y-coordinate one later determines which of the two cases holds.

We first show that X is a function in x alone. Consider . Since is even, by replacing by , we rewrite the expression as

and have that

Here, it seems not right, we throw away ?

Now if for one then satisfies

for all l-torsion points P.

As mentioned earlier, using Y and we are now able to determine which of the two values of ( or ) works. This gives the value of . Schoof's algorithm stores the values of in a variable for each prime l considered.

Case 2:

We begin with the assumption that . Since l is an odd prime it cannot be that and thus . The characteristic equation yields that . And consequently that . 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 .

Additional case

If you recall, our initial considerations omit the case of . 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 .

The algorithm

    Input:
        1. An elliptic curve .
        2. An integer q for a finite field  with .
    Output:
        The number of points of E over .
    Choose a set of odd primes S not containing p such that 
    Put  if , else .
    Compute the division polynomial . 
    All computations in the loop below are performed in the ring 
    For  do:
        Let  be the unique integer such that   and .
        Compute ,  and .   
        if  then
            Compute .
            for  do:
                if  then
                    if  then
                        ;
                    else
                        .
        else if q is a square modulo l then
            compute w with 
            compute 
            if  then
                
            else if  then
                
            else
                
        else
            
    Use the Chinese Remainder Theorem to compute t modulo N
        from the equations , where .
    Output .

Complexity

Most of the computation is taken by the evaluation of and , for each prime , that is computing , , , for each prime . This involves exponentiation in the ring and requires multiplications. Since the degree of is , each element in the ring is a polynomial of degree . By the prime number theorem, there are around primes of size , giving that is and we obtain that . Thus each multiplication in the ring requires multiplications in which in turn requires bit operations. In total, the number of bit operations for each prime is . Given that this computation needs to be carried out for each of the primes, the total complexity of Schoof's algorithm turns out to be . Using fast polynomial and integer arithmetic reduces this to .

Improvements to Schoof's algorithm

In the 1990s, Noam Elkies, followed by A. O. L. Atkin, devised improvements to Schoof's basic algorithm by restricting the set of primes considered before to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime is called an Elkies prime if the characteristic equation: splits over , while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the Schoof–Elkies–Atkin algorithm. The first problem to address is to determine whether a given prime is Elkies or Atkin. In order to do so, we make use of modular polynomials, which come from the study of modular forms and an interpretation of elliptic curves over the complex numbers as lattices. Once we have determined which case we are in, instead of using division polynomials, we are able to work with a polynomial that has lower degree than the corresponding division polynomial: rather than . For efficient implementation, probabilistic root-finding algorithms are used, which makes this a Las Vegas algorithm rather than a deterministic algorithm. Under the heuristic assumption that approximately half of the primes up to an bound are Elkies primes, this yields an algorithm that is more efficient than Schoof's, with an expected running time of using naive arithmetic, and using fast arithmetic. Although this heuristic assumption is known to hold for most elliptic curves, it is not known to hold in every case, even under the GRH.

Implementations

Several algorithms were implemented in C++ by Mike Scott and are available with source code. The implementations are free (no terms, no conditions), and make use of the MIRACL library which is distributed under the AGPLv3.

  • Schoof's algorithm implementation for with prime .
  • Schoof's algorithm implementation for .

See also

References

  • R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483–494, 1985. Available at http://www.mat.uniroma2.it/~schoof/ctpts.pdf
  • R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219–254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
  • G. Musiker: Schoof's Algorithm for Counting Points on . Available at http://www.math.umn.edu/~musiker/schoof.pdf
  • V. Müller : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991. Available at http://lecturer.ukdw.ac.id/vmueller/publications.php
  • A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
  • L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.
  • N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994

Read other articles:

جامعة بينغامتون   معلومات التأسيس 1946[1]  الموقع الجغرافي إحداثيات 42°05′21″N 75°58′12″W / 42.08925°N 75.96989°W / 42.08925; -75.96989  الرمز البريدي 13850-6000[2]،  و13902[3][4][5][1]  البلد الولايات المتحدة[1]  إحصاءات عدد الطلاب 16818 (1 سبتمبر 2021)[6]1812...

 

2005 compilation album by Various ArtistsWhatever: The '90s Pop & Culture BoxCompilation album by Various ArtistsReleased2005Recorded1989-1999GenreRock, popLabelRhino Records Whatever: The '90s Pop & Culture Box is a seven-disc, 130-track box set of popular music hits of the 1990s. Released by Rhino Records in 2005, the box set was based on the success of Have a Nice Decade: The 70s Pop Culture Box, and Like Omigod! The 80s Pop Culture Box (Totally), Rhino's box sets covering ...

 

Komjen. Pol. (Purn.) Drs.Dwi PriyatnoS.H.Inspektur Pengawasan Umum PolriMasa jabatan1 September 2014 – 13 September 2017PendahuluAnton Bachrul AlamPenggantiPutut Eko Bayu SenoKepala Kepolisian Daerah Jawa Tengah ke-14Masa jabatan12 Juni 2013 – 7 Maret 2014PendahuluDidiek Sutomo TriwidodoPenggantiNoer AliStaf Ahli Bidang Sosial Politik KapolriMasa jabatan18 Desember 2012 – 12 Juni 2013PendahuluArif WachyunadiPenggantiMudji Waluyo Informasi pribadiLahir12 No...

Au 1er janvier 2007, le nombre d'habitants du Languedoc-Roussillon était estimé à 2 548 000 habitants[1], soit plus ou moins 4 % de la population de la France métropolitaine. Le rythme de croissance démographique de la région est le plus élevé de France. Il est avant tout dû au solde migratoire (+ 1,24 % par an depuis 1999), le solde naturel étant très faible (+ 0,12 % annuellement)[2]. Évolution de la population Années Population au 1er janvier départem...

 

Lipoprotein lipaseالمعرفاتالرمز، (أو الرموز) LPL; HDLCQ11; LIPDمعرفات خارجية OMIM: 609708 MGI: 96820 هومولوجين: 200 مختبر علم الأحياء الجزيئي الأوروبي الكيميائي: 2060 بطاقات الجينات: LPL Geneرقم التصنيف الإنزيمي 3.1.1.34 علم الوجود الجيني الوظيفة الجزيئية • lipoprotein lipase activity • phospholipase activity • triglyceride lipase ...

 

FSV 63 Luckenwalde Basisdaten Name Fußballsportverein 63 Luckenwalde e. V. Sitz Luckenwalde, Brandenburg Gründung 1963 Farben Blau-Gelb Präsident Dirk Heinze Website fsv63-luckenwalde.de Erste Fußballmannschaft Cheftrainer Michael Braune Spielstätte Werner-Seelenbinder-Stadion Plätze 3000 Liga Regionalliga Nordost 2022/23 13. Platz Heim Auswärts Der FSV 63 Luckenwalde ist ein deutscher Fußballverein aus Luckenwalde im Landkreis Teltow-Fläming. Der Verein entstand im Jahr 1963 au...

AruiteruSingel oleh Morning Musumedari album 7.5 Fuyu Fuyu Morning Musume Mini! dan Sexy 8 BeatSisi-BOdore! Morning CurryDirilis8 November 2006 (2006-11-08)FormatCD, DVDDirekam2006GenrePopLabelZetimaPenciptaTsunkuProduserTsunkuVideo musikAruiteru di YouTube Aruiteru (歩いてるcode: ja is deprecated , Berjalan) Adalah singel ke tigapuluh satu dari grup idola Jepang Morning Musume. Sejarah rilis Aruiteru dirilis pada tanggal 8 November 2006. Singel ini terjual sekitar 55.694 kopi dan me...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (نوفمبر 2018) ساره بايكر (بالإنجليزية: Sarah Baker)‏  معلومات شخصية الميلاد 9 سبتمبر 1990 (33 سنة)  واشنطن  مواطنة الولايات المتحدة  الحياة العملية المدرسة الأم جامعة جي...

 

Bilateral relationsCzechoslovakia–United States relations Czechoslovakia United States Diplomatic missionEmbassy of the Czech Republic, Washington, D.C.Embassy of the United States, Prague Relations between Czechoslovakia and the United States refer to two periods in Czechoslovakia's history. The first being the establishment of Czechoslovakia after its declaration of independence in 1918 from Austria-Hungary initiated by President Woodrow Wilson as part of his Fourteen Points following Wor...

Japanese filmmaker and animator The native form of this personal name is Shinkai Makoto. This article uses Western name order when mentioning individuals. In this Japanese name, the surname is Shinkai. Makoto Shinkai新海 誠Shinkai at the 2023 Berlin International Film FestivalBornMakoto Niitsu (1973-02-09) February 9, 1973 (age 50)Koumi, JapanEducationChuo UniversityOccupationsAnimatorfilmmakerauthormanga artistYears active1996–presentKnown forYour NameWeathering with ...

 

Parte de uma série sobrePatrimónio de Portugal Classificação Classificação do património em Portugal MN IIP IIM Património Mundial IPPAR (1992-2007) IGESPAR (2007-2015) DGPC (2015-) Listas por distrito Lista geral Aveiro Beja Braga Bragança Castelo Branco Coimbra Évora Faro Guarda Leiria Lisboa Portalegre Porto Santarém Setúbal Viana do Castelo Vila Real Viseu Açores Madeira Listas por tipologia Castelos Castros Cruzeiros Edifícios Fortalezas Marcos Megálitos Palácios Pelourin...

 

2020 single by JinsoulAs Time GoesSingle by Jinsoulfrom the album Meow, the Secret Boy (Original Television Soundtrack) ReleasedApril 15, 2020 (2020-04-15)Length3:06LabelDonuts Music NDreamusSongwriter(s)Jay LeeProducer(s)Jay LeeJinsoul singles chronology JinSoul (2017) As Time Goes (2020) Music videoAs Time Goes Video on YouTube As Time Goes (Korean: 시간은 한 바퀴 돌아; RR: sigan-eun han bakwi dol-a) is a song recorded by South Korean singer Jins...

US crime drama television series PerceptionGenreCrime dramaPolice proceduralCreated byKenneth BillerMike SussmanStarringEric McCormackRachael Leigh CookKelly RowanArjay SmithLeVar BurtonScott WolfTheme music composerTree AdamsComposerTree AdamsCountry of originUnited StatesOriginal languageEnglishNo. of seasons3No. of episodes39 (list of episodes)ProductionExecutive producersKenneth BillerMike SussmanAlan PoulProducerEric McCormackRunning time43 minutesProduction companiesPaperboy Productions...

 

Scottish golfer Scott JamiesonJamieson at the 2009 Dutch FuturesPersonal informationBorn (1983-11-28) 28 November 1983 (age 40)Glasgow, ScotlandHeight1.85 m (6 ft 1 in)Weight80 kg (176 lb; 12 st 8 lb)Sporting nationality ScotlandResidenceGlasgow, ScotlandSpouseNatalie JamiesonChildren3CareerCollegeAugusta State UniversityTurned professional2006Current tour(s)European TourFormer tour(s)Challenge TourPGA EuroPro TourProfessional wins3Highest ranking6...

 

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2011) (Learn how and when to remove this template message) Sultanate of Bulunganکسلطانن بولوڠنKesultanan Bulungan1731–1964 Flag Coat of arms StatusVassal of SuluPart of the Dutch East Indies (from 1880s)CapitalTanjung PalasCommon languagesBulungan-MalayReligion Sunni IslamGovernmentM...

La compétition de volley-ball aux Jeux africains a eu lieu à Alger, en Algérie, du 14 au 22 juillet 2007. Épreuve masculine Équipes Groupe A Groupe B Algérie Kenya Afrique du Sud Seychelles RD Congo Ghana Égypte Tunisie Cameroun Nigeria Botswana Sénégal Groupe A Équipe Points G W L PW PL Ratio SW SL Ratio 1. Algérie 10 5 5 0 1.428 15 1 15.000 2. Kenya 9 5 4 1 1.116 12 3 4.000 3. Afrique du Sud 8 5 3 2 1.010 9 9 1.000 4. Seychelles 6 5 1 4 0.951 6 13 0.462 5. RD Congo 6 5 1 4 0.869 ...

 

Lambang negara JermanVersionsLambang yang dipakai pada institusi federalDetailPemangkuPemerintah JermanDigunakan sejak23 Mei 19493 Oktober 1990 (lambang baru)PerisaiElang hitam dengan paruh merahVersi awalVersi terkini lambang negara Jerman diperkenalkan pada masa akhir Republik Weimar Lambang negara Jerman, menggambarkan elang hitam dengan paruh dan cakar berwarna merah, di atas latar berbentuk perisai berwarna kuning emas. Warna-warna yang digunakan dalam lambang ini sama dengan warna Bende...

 

Standings and results for Group B of the regular season phase of the 2007–08 Euroleague basketball tournament. Main page: 2007–08 Euroleague Key to colors      Top five places in each group, plus highest-ranked sixth-place team,advance to Top 16      Eliminated Standings The Euroleague fixture between Efes Pilsen S.K. and BC Lietuvos Rytas Team Pld W L PF PA Diff 1. Lietuvos Rytas Vilnius 14 11 3 1127 999 +128 2. Maccabi Tel Aviv 14 11 3 1162 1108 +...

ATP Tour 2019stagione di torneiRafael Nadal, chiude l'anno da numero uno e vince due Slam.Sport Tennis SerieATP Tour Durata31 dicembre 2018 – 24 novembre 2019 Edizione50ª Tornei67 CategorieGrande Slam (4)ATP FinalsNext Generation ATP FinalsATP World Tour Masters 1000 (9)ATP World Tour 500 (13)ATP World Tour 250 (39) RisultatiMaggior n. di titoli Dominic Thiem Novak Djokovic (5) Maggior n. di finali Daniil Medvedev (9) Maggiori guadagni Rafael Nadal ($16.349.586) Maggior punteggio Rafael Na...

 

Diptera Clasificación científicaDominiu: EukaryotaReinu: AnimaliaSubreinu: MetazoaFilu: ArthropodaClas: InsectaSubclas: PterygotaInfraclas: NeopteraSuperorde: EndopterygotaOrde: DipteraSubórdenes Nematocera* BrachyceraConsultes[editar datos en Wikidata] Los dípteros (Diptera, gr. dos ales) son un orde d'inseutos neópteros carauterizaos porque les sos ales posteriores amenorgar a halterios, esto ye, que tienen namái dos ales membranoses y non cuatro comos la gran mayoría de los inseutos...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!