Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: AlexanderCurl on November 14, 2022, 11:25:36 AM



Title: Even or Odd Point
Post by: AlexanderCurl on November 14, 2022, 11:25:36 AM
A-one.


Title: Re: Even or Odd Point
Post by: _Counselor on November 14, 2022, 12:55:50 PM
So, to test number N you need N+2 add/sub operations.
Isn't it easier to just iterate over all the points from 1 to N? :)


Title: Re: Even or Odd Point
Post by: PrivatePerson on November 14, 2022, 08:24:15 PM
How can knowledge of an even or odd point help in hacking secp256k1?


Title: Re: Even or Odd Point
Post by: NotATether on November 15, 2022, 06:55:11 PM
So, to test number N you need N+2 add/sub operations.

Yeah, except the points are in random order so you have no way of knowing how far from the median the point is - which would imply that the computation would be faster.

This is still going to be prohibitively expensive for large N. It is O(n). Any method with a runtime greater than O(log N) is not going to be practical in cryptography.


Title: Re: Even or Odd Point
Post by: CrunchyF on November 17, 2022, 02:39:31 PM

here you only need to know the range where point is and find the right sequence of powers of 2 down.
This method also computationally quite hard. for example for puzzle #120 the sequence will  be around 46 values if you put lower 2^30 in bloomfilter.



Alexander, can u explain how you arrive to a sequence of 46 values of power of 2 with a bloomfilter of size 2^30 for puzzle 120?
Thanks


Title: Re: Even or Odd Point
Post by: CrunchyF on November 17, 2022, 03:54:24 PM

here you only need to know the range where point is and find the right sequence of powers of 2 down.
This method also computationally quite hard. for example for puzzle #120 the sequence will  be around 46 values if you put lower 2^30 in bloomfilter.



Alexander, can u explain how you arrive to a sequence of 46 values of power of 2 with a bloomfilter of size 2^30 for puzzle 120?
Thanks

46  is approximately. i cannot of course know it exactly.
here is the code. you can test any secp256k1 range value.
the same will be with point operations.
p=120 # 2^120
puzzle = 1231052970201832551532555186137109517 #value to test

pows = [2**0,2**1,2**2,2**3,2**4,2**5,2**6,2**7,2**8,2**9,
        2**10,2**11,2**12,2**13,2**14,2**15,2**16,2**17,2**18,2**19,
        2**20,2**21,2**22,2**23,2**24,2**25,2**26,2**27,2**28,2**29,
        2**30,2**31,2**32,2**33,2**34,2**35,2**36,2**37,2**38,2**39,
        2**40,2**41,2**42,2**43,2**44,2**45,2**46,2**47,2**48,2**49,
        2**50,2**51,2**52,2**53,2**54,2**55,2**56,2**57,2**58,2**59,
        2**60,2**61,2**62,2**63,2**64,2**65,2**66,2**67,2**68,2**69,
        2**70,2**71,2**72,2**73,2**74,2**75,2**76,2**77,2**78,2**79,
        2**80,2**81,2**82,2**83,2**84,2**85,2**86,2**87,2**88,2**89,
        2**90,2**91,2**92,2**93,2**94,2**95,2**96,2**97,2**98,2**99,
        2**100,2**101,2**102,2**103,2**104,2**105,2**106,2**107,2**108,2**109,
        2**110,2**111,2**112,2**113,2**114,2**115,2**116,2**117,2**118,2**119,
        2**120,2**121,2**122,2**123,2**124,2**125,2**126,2**127,2**128,2**129,
        2**130,2**131,2**132,2**133,2**134,2**135,2**136,2**137,2**138,2**139,
        2**140,2**141,2**142,2**143,2**144,2**145,2**146,2**147,2**148,2**149,
        2**150,2**151,2**152,2**153,2**154,2**155,2**156,2**157,2**158,2**159,
        2**160,2**161,2**162,2**163,2**164,2**165,2**166,2**167,2**168,2**169,
        2**170,2**171,2**172,2**173,2**174,2**175,2**176,2**177,2**178,2**179,
        2**180,2**181,2**182,2**183,2**184,2**185,2**186,2**187,2**188,2**189,
        2**190,2**191,2**192,2**193,2**194,2**195,2**196,2**197,2**198,2**199,
        2**200,2**201,2**202,2**203,2**204,2**205,2**206,2**207,2**208,2**209,
        2**210,2**211,2**212,2**213,2**214,2**215,2**216,2**217,2**218,2**219,
        2**220,2**221,2**222,2**223,2**224,2**225,2**226,2**227,2**228,2**229,
        2**230,2**231,2**232,2**233,2**234,2**235,2**236,2**237,2**238,2**239,
        2**240,2**241,2**242,2**243,2**244,2**245,2**246,2**247,2**248,2**249,
        2**250,2**251,2**252,2**253,2**254,2**255,2**256]

pattern = []
p = 120
puzzle = 1231052970201832551532555186137109517
print(f'Puzzle: {puzzle}')
p = p - 1
act1 = puzzle - pows[p]
print(f'{puzzle} - {pows[p]} = {act1}')
p = p - 1
counter = 0
while p > 0:
    if act1 < pows[p]:
        p = p - 1
        continue
    else:
        counter += 1
        save = act1
        act1 -= pows[p]
        print(f'{counter}: {save} - {pows[p]} = {act1} power=[{p}]')
        pattern.append(p)
        p = p - 1
s = ''
for p in pattern:
    s += 'p' + str(p) + ','
print(s)

the actual code to achieve that i will not share. guess anyone with coding skills can do it from this explanation alone.
it will require good knowledge of combinatorics in order to try it.


Ok maybe I understand.
46 is the average length of the power of 2 sequence? that's right?