Category: Computer Science

Blog Entry © Wednesday, October 29, 2025, by James Pate Williams, Jr. Hydrogenic Atomic Spectral Lines

Blog Entry Wednesday October 29 2025Download
// HydrogenSpectralLines.cpp : Defines the entry point for the application.
//

#include "pch.h"
#include "framework.h"
#include "HydrogenSpectralLines.h"

#define MAX_LOADSTRING 100

// Global Variables:
HINSTANCE hInst;                                // current instance
WCHAR szTitle[MAX_LOADSTRING];                  // The title bar text
WCHAR szWindowClass[MAX_LOADSTRING];            // the main window class name
WCHAR buffer[32768], line[128], line1[128], line2[512];
double c = 299792458;
double h = 4.135667696e-15;

// Forward declarations of functions included in this code module:
ATOM                MyRegisterClass(HINSTANCE hInstance);
BOOL                InitInstance(HINSTANCE, int);
LRESULT CALLBACK    WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK    About(HWND, UINT, WPARAM, LPARAM);

int APIENTRY wWinMain(_In_ HINSTANCE hInstance,
                     _In_opt_ HINSTANCE hPrevInstance,
                     _In_ LPWSTR    lpCmdLine,
                     _In_ int       nCmdShow)
{
    UNREFERENCED_PARAMETER(hPrevInstance);
    UNREFERENCED_PARAMETER(lpCmdLine);

    // TODO: Place code here.

    // Initialize global strings
    LoadStringW(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
    LoadStringW(hInstance, IDC_HYDROGENSPECTRALLINES, szWindowClass, MAX_LOADSTRING);
    MyRegisterClass(hInstance);

    // Perform application initialization:
    if (!InitInstance (hInstance, nCmdShow))
    {
        return FALSE;
    }

    HACCEL hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_HYDROGENSPECTRALLINES));

    MSG msg;

    // Main message loop:
    while (GetMessage(&msg, nullptr, 0, 0))
    {
        if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
        {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
        }
    }

    return (int) msg.wParam;
}

//
//  FUNCTION: MyRegisterClass()
//
//  PURPOSE: Registers the window class.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
    WNDCLASSEXW wcex = { };

    wcex.cbSize = sizeof(WNDCLASSEX);

    wcex.style          = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc    = WndProc;
    wcex.cbClsExtra     = 0;
    wcex.cbWndExtra     = 0;
    wcex.hInstance      = hInstance;
    wcex.hIcon          = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_HYDROGENSPECTRALLINES));
    wcex.hCursor        = LoadCursor(nullptr, IDC_ARROW);
    wcex.hbrBackground  = (HBRUSH)(COLOR_WINDOW+1);
    wcex.lpszMenuName   = MAKEINTRESOURCEW(IDC_HYDROGENSPECTRALLINES);
    wcex.lpszClassName  = szWindowClass;
    wcex.hIconSm        = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

    return RegisterClassExW(&wcex);
}

//
//   FUNCTION: InitInstance(HINSTANCE, int)
//
//   PURPOSE: Saves instance handle and creates main window
//
//   COMMENTS:
//
//        In this function, we save the instance handle in a global variable and
//        create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   hInst = hInstance; // Store instance handle in our global variable

   HWND hWnd = CreateWindowW(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, nullptr, nullptr, hInstance, nullptr);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

#define IDC_COMPUTE_BUTTON  1010
#define IDC_CANCEL_BUTTON   1020
#define IDC_CLEAR_BUTTON    1030
#define IDC_EDIT_MULTILINE  1040

