tnt-lib 0.1.4

A Rust implementation of many certificates about Integers
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

#include "tnt-lib/include/aks_theorem.h"

using namespace std;
using namespace NTL;

bool aks_theorem(unsigned int n, unsigned int r, unsigned int s){
        ZZ_p::init(to_ZZ(n));
        ZZ_pX f(r, 1); f -= 1;
        const ZZ_pXModulus pf(f);

        ZZ_pX rPoly(1, 1);				// x
        PowerMod(rPoly, rPoly, n, pf);	// x^n
        unsigned int a;
        for (a = 1; a <= s; ++a)
        {
            ZZ_pX lPoly(1, 1);	// x
            lPoly -= a;			// x - a
            PowerMod(lPoly, lPoly, n, pf);	// (x - a)^n
            lPoly += a;			// (x - a)^n + a
            if (lPoly != rPoly)
            {
                return false;
            }
        }
        return true;
}