Schoof’s point-counting algorithm - Revision history

Rational Point: /* Main plan of attack */

2025-02-13T05:31:49Z

Main plan of attack

← Older revision		Revision as of 05:31, 13 February 2025
Line 6:		Line 6:
	== Main plan of attack ==		== Main plan of attack ==

	A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime order ''q''.		A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime order and characteristic ''q''.

	The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q'''''Z'''</sub>.		The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q'''''Z'''</sub>.

Rational Point: over a finite field

2025-02-13T05:30:37Z

over a finite field

← Older revision		Revision as of 05:30, 13 February 2025
Line 1:		Line 1:
	'''René Schoof's point counting algorithm''' <ref>René Schoof. ''Mathematics of Computation,'' vol. 44. no. 170		'''René Schoof's point counting algorithm''' <ref>René Schoof. ''Mathematics of Computation,'' vol. 44. no. 170
	April 1985. pp. 483–494. https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777280-6/S0025-5718-1985-0777280-6.pdf</ref> determines the exact number of points on an elliptic curve within the range determined by [[Hasse’s theorem]].		April 1985. pp. 483–494. https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777280-6/S0025-5718-1985-0777280-6.pdf</ref> determines the exact number of points on an elliptic curve over a finite field within the range determined by [[Hasse’s theorem]].

	The algorithm is claimed to run in polynomial time. It is alarming, or should be, to users of cryptographic schemes that depend on the difficulty of solving the discrete [[logarithm problem]] over elliptic curves, that a problem once requiring baby-step giant-step or similar algorithms was suddenly solved in polynomial time.		The algorithm is claimed to run in polynomial time. It is alarming, or should be, to users of cryptographic schemes that depend on the difficulty of solving the discrete [[logarithm problem]] over elliptic curves, that a problem once requiring baby-step giant-step or similar algorithms was suddenly solved in polynomial time.

Rational Point: /* Main plan of attack */ order

2025-02-13T05:27:48Z

Main plan of attack: order

← Older revision		Revision as of 05:27, 13 February 2025
Line 6:		Line 6:
	== Main plan of attack ==		== Main plan of attack ==

	A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime ~~characteristic~~ ''q''.		A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime order ''q''.

	The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q'''''Z'''</sub>.		The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q'''''Z'''</sub>.

Rational Point: /* Main plan of attack */ "Z/qZ"

2025-02-13T05:21:00Z

Main plan of attack: "Z/qZ"

← Older revision		Revision as of 05:21, 13 February 2025
Line 8:		Line 8:
	A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime characteristic ''q''.		A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime characteristic ''q''.

	The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q''</sub>.		The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q'''''Z'''</sub>.

	The main idea presented by René Schoof is to solve this characteristic equation modulo ℓ for each of the small primes ℓ, and then combine the solutions using the [[Chinese remainder theorem]] to determine ''t'' uniquely within the range <nowiki>[</nowiki>‑2''g''√''q'',2''g''√''q''<nowiki>]</nowiki> so that ♯''E''<sub>'''Z'''/''q''</sub> = ''q'' + 1 ‑ ''t''.		The main idea presented by René Schoof is to solve this characteristic equation modulo ℓ for each of the small primes ℓ, and then combine the solutions using the [[Chinese remainder theorem]] to determine ''t'' uniquely within the range <nowiki>[</nowiki>‑2''g''√''q'',2''g''√''q''<nowiki>]</nowiki> so that ♯''E''<sub>'''Z'''/''q'''''Z'''</sub> = ''q'' + 1 ‑ ''t''.

	== Schoof–Elkies–Atkin (SEA) ==		== Schoof–Elkies–Atkin (SEA) ==

Rational Point: /* Main plan of attack */

2025-02-11T22:26:50Z

Main plan of attack

← Older revision		Revision as of 22:26, 11 February 2025
Line 8:		Line 8:
	A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime characteristic ''q''.		A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime characteristic ''q''.

	The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q''</sub>		The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q''</sub>.

	The main idea presented by René Schoof is to solve this characteristic equation modulo ℓ for each of the small primes ℓ, and then combine the solutions using the [[Chinese remainder theorem]] to determine ''t'' uniquely within the range <nowiki>[</nowiki>‑2''g''√''q'',2''g''√''q''<nowiki>]</nowiki> so that ♯''E''<sub>'''Z'''/''q''</sub> = ''q'' + 1 ‑ ''t''.		The main idea presented by René Schoof is to solve this characteristic equation modulo ℓ for each of the small primes ℓ, and then combine the solutions using the [[Chinese remainder theorem]] to determine ''t'' uniquely within the range <nowiki>[</nowiki>‑2''g''√''q'',2''g''√''q''<nowiki>]</nowiki> so that ♯''E''<sub>'''Z'''/''q''</sub> = ''q'' + 1 ‑ ''t''.