//
//  FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  PURPOSE: Processes messages for the main window.
//
//  WM_COMMAND  - process the application menu
//  WM_PAINT    - Paint the main window
//  WM_DESTROY  - post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    static HFONT hFont = nullptr;
    static HWND hCombo1 = nullptr;
    static HWND hCombo2 = nullptr;
    static HWND hCombo3 = nullptr;
    static HWND hCombo4 = nullptr;
    static HWND hEditMultiline = nullptr;

    switch (message)
    {
    case WM_CREATE:
        CreateWindowEx(0, L"STATIC", L"Series:", WS_CHILD | WS_VISIBLE,
            10, 10, 80, 20, hWnd, (HMENU)IDC_STATIC, hInst, NULL);
        hCombo1 = CreateWindowEx(0, L"COMBOBOX", nullptr,
            WS_CHILD | WS_VISIBLE | CBS_DROPDOWNLIST | WS_VSCROLL |
            ES_AUTOVSCROLL, 120, 10, 200, 100, hWnd, nullptr, hInst, nullptr);
        CreateWindowEx(0, L"STATIC", L"n2:", WS_CHILD | WS_VISIBLE,
            10, 40, 80, 20, hWnd, (HMENU)IDC_STATIC, hInst, NULL);
        hCombo2 = CreateWindowEx(0, L"COMBOBOX", nullptr,
            WS_CHILD | WS_VISIBLE | CBS_DROPDOWNLIST | WS_VSCROLL |
            ES_AUTOVSCROLL, 120, 40, 120, 150, hWnd, nullptr, hInst, nullptr);
        CreateWindowEx(0, L"STATIC", L"atom:", WS_CHILD | WS_VISIBLE,
            10, 70, 80, 20, hWnd, (HMENU)IDC_STATIC, hInst, NULL);
        hCombo3 = CreateWindowEx(0, L"COMBOBOX", nullptr,
            WS_CHILD | WS_VISIBLE | CBS_DROPDOWNLIST | WS_VSCROLL |
            ES_AUTOVSCROLL, 120, 70, 120, 150, hWnd, nullptr, hInst, nullptr);
        CreateWindowEx(0, L"STATIC", L"formula:", WS_CHILD | WS_VISIBLE,
            10, 100, 80, 20, hWnd, (HMENU)IDC_STATIC, hInst, NULL);
        hCombo4 = CreateWindowEx(0, L"COMBOBOX", nullptr,
            WS_CHILD | WS_VISIBLE | CBS_DROPDOWNLIST | WS_VSCROLL |
            ES_AUTOVSCROLL, 120, 100, 120, 150, hWnd, nullptr, hInst, nullptr);
        CreateWindowEx(0, L"BUTTON", L"Compute", WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON,
            10, 140, 80, 30, hWnd, (HMENU)IDC_COMPUTE_BUTTON, hInst, NULL);
        CreateWindowEx(0, L"BUTTON", L"Cancel", WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON,
            10, 180, 80, 30, hWnd, (HMENU)IDC_CANCEL_BUTTON, hInst, NULL);
        CreateWindowEx(0, L"BUTTON", L"Clear", WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON,
            10, 220, 80, 30, hWnd, (HMENU)IDC_CLEAR_BUTTON, hInst, NULL);
        hFont = CreateFont(16, 0, 0, 0, FW_BOLD, FALSE, FALSE, FALSE,
            UNICODE, OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS,
            DEFAULT_QUALITY, DEFAULT_PITCH | FF_SWISS, L"Courier New");
        hEditMultiline = CreateWindowEx(
            WS_EX_CLIENTEDGE,                       // Extended style for sunken border
            TEXT("EDIT"),                           // Class name
            TEXT(""),                               // Initial text (can be blank)
            WS_CHILD | WS_VISIBLE | WS_VSCROLL | ES_AUTOHSCROLL |
            ES_LEFT | ES_MULTILINE | ES_AUTOVSCROLL | WS_HSCROLL | WS_VSCROLL,
            340, 10, 640, 400,                      // Position and size
            hWnd,                                   // Parent window handle
            (HMENU)IDC_EDIT_MULTILINE,              // Unique control ID
            hInst,                                  // Application instance
            NULL                                    // Extra parameter
        );
        SendMessage(hCombo1, WM_SETFONT, (WPARAM)hFont, 0);
        SendMessage(hCombo2, WM_SETFONT, (WPARAM)hFont, 0);
        SendMessage(hCombo3, WM_SETFONT, (WPARAM)hFont, 0);
        SendMessage(hCombo4, WM_SETFONT, (WPARAM)hFont, 0);
        SendMessage(hEditMultiline, WM_SETFONT, (WPARAM)hFont, 0);
        SendMessage(hCombo1, CB_ADDSTRING, 0, (LPARAM)L"Lyman    n1 = 1 n2 >= 2");
        SendMessage(hCombo1, CB_ADDSTRING, 0, (LPARAM)L"Balmer   n1 = 2 n2 >= 3");
        SendMessage(hCombo1, CB_ADDSTRING, 0, (LPARAM)L"Paschen  n1 = 3 n2 >= 4");
        SendMessage(hCombo1, CB_ADDSTRING, 0, (LPARAM)L"Brackett n1 = 4 n2 >= 5");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"2");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"3");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"4");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"5");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"6");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"7");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"8");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"9");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"10");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"11");
        SendMessage(hCombo2, CB_ADDSTRING, 0, (LPARAM)L"12");
        SendMessage(hCombo1, CB_SETCURSEL, 0, 0);
        SendMessage(hCombo3, CB_ADDSTRING, 0, (LPARAM)L"hydrogen");
        SendMessage(hCombo3, CB_ADDSTRING, 0, (LPARAM)L"helium+");
        SendMessage(hCombo3, CB_ADDSTRING, 0, (LPARAM)L"lithium++");
        SendMessage(hCombo4, CB_ADDSTRING, 0, (LPARAM)L"energy eV");
        SendMessage(hCombo4, CB_ADDSTRING, 0, (LPARAM)L"frequency Hz");
        SendMessage(hCombo4, CB_ADDSTRING, 0, (LPARAM)L"wavelength A");
        SendMessage(hCombo1, CB_SETCURSEL, 0, 0);
        SendMessage(hCombo2, CB_SETCURSEL, 0, 0);
        SendMessage(hCombo3, CB_SETCURSEL, 0, 0);
        SendMessage(hCombo4, CB_SETCURSEL, 0, 0);
        buffer[0] = L'\0';
        break;
    case WM_COMMAND:
        {
            int wmId = LOWORD(wParam);
            // Parse the menu selections:
            switch (wmId)
            {
            case IDM_ABOUT:
                DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
                break;
            case IDC_COMPUTE_BUTTON:
            {
                int n1 = 0, n2 = 0;
                WCHAR series[16] = { 0 };

                if (hCombo1)
                {
                    GetWindowText(hCombo1, line, 128);
                }

                if (std::wcsstr(line, L"Lyman"))
                {
                    wcscpy_s(series, L"Lyman");
                    n1 = 1;
                }
                
                else if (std::wcsstr(line, L"Balmer"))
                {
                    wcscpy_s(series, L"Balmer");
                    n1 = 2;
                }

                else if (std::wcsstr(line, L"Paschen"))
                {
                    wcscpy_s(series, L"Paschen");
                    n1 = 3;
                }

                else if (std::wcsstr(line, L"Brackett"))
                {
                    wcscpy_s(series, L"Brackett");
                    n1 = 4;
                }

                if (hCombo2)
                {
                    GetWindowText(hCombo2, line, 128);
                    std::wstring n2Str(line);
                    n2 = stoi(n2Str);
                }

                if (n2 < n1 + 1)
                {
                    MessageBox(hWnd, L"n2 must be greater than equal n1 + 1",
                        L"Warning", MB_OK | MB_ICONWARNING);
                    break;
                }

                double Z = 1.0;
                GetWindowText(hCombo3, line, 128);

                if (wcscmp(line, L"hydrogen") == 0)
                {
                    Z = 1.0;
                }

                else if (wcscmp(line, L"helium+") == 0)
                {
                    Z = 2.0;
                }

                else if (wcscmp(line, L"lithium++") == 0)
                {
                    Z = 3.0;
                }

                double deltaE = -13.6 * Z * Z * (1.0 / (n1 * n1) - 1.0 / (n2 * n2));
                double nu = deltaE / h;
                double lambda = c / nu / 1.0e-10;
                double number = deltaE;
    
                GetWindowText(hCombo4, line1, 128);

                if (wcscmp(line1, L"energy eV") == 0)
                {
                    number = deltaE;
                }

                else if (wcscmp(line1, L"frequency Hz") == 0)
                {
                    number = nu;
                }

                else if (wcscmp(line1, L"wavelength A") == 0)
                {
                    number = lambda;
                }

                swprintf_s(line2, L"%s\t%s\t%s\t%d\t%d\t%lf\r\n",
                    series, line, line1, n1, n2, number);
                wcscat_s(buffer, line2);

                if (hEditMultiline)
                {
                    SetWindowText(hEditMultiline, buffer);
                }

                break;
            }
            case IDC_CLEAR_BUTTON:
                buffer[0] = '\0';
                SetWindowText(hEditMultiline, buffer);
                break;
            case IDC_CANCEL_BUTTON:
            case IDM_EXIT:
                DestroyWindow(hWnd);
                break;
            default:
                return DefWindowProc(hWnd, message, wParam, lParam);
            }
        }
        break;
    case WM_PAINT:
        {
            PAINTSTRUCT ps;
            HDC hdc = BeginPaint(hWnd, &ps);
            // TODO: Add any drawing code that uses hdc here...
            EndPaint(hWnd, &ps);
        }
        break;
    case WM_DESTROY:
        PostQuitMessage(0);
        break;
    default:
        return DefWindowProc(hWnd, message, wParam, lParam);
    }
    return 0;
}

// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
    UNREFERENCED_PARAMETER(lParam);
    switch (message)
    {
    case WM_INITDIALOG:
        return (INT_PTR)TRUE;

    case WM_COMMAND:
        if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
        {
            EndDialog(hDlg, LOWORD(wParam));
            return (INT_PTR)TRUE;
        }
        break;
    }
    return (INT_PTR)FALSE;
}

Blog Entry © Sunday, October 26, 2025, by James Pate Williams, Jr. More Factoring with Arjen K. Lenstra’s LIP (Large Integer Package)

Blog Entry Sunday October 26 2025Download

Blog Entry © Thursday, October 23, 2025, by James Pate Williams, Jr. A Stochastic ProblemRelated to the Subset Sum Problem

Blog Entry Thursday October 23 2025Download

Blog Entry © Tuesday, October 21, 2025, by James Pate Williams, Jr., Solving Low Density Subset Sum Problems Using the LLL-Lattice Reduction Algorithm

Blog Entry Tuesday October 21 2025Download
// Algorithm found in the "Handbook of
// Applied Cryptography" (c) 1997 by
// Alfred J. Menezes, Paul C van Oorschot,
// and Scott Vanstone 3.105 Algorithm
// Chapter 3 pages 120 - 121

#pragma once
class LLL_Lattice
{

private:

