Category: Uncategorized

Six Large Integer Factoring Methods Using Arjen K. Lenstra’s Free Large Integer Package (Free LIP) by James Pate Wiliams, Jr.

This C code uses singly linked lists as the key data structure. The factoring methods are trial division, Brent’s modification of the well-known Pollard rho method, Cohen-Pollard p – 1 algorithm first stage, Lehman’s method, Cohen’s algorithm for the Lenstra’s elliptic curve method, and the Free LIP elliptic curve method. I include a couple of sample factorizations by the Free LIP built-in Lenstra elliptic curve method. These include the seventh Fermat number 2^128+1 and the eighth Fermat number 2^256+1.

/*
Author:  Pate Williams (c) 1997

Algorithm 8.4.1 (Lehman). See "A Course in
Computational Algebraic Number Theory" by
Henri Cohen page 425.

Author:  Pate Williams (c) 1997 - 2022

Algorithm 8.5.2 (Pollard rho). See "A Course in
Computational Algebraic Number Theory" by Henri
Cohen page 429.

Author:  Pate Williams (c) 1997 - 2022

Algorithm 8.8.2 (p - 1 First Stage). See "A Course
in Computational Algebraic Number Theory" by Henri
Cohen page 439.

Author:  Pate Williams (c) 1997 - 2022

Algorithm 10.3.3 (Lenstra's ECM). See "A Course
in Computational Algebraic Number Theory" by
Henri Cohen page 488.
*/

#include "LIP_data_structures.h"
#include <crtdbg.h>

#ifndef CLK_TCK
#define CLK_TCK CLOCKS_PER_SEC
#endif

typedef struct myThreadData
{
	int zacount;
	verylong zn;
	PFACTORNODE current;
	PFACTORNODE first;
	PFACTORNODE(*tdFunction)(
		verylong*,
		PFACTORNODE,
		int*);
} THREADDATA, *PTHREADDATA;

DWORD WINAPI TdThread(LPVOID lpParam)
{
	clock_t time0 = clock();
	PTHREADDATA td = (PTHREADDATA)lpParam;
	PFACTORNODE head = td->first;
	td->current = td->tdFunction(
		&td->zn, td->first, &td->zacount);
	td->first = td->current;
	PFACTORNODE last = find_last(td->first);
	quick_sort(td->first, last);

	if (td->first != NULL)
	{
		while (td->first != NULL)
		{
			if (zprobprime(td->first->factor.zfactor, 20))
			{
				zwrite(td->first->factor.zfactor);

				if (td->first->factor.exponent > 1)
					printf(" ^ %d ", td->first->factor.exponent);

				printf("\n");
			}
			
			td->first = td->first->next;
		}
	}

	PFACTORNODE ptr = head;

	while (ptr != NULL)
	{
		ptr = delete_factor_node(head);
		head = ptr;
	}

	double time = (clock() - time0) / (double)CLK_TCK;
	printf("total time required: %f seconds\n", time);
	return TRUE;
}

