• Reference
  • 怎么样用c语言求1000的阶乘？ - 知乎

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++

#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

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

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

对于此题，可以拓展了解: Hensel's lemma

后几道 Crypto 方向题目有时间再写