	static double Scalar(
		int n,
		std::vector<double> u,
		std::vector<double> v);
	static void RED(
		int k, int l, int n,
		std::vector<std::vector<double>>& b,
		std::vector<std::vector<double>>& h,
		std::vector<std::vector<double>>& mu);
	static void SWAP(
		int k, int k1, int kmax, int n,
		double m, std::vector<double>& B,
		std::vector<std::vector<double>>& b,
		std::vector<std::vector<double>>& bs,
		std::vector<std::vector<double>>& h,
		std::vector<std::vector<double>>& mu);

public:

	static bool LLL(
		int n,
		std::vector<std::vector<double>>& b,
		std::vector<std::vector<double>>& h);
};


#include "pch.h"
#include "LLL_Lattice.h"

double LLL_Lattice::Scalar(
    int n,
    std::vector<double> u,
    std::vector<double> v)
{
    // Calculate the scalar product of two vectors [1..n]
    double sum = 0.0;

    for (int i = 1; i <= n; i++) sum += u[i] * v[i];
    return sum;
}

void LLL_Lattice::RED(
    int k, int l, int n,
    std::vector<std::vector<double>>& b,
    std::vector<std::vector<double>>& h,
    std::vector<std::vector<double>>& mu)
{
    int i, q = (int)(0.5 + mu[k][l]);

    if (fabs(mu[k][l]) > 0.5)
    {
        for (i = 1; i <= n; i++)
        {
            b[k][i] -= q * b[l][i];
            h[i][k] -= q * h[i][l];
        }

        mu[k][l] -= q;

        for (i = 1; i <= l - 1; i++)
        {
            mu[k][i] -= q * mu[l][i];
        }
    }
}

