อัลกอริทึมของ Schoofเป็นอัลกอริทึมที่มีประสิทธิภาพในการนับจุดบนเส้นโค้งวงรีเหนือฟิลด์จำกัดอัลกอริทึมนี้มีประโยชน์ในด้านการเข้ารหัสลับด้วยเส้นโค้งวงรีซึ่งการทราบจำนวนจุดมีความสำคัญต่อการประเมินความยากของการแก้ปัญหาลอการิทึมแบบไม่ต่อเนื่องในกลุ่มจุดบนเส้นโค้งวงรี

อัลกอริทึมนี้ได้รับการตีพิมพ์โดยRené Schoofในปี 1985 และถือเป็นความก้าวหน้าทางทฤษฎี เนื่องจากเป็นอัลกอริทึมเชิงกำหนดแบบใช้เวลาพหุนามตัวแรกสำหรับการนับจุดบนเส้นโค้งวงรีก่อนหน้าอัลกอริทึมของ Schoof วิธีการนับจุดบนเส้นโค้งวงรี เช่น อัลกอริทึมแบบง่าย และ อัลกอริทึมแบบ ก้าวเล็กก้าวใหญ่ส่วนใหญ่แล้วยุ่งยากและใช้เวลาในการทำงานแบบเลขชี้กำลัง

บทความนี้อธิบายถึงแนวทางของ Schoof โดยเน้นที่แนวคิดทางคณิตศาสตร์ที่เป็นพื้นฐานของโครงสร้างอัลกอริทึม

ให้เป็นเส้นโค้งเชิงวงรีที่กำหนดบนฟิลด์จำกัดโดยที่สำหรับจำนวนเฉพาะ และจำนวนเต็มบนฟิลด์ที่มีลักษณะเฉพาะเส้นโค้งเชิงวงรีสามารถกำหนดได้ด้วยสมการไวเออร์สตรัส (แบบย่อ) ${\displaystyle E}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle q=p^{n}}$${\displaystyle p}$${\displaystyle n}$${\displaystyle \geq 1}$${\displaystyle \neq 2,3}$

${\displaystyle y^{2}=x^{3}+Ax+B}$

