3. Modul de implementare

Arhitectura bibliotecii

Testul este organizat ca o bibliotecă C++ orientată pe obiecte, cu două cerințe de proiectare în prim-plan: o transformată $O(n\log n)$ (un DFT direct $O(n^2)$ ar fi inutilizabil peste câteva mii de biți) și o structură modulară, reutilizabilă:

• DftEngine (interfață) cu FftEngine (radix-2 + Bluestein, $O(n\log n)$) și DirectDftEngine ($O(n^2)$, pentru verificare) - tipar Strategy.
• BitSequence concentrează toate sursele de intrare (text, binar, stdin), conversia bipolară și împărțirea în fluxuri.
• RandomnessTest / SpectralTest - testul 2.6.
• Assessment - proporție + uniformitate peste multe fluxuri.

Aceeași arhitectură deservește întreaga suită SP 800-22: fiecare test implementează RandomnessTest (un TestReport uniform) și se înregistrează printr-o linie, deci toate cele 15 teste folosesc același motor, API și pagini. Lucrarea ramane concentrata pe testul spectral. Poți răsfoi codul, evidențiat sintactic, în Cod sursă.

Nucleul testului

Pașii 1-8 din capitolul matematic se regăsesc unu-la-unu:

SpectralResult SpectralTest::analyze(const BitSequence &seq) const
{
    const std::size_t n = seq.size();
    // Pasii 1-2: bitii devin +/-1, apoi DFT.
    const std::vector<Complex> spectrum = engine_->transform(seq.toBipolar());
 
    // Pasul 3: primele n/2 module (DC inclus, Nyquist exclus).
    const std::size_t half = n / 2;
    // Pasul 4: pragul de 95%.
    const double threshold = std::sqrt(std::log(20.0) * (double)n);
 
    // Pasul 6: cate varfuri cad sub prag.
    long n1 = 0;
    for (std::size_t i = 0; i < half; i++)
        if (std::abs(spectrum[i]) < threshold)
            n1++;
 
    SpectralResult r;
    r.n0 = 0.95 * (double)n / 2.0;                          // Pasul 5
    const double denom = std::sqrt((double)n / 4.0 * 0.95 * 0.05);
    r.d = ((double)n1 - r.n0) / denom;                      // Pasul 7
    r.pValue = std::erfc(std::fabs(r.d) / std::sqrt(2.0));  // Pasul 8
    return r;
}

Rezultatul este exact cel produs de aritmetica corectă, identic cu al codului de referință NIST.

Transformata rapidă pentru lungimi arbitrare

DFT-ul direct ar însemna $\approx 10^{12}$ operații pentru un milion de biți. Fișierele NIST au $\approx 10^6$ biți, iar $10^6$ nu este o putere a lui 2, deci un FFT radix-2 clasic nu se aplică direct.

Soluția este algoritmul lui Bluestein (chirp-z), care exprimă un DFT de lungime arbitrară $n$ printr-o convoluție calculabilă cu un FFT radix-2:

$S[k] = e^{-i\pi k^2/n} \sum_{j=0}^{n-1} \big(x_j\, e^{-i\pi j^2/n}\big)\, e^{\,i\pi (k-j)^2/n}.$

Complexitatea devine $O(n\log n)$; o secvență de $10^6$ biți se procesează în $\approx 0.43$ secunde.

Analiza de nivel 2

Pentru a reproduce analiza globală NIST, Assessment împarte secvența în fluxuri, rulează testul pe fiecare și calculează proporția de treceri (cu intervalul $\hat p \pm 3\sqrt{\hat p\,\alpha/s}$) și uniformitatea valorilor $p$ (test $\chi^2$ pe 10 intervale, transformat prin funcția gamma incompletă regularizată).

Aplicația web rulează exact aceste binare prin API-ul public.