SpeedUp
题意: 提交 'flag' + {{ $\text{SHA256}\left(\sum_{{i=0}}^{{\lfloor \log_{10} (2^{27}!) \rfloor}} \left( \left\lfloor \frac{{2^{27}!}}{{10^i}} \right\rfloor \mod 10 \right)\right)$ }} + '}'
上面这个式子让 GPT 写的 (图一乐，而且这么求 number length 慢的要死(慢过 str(number).__len__()，而实际上是可以 log 巴拉巴拉求的，忘了复杂度了，总之是可以更快，而且实际上也不用求长度，见最后的代码))
对于计算 (2^27)! 的数位和并对其进行 SHA256 哈希的过程，您可以使用下面的 LaTeX 表达式：
这个表达式表示：
- $\lfloor \log_{10} (2^{27}!) \rfloor$ 表示 $(2^{27}!)$ 的位数，即计算出数位数。
- 然后通过循环 $\sum_{{i=0}}^{{\lfloor \log_{10} (2^{27}!) \rfloor}}$，从每一位提取数字 $\left\lfloor \frac{{2^{27}!}}{{10^i}} \right\rfloor \mod 10$。
- 将提取的数字进行求和，即求得数位和。
- 最后对数位和应用 SHA256 哈希算法。
下面的代码大概 2min 出结果
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
| #include <iostream>
#include <sstream>
#include <iomanip>
#include <openssl/sha.h>
#include <gmpxx.h>
#include <bits/stdc++.h>
#include <chrono> // 引入计时器库
using namespace std;
using namespace std::chrono;
auto getPrimePow(size_t n)
{
vector<pair<size_t,size_t>> tab;
vector<bool> ar;
ar.resize(n+1);
tab.reserve(2*n/log(n));
for (size_t i=2;i<=n;++i)
{
if (!ar[i])
{
size_t cnt=0;
for (size_t j=i;j<=n;j+=i)
{
ar[j]=true;
}
for (size_t j=i;j<=n;j*=i)
{
cnt+=n/j;
}
tab.emplace_back(i,cnt);
}
}
return tab;
}
template<typename iter>
mpz_class cal_odd(iter beg,iter end)
{
if (beg==end)
{
if (beg->second%2)
{
beg->second/=2;
return beg->first;
}
else
{
beg->second/=2;
return 1;
}
}
auto mid=beg+(end-beg)/2;
return cal_odd(beg,mid)*cal_odd(mid+1,end);
}
mpz_class cal(std::vector<std::pair<size_t, size_t>>&tab)
{
mpz_class ans=1;
if (tab.size())
{
ans=cal_odd(tab.begin(),tab.end());
while (tab.size()&&tab.back().second==0)
tab.pop_back();
auto subans=cal(tab);
ans*=subans*subans;
}
return ans;
}
mpz_class Factorial(size_t n)
{
auto tab=getPrimePow(n);
return cal(tab);
}
mpz_class Sum(string str){
mpz_class cnt=0;
for(int i=0;i<str.size();i++){
cnt+=str[i]-'0';
}
return cnt;
}
int main()
{
size_t i = 134217728;
auto start = high_resolution_clock::now(); // 记录开始时间
// i = 5;
auto answer = Factorial(i);
auto stop = high_resolution_clock::now(); // 记录阶乘结束时间
auto duration = duration_cast<milliseconds>(stop - start); // 计算阶乘所需时间
cout << "计算阶乘耗时（毫秒）: " << duration.count() << "ms" << endl;
start = high_resolution_clock::now(); // 记录开始时间
// 初始化数位和为 0
mpz_class sum = 0;
// 求阶乘结果的数位和
// while (answer > 0) {
// sum = sum + (answer % 10); // 求得当前位的数值并加到 sum 上
// answer /= 10; // 去除当前位，继续计算下一位
// }
std::ostringstream oss;
oss << answer;
std::string ansString = oss.str();
sum = Sum(ansString);
stop = high_resolution_clock::now();
duration = duration_cast<milliseconds>(stop - start);
cout << "计算数位和耗时（毫秒）: " << duration.count() << "ms" << endl;
// 输出数位和
std::cout << "数位和为: " << sum << std::endl;
start = high_resolution_clock::now(); // 记录开始时间
// 将数位和转换为字符串
std::ostringstream osss;
osss << sum;
std::string sumString = osss.str();
stop = high_resolution_clock::now();
duration = duration_cast<milliseconds>(stop - start);
cout << "计算将数位和转换为字符串耗时（毫秒）: " << duration.count() << "ms" << endl;
std::cout << sumString << '\n';
start = high_resolution_clock::now(); // 记录开始时间
// 计算 SHA-256 哈希
unsigned char hash[SHA256_DIGEST_LENGTH];
SHA256_CTX ctx;
SHA256_Init(&ctx);
SHA256_Update(&ctx, sumString.c_str(), sumString.length());
SHA256_Final(hash, &ctx);
// 输出 SHA-256 哈希结果
std::cout << "SHA-256 哈希结果为: ";
for (size_t i = 0; i < SHA256_DIGEST_LENGTH; ++i) {
printf("%02x", hash[i]);
}
std::cout << std::endl;
stop = high_resolution_clock::now();
duration = duration_cast<milliseconds>(stop - start);
cout << "计算hash耗时（毫秒）: " << duration.count() << "ms" << endl;
return 0;
}
|
一点点魔法
6min 出结果
Sagemath
1
2
3
| number = factorial(2**27)
digit_sum = sum(int(d) for d in str(number))
print(digit_sum)
|
not only rsa
$e$, $\phi(n)$ 不互素，后面这块专门出一期来讲，对于本题又发现 $n$ 使用 factordb 可分: $n=p^5$ ，结合 RSA 加密逻辑所以我们有 $C = m ^ e \pmod{p^5}$ ，选择在有限域下开根
Sagemath
1
2
3
4
5
6
7
| sage: import libnum
....: Zmn = Zmod(p ** 5)
....: m_list = Zmn(c).nth_root(e, all = True) # 必要
....: for i in m_list:
....: m = libnum.n2s(int(i))
....: if b'flag{' in m:
....: print(m)
|
得到 flag
后几道 Crypto 方向题目有时间再写