int main()
{
	int i = 0, zacount = 0;
	verylong zN = 0, zf = 0, zn = 0, zo = 0;
	verylong zaddend = 0, zbase = 0, ztemp = 0;
	verylong zq = 0, zr = 0, zs = 0;
	PFACTORNODE current = NULL, first = NULL;

	while (1)
	{
		char optionStr[256], numStr[256] = { 0 }, option, *bPtr, *ePtr;
		int base, expon, addend, iExpon = 0, positive;

		printf("Menu\n");
		printf("1 Trial Division\n");
		printf("2 Brent-Pollard rho Method\n");
		printf("3 Cohen-Pollard p - 1 Method\n");
		printf("4 Lehman's Method\n");
		printf("5 Cohen Lenstra's Elliptic Curve Method\n");
		printf("6 FreeLIP Lenstra's Elliptic Curve Method\n");
		printf("7 Exit\n");
		printf("Enter choice (1 - 7): ");
		scanf_s("%s", optionStr, 256);
		option = optionStr[0];

		zone(&zo);

		if (option == '7')
			break;

		if (option < '1' || option > '6')
		{
			printf("Unknown choice, please reenter choice\n");
			continue;
		}

		printf("enter the number below (0 to quit):\n");
		scanf_s("%s", numStr, 256);

		bPtr = strchr(numStr, '^');

		if (bPtr != NULL)
		{
			*bPtr = '\0';
			base = atoi(numStr);
			ePtr = strchr(bPtr + 1, '+');

			if (ePtr != NULL)
				positive = 1;

			else {
				ePtr = strchr(bPtr + 1, '-');

				if (ePtr != NULL)
					positive = 0;
			}

			if (ePtr != NULL)
				*ePtr = '\0';

			expon = atoi(bPtr + 1);

			if (ePtr != NULL) {
				addend = atoi(ePtr + 1);

				if (positive == 0)
					addend = -addend;
			}

			else
				addend = 0;

			zintoz(base, &zbase);
			zintoz(addend, &zaddend);
			zsexp(zbase, expon, &ztemp);
			zadd(ztemp, zaddend, &zN);

			numStr[0] = '\0';
		}

		else
			zstrtoz(numStr, &zN);

		zcopy(zN, &zn);

		if (zmcomposite(zn, 20) == 0)
		{
			printf("Number is prime\n");
			continue;
		}

		first = insert_first_factor_node(zo, 0);
		zacount = 1;

		DWORD dwMilliseconds;
		PTHREADDATA pThreadData = (PTHREADDATA)
			malloc(sizeof(THREADDATA));

		if (pThreadData == NULL)
			exit(0);

		memset(pThreadData, 0, sizeof(THREADDATA));

		pThreadData->current = NULL;
		pThreadData->first = first;
		pThreadData->zacount = 1;
		zcopy(zn, &pThreadData->zn);

		printf("Wait milliseconds = ");
		scanf_s("%ld", &dwMilliseconds);

		if (option == '1')
		{
			pThreadData->tdFunction = trial_division;

			DWORD threadId;
			HANDLE hMutex = CreateMutex(
				NULL, FALSE, NULL);

			if (hMutex == NULL)
				exit(0);

			HANDLE thread = CreateThread(
				NULL,
				0,
				(LPTHREAD_START_ROUTINE)TdThread,
				pThreadData,
				0,
				&threadId);

			WaitForSingleObject(thread, dwMilliseconds);
			CloseHandle(thread);
			CloseHandle(hMutex);
		}

		else if (option == '2')
		{
			pThreadData->tdFunction = Brent_Pollard_Method;

			DWORD threadId;
			HANDLE hMutex = CreateMutex(
				NULL, FALSE, NULL);

			if (hMutex == NULL)
				exit(0);

			HANDLE thread = CreateThread(
				NULL,
				0,
				(LPTHREAD_START_ROUTINE)TdThread,
				pThreadData,
				0,
				&threadId);

			if (thread == NULL)
				exit(0);

			WaitForSingleObject(thread, dwMilliseconds);
			CloseHandle(thread);
			CloseHandle(hMutex);
		}

		else if (option == '3')
		{
			pThreadData->tdFunction = Cohen_Pollard_Method;

			DWORD threadId;
			HANDLE hMutex = CreateMutex(
				NULL, FALSE, NULL);

			if (hMutex == NULL)
				exit(0);

			HANDLE thread = CreateThread(
				NULL,
				0,
				(LPTHREAD_START_ROUTINE)TdThread,
				pThreadData,
				0,
				&threadId);

			WaitForSingleObject(thread, dwMilliseconds);
			CloseHandle(thread);
			CloseHandle(hMutex);
		}

		else if (option == '4')
		{
			pThreadData->tdFunction = Lehman;

			DWORD threadId;
			HANDLE hMutex = CreateMutex(
				NULL, FALSE, NULL);

			if (hMutex == NULL)
				exit(0);

			HANDLE thread = CreateThread(
				NULL,
				0,
				(LPTHREAD_START_ROUTINE)TdThread,
				pThreadData,
				0,
				&threadId);

			WaitForSingleObject(thread, dwMilliseconds);
			CloseHandle(thread);
			CloseHandle(hMutex);
		}

		else if (option == '5')
		{
			first = CohenEllipticCurveMethod(
				numStr, base, expon, addend);
		}

		else if (option == '6')
		{
			pThreadData->tdFunction = LenstraEllipticCurveMethod;

			DWORD threadId;
			HANDLE hMutex = CreateMutex(
				NULL, FALSE, NULL);

			if (hMutex == NULL)
				exit(0);

			HANDLE thread = CreateThread(
				NULL,
				0,
				(LPTHREAD_START_ROUTINE)TdThread,
				pThreadData,
				0,
				&threadId);

			WaitForSingleObject(thread, dwMilliseconds);
			CloseHandle(thread);
			CloseHandle(hMutex);
		}

		zfree(&pThreadData->zn);
		free(pThreadData);
	}

	zfree(&zaddend);
	zfree(&zbase);
	zfree(&ztemp);
	zfree(&zN);
	zfree(&zf);
	zfree(&zn);
	zfree(&zo);
	zfree(&zq);
	zfree(&zr);
	zfree(&zs);
	return 1;
}

#pragma once
#include "..\LIPFactoring\lip.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define my_B 1000000l
#define my_NUMBER_PRIMES 78498l
#define my_BOUND 100000000l

/* https://www.tutorialspoint.com/data_structures_algorithms/linked_list_program_in_c.htm */
/* https://www.geeksforgeeks.org/quicksort-on-singly-linked-list */

typedef struct my_factor
{
	long exponent;		// secondary storage key
	verylong zfactor;	// primary storage key
} FACTOR, *PFACTOR;

typedef struct my_factor_node
{
	FACTOR factor;
	struct my_factor_node* next;
} FACTORNODE, *PFACTORNODE;

/* basic singly linked list functions
** the c means complete comparison including
** the exponents of the factor or factor_node
** s denotes a shallow comparison */
int factor_z_compare_c(FACTOR lt, FACTOR rt);
int factor_z_compare_s(FACTOR lt, FACTOR rt);
int factor_node_z_compare_c(FACTORNODE lt, FACTORNODE rt);
int factor_node_z_compare_s(FACTORNODE lt, FACTORNODE rt);
PFACTORNODE insert_first_factor_node(verylong zf, int exponent);
PFACTORNODE insert_factor_node(PFACTORNODE current, FACTOR factor);
PFACTORNODE delete_factor_node(PFACTORNODE first);
PFACTORNODE linear_search_factor_c(PFACTORNODE first, FACTOR factor);
PFACTORNODE linear_search_factor_s(PFACTORNODE first, FACTOR factor);
void reverse(PFACTORNODE* first_ref);
// old school factoring algorithms
PFACTORNODE trial_division(verylong *zN, PFACTORNODE fn, int *count);
int trial_division_1(long B, verylong *zN, verylong *zf);
PFACTORNODE Brent_Pollard_Method(verylong *zN, PFACTORNODE fn, int *count);
PFACTORNODE Cohen_Pollard_Method(verylong *zN, PFACTORNODE fn, int *count);
PFACTORNODE Lehman(verylong *zN, PFACTORNODE fn, int *count);
PFACTORNODE find_last(PFACTORNODE first);
void quick_sort(PFACTORNODE first, PFACTORNODE last);

