Category: Memoirs of James Pate Williams Jr

#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