Legendre Symbol Breakthrough in ECC

If we can tell if a scalar for a point is less than half its order, that pretty much ruins the curve. The whole security of elliptic curve cryptography is based on how hard it is to solve the ECDLP. If a method can reliably predict whether that scalar k is below n/2 just from point Q's coordinates, it’s like having a "bit oracle".

I've made a version that runs on secp256k1.

Doesn't work for Puzzle 135 though. It’s all about those little toy curves. On secp256k1, even if you know the private key is under 2^135, the points Q=k·G look just like any others. The x,y coordinates aren’t gonna give away if k is in the first half of anything.

So, if this actually worked, wouldn't the discoverer use it for something more serious than just puzzles?

One million bucks for Puzzle 135 is still a steal compared to cracking a real 2²⁵⁶ key. By the way, did you ever try using an actual Bitcoin key longer than 120 bits?

A million bucks is nothing compared to what we’re discussing. If someone could actually solve ECDLP, they'd keep it under wraps or make sure no one knows about it.

Every point on a curve has two valid halves. This technique could help find the right half. A 2^256 key can be cracked in 256 steps using this method.

Totally agree. If it could work on real 2^256 keys, it’d be way more valuable than any puzzle. I want it to work too, but real Bitcoin keys are a whole different level compared to Puzzle 135.

Have you actually tested this out? What’s your operations per second like?

✅ Done at Step 128. Here’s my calculation string: (lots of calculations)!

Have you attempted Puzzle 135? If you can solve 130 in a second, 135 should be a walk in the park.

If I say my kidnapping won’t take long, it’s important I come across as a joker, just saying.

I ran your claim through tests. Results: Your toy curve had 98.5% accuracy pretty good! But secp256k1 only hit 49%. That’s basically a coin toss.

For your curve (p=79, n=67), accuracy was 100%. But yeah, that was just a joke.

Alright, I’ll challenge you. Create a 100% successful example for any curve larger than 79 where a=0 and b=7, and where the order is prime.

True, I messed up with k <= 33 instead of k <= 34. It was an off-by-one mistake.

But hitting 100% accuracy on a small curve by hand-crafting the decision tree isn’t impressive. That’s just enumeration, not real algorithm work.

You claimed to break ECC. Now you have to show it can scale. Reference curve y² = x³ + 7 with prime order is p=127, n=127. Show us your oracle for that.

Claiming there’s no adaptive method for secp256k1 is just speculation. No one has done it yet. I’ll wait for a new example.

Thanks for the feedback. I know the example curve is small, but this attack isn’t like traditional ECDLP solvers.