С.И.Хашин
Обычные порядки:
orders.h - заголовочный файл
orders.cpp - реализация.
Порядки Фробениуса:
forders.h - заголовочный файл
forders.cpp - реализация.
Вычисление, сохранение в файл, последующее чтение и быстрый доступ к порядкам целого a по различным простым модулям p, начиная с 2 и до заданного предела.
Нахождение порядка числа a по простому модулю p — довольно медленная процедура. Требуется во-первых, разложить число p-1 на простые множители, а во-вторых много раз вычислять ak mod p для различных k. Поэтому желательно иметь заранее вычисленные значения порядков.
Для реализации этого предлагается класс orders и несколько статических
его членов (динамических членов у класса нет).
Модуль состоит из двух файлов:
orders.h - заголовочный файл
orders.cpp - реализация.
Класс используется совместно с модулем z64 и является его продолжением.
Основные методы класса:
static int fill(unsigned a0, u64 maxN=0); // load/calculate seive and orders(base)
При первом запуске вычисляет искомые порядки, то есть порядки числа a по всем простым модулям, меньшим maxN. Эти порядки запоминаются в файле и при следующем запуске уже не вычисляются, а просто загружаются из файла.
Имя файла задается в функции
static char *order_file_name( unsigned a0);
и сейчас оно выглядит так:
sprintf(fname_buf, "%sords\\ord_%04d.dat", z64::path, a0);
где z64::path — путь к файлу, из которого загружались простые числа в модуле z64.
static unsigned nOrd(); // number of calculated orders
static u64 maxP(); // last P
static unsigned A() ; // base
static u64 ordI(unsigned i); // order(a, p(i))
static u64 ordP(u64 p0); // order(a, p0)
static u64 ordPP(u64 p0, int k); // order(a, p0^k)
static u64 ordN(u64 n); // order(a, n), n - any natural
static u64 iordP(u64 p0); // (p0-1)/order(a, p0)
Я на своем компьютере за несколько часов создал в каталоге C:\a\primes\ords\ файлы ord_NNNN.dat, где NNNN – все простые числа от 2 до 257, то есть файлы
ord_0002.dat ord_0003.dat ... ord_0257.dat
Пример использования:
u64 maxN = 1 << 30; // 2^30
Eload(maxN); // Читаем список простых чисел до maxN
int a = 11; // База
orders::fill(a, maxN); // Читаем порядки числа a по модулям простых чисел до maxN
double sum = 0, summ = 0;
for (u64 p = z64::NextPrime(a); p < maxN; p = z64::NextPrime(p)) {
u64 iq = orders::iordP(p);
sum += iq;
summ += 1./iq;
cnt++;
}
printf("%3d, %15.10f, %15.10f\n", a, sum/cnt, summ/cnt);
Для вычисления порядков Фробениуса используется аналогичный модуль forders. Вот его основные функции:
static int fill(int a0, int b0, int c0, u64 maxN=0); // load/calculate seive and orders(base)
static unsigned nOrd() {return nord; }; // number of calculated orders
static u64 maxP() {return maxP_; }; // last P
static int A() {return a; }; // base
static int B() {return b; }; // base
static int C() {return c; }; // base
static u64 fordI(unsigned i); // FrobOrder(a,b,c, p(i))
static u64 fordP(u64 p0); // FrobOrder(a,b,c, p0)
static unsigned fCordI(unsigned i); // co-FrobOrder(a,b,c, p(i))
static u64 fCordP(u64 p0); // co-FrobOrder(a,b,c, p0)
Замечание. Если число a является квадратичным вычетом по модулю p (то есть является полным квадратом по модулю p), то порядок Фробениуса считаем равным 0!
Пример использования:
u64 maxN = 1 << 30; // 2^30
Eload(maxN); // Читаем список простых чисел до maxN
int a = 11; // База
orders::fill(a, maxN); // Читаем порядки Фробениуса числа a по модулям простых чисел до maxN
double sum = 0, summ = 0;
for (u64 p = z64::NextPrime(a); p < maxN; p = z64::NextPrime(p)) {
u64 iq = forders::fordP(p);
sum += iq;
summ += 1./iq;
cnt++;
}
printf("%3d, %15.10f, %15.10f\n", a, sum/cnt, summ/cnt);