# RareSkills Authors - Elliptic Curves Over Finite Field (Highlights)  ## Metadata **Review**:: [readwise.io](https://readwise.io/bookreview/38664717) **Source**:: #from/readwise #from/reader **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[RareSkills Authors]] **Full Title**:: Elliptic Curves Over Finite Field **Category**:: #articles #readwise/articles **Category Icon**:: 📰 **URL**:: [www.rareskills.io](https://www.rareskills.io/post/elliptic-curves-finite-fields) **Host**:: [[www.rareskills.io]] **Highlighted**:: [[2024-03-14]] **Created**:: [[2024-03-16]] ## Highlights - Not every x value will result in an integer for the y value when we solve the equation, so no point will be present at that value for x. ([View Highlight](https://read.readwise.io/read/01hry8zgb65vjbhpng7mt0f7jv)) ^692644241 - We established in the previous article that elliptic curve points with the “connect and flip” operation are a group. When we do this over a finite field, it remains a group, but it becomes a cyclic group, which is tremendously useful for our application. ([View Highlight](https://read.readwise.io/read/01hry92mgmzqk1yf6h0t1jeay0)) ^692644457 - In a finite field, the inverse of an element is the number you multiply it with to get the finite field element 1. For example, in modulo 23, 6 is the inverse of 4 because when you multiply them together modulo 23, you get 1. When the order of the field is prime, every number except zero has an inverse. ([View Highlight](https://read.readwise.io/read/01hry99n9282f7m8mmcabwkaz7)) ^692645293 - We use the [Tonelli Shanks Algorithm](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) to compute modular square roots. ([View Highlight](https://read.readwise.io/read/01hry9cejhgfxr51rhdvfskf4n)) ^692645435 - from libnum import has_sqrtmod_prime_power ([View Highlight](https://read.readwise.io/read/01hry9j0bmwtwks33w62mdd0c5)) ^692646557 - Although we use square roots to determine if a point is on the curve, and square roots are not a valid field operator, we do not use square roots to compute the addition and doubling of points. ([View Highlight](https://read.readwise.io/read/01hry9qnj0pd8xvxg9v0v9wkfr)) ^692647454 - We can assign each point a “number” based on how many times we added the generator to itself to arrive at that point. ([View Highlight](https://read.readwise.io/read/01hry9vwvf10bchngwcrn2t056)) ^692650516 - Here is an interesting observation: note that points that share the same x-value add up to 12, which corresponds to the identity element (12 mod 11 = 1). If we add the point (4, 1), which is point 11 in our plot to (4, 10), we will get the point at in infinity, which would be the 12th element in the group. ([View Highlight](https://read.readwise.io/read/01hrya34tg0se0svfxyznmgqtw)) ^692652648 - There is no such thing as elliptic curve point multiplication. When we say “scalar multiplication” we really mean repeated addition. ([View Highlight](https://read.readwise.io/read/01hrya6kpfcddv5nmk6yxcxdwf)) ^692652864 - The field modulus is the modulo we do the curve over. The curve order is the number of points on the curve. ([View Highlight](https://read.readwise.io/read/01hryae6sy8eecq8f24gsy36qd)) ^692653478 Number of additions wraps around curve order. - However, in a finite field, 1/2 can be meaningfully computed as the multiplicative inverse of 2. Therefore, 5 / 2 can be encoded as 5 * inv(2). Here’s how we can do it in python ([View Highlight](https://read.readwise.io/read/01hryaghzxqt2g3wrx0b4gfjqv)) ^692653640 - multiply((order - x) * G1) == neg(multiply(G1, x)) ([View Highlight](https://read.readwise.io/read/01hryasjas9hhy098b54cg7e1e)) ^692655369 - It turns out, computing the number of points can be done in polynomial time with [Shoof’s Algorithm](https://en.wikipedia.org/wiki/Schoof%27s_algorithm). ([View Highlight](https://read.readwise.io/read/01hryb0t50hk3k2y1b8v5745zk)) ^692656083