โดยที่เซตของจุดที่กำหนดบนประกอบด้วยคำตอบที่สอดคล้องกับสมการเส้นโค้งและจุดที่อนันต์โดยใช้กฎกลุ่มบนเส้นโค้งวงรีที่จำกัดเฉพาะเซตนี้ จะเห็นได้ว่าเซตนี้ก่อตัวเป็นกลุ่มอาเบเลียนโดยมีเป็นสมาชิกศูนย์ ในการนับจำนวนจุดบนเส้นโค้งวงรี เราคำนวณจำนวนสมาชิกของวิธีการของ Schoof ในการคำนวณจำนวนสมาชิกใช้ทฤษฎีบทของ Hasse เกี่ยวกับเส้นโค้งวงรีร่วมกับทฤษฎีบทเศษเหลือของจีนและพหุนามการหาร ${\displaystyle A,B\in \mathbb {F} _{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle (a,b)\in \mathbb {F} _{q}^{2}}$${\displaystyle O}$${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle O}$${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle \#E(\mathbb {F} _{q})}$

ทฤษฎีบทของ Hasse กล่าวว่า ถ้าเป็นเส้นโค้งเชิงวงรีบนฟิลด์จำกัดแล้วจะสอดคล้องกับเงื่อนไข ${\displaystyle E/\mathbb {F} _{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \#E(\mathbb {F} _{q})}$

${\displaystyle \mid q+1-\#E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q}}.}$

ผลลัพธ์อันทรงพลังนี้ ซึ่งเสนอโดย Hasse ในปี 1934 ช่วยลดความซับซ้อนของปัญหาของเราโดยการจำกัดให้เหลือเพียงชุดความเป็นไปได้ที่จำกัด (แม้ว่าจะใหญ่ก็ตาม) โดยกำหนดให้เป็นและใช้ผลลัพธ์นี้ เราจะได้ว่า การคำนวณค่าของmodulo โดยที่เพียงพอสำหรับการกำหนดและดังนั้นแม้ว่าจะไม่มีวิธีที่มีประสิทธิภาพในการคำนวณโดยตรงสำหรับ ทั่วไปแต่ก็สามารถคำนวณสำหรับจำนวนเฉพาะขนาดเล็กได้อย่างมีประสิทธิภาพ เราเลือกเป็นเซตของจำนวนเฉพาะที่แตกต่างกัน โดยที่เมื่อกำหนดให้สำหรับทุกทฤษฎีบทเศษเหลือของจีนช่วยให้เราสามารถคำนวณได้ ${\displaystyle \#E(\mathbb {F} _{q})}$${\displaystyle t}$${\displaystyle q+1-\#E(\mathbb {F} _{q})}$${\displaystyle t}$${\displaystyle N}$${\displaystyle N>4{\sqrt {q}}}$${\displaystyle t}$${\displaystyle \#E(\mathbb {F} _{q})}$${\displaystyle t{\pmod {N}}}$${\displaystyle N}$${\displaystyle t{\pmod {l}}}$${\displaystyle l}$${\displaystyle S=\{l_{1},l_{2},...,l_{r}\}}$${\displaystyle \prod l_{i}=N>4{\sqrt {q}}}$${\displaystyle t{\pmod {l_{i}}}}$${\displaystyle l_{i}\in S}$${\displaystyle t{\pmod {N}}}$

ในการคำนวณหาจำนวนเฉพาะเราใช้ทฤษฎีเอนโดมอร์ฟิซึมของโฟรเบนิอุสและพหุนามการหารโปรดทราบว่าการพิจารณาจำนวนเฉพาะนั้นไม่ใช่เรื่องเสียหาย เพราะเราสามารถเลือกจำนวนเฉพาะที่ใหญ่กว่ามาแทนที่ได้เสมอ เพื่อให้แน่ใจว่าผลคูณมีขนาดใหญ่พอ อย่างไรก็ตาม อัลกอริทึมของชูฟมักถูกนำมาใช้บ่อยที่สุดในการแก้ปัญหานี้เนื่องจากมีอัลกอริทึมที่มีประสิทธิภาพมากกว่า หรือที่เรียกว่าอัลกอริทึมแบบ adic สำหรับฟิลด์ที่มีลักษณะเฉพาะขนาดเล็ก ${\displaystyle t{\pmod {l}}}$${\displaystyle l\neq p}$${\displaystyle \phi }$${\displaystyle l\neq p}$${\displaystyle q=p}$${\displaystyle p}$

เมื่อกำหนดเส้นโค้งวงรีที่นิยามไว้บนเราจะพิจารณาจุดบนบนซึ่งเป็นการปิดเชิงพีชคณิตของกล่าวคือ เราอนุญาตให้มีจุดที่มีพิกัดอยู่ใน การแปลงฟรอเบนิอุสของบนขยายไปยังเส้นโค้งวงรีโดย ${\displaystyle E}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle E}$${\displaystyle {\bar {\mathbb {F} }}_{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle {\bar {\mathbb {F} }}_{q}}$${\displaystyle {\bar {\mathbb {F} }}_{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \phi :(x,y)\mapsto (x^{q},y^{q})}$

แผนที่นี้คือเอกลักษณ์บนและสามารถขยายไปยังจุดที่อนันต์ได้ทำให้เป็นมอร์ฟิซึมกลุ่มจากไปยังตัวมันเอง ${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle O}$${\displaystyle E({\bar {\mathbb {F} }}_{q})}$

เอนโดมอร์ฟิซึมของฟรอเบนิอุสสอดคล้องกับพหุนามกำลังสอง ซึ่งเชื่อมโยงกับจำนวนสมาชิกของเซตโดยทฤษฎีบทต่อไปนี้: ${\displaystyle E(\mathbb {F} _{q})}$

ทฤษฎีบท:เอนโดมอร์ฟิซึมของฟรอเบนิอุสที่กำหนดโดยสอดคล้องกับสมการลักษณะเฉพาะ ${\displaystyle \phi }$

${\displaystyle \phi ^{2}-t\phi +q=0,}$ที่ไหน${\displaystyle t=q+1-\#E(\mathbb {F} _{q})}$

ดังนั้นเราจึงได้ว่าสำหรับทั้งหมดที่โดยที่ + หมายถึงการบวกบนเส้นโค้งวงรี และและ หมายถึงการคูณสเกลาร์ของด้วยและของ ด้วย ตาม ลำดับ${\displaystyle P=(x,y)\in E}$${\displaystyle (x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})}$${\displaystyle q(x,y)}$${\displaystyle t(x^{q},y^{q})}$${\displaystyle (x,y)}$${\displaystyle q}$${\displaystyle (x^{q},y^{q})}$${\displaystyle t}$

เราอาจลองคำนวณจุดเหล่านี้ในเชิงสัญลักษณ์โดยใช้ฟังก์ชันในวงแหวนพิกัดของ แล้วจึงค้นหาค่าของที่สอดคล้องกับสมการ อย่างไรก็ตาม ระดับดีกรีจะสูงมาก และวิธีการนี้จึงไม่สามารถนำไปใช้ได้จริง ${\displaystyle (x^{q^{2}},y^{q^{2}})}$${\displaystyle (x^{q},y^{q})}$${\displaystyle q(x,y)}$${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)}$${\displaystyle E}$${\displaystyle t}$

แนวคิดของ Schoof คือการดำเนินการคำนวณนี้โดยจำกัดเฉพาะจุดที่มีลำดับสำหรับจำนวนเฉพาะขนาดเล็กต่างๆเมื่อกำหนดจำนวนเฉพาะคี่แล้วเราจะดำเนินการแก้ปัญหาการหาค่าซึ่งนิยามว่าสำหรับจำนวนเฉพาะที่กำหนดถ้าจุดอยู่ใน กลุ่ม ย่อยทอร์ชั่นแล้ว โดยที่คือจำนวนเต็มที่ไม่ซ้ำกันซึ่ง และสังเกตว่าและสำหรับจำนวนเต็มใดๆเราจะได้ดังนั้นจะมีลำดับเดียวกันกับดังนั้นสำหรับที่อยู่ในเราก็จะมีถ้าดังนั้นเราจึงลดปัญหาของเราลงเหลือการแก้สมการ ${\displaystyle l}$${\displaystyle l}$${\displaystyle l}$${\displaystyle t_{l}}$${\displaystyle t{\pmod {l}}}$${\displaystyle l\neq 2,p}$${\displaystyle (x,y)}$${\displaystyle l}$${\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q}}})\mid lP=O\}}$${\displaystyle qP={\bar {q}}P}$${\displaystyle {\bar {q}}}$${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$${\displaystyle \mid {\bar {q}}\mid <l/2}$${\displaystyle \phi (O)=O}$${\displaystyle r}$${\displaystyle r\phi (P)=\phi (rP)}$${\displaystyle \phi (P)}$${\displaystyle P}$${\displaystyle (x,y)}$${\displaystyle E[l]}$${\displaystyle t(x^{q},y^{q})={\bar {t}}(x^{q},y^{q})}$${\displaystyle t\equiv {\bar {t}}{\pmod {l}}}$

${\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{q},y^{q}),}$

โดยที่และมีค่าเป็นจำนวนเต็มใน. ${\displaystyle {\bar {t}}}$${\displaystyle {\bar {q}}}$${\displaystyle [-(l-1)/2,(l-1)/2]}$

พหุนามการหารลำดับที่lมีลักษณะที่รากของมันคือ พิกัด xของจุดที่มีลำดับl อย่างแม่นยำ ดังนั้น การจำกัดการคำนวณให้อยู่ที่ จุด l -torsion หมายถึงการคำนวณนิพจน์เหล่านี้เป็นฟังก์ชันในวงแหวนพิกัดของE และมอดูลัสพหุนามการหารลำดับที่l กล่าว คือ เรากำลังทำงานในซึ่งหมายความว่าโดยเฉพาะอย่างยิ่ง ดีกรีของXและ Yที่กำหนดผ่าน มีค่าอย่าง มากที่สุด 1 ในyและอย่างมากที่สุด ในx${\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$${\displaystyle (X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$${\displaystyle (l^{2}-3)/2}$

การคูณสเกลาร์สามารถทำได้โดยใช้ วิธีการ คูณสองเท่าแล้วบวกหรือโดยใช้พหุนามหารลำดับที่ th วิธีหลังให้ผลลัพธ์ดังนี้: ${\displaystyle {\bar {q}}(x,y)}$${\displaystyle {\bar {q}}}$

${\displaystyle {\bar {q}}(x,y)=(x_{\bar {q}},y_{\bar {q}})=\left(x-{\frac {\psi _{{\bar {q}}-1}\psi _{{\bar {q}}+1}}{\psi _{\bar {q}}^{2}}},{\frac {\psi _{2{\bar {q}}}}{2\psi _{\bar {q}}^{4}}}\right)}$

โดยที่เป็นพหุนามหารลำดับที่nโปรดทราบว่า เป็นฟังก์ชันในxเท่านั้น และใช้สัญลักษณ์แทน ${\displaystyle \psi _{n}}$${\displaystyle y_{\bar {q}}/y}$${\displaystyle \theta (x)}$

เราต้องแบ่งปัญหาออกเป็นสองกรณี คือ กรณีที่และกรณีที่ โปรดทราบว่าความเท่าเทียมกันเหล่านี้ตรวจสอบโดยใช้โมดูลัส ${\displaystyle (x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)}$${\displaystyle (x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)}$${\displaystyle \psi _{l}}$

โดยใช้สูตรการบวกสำหรับกลุ่มเราจะได้: ${\displaystyle E(\mathbb {F} _{q})}$

${\displaystyle X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\bar {q}}}}\right)^{2}-x^{q^{2}}-x_{\bar {q}}.}$

