Title: Puzzle Factorization Post by: iceland2k14 on July 14, 2024, 11:27:53 AM For the BTC Puzzle https://bitcointalk.org/index.php?topic=5218972.0 (https://bitcointalk.org/index.php?topic=5218972.0) to try the possibility of simplification using the probabilistic approach.
If we start analyzing all the Found Keys we see that most of them are NOT PRIME. https://www.talkimg.com/images/2024/07/14/oqq9l.jpeg So instead of blind bruteforcing we could try to find the maximum likelihood range. This off course may not work for each of the remaining puzzle but if we see them together as a whole there seems to be a way of approach for many of them. Privatekey being a composite number will have several factors. We are not interested in the Prime Factors but instead all the possible factors. Because once we have (somehow) a factor of the privatekey then the difficulty of that Key is reduced. Before thinking about how we can get a factor of the unknown Key, Lets analyze this concept in the already Found Keys first. There are some interesting observation. Some Keys are hopeless and have very less number of factors but some Keys are juicy and have a factor in almost all bit. https://www.talkimg.com/images/2024/07/14/oqxzm.png If we looks closely in every 10 Keys there is definitely 1 or more juicy Key present. Another observation is we are looking for Factors which are not very small and not very big. Small factor will leave rest of Key bruteforcing almost same level and Big Factor finding itself is a huge challenge. The Best is if the factor is somewhere in closer to the mid level of the Key. So again lets try for this search in existing Keys. https://www.talkimg.com/images/2024/07/14/o0AZH.png Here if we look for Factors closer to Q1 then we have much narrower range to search for. The same thing can be also observed in Q2 or Q3. Now if we use this range of -10 to 25% of distance for the closest factor and check the same in existing Keys, we can validate that we would have found these puzzles as shown in transparent lines. The beauty of big mid factor is that second factor will also be closer to similar strength and will help in search range limit. https://www.talkimg.com/images/2024/07/14/o0ndd.png Applying the same idea to the remaining Puzzles becomes interesting as the reduction in difficulty level would be significant. https://www.talkimg.com/images/2024/07/14/o0Gl2.png Note: 1. This whole analysis is to focus on the most relevant range, if you do not want to search for everything (hardware or time shortage) 2. If we still have to scan through all the factors and for each Factor all the Keys, then there is no gain in the search 2. For the Pubkey Kangaroo search the overhead of switching factors range would soon overpower the advantage of stride search of Keys Title: Re: Puzzle Factorization Post by: CY4NiDE on July 16, 2024, 01:55:26 AM So if I understood correctly since at least 1 key in a group of ~10 keys probably has factors in almost every lower bit range, we can attempt to reduce the size of the problem by carefully choosing the bit range of the stride values in relation to the keys we are targeting. We can limit the amount of possible values we need to brute force through (stride range is not too big) while still enabling the program to traverse a key space in minimal time (stride value is not too small) thus maximizing the amount of candidates being checked per time unit while drastically reducing the size of the set. We are now searching for a stride value in a much smaller bit range, albeit slower (and there could be more than one value that opens the doors for us, or none).
I like it. This is my current approach: Code: import argparse It's currently taking me 120 seconds to check two ~36 bit stride values against puzzles 66-76 using two GPUs. Does anyone know of another CUDA based program other than BitCrack that has the stride option? Title: Re: Puzzle Factorization Post by: GR Sasa on July 23, 2024, 07:00:23 PM Hello,
i tried puzzle factoring and took for testing purposes puzzle 64. Code: 64 | 000000000000000000000000000000000000000000000000F7051F27B09112D4 | 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN | 03100611c54dfef604163b8358f7b7fac13ce478e02cb224ae16d45526b25d9d4d Since the private key for #64 is known, i used some websites to get its factor and did a test for puzzle 64. I used the following strides, and surprisingly i don't know the reason why it didn't catch the private key even though i subtract 1 because of the starting private key, still didn't hit. ??? Possible_Strides_For_Puzzle_64: Code: 124 544615 496846 None of those strides worked, so i must have did a mistake? Would be nice having your opinions. Title: Re: Puzzle Factorization Post by: madogss on July 25, 2024, 12:16:33 AM Hello, don't know if this would work but have you tried turning them into hex form by that i mean consider those strides as decimal and not hex i tried puzzle factoring and took for testing purposes puzzle 64. Code: 64 | 000000000000000000000000000000000000000000000000F7051F27B09112D4 | 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN | 03100611c54dfef604163b8358f7b7fac13ce478e02cb224ae16d45526b25d9d4d Since the private key for #64 is known, i used some websites to get its factor and did a test for puzzle 64. I used the following strides, and surprisingly i don't know the reason why it didn't catch the private key even though i subtract 1 because of the starting private key, still didn't hit. ??? Possible_Strides_For_Puzzle_64: Code: 124 544615 496846 None of those strides worked, so i must have did a mistake? Would be nice having your opinions. Title: Re: Puzzle Factorization Post by: NotATether on July 25, 2024, 06:28:02 AM It's kinda hard to identify the prime numbers, as in computing only the non-prime numbers at runtime though, because there is still a huge amount of numbers in Z(2^256) that are not prime.
So you could be multiplying by two, or by three, or by five, or seven, or a combination thereof, but you don't really have anything more efficient than that using this method. Plus if you are just searching these sequences in that order, or even some other order, then you are more likely to miss the actual key (in addition to the risk that the key is prime). Not to mention that multiplication by anything that isn't two is inefficient. Title: Re: Puzzle Factorization Post by: GR Sasa on July 25, 2024, 12:03:14 PM don't know if this would work but have you tried turning them into hex form by that i mean consider those strides as decimal and not hex Yes, i converted them to Hexadecimal, subtracted 1 because of starting private key, actually no chances i'm not sure what i am doing wrong, i gotta test it more deeply when i get enough time Title: Re: Puzzle Factorization Post by: CrunchyF on August 26, 2024, 08:48:59 PM Privatekey being a composite number will have several factors. We are not interested in the Prime Factors but instead all the possible factors. what do you mean by "all the possible factors"? this is what i found by factorizing the priv keys Code: Puzzle 1: 0x1 : 1 : 1 i don't understand how you found the "special" pattern you highlight on your graphics Title: Re: Puzzle Factorization Post by: iceland2k14 on August 31, 2024, 07:07:13 AM what do you mean by "all the possible factors"? For Example for Puzzle 65 Code: 30568377312064202855 : {5, 67, 335, 5639, 28195, 377813, 1889065, 16181749866767, 80908749333835, 1084177241073389, 5420886205366945, 91248887498699113, 456244437493495565, 6113675462412840571, 30568377312064202855} Title: Re: Puzzle Factorization Post by: CrunchyF on September 01, 2024, 09:50:56 AM Ok thanks.
I generated 400 randoms privkeys in the range of puzzle 64-65. I obtain that with all factors of every key: https://www.talkimg.com/images/2024/09/01/9VZq3.png the specific pattern you noticed occurs around 1/10 times (as you found before) so i don't think this a way to say that the priv key of the puzzle was not generated randomly and we can find a trick to speed up the search Title: Re: Puzzle Factorization Post by: iceland2k14 on September 06, 2024, 11:19:53 AM so i don't think this a way to say that the priv key of the puzzle was not generated randomly and we can find a trick to speed up the search It is not about how the privatekey is generated. We know that process already. The creator himself told that. It is about the way of searching most relevant range first thinking about the 84 remaining puzzles. As clearly mentioned in Note 1 and 2. Title: Re: Puzzle Factorization Post by: COBRAS on September 06, 2024, 11:14:36 PM How this factors correlate with difference in quantity of 0 and quantity of 1 in privkey in bin format?
Difference is has, most probably key and not, for ex with quantity of zero - quantity of ones = 6 more probably , or =2 less probably , or =0 les less probably, etc not need generate all privkeys. Title: Re: Puzzle Factorization Post by: iceland2k14 on September 15, 2024, 06:40:16 AM |