Rational Point: Main plan of attack

2025-02-11T22:26:18Z

Main plan of attack

← Older revision		Revision as of 22:26, 11 February 2025
Line 2:		Line 2:
	April 1985. pp. 483–494. https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777280-6/S0025-5718-1985-0777280-6.pdf</ref> determines the exact number of points on an elliptic curve within the range determined by [[Hasse’s theorem]].		April 1985. pp. 483–494. https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777280-6/S0025-5718-1985-0777280-6.pdf</ref> determines the exact number of points on an elliptic curve within the range determined by [[Hasse’s theorem]].

	The algorithm ~~runs~~ in polynomial time. It is alarming, or should be, to users of cryptographic schemes that depend on the difficulty of solving the discrete [[logarithm problem]] over elliptic curves, that a problem once requiring baby-step giant-step or similar algorithms was suddenly solved in polynomial time.		The algorithm is claimed to run in polynomial time. It is alarming, or should be, to users of cryptographic schemes that depend on the difficulty of solving the discrete [[logarithm problem]] over elliptic curves, that a problem once requiring baby-step giant-step or similar algorithms was suddenly solved in polynomial time.

			== Main plan of attack ==

			A collection of distinct small primes is chosen, enough that their product exceeds the range of 4''g''√''q'' determined by [[Hasse’s theorem]], depending on the [[genus]] ''g'' of the curve ''E'' over the field of prime characteristic ''q''.

			The [[Frobenius endomorphism]] ''φ'' : (''x'',''y'') → (''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup> ‑ ''tφ'' + ''q'' = 0 with ''t'' = ''q'' + 1 ‑ ♯''E''<sub>'''Z'''/''q''</sub>

			The main idea presented by René Schoof is to solve this characteristic equation modulo ℓ for each of the small primes ℓ, and then combine the solutions using the [[Chinese remainder theorem]] to determine ''t'' uniquely within the range <nowiki>[</nowiki>‑2''g''√''q'',2''g''√''q''<nowiki>]</nowiki> so that ♯''E''<sub>'''Z'''/''q''</sub> = ''q'' + 1 ‑ ''t''.

			== Schoof–Elkies–Atkin (SEA) ==

	[https://en.wikipedia.org/wiki/Schoof%E2%80%93Elkies%E2%80%93Atkin_algorithm Schoof–Elkies–Atkin (SEA)] is an improved variant which is much more efficient, of Las Vegas type expected termination.		[https://en.wikipedia.org/wiki/Schoof%E2%80%93Elkies%E2%80%93Atkin_algorithm Schoof–Elkies–Atkin (SEA)] is an improved variant which is much more efficient, of Las Vegas type expected termination.

Rational Point: Rational Point moved page Schoof’s point counting algorithm to Schoof’s point-counting algorithm: Misspelled title: hyphenate

2025-02-10T02:32:07Z

Rational Point moved page Schoof’s point counting algorithm to Schoof’s point-counting algorithm: Misspelled title: hyphenate

← Older revision	Revision as of 02:32, 10 February 2025
(No difference)

Rational Point: Rational Point moved page Schoof's point counting algorithm to Schoof’s point counting algorithm: Misspelled title

2025-02-08T08:31:20Z

Rational Point moved page Schoof's point counting algorithm to Schoof’s point counting algorithm: Misspelled title

← Older revision	Revision as of 08:31, 8 February 2025
(No difference)

Rational Point: sources

2025-02-08T08:29:23Z

sources

New page

'''René Schoof's point counting algorithm''' <ref>René Schoof. ''Mathematics of Computation,'' vol. 44. no. 170
April 1985. pp. 483–494. https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777280-6/S0025-5718-1985-0777280-6.pdf</ref> determines the exact number of points on an elliptic curve within the range determined by [[Hasse’s theorem]].

The algorithm runs in polynomial time. It is alarming, or should be, to users of cryptographic schemes that depend on the difficulty of solving the discrete [[logarithm problem]] over elliptic curves, that a problem once requiring baby-step giant-step or similar algorithms was suddenly solved in polynomial time.

[https://en.wikipedia.org/wiki/Schoof%E2%80%93Elkies%E2%80%93Atkin_algorithm Schoof–Elkies–Atkin (SEA)] is an improved variant which is much more efficient, of Las Vegas type expected termination.

Such an easy method of calculating the order of an elliptic curve over a finite field, that is, the exact number of points on it, might lead to easy solutions for the discrete [[logarithm problem]] in general, and we should assume this to be the case, especially in light of redactions of published information from certain European axis-aligned non-U.S. and “ex-pat” sources, unless there are good explanations why this is not so.

[[Elliptic Curve Crypto:General disclaimer]].