/* Lenstra's Elliptic Curve Method define and point structure */

#define CURVES 1024l

typedef struct ec_point
{ 
	verylong zx, zy, zz;
} ECPOINT, *PECPOINT;

PFACTORNODE CohenEllipticCurveMethod(
	char *numStr, int base, int expon, int addend);

PFACTORNODE LenstraEllipticCurveMethod(
	verylong *zN, PFACTORNODE first, int *count);

#include "LIP_data_structures.h"

/* complete factor comparison */

int factor_z_compare_c(FACTOR lt, FACTOR rt)
{
	verylong zlt, zrt;
	
	zcopy(lt.zfactor, &zlt);
	zcopy(rt.zfactor, &zrt);
	int zc = zcompare(zlt, zrt);
	
	if (zc > 0)
		return +1;
	if (zc < 0)
		return -1;
	if (lt.exponent < rt.exponent)
		return -1;
	if (lt.exponent > rt.exponent)
		return -1;
	
	return 0;
}

/* shallow factor comparison */

int factor_z_compare_s(FACTOR lt, FACTOR rt)
{
	verylong zlt = 0, zrt = 0;

	zcopy(lt.zfactor, &zlt);
	zcopy(rt.zfactor, &zrt);
	int zc = zcompare(zlt, zrt);

	if (zc > 0)
		return +1;
	if (zc < 0)
		return -1;

	return 0;
}

/* complete factor_node comparison */

int factor_node_z_compare_c(FACTORNODE lt, FACTORNODE rt)
{
	verylong zlt, zrt;

	zcopy(lt.factor.zfactor, &zlt);
	zcopy(rt.factor.zfactor, &zrt);
	int zc = zcompare(zlt, zrt);

	if (zc > 0)
		return +1;
	if (zc < 0)
		return -1;
	if (lt.factor.exponent < rt.factor.exponent)
		return -1;
	if (lt.factor.exponent > rt.factor.exponent)
		return -1;

	return 0;
}

/* shallow factor node comparison */

int factor_node_z_compare_s(FACTORNODE lt, FACTORNODE rt)
{
	verylong zlt, zrt;

	zcopy(lt.factor.zfactor, &zlt);
	zcopy(rt.factor.zfactor, &zrt);
	int zc = zcompare(zlt, zrt);

	if (zc > 0)
		return +1;
	if (zc < 0)
		return -1;

	return 0;
}

/* returns the first factor node */

PFACTORNODE insert_first_factor_node(verylong zf, int exponent)
{
	PFACTORNODE first = (PFACTORNODE) malloc(sizeof(FACTORNODE));
	
	memset(first, 0, sizeof(FACTORNODE));
	zcopy(zf, &first->factor.zfactor);
	first->factor.exponent = exponent;
	first->next = NULL;
	return first;
}

/* insert a factor node in order */

PFACTORNODE insert_factor_node(PFACTORNODE first, FACTOR factor)
{
	if (first == NULL)
		return NULL;

	PFACTORNODE next = (PFACTORNODE)malloc(sizeof(FACTORNODE));

	memset(next, 0, sizeof(FACTORNODE));
	next->factor.exponent = factor.exponent;
	zcopy(factor.zfactor, &next->factor.zfactor);
	next->next = first;
	return next;
}

PFACTORNODE delete_factor_node(PFACTORNODE first)
{
	if (first == NULL)
		return NULL;

	PFACTORNODE toDelete = first;

	first = first->next;

	zfree(&toDelete->factor.zfactor);
	free(toDelete);
	return first;
}

PFACTORNODE linear_search_factor_c(PFACTORNODE first, FACTOR factor)
{
	int found = 0;
	PFACTORNODE ptr = first;

	if (ptr == NULL)
		return NULL;

	do
	{
		found = factor_z_compare_c(ptr->factor, factor);

		if (found == 0)
			return ptr;
		else
			ptr = ptr->next;

	} while (ptr != NULL);

	return NULL;
}

void reverse(PFACTORNODE* first_ref)
{
	PFACTORNODE prev = NULL;
	PFACTORNODE current = *first_ref;
	PFACTORNODE next;

	while (current != NULL) {
		next = current->next;
		current->next = prev;
		prev = current;
		current = next;
	}

	*first_ref = prev;
}


PFACTORNODE linear_search_factor_s(PFACTORNODE first, FACTOR factor)
{
	int found = 0;
	PFACTORNODE ptr = first;

	if (ptr == NULL)
		return NULL;

	do
	{
		found = factor_z_compare_s(ptr->factor, factor);

		if (found == 0)
			return ptr;
		else
			ptr = ptr->next;

	} while (ptr != NULL);

	return NULL;
}

PFACTORNODE partition(PFACTORNODE first, PFACTORNODE last)
{
	if (first == last || first == NULL || last == NULL)
		return first;

	PFACTORNODE pivot = first;
	PFACTORNODE front = first;
	FACTOR temp;

	while (front != NULL && front != last)
	{
		if (zcompare(
			front->factor.zfactor, last->factor.zfactor) < 0) {
			pivot = first;
			temp = first->factor;
			first->factor = front->factor;
			front->factor = temp;

			first = first->next;
		}

		front = front->next;
	}

	temp = first->factor;
	first->factor = last->factor;
	last->factor = temp;
	return pivot;
}

PFACTORNODE find_last(PFACTORNODE first)
{
	while (first->next != NULL)
	{
		first = first->next;
	}

	return first;
}