โปรดทราบว่าการคำนวณนี้จะล้มเหลวหากสมมติฐานเรื่องความไม่เท่ากันนั้นไม่ถูกต้อง

ตอนนี้เราสามารถใช้ พิกัด xเพื่อจำกัดตัวเลือกให้เหลือเพียงสองความเป็นไปได้ คือ กรณีบวกและกรณีลบ จากนั้นจึงใช้ พิกัด yเพื่อพิจารณาว่ากรณีใดในสองกรณีนั้นเป็นจริง ${\displaystyle {\bar {t}}}$

ขั้นแรก เราจะแสดงว่าXเป็นฟังก์ชันของxเพียงอย่างเดียว พิจารณาเนื่องจากเป็นจำนวนคู่ โดยการแทนที่ด้วยเราจึงเขียนนิพจน์ใหม่ได้เป็น ${\displaystyle (y^{q^{2}}-y_{\bar {q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/y)^{2}}$${\displaystyle q^{2}-1}$${\displaystyle y^{2}}$${\displaystyle x^{3}+Ax+B}$

${\displaystyle (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))^{2}}$

และมีสิ่งนั้น

${\displaystyle X(x)\equiv (x^{3}+Ax+B)\left({\frac {(x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x)}{x^{q^{2}}-x_{\bar {q}}}}\right)^{2}{\bmod {\psi }}_{l}(x).}$

ถ้าหากสำหรับบางคนแล้ว ก็ถือว่าน่าพอใจ ${\displaystyle X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)}$${\displaystyle {\bar {t}}\in [0,(l-1)/2]}$${\displaystyle {\bar {t}}}$

