#pragma once
class PrimalityTests
{
public:
static int Jacobi(long long a, long long n);
static void LongLongToBits(
long long n, std::vector<int>& bits);
static long long ModPow(
long long a, long long k, long long n);
static bool MillerRabin(long long n, int t);
static bool SolovayStrassen(long long n, int t);
};
#include "pch.h"
#include "PrimalityTests.h"
int PrimalityTests::Jacobi(long long a, long long n) {
int s;
long long a1, b = a, e = 0, m, n1;
if (a == 0)
return 0;
if (a == 1)
return 1;
while ((b & 1) == 0)
b >>= 1, e++;
a1 = b;
m = n % 8;
if (!(e & 1))
s = +1;
else if (m == 1 || m == 7)
s = +1;
else if (m == 3 || m == 5)
s = -1;
if (n % 4 == 3 && a1 % 4 == 3)
s = -s;
if (a1 != 1)
n1 = n % a1;
else
n1 = 1;
return s * Jacobi(n1, a1);
}
void PrimalityTests::LongLongToBits(
long long n, std::vector<int>& bits) {
bits.clear();
while (n > 0) {
int digit = (int)(n % 2);
bits.push_back(digit);
n /= 2;
}
}
long long PrimalityTests::ModPow(
long long a, long long k, long long n) {
std::vector<int> kBits;
LongLongToBits(k, kBits);
long long b = 1;
if (k == 0) {
return b;
}
long long A = a;
if (kBits[0] == 1) {
b = a;
}
for (int i = 1; i < (int)kBits.size(); i++) {
A = (A * A) % n;
if (kBits[i] == 1) {
b = (A * b) % n;
}
}
return b;
}
bool PrimalityTests::MillerRabin(long long n, int t) {
if (n == 2 || n == 3) {
return true;
}
long long m = n % 2;
if (m == 0) {
return false;
}
long long n2 = n - 2;
std::random_device rd; // Seed generator
std::mt19937 mt(rd()); // Mersenne Twister engine
std::uniform_int_distribution<long long> dist(2, n2);
long long n1 = n - 1;
long long r = n1;
long s = 0;
m = r % 2;
while (m == 0) {
r = r / 2;
m = r % 2;
s++;
}
for (int i = 1; i <= t; i++) {
long long a = dist(mt);
long long y = ModPow(a, r, n);
if (y != 1 && y != n1) {
int j = 1;
while (j <= s && y != n1) {
y = ModPow(y, 2, n);
if (y == 1)
return false;
j++;
}
if (y != n1)
return false;
}
}
return true;
}
bool PrimalityTests::SolovayStrassen(long long n, int t) {
long long n1 = n - 1, n2 = n - 2, n12 = n1 / 2;
std::random_device rd; // Seed generator
std::mt19937 mt(rd()); // Mersenne Twister engine
std::uniform_int_distribution<long long> dist(2, n2);
for (int i = 1; i <= t; i++) {
long long a = dist(mt);
long long r = ModPow(a, n12, n);
if (r != 1 && r != n1)
return false;
int s = Jacobi(a, n);
if (!(r == s) && !(s == -1 && r == n1))
return false;
}
return true;
}
// ProbPrimalityTests.cpp (c) Monday, October 13, 2025
// Reference: "Handbook of Applied Cryptography" by
// Alfred J. Menezes, Paul C. van Oorschot, Scott A.
// Vanstone Chapters 2, 3, and 4
// https://www.walter-fendt.de/html5/men/primenumbers_en.htm
#include "pch.h"
int main()
{
while (true) {
std::string str = "";
std::cout << "== Menu ==" << std::endl;
std::cout << "1 Test Jacobi" << std::endl;
std::cout << "2 Test To Bits" << std::endl;
std::cout << "3 Test ModPow" << std::endl;
std::cout << "4 Test Miller-Rabin" << std::endl;
std::cout << "5 Test Solovay-Strassen" << std::endl;
std::cout << "6 Exit" << std::endl;
std::cout << "Option (1 - 6): ";
std::getline(std::cin, str);
int option = std::stoi(str);
if (option < 1 || option > 6) {
std::cout << "Illegal option" << std::endl;
continue;
}
if (option == 6) {
break;
}
switch (option) {
case 1: {
std::cout << "a = ";
std::getline(std::cin, str);
long long a = std::stoll(str);
std::cout << "n = ";
std::getline(std::cin, str);
long long n = std::stoll(str);
int j = PrimalityTests::Jacobi(a, n);
std::cout << "Jacobi = " << j << std::endl;
break;
}
case 2: {
std::vector<int> bits = { };
std::cout << "n = ";
std::getline(std::cin, str);
long long n = std::stoll(str);
PrimalityTests::LongLongToBits(n, bits);
for (int i = (int)bits.size() - 1; i >= 0; i--) {
std::cout << bits[i];
}
std::cout << std::endl;
break;
}
case 3: {
std::cout << "a = ";
std::getline(std::cin, str);
long long a = std::stoll(str);
std::cout << "k = ";
std::getline(std::cin, str);
long long k = std::stoll(str);
std::cout << "n = ";
std::getline(std::cin, str);
long long n = std::stoll(str);
long long m = PrimalityTests::ModPow(a, k, n);
std::cout << "ModPow(a, k, n) = " << m << std::endl;
break;
}
case 4: {
std::cout << "n = ";
std::getline(std::cin, str);
long long n = std::stoll(str);
std::cout << "t = ";
std::getline(std::cin, str);
int t = std::stoi(str);
bool mr = PrimalityTests::MillerRabin(n, t);
std::cout << "Miller-Rabin = " << mr << std::endl;
break;
}
case 5: {
std::cout << "n = ";
std::getline(std::cin, str);
long long n = std::stoll(str);
std::cout << "t = ";
std::getline(std::cin, str);
int t = std::stoi(str);
bool ss = PrimalityTests::SolovayStrassen(n, t);
std::cout << "Solavay-Strassen = " << ss << std::endl;
break;
}
}
}
return 0;
}
// pch.h: This is a precompiled header file.
// Files listed below are compiled only once, improving build performance for future builds.
// This also affects IntelliSense performance, including code completion and many code browsing features.
// However, files listed here are ALL re-compiled if any one of them is updated between builds.
// Do not add files here that you will be updating frequently as this negates the performance advantage.
#ifndef PCH_H
#define PCH_H
#include <iostream>
#include <random>
#include <string>
#include <vector>
#include "framework.h"
#include "PrimalityTests.h"
#endif //PCH_H
Numerical Explorations 