void quick_sort(PFACTORNODE first, PFACTORNODE last)
{
	if (first == last) {
		return;
	}

	PFACTORNODE pivot = partition(first, last);

	if (pivot != NULL && pivot->next != NULL) {
		quick_sort(pivot->next, last);
	}

	if (pivot != NULL && first != pivot) {
		quick_sort(first, pivot);
	}
}

PFACTORNODE do_Brent_Pollard(verylong *zN, PFACTORNODE first, int *count)
{
	int e, one, pr;
	long c, i, k, l;
	verylong zP = 0, za = 0, zb = 0, zg = 0, zn = 0;
	verylong zx = 0, zx1 = 0, zy = 0;
	FACTOR factor;
	PFACTORNODE current = NULL;

	zcopy(*zN, &zn);

	do {
		c = 0, k = l = 1;
		zone(&zP);
		zintoz(2l, &zy);
		zintoz(2l, &zx);
		zintoz(2l, &zx1);
	L2:
		zsq(zx, &za);
		zsadd(za, 1l, &zb);
		zmod(zb, zn, &zx);
		zsub(zx1, zx, &za);
		zmulmod(za, zP, zn, &zb);
		zcopy(zb, &zP);

		if (++c == 20) {
			zgcd(zP, zn, &zg);
			
			if (zscompare(zg, 1l) > 0)
				goto L4;
			
			zcopy(zx, &zy);
			c = 0;
		}

		if (--k != 0)
			goto L2;

		zgcd(zP, zn, &zg);

		if (zscompare(zg, 1l) > 0)
			goto L4;

		zcopy(zx, &zx1);
		k = l, l *= 2;

		for (i = 0; i < k; i++)
		{
			zsq(zx, &za);
			zsadd(za, 1l, &zb);
			zmod(zb, zn, &zx);
		}

		zcopy(zx, &zy);
		c = 0;

		goto L2;
	L4:
		do {
			zsq(zy, &za);
			zsadd(za, 1l, &zb);
			zmod(zb, zn, &zy);
			zsub(zx1, zy, &za);
			zgcd(za, zn, &zg);
		} while (zscompare(zg, 1l) == 0);

		if (zcompare(zg, zn) == 0)
		{
			fprintf(stderr, "fatal error\nBrent's method failed\n");
			exit(1);
		}

		if (!zprobprime(zg, 20l))
		{
			zcopy(zg, &za);

			if ((current = trial_division(&zg, first, count)) == NULL) {
				fprintf(stderr, "fatal error\ncould not trial divide\n");
				exit(1);
			}

			first = current;
			zcopy(za, &zg);
			zdiv(zn, zg, &za, &zb);
			zcopy(za, &zn);
		}

		else
		{
			e = 0;

			do {
				zdiv(zn, zg, &za, &zb);
				zcopy(za, &zn);
				zmod(zn, zg, &za);
				e++;
			} while (zscompare(za, 0l) == 0);

			if (first != NULL)
			{
				factor.exponent = e;
				factor.zfactor = 0;
				zcopy(zg, &factor.zfactor);
				current = insert_factor_node(first, factor);
				first = current;
				*count = *count + 1;
			}
		}
		
		one = zscompare(zn, 1l) == 0;

		if (!one)
		{
			pr = zprobprime(zn, 20l);

			if (pr)
			{
				factor.exponent = 1;
				factor.zfactor = 0;
				zcopy(zn, &factor.zfactor);
				current = insert_factor_node(first, factor);
				first = current;
				break;
			}
		}
	} while (!one);

	zfree(&zP);
	zfree(&za);
	zfree(&zb);
	zfree(&zg);
	zfree(&zn);
	zfree(&zx);
	zfree(&zx1);
	zfree(&zy);
	return first;
}

PFACTORNODE Brent_Pollard_Method(
	verylong *zN,
	PFACTORNODE first,
	int *count)
{
	verylong zq = 0, zr = 0;
	FACTOR factor;
	PFACTORNODE current = NULL, ptr;

	*count = 0;

	while (1)
	{
		current = do_Brent_Pollard(zN, first, count);
		first = current;
		ptr = first;

		while (ptr != NULL)
		{
			zdiv(*zN, ptr->factor.zfactor, &zq, &zr);

			while (zscompare(zr, 0l))
			{
				zdiv(zq, ptr->factor.zfactor, &zq, &zr);
			}

			if (zscompare(zq, 1l))
				goto out_loop;

			if (zprobprime(zq, 20l))
				goto out_loop;

			ptr = ptr->next;
		}

		if (zscompare(*zN, 1l) == 0)
			return first;

		if (zprobprime(*zN, 20l) > 0)
			break;
	}
out_loop:
	zfree(&zq);
	zfree(&zr);
	factor.exponent = 1;
	factor.zfactor = 0;
	zcopy(*zN, &factor.zfactor);
	current = insert_factor_node(first, factor);
	first = current;
	return first;
}

