Schoof's algorithm: Difference between revisions

Revision as of 13:19, 18 May 2016

Revision as of 09:00, 12 July 2016

Line 141:

{{nowrap|<math>t_{l}=0</math>}}

Use the [[Chinese Remainder Theorem]] to compute {{mvar|t}} modulo {{mvar|N}}.

Output <math>q+1-t</math>.

Note that since the set {{mvar|S}} was chosen so that <math>N>4\sqrt{q}</math>, by Hasse's theorem, we in fact know {{mvar|t}} and <math> \sharp E(\mathbb{F}_{q}) = q+1-t</math> precisely.

==Complexity==