我假设问题中字符串末尾的空格是故意的,所以我把它留在了里面。
“弗兰克是“顶尖”学生之一 topicId{59220691223} ”
6026d9b3 23898bcd7ecdbcbcd575b0a1d9dc22fd9e60074aefcbaade494a50ae
“弗兰克是“最好的”学生之一 topicId{59220691223} ”
6026d9b3 1ba780bb9973e7cfc8c9f74a35b54448d441a61cc9bf8db0fcae5280
实际上,使用蛮力找到了大约 70 亿次尝试,比我预期的要多得多。
我认为 2^32 大约是 43 亿,因此在 43 亿次尝试后找不到任何匹配的机会约为 36.78%

实际上,我在大约 70 亿次尝试后找到了匹配,在 70 亿次尝试中没有匹配的可能性不到 20%。

这是我在 7 个线程上运行的 C++ 代码,每个线程都有不同的起点,一旦在任何线程上找到匹配项,它就会退出。每个线程还会更新其进度,以每 100 万次尝试计算一次。
我已经快速转发到在 threadId=5 上找到匹配项的位置,因此运行时间不到一分钟。但是,如果您更改起点,则可以寻找其他匹配项。
而且我也不确定如何使用Floyd 和 Brent,因为字符串必须使用相同的 topicId,所以你被锁定在前缀和后缀上。
/*
To compile go get picosha2 header file from https://github.com/okdshin/PicoSHA2
Copy this code into same directory as picosha2.h file, save it as hash.cpp for example.
On Linux go to command line and cd to directory where these files are.
To compile it:
g++ -O2 -o hash hash.cpp -l pthread
And run it:
./hash
*/
#include <iostream>
#include <string>
#include <thread>
#include <mutex>
// I used picoSHA2 header only file for the hashing
// https://github.com/okdshin/PicoSHA2
#include "picosha2.h"
// return 1st 4 bytes (8 chars) of SHA256 hash
std::string hash8(const std::string& src_str) {
std::vector<unsigned char> hash(picosha2::k_digest_size);
picosha2::hash256(src_str.begin(), src_str.end(), hash.begin(), hash.end());
return picosha2::bytes_to_hex_string(hash.begin(), hash.begin() + 4);
}
bool done = false;
std::mutex mtxCout;
void work(unsigned long long threadId) {
std::string a = "Frank is one of the \"best\" students topicId{",
b = "Frank is one of the \"top\" students topicId{";
// Each thread gets a different starting point, I've fast forwarded to the part
// where I found the match so this won't take long to run if you try it, < 1 minute.
// If you want to run a while drop the last "+ 150000000ULL" term and it will run
// for about 1 billion total (150 million each thread, assuming 7 threads) take
// about 30 minutes on Linux.
// Collision occurred on threadId = 5, so if you change it to use less than 6 threads
// then your mileage may vary.
unsigned long long start = threadId * (11666666667ULL + 147000000ULL) + 150000000ULL;
unsigned long long x = start;
for (;;) {
// Not concerned with making the reading/updating "done" flag atomic, unlikely
// 2 collisions are found at once on separate threads, and writing to cout
// is guarded anyway.
if (done) return;
std::string xs = std::to_string(x++);
std::string hashA = hash8(a + xs + "} "), hashB = hash8(b + xs + "} ");
if (hashA == hashB) {
std::lock_guard<std::mutex> lock(mtxCout);
std::cout << "*** SOLVED ***" << std::endl;
std::cout << (x-1) << std::endl;
std::cout << "\"" << a << (x - 1) << "} \" = " << hashA << std::endl;
std::cout << "\"" << b << (x - 1) << "} \" = " << hashB << std::endl;
done = true;
return;
}
if (((x - start) % 1000000ULL) == 0) {
std::lock_guard<std::mutex> lock(mtxCout);
std::cout << "thread: " << threadId << " = " << (x-start)
<< " tries so far" << std::endl;
}
}
}
void runBruteForce() {
const int NUM_THREADS = 7;
std::thread threads[NUM_THREADS];
for (int i = 0; i < NUM_THREADS; i++) threads[i] = std::thread(work, i);
for (int i = 0; i < NUM_THREADS; i++) threads[i].join();
}
int main(int argc, char** argv) {
runBruteForce();
return 0;
}