PFACTORNODE first_stage(long k, verylong *zN, long x0, long *p,
	verylong *zx, PFACTORNODE first, int *count)
{
	long c = 0, i = -1, j = i, l, q, q1;
	static verylong zg = 0, zq1 = 0, zt = 0, zx1 = 0, zy = 0;
	FACTOR factor;
	PFACTORNODE current = NULL;

	*count = 0;
	zzero(&zg);
	zsadd(zg, x0, zx);
	zcopy(*zx, &zy);
L2:
	i++;
	if (i > k) {
		zsadd(*zx, -1l, &zx1);
		zgcd(zx1, *zN, &zg);
		if (zscompare(zg, 1l) == 0) return NULL;
		else {
			i = j;
			zcopy(zy, zx);
			goto L5;
		}
	}
	else {
		q = p[i];
		q1 = q;
		l = my_B / q;
	}

	while (q1 <= l) q1 *= q;
	zzero(&zt);
	zsadd(zt, q1, &zq1);
	zcopy(*zx, &zt);
	zexpmod(zt, zq1, *zN, zx);
	if (++c < 20) goto L2;
	zsadd(*zx, -1l, &zx1);
	zgcd(zx1, *zN, &zg);
	if (zscompare(zg, 1l) == 0) {
		c = 0;
		j = i;
		zcopy(*zx, &zy);
		goto L2;
	}
	else {
		i = j;
		zcopy(zy, zx);
	}
L5:
	i++;
	q = p[i];
	q1 = q;
L6:
	zzero(&zt);
	zsadd(zt, q, &zq1);
	zcopy(*zx, &zt);
	zexpmod(zt, zq1, *zN, zx);
	zsadd(*zx, -1l, &zx1);
	zgcd(zx1, *zN, &zg);
	if (zscompare(zg, 1l) == 0) {
		q1 *= q;
		if (q1 <= my_B) goto L6; else goto L5;
	}
	else
	{
		if (zcompare(zg, *zN) < 0) {
			factor.exponent = 1;
			factor.zfactor = 0;
			zcopy(zg, &factor.zfactor);
			current = insert_factor_node(first, factor);
			first = current;
			*count = *count + 1;
			zcopy(*zN, &zq1);
			zdiv(zq1, zg, zN, &zx1);
			return first;
		}

		if (zcompare(zg, *zN) == 0)
		{
			first = NULL;
		}
	}

	zfree(&zg);
	zfree(&zq1);
	zfree(&zt);
	zfree(&zx1);
	zfree(&zy);
	return first;
}

PFACTORNODE Cohen_Pollard_Method(
	verylong *zN,
	PFACTORNODE first,
	int *count)
{
	long cnt, i, *p = (long *)malloc(my_NUMBER_PRIMES * sizeof(long));
	verylong zx = 0;
	PFACTORNODE current = NULL;

	zpstart2();

	for (i = 0; i < my_NUMBER_PRIMES; i++)
		p[i] = zpnext();

	i = 0;

	int j = p[0];

	do {
		while ((current = first_stage(my_NUMBER_PRIMES, zN,
			j, p, &zx, first, &cnt)) != NULL && i < my_NUMBER_PRIMES)
		{
			i++;
			j = p[i];
			first = current;
			count += cnt;
		}
		j = p[++i];
	} while (
		!zscompare(*zN, 1l) &&
		!zprobprime(*zN, 20) &&
		i < my_NUMBER_PRIMES);

	FACTOR factor;

	factor.exponent = 1;
	factor.zfactor = *zN;
	current = insert_factor_node(first, factor);
	first = current;
	free(p);
	return first;
}

int square_test(verylong zn, verylong *zq)
{
	int square = 1;
	long q11[11], q63[63], q64[64], q65[65];
	long k, r, t;
	verylong zd = 0;

	for (k = 0; k < 11; k++) q11[k] = 0;
	for (k = 0; k < 6; k++) q11[(k * k) % 11] = 1;
	for (k = 0; k < 63; k++) q63[k] = 0;
	for (k = 0; k < 32; k++) q63[(k * k) % 63] = 1;
	for (k = 0; k < 64; k++) q64[k] = 0;
	for (k = 0; k < 32; k++) q64[(k * k) % 64] = 1;
	for (k = 0; k < 65; k++) q65[k] = 0;
	for (k = 0; k < 33; k++) q65[(k * k) % 65] = 1;
	t = zsmod(zn, 64l);
	r = zsmod(zn, 45045);
	if (q64[t] == 0) square = 0;
	if (square && q63[r % 63] == 0) square = 0;
	if (square && q65[r % 65] == 0) square = 0;
	if (square && q11[r % 11] == 0) square = 0;
	if (square) {
		zsqrt(zn, zq, &zd);
		if (zscompare(zd, 0l) != 0) square = 0;
	}

	zfree(&zd);
	return square;
}

int trial_division_1(long B, verylong *zN, verylong *zf)
{
	int e = 0;
	long p;
	verylong za = 0, zb = 0;

	zcopy(*zN, &za);
	zpstart2();
	do {
		p = zpnext();
		if (zsmod(za, p) == 0) {
			do {
				zsdiv(za, p, &zb);
				zcopy(zb, &za);
				e++;
			} while (zsmod(za, p) == 0);
			zintoz(p, zf);
			zcopy(za, zN);
		}
	} while (!e && p <= B);

	zfree(&za);
	zfree(&zb);
	return e;
}

