Encountered this error while implementing NTT cpp code: terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc

Question

I recently started implementing post-quantum crypto and needed to implement the polynomial multiplication for which number theoretic transform (ntt) is used to reduce its time of computation and this code below is one of the approach(not the most optimal but optimal compared to naive convolution implementation) and this is the code i've used in implementing multiplication of two polynomials using number theoretic transform (ntt) for post-quantum kyber crypto. I encountered this error while implementing the below code: terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc

#include <bits/stdc++.h>
using namespace std;
int MODULUS = 17;
int GEN = 13;
int pm(int base, int exp, int modulus) {
    int result = 1;
    base %= modulus;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % modulus;
        }
        exp >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}
std::vector<int> cooley_tukey_ntt(const std::vector<int>& a, int gen = GEN, int modulus = MODULUS) {
    if (a.size() == 1) {
        return a;
    }

    std::vector<int> omegas(a.size());
    omegas[0] = 1;
    for (int i = 1; i < a.size(); ++i) {
        omegas[i] = (omegas[i - 1] * gen) % modulus;
    }

    std::vector<int> even, odd;
    for (int i = 0; i < a.size(); i += 2) {
        even.push_back(a[i]);
        odd.push_back(a[i + 1]);
    }

    std::vector<int> even_ntt = cooley_tukey_ntt(even, pm(gen, 2, modulus), modulus);
    std::vector<int> odd_ntt = cooley_tukey_ntt(odd, pm(gen, 2, modulus), modulus);

    std::vector<int> out(a.size());
    for (int k = 0; k < a.size() / 2; ++k) {
        int p = even_ntt[k];
        int q = (omegas[k] * odd_ntt[k]) % modulus;
        out[k] = (p + q) % modulus;
        out[k + a.size() / 2] = (p - q + modulus) % modulus;
    }

    return out;
}
std::vector<int> cooley_tukey_intt(const std::vector<int>& a, int gen = GEN, int modulus = MODULUS) {
    if (a.size() == 1) {
        return a;
    }

    std::vector<int> omegas(a.size());
    omegas[0] = 1;
    for (int i = 1; i < a.size(); ++i) {
        omegas[i] = (omegas[i - 1] * pm(gen, modulus - 2, modulus)) % modulus;
    }

    std::vector<int> even, odd;
    for (int i = 0; i < a.size(); i += 2) {
        even.push_back(a[i]);
        odd.push_back(a[i + 1]);
    }

    std::vector<int> even_ntt = cooley_tukey_intt(even, pm(gen, 2, modulus), modulus);
    std::vector<int> odd_ntt = cooley_tukey_intt(odd, pm(gen, 2, modulus), modulus);

    std::vector<int> out(a.size());
    int scaler = pm(a.size(), modulus - 2, modulus);
    for (int k = 0; k < a.size() / 2; ++k) {
        int p = even_ntt[k];
        int q = (omegas[k] * odd_ntt[k]) % modulus;
        out[k] = ((p + q)*scaler) % modulus;
        out[k + a.size() / 2] = (((p - q + modulus))*scaler) % modulus;
    }

    return out;
}
vector<int> ntt_mul_nwc_attempt(vector<int>p, vector<int>q, int gen=GEN, int modulus=MODULUS){
 int deg_d = p.size();
 vector<int>pp=p;
 vector<int>qq=q;
 for(int i=0;i<deg_d;i++){pp.push_back(0);qq.push_back(0);}
 vector<int>pp_ntt=cooley_tukey_ntt(pp);
 vector<int>qq_ntt=cooley_tukey_ntt(qq);
 vector<int>rr_ntt;
 for(int i=0;i<pp.size();i++)
 {
    rr_ntt[i]=((pp_ntt[i]*qq_ntt[i])%modulus);
 }
 vector<int>rr=cooley_tukey_intt(rr_ntt);
 
 for(int i=deg_d;i<rr.size();i++)
 {
    rr[i - deg_d] = (rr[i - deg_d] - rr[i]) % modulus;
    rr[i] = 0;
 }
 rr.resize(deg_d);
 return rr;
}
int main() {
    vector<int>p = {1, 2, 3, 4};
    vector<int>q = {1, 3, 5, 7};
    vector<int>pq_nwc_attempt = ntt_mul_nwc_attempt(p, q);
    for(auto i:pq_nwc_attempt)cout<<i<<" ";
    return 0;
}

Answer 1

This is definitely wrong:

std::vector<int>rr_ntt;
for (int i = 0; i < pp.size(); i++)
{
    rr_ntt[i] = ((pp_ntt[i] * qq_ntt[i]) % modulus);
}

The rr_ntt vector is empty. Any attempt of accessing index i of the rr_ntt vector in the for loop is an out-of-bounds access.

If you had used at() instead of [] to access the elements, the error is easily seen with this example, as a std::out_of_range exception is thrown.

Whether this is the exact cause of the problem you're seeing, I don't know. But I do know that your program has an out-of-bounds access, meaning that the behavior of the code from there is undefined.