void LLL_Lattice::SWAP(
    int k, int k1, int kmax, int n,
    double m, std::vector<double>& B,
    std::vector<std::vector<double>>& b,
    std::vector<std::vector<double>>& bs,
    std::vector<std::vector<double>>& h,
    std::vector<std::vector<double>>& mu)
{
    double C, t;
    int i, j;
    std::vector<double> c(n + 1);

    for (j = 1; j <= n; j++)
    {
        t = b[k][j];
        b[k][j] = b[k1][j];
        b[k1][j] = t;
        t = h[j][k];
        h[j][k] = h[j][k1];
        h[j][k1] = t;
    }

    if (k > 2)
    {
        for (j = 1; j <= k - 2; j++)
        {
            t = mu[k][j];
            mu[k][j] = mu[k1][j];
            mu[k1][j] = t;
        }
    }

    C = B[k] + m * m * B[k1];
    mu[k][k1] = m * B[k1] / C;

    for (i = 1; i <= n; i++)
    {
        c[i] = bs[k1][i];
    }

    for (i = 1; i <= n; i++)
    {
        bs[k1][i] = bs[k][i] + m * c[i];
    }
    
    for (i = 1; i <= n; i++)
    {
        bs[k][i] = -m * bs[k][i] + B[k] * c[i] / C;
    }

    B[k] *= B[k1] / C;
    B[k1] = C;

    for (i = k + 1; i <= kmax; i++)
    {
        t = mu[i][k];
        mu[i][k] = mu[i][k1] - m * t;
        mu[i][k1] = t + mu[k][k1] * mu[i][k];
    }
}

bool LLL_Lattice::LLL(
    int n,
    std::vector<std::vector<double>>& b,
    std::vector<std::vector<double>>& h)
{
    // Lattice reduction algorithm
 
    double m;
    std::vector<double> B(n + 1);
    std::vector<double> bv(n + 1);
    std::vector<double> bw(n + 1);
    std::vector<std::vector<double>> bs(n + 1,
        std::vector<double>(n + 1));
    std::vector<std::vector<double>> mu(n + 1,
        std::vector<double>(n + 1));
    int i, j, k, k1, kmax = 1, l;

    for (i = 1; i <= n; i++)
        bv[i] = bs[1][i] = b[1][i];

    B[1] = Scalar(n, bv, bv);

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            h[i][j] = 0.0;
        }
        
        h[i][i] = 1.0;
    }

    for (k = 2; k <= n; k++)
    {
        if (k <= kmax)
            goto Label3;

        kmax = k;
        for (i = 1; i <= n; i++)
        {
            bs[k][i] = b[k][i];
        }

        for (j = 1; j <= k - 1; j++)
        {
            for (l = 1; l <= n; l++)
            {
                bv[l] = b[k][l];
                bw[l] = bs[j][l];
            }

            mu[k][j] = Scalar(n, bv, bw) / B[j];

            for (i = 1; i <= n; i++)
            {
                bs[k][i] -= mu[k][j] * bs[j][i];
            }
        }

        for (i = 1; i <= n; i++)
        {
            bv[i] = bs[k][i];
        }

        B[k] = Scalar(n, bv, bv);

        if (B[k] == 0.0)
            return false;

    Label3:

        k1 = k - 1;
        m = mu[k][k1];
        RED(k, k1, n, b, h, mu);

        if (B[k] < (0.75 - m * m) * B[k1])
        {
            SWAP(k, k1, kmax, n, m, B, b, bs, h, mu);
            k = max(2, k1);
            goto Label3;
        }

        for (l = k - 2; l >= 1; l--)
        {
            RED(k, l, n, b, h, mu);
        }
    }

    return true;
}

Blog Entry © Sunday, October 19, 2025, by James Pate Williams, Jr. LIPCalculator (Large Integer Package Calculator)

Blog Entry Sunday October 19 2025Download

Blog Entry © Wednesday, October 15, 2025, by James Pate Williams, Jr. Miscellaneous Algorithms from Chapters 2 and 4 of the “Handbook of Applied Cryptography” by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone

Blog Entry Tuesday October 14 2025Download
#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

Blog Entry © Sunday, October 12, 2025, by James Pate Williams, Jr. More 64-Bit Factoring Using Pollard’s Cubic Integer Factoring Algorithm

Blog Entry Sunday October 12 2025Download

Blog Entry © Saturday, October 11, 2025, by James Pate Williams, Jr., Starling’s Virial Expansion for a Real Gas or Liquid 1972

Blog Entry Saturday October 11 2025Download

Blog Entry © Tuesday, September 30, 2025, by James Pate Williams, Jr. Win32 Desktop C++ App to Solve Small Instances of the N-Queens Puzzle Using a Permutation Based Algorithm and Chronological Backtracking

Blog Entry Tuesday September 30 2025Download