int do_Lehman(verylong *zN, verylong *zf)
{
	long B = pow(zdoub(*zN), 1.0 / 3.0), a, k = 0, m, r;
	int e = trial_division_1(B, zN, zf);
	verylong za = 0, zb = 0, zc = 0, zh = 0, zl = 0;
	verylong zr = 0, zs = 0;

	if (!e) {
	L2:
		k++;
		if (k > B) goto L4;
		if (!(k & 1)) {
			zone(&zr);
			m = 2;
		}
		else {
			zsadd(*zN, k, &zr);
			m = 4;
		}
		zsmul(*zN, k, &za);
		zlshift(za, 2l, &zl);
		zintoz(B, &zh);
		zsq(zh, &zb);
		zadd(zl, zb, &zh);
		zsqrt(zl, &za, &zb);
		zsq(za, &zs);
		while (zcompare(zs, zl) < 0) {
			zsadd(za, 1l, &zb);
			zcopy(zb, &za);
			zsq(za, &zs);
		}
		r = zsmod(zr, m);
		while (!e && zcompare(zs, zh) <= 0) {
			a = zsmod(za, m);
			if (a == r) {
				zsub(zs, zl, &zc);
				if (zscompare(zc, 0l) == 0 || square_test(zc, &zb)) {
					zadd(za, zb, &zc);
					zgcd(zc, *zN, zf);
					do {
						zdiv(*zN, *zf, &za, &zb);
						zcopy(za, zN);
						zmod(za, *zf, &zb);
						e++;
					} while (zscompare(zb, 0l) == 0);
				}
			}
			if (!e) {
				zsadd(za, 1l, &zb);
				zcopy(zb, &za);
				zsq(za, &zs);
			}
		}
		if (!e) goto L2;
	}
L4:
	zfree(&za);
	zfree(&zb);
	zfree(&zc);
	zfree(&zh);
	zfree(&zl);
	zfree(&zr);
	zfree(&zs);
	return e;
}

PFACTORNODE Lehman(
	verylong *zN,
	PFACTORNODE first,
	int *count)
{
	int e = 0;
	verylong zf = 0;
	FACTOR factor;
	PFACTORNODE current = NULL;

	while (1)
	{
		e = do_Lehman(zN, &zf);

		if (e)
		{
			factor.exponent = e;
			factor.zfactor = 0;
			zcopy(zf, &factor.zfactor);
			current = insert_factor_node(first, factor);
			first = current;
			*count = *count + 1;
		}
		
		else if (zprobprime(*zN, 20l))
		{
			factor.exponent = 1;
			factor.zfactor = 0;
			zcopy(*zN, &factor.zfactor);
			current = insert_factor_node(first, factor);
			first = current;
			*count = *count + 1;
			break;
		}

		else
			break;
	}

	zfree(&zf);
	return first;
}

PFACTORNODE trial_division(
	verylong *zN,
	PFACTORNODE first,
	int *count)
{
	int e, one = 0, pr = 0;
	long B, p;
	verylong za = 0, zb = 0, zl = 0, zo = 0, zp = 0;
	FACTOR factor;
	PFACTORNODE current = NULL;

	zsqrt(*zN, &za, &zb);
	zone(&zo);
	zcopy(*zN, &zl);

	if (zscompare(za, my_BOUND) > 0)
		B = my_BOUND;

	else
		B = ztoint(za);

	zcopy(*zN, &za);
	zpstart2();

	do {
		p = zpnext();

		if (zsmod(za, p) == 0)
		{
			e = 0;

			do {
				zsdiv(za, p, &zb);
				zcopy(zb, &za);
				e++;
			} while (zsmod(za, p) == 0);

			zintoz(p, &zp);
			factor.exponent = e;
			factor.zfactor = 0;
			zcopy(zp, &factor.zfactor);
			current = insert_factor_node(first, factor);
			first = current;
			*count = *count + 1;
			zcopy(za, zN);
			one = zscompare(*zN, 1l) == 0;
			pr = zprobprime(*zN, 20l);

			if (!one && pr)
			{
				factor.exponent = 1;
				zcopy(*zN, &factor.zfactor);
				current = insert_factor_node(first, factor);
				first = current;
				*count = *count + 1;
				break;
			}

			else
			{
				factor.exponent = 1;
				factor.zfactor = 0;
				zcopy(*zN, &factor.zfactor);
				current = insert_factor_node(first, factor);
				first = current;
				*count = *count + 1;
			}
		}
	} while (!one && p <= B);

	PFACTORNODE last = (PFACTORNODE)malloc(sizeof(FACTORNODE));

	last->factor.exponent = 1;
	last->factor.zfactor = 0;
	zcopy(zl, &last->factor.zfactor);
	current = insert_factor_node(first, last->factor);
	first = current;
	*count = *count + 1;

	zfree(&za);
	zfree(&zb);
	zfree(&zl);
	zfree(&zo);
	zfree(&zp);
	return first;
}

int partial_addition(verylong za,
	verylong zn,
	ECPOINT P,
	ECPOINT Q,
	PECPOINT R,
	verylong *zd)

	/* returns 0 if sum is found or 1 if divisor is found */