${\displaystyle \phi ^{2}(P)\mp {\bar {t}}\phi (P)+{\bar {q}}P=O}$

สำหรับ จุดบิดlทั้งหมดP

ดังที่กล่าวไว้ก่อนหน้านี้ การใช้Yและตอนนี้เราสามารถระบุได้ว่าค่าใดในสองค่าของ( หรือ) ที่ใช้ได้ผล ซึ่งจะให้ค่าของอัลกอริทึมของ Schoof จะเก็บค่าของ ไว้ในตัวแปร สำหรับจำนวนเฉพาะ lแต่ละตัวที่พิจารณา ${\displaystyle y_{\bar {t}}^{q}}$${\displaystyle {\bar {t}}}$${\displaystyle {\bar {t}}}$${\displaystyle -{\bar {t}}}$${\displaystyle t\equiv {\bar {t}}{\pmod {l}}}$${\displaystyle {\bar {t}}{\pmod {l}}}$${\displaystyle t_{l}}$

เราเริ่มต้นด้วยสมมติฐานที่ว่า. เนื่องจากlเป็นจำนวนเฉพาะคี่ จึงเป็นไปไม่ได้ที่และดังนั้น. สมการลักษณะเฉพาะให้ผลลัพธ์ว่า. และด้วยเหตุนี้ว่า. ซึ่งหมายความว่าqเป็นกำลังสองมอดูล lให้ . คำนวณในและตรวจสอบว่า. ถ้าเป็นเช่นนั้นจะขึ้นอยู่กับพิกัด y ${\displaystyle (x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)}$${\displaystyle {\bar {q}}(x,y)=-{\bar {q}}(x,y)}$${\displaystyle {\bar {t}}\neq 0}$${\displaystyle {\bar {t}}\phi (P)=2{\bar {q}}P}$${\displaystyle {\bar {t}}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}}$${\displaystyle q\equiv w^{2}{\pmod {l}}}$${\displaystyle w\phi (x,y)}$${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$${\displaystyle {\bar {q}}(x,y)=w\phi (x,y)}$${\displaystyle t_{l}}$${\displaystyle \pm 2w{\pmod {l}}}$

ถ้าqไม่ใช่กำลังสองมอดูล lหรือถ้าสมการไม่เป็นจริงสำหรับwและ ใดๆ สมมติฐานของเราที่ว่า นั้นเป็นเท็จ ดังนั้นสมการลักษณะเฉพาะให้ผลลัพธ์เป็น ${\displaystyle -w}$${\displaystyle (x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)}$${\displaystyle (x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)}$${\displaystyle t_{l}=0}$

ถ้าจำได้ การพิจารณาเบื้องต้นของเราละเว้นกรณีของเนื่องจากเราถือว่าqเป็นจำนวนคี่และโดยเฉพาะอย่างยิ่งก็ต่อเมื่อมีสมาชิกที่มีอันดับ 2 เท่านั้น ตามนิยามของการบวกในกลุ่ม สมาชิกใดๆ ที่มีอันดับ 2 จะต้องอยู่ในรูปดังนั้นก็ต่อเมื่อพหุนามมีรากในก็ต่อเมื่อ ${\displaystyle l=2}$${\displaystyle q+1-t\equiv t{\pmod {2}}}$${\displaystyle t_{2}\equiv 0{\pmod {2}}}$${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle (x_{0},0)}$${\displaystyle t_{2}\equiv 0{\pmod {2}}}$${\displaystyle x^{3}+Ax+B}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}$

 ป้อนข้อมูล: 1. เส้นโค้งวงรี${\displaystyle E=y^{2}-x^{3}-Ax-B}$ 2. จำนวนเต็มqสำหรับฟิลด์จำกัดที่มี.${\displaystyle F_{q}}$${\displaystyle q=p^{b},b\geq 1}$ ผลลัพธ์: จำนวนจุดของEหารด้วย.${\displaystyle F_{q}}$ เลือกเซตของจำนวนเฉพาะคี่Sที่ไม่มีp อยู่ใน เซตโดยกำหนดให้${\displaystyle N=\prod _{l\in S}l>4{\sqrt {q}}.}$ถ้ามิฉะนั้นคำนวณพหุนามการหาร${\displaystyle t_{2}=0}$${\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}$${\displaystyle t_{2}=1}$${\displaystyle \psi _{l}}$ การคำนวณทั้งหมดในลูปด้านล่างดำเนินการในริง${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).}$For do : ${\displaystyle l\in S}$ให้ เป็นจำนวนเต็มที่ไม่ซ้ำกัน${\displaystyle {\bar {q}}}$ซึ่ง และคำนวณ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$${\displaystyle \mid {\bar {q}}\mid <l/2}$, และถ้าแล้วคำนวณ${\displaystyle (x^{q},y^{q})}$${\displaystyle (x^{q^{2}},y^{q^{2}})}$${\displaystyle (x_{\bar {q}},y_{\bar {q}})}$สำหรับdo : ถ้าแล้วถ้าแล้วมิฉะนั้น มิฉะนั้นถ้าqเป็นกำลังสองมอดูล l แล้วคำนวณwด้วยคำนวณถ้าแล้วมิฉะนั้น ถ้าแล้วมิฉะนั้นมิฉะนั้น ใช้ ทฤษฎีบทเศษเหลือ ของจีนเพื่อคำนวณtมอดูลN จากสมการโดยที่${\displaystyle x^{q^{2}}\neq x_{\bar {q}}}$${\displaystyle (X,Y)}$${\displaystyle 1\leq {\bar {t}}\leq (l-1)/2}$${\displaystyle X=x_{\bar {t}}^{q}}$${\displaystyle Y=y_{\bar {t}}^{q}}$${\displaystyle t_{l}={\bar {t}}}$${\displaystyle t_{l}=-{\bar {t}}}$${\displaystyle q\equiv w^{2}{\pmod {l}}}$${\displaystyle w(x^{q},y^{q})}$${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})}$${\displaystyle t_{l}=2w}$${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})}$${\displaystyle t_{l}=-2w}$${\displaystyle t_{l}=0}$${\displaystyle t_{l}=0}$${\displaystyle t\equiv t_{l}{\pmod {l}}}$${\displaystyle l\in S}$ เอาต์พุต​ ${\displaystyle q+1-t}$

