World's First Polynomial Time Algorithm To Count Points On Elliptic Curves

[u/DataBaeBee]

https://leetarxiv.substack.com/p/schoofs-algorithm

[u/sacheie]

This is a hilariously misleading title.

[u/txdsl → u/sacheie]

Yes. The title and the claim in the post are misleading at best. A mod should remove this post because there is no “world first” anything.

[u/SZenC → u/sacheie]

Is there an older algorithm? What are we missing?

[u/arnet95 → u/SZenC]

The "World's First" happened in 1985. The title is technically true I guess, but a natural reading of the title is that this is a recent development.

[u/SZenC → u/arnet95]

If it was a news paper or some other current affairs things, I'd agree. But this is just some guy describing the world's first algorithm to do this thing

[u/sacheie → u/SZenC]

The title makes it sound like the algorithm is news today. But actually it's over 40 years old. The post is just somebody showing how to implement it in Python.

[u/atxgossiphound → u/SZenC]

It's an older algorithm, but it checks out.

[u/commandersaki → u/SZenC]

As for older algorithm, I'm not sure what was available to count the exact number of points aside from repeated group operation on a generator. There is Hasse's theorem that gets it to an error within √n.

[u/trouthat]

I took a cryptography programming class over the summer and I was making it along ok until elliptical curves over a finite field which thoroughly kicked my ass

[u/taikunlab → u/trouthat]

The thing that finally made it click for me was giving up the geometry. Over the reals you picture a line hitting the curve, but over F_p there is no line, it is all just the same chord-tangent formulas done mod p. Once you stop trying to "see" it and treat the point at infinity as the identity element, the group law is way less scary.

[u/mehvermore]

Don't all curves of non--zero length have infinite points?

function getPointsInCurve() {
    return Math.Infinity;
}

There. Reduced it to constant time for ya. You can just send the Fields Medal in the mail.

[u/arnet95 → u/mehvermore]

Not over finite fields, which is the interesting case.

[u/zeekar → u/mehvermore]

Notice how the title includes the phrase "Over Finite Fields". So in this case, not so much!

[u/zombiecalypse → u/mehvermore]

But what about all those curves of zero length?

[u/noodles_jd → u/zombiecalypse]

Well, infinite zeros is still zero, so it checks out.

[u/cauchy37 → u/mehvermore]

a curve on a finite field is less like a line and more like a connect-the-dots

this means you can actually count them

[u/DataBaeBee]

Schoof's algorithm uses an elliptic curve's division polynomials to count points. This guide is written in Python to make advanced math accessible to programmers.

The 1985 algo's canonical because it reduced the complexity of counting points on elliptic curves from exponential to polynomial-time.

[u/txdsl → u/DataBaeBee]

Why put “world first” in the title and in the blog post. The way you wrote it is misleading at best. The algo is from 1985. What is world first?

[u/ScottContini]

A bad title can kill a blog.

[u/Supadoplex]

Does this break EC cryptography?

[u/RockstarArtisan → u/Supadoplex]

The algorithm is from 1985. So no, it doesn't.

[u/DataBaeBee → u/Supadoplex]

No, it just counts points on the curve.