{
	int result = -1, value = 0;
	verylong zb = 0, zc = 0, zl = 0, zs = 0;
	verylong zt = 0, zx = 0, zy = 0, zy2 = 0;

	if (zcompare(P.zx, Q.zx) == 0 &&
		zscompare(P.zy, 0l) == 0 &&
		zscompare(Q.zy, 0l) == 0) {
		zzero(&R->zx);
		zone(&R->zy);
		return 0;
	}

	zsub(zn, Q.zy, &zb);

	if (zcompare(P.zx, Q.zx) == 0 &&
		zcompare(P.zy, zb) == 0) {
		zzero(&R->zx);
		zone(&R->zy);
		return 0;
	}

	if (zscompare(P.zx, 0l) == 0 &&
		zscompare(P.zy, 1l) == 0 &&
		zscompare(P.zz, 0l) == 0) {

		/* O + Q = Q */

		zcopy(Q.zx, &R->zx);
		zcopy(Q.zy, &R->zy);
		zcopy(Q.zz, &R->zz);
		value = 0;
	}

	else if (zscompare(Q.zx, 0l) == 0 &&
		zscompare(Q.zy, 1l) == 0 &&
		zscompare(Q.zz, 0l) == 0) {

		/* P + O = P */

		zcopy(P.zx, &R->zx);
		zcopy(P.zy, &R->zy);
		zcopy(P.zz, &R->zz);
		value = 0;
	}

	else {

		/* P != O and Q != O */

		zcopy(Q.zy, &zy2);
		znegate(&zy2);
		if (zcompare(P.zx, Q.zx) == 0 &&
			zcompare(P.zy, zy2) == 0) {
			zzero(&R->zx);
			zone(&R->zy);
			zzero(&R->zz);
		}

		else {
			if (zcompare(P.zx, Q.zx) != 0) {
				zsubmod(P.zx, Q.zx, zn, &zx);
				zexteucl(zx, &zs, zn, &zt, zd);
				if (zscompare(*zd, 1l) != 0) goto L1;
				zsubmod(P.zy, Q.zy, zn, &zy);
				zmulmod(zs, zy, zn, &zl);
			}

			else {
				zaddmod(P.zy, Q.zy, zn, &zy);
				zexteucl(zy, &zs, zn, &zt, zd);
				if (zscompare(*zd, 1l) != 0) goto L1;
				zmulmod(P.zx, P.zx, zn, &zb);
				zsmulmod(zb, 3l, zn, &zc);
				zaddmod(zc, za, zn, &zb);
				zmulmod(zs, zb, zn, &zl);
			}

			zmulmod(zl, zl, zn, &zb);
			zaddmod(P.zx, Q.zx, zn, &zc);
			zsubmod(zb, zc, zn, &zx);
			zcopy(zx, &R->zx);
			zsubmod(zx, P.zx, zn, &zb);
			zmulmod(zl, zb, zn, &zc);
			zaddmod(zc, P.zy, zn, &zy);
			znegate(&zy);
			zcopy(zy, &R->zy);
			zone(&R->zz);
			goto L2;
		L1:
			value = 1;
		L2:
			;
		}
	}

	zfree(&zb);
	zfree(&zc);
	zfree(&zl);
	zfree(&zs);
	zfree(&zt);
	zfree(&zx);
	zfree(&zy);
	zfree(&zy2);
	return value;
}

int multiply(long k,
	verylong za,
	verylong zn,
	ECPOINT P,
	PECPOINT R,
	verylong *zd)
{
	int value = 0;
	ECPOINT A = { 0, 0, 0 };
	ECPOINT S = { 0, 0, 0 };
	ECPOINT T = { 0, 0, 0 };

	zone(&A.zx);
	zone(&A.zy);
	zone(&A.zz);
	zone(&S.zx);
	zone(&S.zy);
	zone(&S.zz);
	zone(&T.zx);
	zone(&T.zy);
	zone(&T.zz);

	R = (PECPOINT)malloc(sizeof(ECPOINT));

	if (R == NULL)
		exit(0);

	memset(R, 0, sizeof(ECPOINT));

	zzero(&R->zx);
	zone(&R->zy);
	zzero(&R->zz);
	zcopy(P.zx, &S.zx);
	zcopy(P.zy, &S.zy);
	zcopy(P.zz, &S.zz);

	while (!value && k != 0) {
		if (k & 1) {
			value = partial_addition(za, zn, *R, S, &A, zd);
			zcopy(A.zx, &R->zx);
			zcopy(A.zy, &R->zy);
			zcopy(A.zz, &R->zz);
		}

		k >>= 1;

		if (!value && k != 0) {
			value = partial_addition(za, zn, S, S, &T, zd);
			zcopy(T.zx, &S.zx);
			zcopy(T.zy, &S.zy);
			zcopy(T.zz, &S.zz);
		}
	}

	if (zscompare(R->zy, 0l) < 0) {
		zadd(R->zy, zn, &A.zy);
		zcopy(A.zy, &R->zy);
	}

	zfree(&A.zx);
	zfree(&A.zy);
	zfree(&A.zz);
	zfree(&S.zx);
	zfree(&S.zy);
	zfree(&S.zz);
	zfree(&T.zx);
	zfree(&T.zy);
	zfree(&T.zz);
	return value;
}

/* the following definition limits the L3 loop */

int LenstrasECM(verylong *zN, verylong *zg)
{
	int expon = 0, found;
	long B = 100000000l, i, j, k = 0, l, *p, q, q1;
	long giveUp = z2log(*zN);
	ECPOINT x, y;
	verylong za[CURVES], zb = 0, zd = 0;

	for (i = 0; i < CURVES; i++)
		za[i] = 0;

	x.zx = x.zy = x.zz = y.zx = y.zy = y.zz = 0;

	zpstart2();

	do {
		q = zpnext();
		k++;
	} while (q < B);

	p = calloc(k, sizeof(long));

	if (!p) {
		expon = -1;
		goto L4;
	}

	zpstart2();

	for (i = 0; i < k; i++)
		p[i] = zpnext();

	for (i = 0; i < CURVES; i++)
		zrandomb(*zN, &za[i]);

L2:

	zone(&x.zx);
	zone(&x.zy);
	zzero(&x.zz);
	i = -1;

L3:

	i++;

	if (i == giveUp) {
		expon = 0;
		goto L4;
	}

	if (i == k) {

		for (i = 0; i < CURVES; i++)
			zrandomb(*zN, &za[i]);

		goto L2;
	}

	q = p[i];
	q1 = q;
	l = B / q;

	while (q1 <= l)
		q1 *= q;

	found = 0;

	for (j = 0; !found && j < CURVES; j++)
		found = multiply(q1, za[j], *zN, x, &y, &zd);

	if (!found)
		goto L3;

	zcopy(y.zx, &x.zx);
	zcopy(y.zy, &x.zy);
	zcopy(y.zz, &x.zz);
	zgcd(zd, *zN, zg);

	if (zcompare(*zg, *zN) == 0) {
		for (j = 0; j < CURVES; j++)
			zrandomb(*zN, &za[j]);

		goto L2;
	}

	if (!zprobprime(*zg, 5l))
		goto L4;

	expon = 0;

	do {
		zdiv(*zN, *zg, &zb, &zd);
		zcopy(zb, zN);
		zmod(*zN, *zg, &zd);
		expon++;
	} while (zscompare(zd, 0l) == 0);

L4:

	for (i = 0; i < CURVES; i++)
		zfree(&za[i]);

	zfree(&zb);
	zfree(&zd);
	zfree(&x.zx);
	zfree(&x.zy);
	zfree(&x.zz);
	zfree(&y.zx);
	zfree(&y.zy);
	zfree(&y.zz);
	return expon;
}