การคำนวณส่วนใหญ่เกิดขึ้นจากการประเมินค่าของและสำหรับจำนวนเฉพาะแต่ละตัวนั่นคือการคำนวณ, , , สำหรับจำนวนเฉพาะแต่ละตัวซึ่งเกี่ยวข้องกับการยกกำลังในริงและต้องใช้การคูณ เนื่องจากดีกรีของคือแต่ละองค์ประกอบในริงจึงเป็นพหุนามดีกรีตามทฤษฎีบทจำนวนเฉพาะมีจำนวนเฉพาะขนาด ประมาณ ซึ่งทำให้ได้ว่าและเราได้ว่าดังนั้นการคูณแต่ละครั้งในริงต้องใช้การคูณซึ่งต้องใช้การดำเนินการบิต ในทั้งหมด จำนวนการดำเนินการบิตสำหรับจำนวนเฉพาะแต่ละตัวคือเนื่องจากการคำนวณนี้ต้องดำเนินการสำหรับจำนวนเฉพาะแต่ละตัว ความซับซ้อนโดยรวมของอัลกอริทึมของ Schoof จึงกลายเป็นการใช้เลขคณิตพหุนามและจำนวนเต็มที่รวดเร็วจะลดความซับซ้อนนี้เหลือ ${\displaystyle \phi (P)}$${\displaystyle \phi ^{2}(P)}$${\displaystyle l}$${\displaystyle x^{q}}$${\displaystyle y^{q}}$${\displaystyle x^{q^{2}}}$${\displaystyle y^{q^{2}}}$${\displaystyle l}$${\displaystyle R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$${\displaystyle O(\log q)}$${\displaystyle \psi _{l}}$${\displaystyle {\frac {l^{2}-1}{2}}}$${\displaystyle O(l^{2})}$${\displaystyle O(\log q)}$${\displaystyle O(\log q)}$${\displaystyle l}$${\displaystyle O(\log q)}$${\displaystyle O(l^{2})=O(\log ^{2}q)}$${\displaystyle R}$${\displaystyle O(\log ^{4}q)}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle O(\log ^{2}q)}$${\displaystyle l}$${\displaystyle O(\log ^{7}q)}$${\displaystyle O(\log q)}$${\displaystyle O(\log ^{8}q)}$${\displaystyle {\tilde {O}}(\log ^{5}q)}$

