Category: Number Theory
Blog Entry © Thursday, October 23, 2025, by James Pate Williams, Jr. A Stochastic ProblemRelated to the Subset Sum Problem
Blog Entry © Tuesday, October 21, 2025, by James Pate Williams, Jr., Solving Low Density Subset Sum Problems Using the LLL-Lattice Reduction Algorithm
// 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 © 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
#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, July 27, 2025, A Bit of Programming Nostalgia Prime Number Related Programs by James Williams, Jr.
/*
Author: Pate Williams c 1995
The following program is a solution to problem 18.15
in Pascalgorithms by Edwin D. Reilly and Francis D.
Federighi page 627. The program uses Simpson's rule
to calculate the number of primes less than or equal
a given number.
*/
#include <math.h>
#include <stdio.h>
typedef double real;
static real f(real x)
{
return(1.0 / log(x));
}
static real simpson(int n, real a, real b)
{
int i;
real evensum, h, oddsum, twoh, x;
if (n % 2 == 1) n = n - 1;
h = (b - a) / n;
twoh = h + h;
x = h + a;
oddsum = 0.0;
for (i = 1; i <= n / 2; i++)
{
oddsum += f(x);
x = twoh + x;
}
x = twoh + a;
evensum = 0.0;
for (i = 1; i <= n / 2 - 1; i++)
{
evensum += f(x);
x = twoh + x;
}
return(h / 3.0 * (f(a) + f(b) + 4.0 * oddsum + 2.0 * evensum));
}
int main(void)
{
int i, n, Nmaximum = 0, Nminimum = 0, Nstep;
printf("n = "); scanf_s("%d", &n);
printf("N minimum = "); scanf_s("%d", &Nminimum);
printf("N maximum = "); scanf_s("%d", &Nmaximum);
printf("N step = "); scanf_s("%d", &Nstep);
printf("\n");
printf("----------------------------------------\n");
printf("Min\t\tMax\t\tprimes\n");
printf("----------------------------------------\n");
for (i = Nminimum; i <= Nmaximum; i += Nstep)
{
printf("%8d\t%8d\t%8.0lf\n", Nminimum, i + Nstep,
simpson(n, Nminimum, i + Nstep));
}
printf("----------------------------------------\n");
return(0);
}
n = 1024
N minimum = 0
N maximum = 10000000
N step = 1000000
----------------------------------------
Min Max primes
----------------------------------------
0 1000000 78551
0 2000000 148923
0 3000000 216788
0 4000000 283122
0 5000000 348361
0 6000000 412754
0 7000000 476461
0 8000000 539590
0 9000000 602224
0 10000000 664424
0 11000000 726239
----------------------------------------
D:\PrimeCounter\x64\Release\PrimeCounter.exe (process 51884) exited with code 0 (0x0).
Press any key to close this window . . .
/*
Author: Pate Williams c 1995
The following is a translation of the Pascal program
sieve found in Pascalgorithms by Edwin D. Reilly and
Francis D. Federighi page 652. This program uses sets
to represent the sieve (see C Programming Language An
Applied Perspective by Lawrence Miller and Alec Qui-
lici pages 160 - 162).
*/
#include <math.h>
#include <stdio.h>
#define _WORD_SIZE 32
#define _VECT_SIZE 524288
#define SET_MIN 0
#define SET_MAX 16777215
typedef unsigned long SET[_VECT_SIZE];
typedef long ELEMENT;
typedef unsigned long LONG;
SET set;
static int get_bit_pos(int* long_ptr, int* bit_ptr,
ELEMENT element)
{
*long_ptr = element / _WORD_SIZE;
*bit_ptr = element % _WORD_SIZE;
return(element >= SET_MIN && element <= SET_MAX);
}
static void set_bit(ELEMENT element, int inset)
{
int bit, word;
if (get_bit_pos(&word, &bit, element))
{
if (inset > 0)
set[word] |= (01 << bit);
else
set[word] &= ~(01 << bit);
}
}
static int get_bit(ELEMENT element)
{
int bit, word;
return(get_bit_pos(&word, &bit, element) ?
(set[word] >> bit) & 01 : 0);
}
static void set_Add(ELEMENT element)
{
set_bit(element, 1);
}
static void set_Del(ELEMENT element)
{
set_bit(element, 0);
}
static int set_Mem(ELEMENT element)
{
return get_bit(element);
}
static void primes(long n)
{
long c, i, inc, k;
double x;
set_Add(2);
for (i = 3; i <= n; i++)
if ((i + 1) % 2 == 0)
set_Add(i);
else
set_Del(i);
c = 3;
do
{
i = c * c;
inc = c + c;
while (i <= n)
{
set_Del(i);
i = i + inc;
}
c += 2;
while (set_Mem(c) == 0) c += 1;
} while (c * c <= n);
k = 0;
for (i = 2; i <= n; i++)
if (set_Mem(i) == 1) k++;
x = n / log(n) - 5.0;
x = x + exp(1.0 + 0.15 * log(n) * sqrt(log(n)));
printf("%8ld\t%8ld\t%8.0lf\n", n, k, x);
}
int main(void)
{
long n = 100L;
printf("----------------------------------------\n");
printf("n\t\tprimes\t\ttheory\n");
printf("----------------------------------------\n");
do
{
primes((int)n);
n = 10L * n;
} while (n < (long)SET_MAX);
printf("----------------------------------------\n");
return(0);
}
----------------------------------------
n primes theory
----------------------------------------
100 25 29
1000 168 181
10000 1229 1261
100000 9592 9634
1000000 78498 78396
10000000 664579 665060
----------------------------------------
D:\Sieve\x64\Release\Sieve.exe (process 60092) exited with code 0 (0x0).
Press any key to close this window . . .
Blog Entry (c) Thursday, June 19, 2025, Factorizations of Some Composite Integers Using Two Different Computer Languages and Methods
Factorizations of the Seventh Fermat Number
and Other Composite Integers Using the
Pollard-Shor-Williams C# App and the LIP
Lenstra Elliptic Curve Method
It took 20.1 hours for J. M. Pollard to
factor the Seventh Fermat Number in
December 1988. He was using an 8-bit
Philips P2012 personal computer with
64k RAM and two 640k floppy drives.
His seven programs were written in the
Pascal computer language. The current
author was using a 64-bit Core i5 Dell
Latitude 3410 notebook computer with
8 GB RAM and a 235 GB solid state
hard drive. The computer language was
Windows 32 vanilla C in the Release x64
Configuration. The operating system was
Windows 11 Pro with the Visual Studio
2022 Community Version Integrated
Development Environment and C#.
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 1
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:20:31.359
Function Evaluations = 661379586
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 2
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:12:31.146
Function Evaluations = 283327140
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 3
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:21:53.637
Function Evaluations = 371472150
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 4
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:15:25.712
Function Evaluations = 197866620
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 5
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:03:06.030
Function Evaluations = 19501012
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 6
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:12:25.076
Function Evaluations = 198404541
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 7
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:20:59.172
Function Evaluations = 168943987
2^128+1
340282366920938463463374607431768211457 39
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 8
59649589127497217 p 17
5704689200685129054721 p 22
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:04:58.588
Function Evaluations = 13754504
Using Lenstra's Elliptic Curve Method
enter the number to be factored below:
2^128+1
340282366920938463463374607431768211457
number has 39 digits
== Menu ==
1 Cohen's Brent-Pollard Method
2 Cohen's Trial Division
3 Lenstra's Elliptic Curve Method
4 Pollard p-1 Method First Stage
5 Pollard p-1 Both Stages
6 Pollard-Shor-Williams Method
7 Exit Application
Enter an option '1' to '7':
3
factorization is complete
Runtime in seconds:
1.00000 sec.
original number has 39-decimal digits
'c' means composite and 'p' means prime
59649589127497217 17-decimal digits p
5704689200685129054721 22-decimal digits p
enter the number to be factored below:
Miscellaneous numbers using the C# app:
2^32+1
4294967297 10
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 1
641 p 3
6700417 p 7
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:00.034
Function Evaluations = 57
2^41-1
2199023255551 13
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 1
13367 p 5
164511353 p 9
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:00.003
Function Evaluations = 1128
2^67-1
147573952589676412927 21
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 1
193707721 p 9
761838257287 p 12
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:00.065
Function Evaluations = 30519
2^144-3
22300745198530623141535718272648361505980413 44
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 1
492729991333 p 12
45259565260477899162010980272761 p 32
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:04.804
Function Evaluations = 2458746
2^32+1
4294967297 10
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 5
641 p 3
6700417 p 7
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:00.001
Function Evaluations = 81
2^41-1
2199023255551 13
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 5
13367 p 5
164511353 p 9
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:00.002
Function Evaluations = 174
2^67-1
147573952589676412927 21
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 5
193707721 p 9
761838257287 p 12
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:00.050
Function Evaluations = 35949
2^144-3
22300745198530623141535718272648361505980413 44
Pseudo-Random Number Generator Seed = 1
Number of Tasks = 5
492729991333 p 12
45259565260477899162010980272761 p 32
Total Elapsed Runtime Hrs:Min:Sec.MS = 00:00:01.613
Function Evaluations = 632928
Now Lenstra's ECM:
enter the number to be factored below:
2^32+1
4294967297
number has 10 digits
== Menu ==
1 Cohen's Brent-Pollard Method
2 Cohen's Trial Division
3 Lenstra's Elliptic Curve Method
4 Pollard p-1 Method First Stage
5 Pollard p-1 Both Stages
6 Pollard-Shor-Williams Method
7 Exit Application
Enter an option '1' to '7':
3
factorization is complete
Runtime in seconds:
0.00000 sec.
original number has 10-decimal digits
'c' means composite and 'p' means prime
641 3-decimal digits p
6700417 7-decimal digits p
enter the number to be factored below:
2^41-1
2199023255551
number has 13 digits
== Menu ==
1 Cohen's Brent-Pollard Method
2 Cohen's Trial Division
3 Lenstra's Elliptic Curve Method
4 Pollard p-1 Method First Stage
5 Pollard p-1 Both Stages
6 Pollard-Shor-Williams Method
7 Exit Application
Enter an option '1' to '7':
3
factorization is complete
Runtime in seconds:
0.00000 sec.
original number has 13-decimal digits
'c' means composite and 'p' means prime
13367 5-decimal digits p
164511353 9-decimal digits p
enter the number to be factored below:
2^67-1
147573952589676412927
number has 21 digits
== Menu ==
1 Cohen's Brent-Pollard Method
2 Cohen's Trial Division
3 Lenstra's Elliptic Curve Method
4 Pollard p-1 Method First Stage
5 Pollard p-1 Both Stages
6 Pollard-Shor-Williams Method
7 Exit Application
Enter an option '1' to '7':
3
factorization is complete
Runtime in seconds:
0.00000 sec.
original number has 21-decimal digits
'c' means composite and 'p' means prime
193707721 9-decimal digits p
761838257287 12-decimal digits p
enter the number to be factored below:
2^144-3
22300745198530623141535718272648361505980413
number has 44 digits
== Menu ==
1 Cohen's Brent-Pollard Method
2 Cohen's Trial Division
3 Lenstra's Elliptic Curve Method
4 Pollard p-1 Method First Stage
5 Pollard p-1 Both Stages
6 Pollard-Shor-Williams Method
7 Exit Application
Enter an option '1' to '7':
3
factorization is complete
Runtime in seconds:
0.00000 sec.
original number has 44-decimal digits
'c' means composite and 'p' means prime
492729991333 12-decimal digits p
45259565260477899162010980272761 32-decimal digits p
enter the number to be factored below:
For the last number 2^144-3 it took J. M. Pollard's
factoring with cubic integers 47 hours in 1988.
Live Person-to-Person Tutoring
Blog Entry (c) Monday September 16, 2024, by James Pate Williams, Jr. Ramanujan Highly Composite Numbers
Ramanujan Highly Composite Numbers
## 2 3 5 7 11 13
1 2 1
2 4 2
3 6 1 1
4 12 2 1
5 24 3 1
6 36 2 2
7 48 4 1
8 60 2 1 1
9 120 3 1 1
10 180 2 2 1
11 240 4 1 1
12 360 3 2 1
13 720 4 2 1
14 840 3 1 1 1
15 1260 2 2 1 1
16 1680 4 1 1 1
17 2520 3 2 1 1
18 5040 4 2 1 1
19 7560 3 3 1 1
20 10080 5 2 1 1
21 15120 4 3 1 1
22 20160 6 2 1 1
23 25200 4 2 2 1
24 27720 3 2 1 1 1
25 45360 4 4 1 1
26 50400 5 2 2 1
27 55440 4 2 1 1 1
28 83160 3 3 1 1 1
29 110880 5 2 1 1 1
30 166320 4 3 1 1 1
31 221760 6 2 1 1 1
32 277200 4 2 2 1 1
33 332640 5 3 1 1 1
34 498960 4 4 1 1 1
35 554400 5 2 2 1 1
36 665280 6 3 1 1 1
37 720720 4 2 1 1 1 1
38 1081080 3 3 1 1 1 1
39 1441440 5 2 1 1 1 1
40 2162160 4 3 1 1 1 1
Runtime in seconds = 182.490
Type any character to exit application
Numerical Explorations 