PFACTORNODE CohenEllipticCurveMethod(
	char *numStr, int base, int iExpon, int addend)
{
	PFACTORNODE current, first;
	FACTOR factor;
	int result;
	int cant, expon, one, pri;
	verylong zn = 0, zN = 0, zd = 0, zg = 0;

	if (strlen(numStr) != 0)
		zstrtoz(numStr, &zN);

	else
	{
		static verylong zb = 0, zp = 0;

		zintoz(base, &zb);

		zsexp(zb, iExpon, &zp);
		zsadd(zp, addend, &zN);
	}

	zcopy(zN, &zn);

	first = insert_first_factor_node(zN, 1);

	cant = pri = 0;

	do {

		expon = LenstrasECM(&zN, &zg);

		if (expon == -1)
		{
			result = -1;
			goto L1;
		}

		if (zprobprime(zg, 20l))
		{
			factor.exponent = expon;
			factor.zfactor = zg;
			current = insert_factor_node(first, factor);
			first = current;
		}

		one = zscompare(zN, 1l) == 0;

		if (zprobprime(zN, 20l))
		{
			factor.exponent = 1;
			factor.zfactor = zN;
			current = insert_factor_node(first, factor);
			first = current;
			break;
		}

	} while (!one);

L1:

	zfree(&zn);
	zfree(&zN);
	zfree(&zd);
	zfree(&zg);

	return first;
}

PFACTORNODE LenstraEllipticCurveMethod(
	verylong *zN, PFACTORNODE first, int *count)
{
	long curvebnd = 1024, e = 0, exp = 0, phase1bnd = 64;
	long grow = 16, info = 2, nbtests = 20, s = 1;
	verylong zf = 0, zn = 0, zq = 0, zr = 0;
	FACTOR factor;
	PFACTORNODE current = NULL;

	zcopy(*zN, &zn);

	while (exp != -1)
	{
		exp = zfecm(zn, &zf, s, &curvebnd, &phase1bnd,
			grow, nbtests, info, (FILE *)NULL);

		if (exp == 1 || exp == -1)
		{
			if (zscompare(zf, 1) != 0)
			{
				*count = *count + 1;
				e = 0;
				zdiv(zn, zf, &zq, &zr);

				while (zscompare(zr, 0l) == 0)
				{
					e++;
					zcopy(zq, &zn);
					zdiv(zn, zf, &zq, &zr);
				}

				factor.exponent = e;
				factor.zfactor = zf;
				current = insert_factor_node(first, factor);
				first = current;
			}

			else
			{
				if (zprobprime(zn, 20))
				{
					factor.exponent = 1;
					factor.zfactor = zn;
					current = insert_factor_node(first, factor);
					first = current;
				}
			}
		}

		else
			break;
	}

	zfree(&zf);
	zfree(&zn);
	zfree(&zq);
	zfree(&zr);
	return first;
}
Lenstra’s Free LIP Lenstra’s ECM Factorization of the Eighth Fermat Number
Lenstra’s Free LIP Lenstra’s ECM Factorization of the Seventh Fermat Number

Blog Entry Monday April 4, 2022

This morning as I was leaving the gym at about 2:00 AM a fellow gym member made the following remark to me: “I hear you are a scientist” and I responded “yes, a computer scientist and computer or software engineer”. Later as I was headed towards my car, this same other gym member pointed towards a planet or star in the early morning sky and asked, “what is the object in the sky he was pointing towards was?”. I did note answer his question on the spot and now I offer the following theories. Well, if we had a high-resolution telescope and/or a spectroscope we could differentiate a planet from a star due to the chemical composition of the object. There is a theory posed by Alpher, Bethe, and Gamov which states the lightest elements in the universe, namely hydrogen and helium were formed during the Big Bang and the other 115 elements were either made by humans in nuclear physics laboratories (breeder nuclear reactors or other means) or the rest of the chemical elements were synthesized in the stars. Stars are classified by the Alpher, Bethe, and Gamov scheme:

Star Type Classification / NASA | Kaggle

https://blogs.scientificamerican.com/basic-space/httpblogsscientificamericancombasic-space20110802on-the-origin-of-chemical-elements/

Asymptotic giant branch – Wikipedia

Blog Entry Tuesday March 29, 2022

This application’s code was translated from vanilla C to C#. The C code is from the treatise “A Numerical Library for Scientists and Engineers” by H. T. Lau “Chapter 5: Analytic Problems – Runge-Kutta 5th order no derivatives in the right hand side”. The first test case is from the preceding tome.

RK2 Test Case
Micheal Penn’s Nonlinear ODE Data Table

I found an interesting differential second order nonlinear initial value equation on Michael Penn’s voluminous YouTube website: Michael Penn – YouTube. The equation is y”(x) = -exp(y). The solution is illustrated in the following table and graph:

Micheal Penn’s Nonlinear ODE Graph