ในช่วงทศวรรษ 1990 โนอัม เอลคีส์และต่อมาเอโอแอล แอตกิน ได้ คิดค้นการปรับปรุงอัลกอริทึมพื้นฐานของชูฟ โดยจำกัดเซตของจำนวนเฉพาะที่พิจารณาก่อนหน้านี้ให้เหลือเฉพาะจำนวนเฉพาะประเภทหนึ่ง ซึ่งต่อมาเรียกว่าจำนวนเฉพาะเอลคีส์และจำนวนเฉพาะแอตกิน ตามลำดับ จำนวนเฉพาะเรียกว่าจำนวนเฉพาะเอลคีส์ ถ้าสมการลักษณะเฉพาะ: แยกออกได้เหนือในขณะที่จำนวนเฉพาะแอตกินคือจำนวนเฉพาะที่ไม่ใช่จำนวนเฉพาะเอลคีส์ แอตกินแสดงให้เห็นวิธีการรวมข้อมูลที่ได้จากจำนวนเฉพาะแอตกินกับข้อมูลที่ได้จากจำนวนเฉพาะเอลคีส์เพื่อสร้างอัลกอริทึมที่มีประสิทธิภาพ ซึ่งต่อมาเป็นที่รู้จักในชื่ออัลกอริทึมชูฟ-เอลคีส์-แอตกินปัญหาแรกที่ต้องแก้ไขคือการพิจารณาว่าจำนวนเฉพาะที่กำหนดให้เป็นจำนวนเฉพาะเอลคีส์หรือแอตกิน ในการทำเช่นนั้น เราใช้พหุนามมอดูลาร์ ซึ่งมาจากการศึกษาฟอร์มมอดูลาร์และการตีความเส้นโค้งวงรีเหนือจำนวนเชิงซ้อนเป็นแลตทิซ เมื่อเรากำหนดได้แล้วว่าเราอยู่ในกรณีใด แทนที่จะใช้พหุนามหารเราสามารถใช้พหุนามที่มีดีกรีต่ำกว่าพหุนามหารที่สอดคล้องกันได้แทนที่จะ ใช้พหุนาม หาร เพื่อการใช้งานที่มีประสิทธิภาพ จะใช้อัลกอริธึมการหาค่ารากแบบความน่าจะเป็น ซึ่งทำให้เป็นอัลกอริธึมลาสเวกัสแทนที่จะเป็นอัลกอริธึมแบบกำหนด ภายใต้สมมติฐานเชิงอนุมานว่าประมาณครึ่งหนึ่งของจำนวนเฉพาะจนถึงขอบเขตที่กำหนดเป็นจำนวนเฉพาะเอลกีส์ จะได้อัลกอริธึมที่มีประสิทธิภาพมากกว่าของชูฟ โดยมีเวลาการทำงานที่คาดหวังคือ เมื่อใช้เลขคณิตแบบง่าย และเมื่อใช้เลขคณิตแบบเร็ว แม้ว่าสมมติฐานเชิงอนุมานนี้จะเป็นที่ทราบกันว่าใช้ได้กับเส้นโค้งวงรีส่วนใหญ่ แต่ก็ไม่เป็นที่ทราบกันว่าใช้ได้ในทุกกรณี แม้ภายใต้GRHก็ตาม ${\displaystyle S=\{l_{1},\ldots ,l_{s}\}}$${\displaystyle l}$${\displaystyle \phi ^{2}-t\phi +q=0}$${\displaystyle \mathbb {F} _{l}}$${\displaystyle O(l)}$${\displaystyle O(l^{2})}$${\displaystyle O(\log q)}$${\displaystyle O(\log ^{6}q)}$${\displaystyle {\tilde {O}}(\log ^{4}q)}$

ไมค์ สก็อตต์ ได้เขียนโปรแกรมอัลกอริธึมหลายตัวด้วยภาษาC++โปรแกรมเหล่านี้ใช้งานได้ฟรี (ไม่มีข้อกำหนดและเงื่อนไขใดๆ) และใช้ ไลบรารี MIRACLซึ่งเผยแพร่ภายใต้ลิขสิทธิ์ AGPLv3

• การนำอัลกอริทึมของ Schoof มาใช้กับจำนวนเฉพาะ${\displaystyle E(\mathbb {F} _{p})}$${\displaystyle p}$
• การนำอัลกอริทึมของ Schoof ไป ใช้สำหรับ.${\displaystyle E(\mathbb {F} _{2^{m}})}$

• การเข้ารหัสเส้นโค้งวงรี
• การนับจุดบนเส้นโค้งวงรี
• พหุนามหาร
• เอนโดมอร์ฟิซึมของฟรอเบนิอุส