Step by Step solution about How to resolve the algorithm Square form factorization step by step in the C++ programming language

The provided C++ code implements a SQUFOF (Squaring and Quadratic Frobenius Normal Form) algorithm to factorise integers. It uses BQF (Binary quadratic form) structures to represent quadratic equations and performs a series of rho and rho inverse operations to identify factors of the input number.

Here's a detailed explanation of the code:

1. Class BQF (Binary Quadratic Form):

   • This class represents a binary quadratic form of the form ax^2 + bxy + cy^2.
   • It has public members a, b, and c, which represent the coefficients of the quadratic equation.
   • It has two private members, q and bb, which are used in the rho and rho inverse operations.

2. Function squfof:

   • This function takes an unsigned 64-bit integer number as input and attempts to factorise it using the SQUFOF algorithm.
   • It first computes the square root of the input number and stores it in sqrt. If the square root is an integer (i.e., sqrt * sqrt == number), it returns sqrt as a factor.
   • If not, it initialises test_value with the input number and sqrt_test_value with the square root of test_value.
   • It creates an initial BQF in the "principal form" (a = 0, b = sqrt_test_value, c = 1) and applies the rho inverse operation to it.

3. Rho and Rho Inverse Operations:

   • The rho function performs a "rho" operation on a BQF. It computes a new BQF with coefficients a, c, and bb, where bb = q * c - b and q = ( sqrt_test_value + b ) / c.
   • The rho_inverse function performs a "rho inverse" operation on a BQF. It computes a new BQF with coefficients c, bb, and a, where bb = -b * b / c and a = test_value - bb * bb / c.

4. Principal Cycle Search:

   • It enters a loop that iterates for 4 * std::sqrt(2 * sqrt_test_value) times, incrementing by 2 in each iteration.
   • For each even iteration, it applies the rho operation to the current BQF.
   • It checks if the square root of the c coefficient of the BQF is an integer. If so, it means a square form has been found.
   • If a square form is found, it computes the inverse square root by creating a new BQF with coefficients a = 0, b = -form.b, and c = sqrt_c.
   • It then applies the rho inverse operation to the inverse square root BQF.

5. Ambiguous Cycle Search:

   • It enters a loop that repeatedly applies the rho operation to the inverse square root BQF until it reaches a BQF where b is equal to the previous value of b.
   • This loop identifies the "symmetry point" of the ambiguous cycle.
   • It computes the greatest common divisor (GCD) of the input number number and the a coefficient of the symmetry point BQF. If the GCD is not 1, it means a factor has been found.

6. Main Function:

   • It uses a random number generator to generate 20 random 64-bit integers within a specified range.
   • For each random integer, it calls the squfof function to attempt factorisation.
   • It prints the factorisation results or an indication of failure if no factor could be found.

Overall, this code demonstrates the implementation of the SQUFOF algorithm for integer factorisation. It uses the BQF structure to represent quadratic equations and employs rho and rho inverse operations to efficiently search for factors.

#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <random>

uint64_t test_value = 0;
uint64_t sqrt_test_value = 0;

class BQF { // Binary quadratic form
public:
	BQF(const uint64_t& a, const uint64_t& b, const uint64_t& c) : a(a), b(b), c(c) {
		q = ( sqrt_test_value + b ) / c;
		bb = q * c - b;
	}

	BQF rho() {
		return BQF(c, bb, a  + q * ( b - bb ));
	}

	BQF rho_inverse() {
		return BQF(c, bb, ( test_value - bb * bb ) / c);
	}

	uint64_t a, b, c;
private:
	uint64_t q, bb;
};

uint64_t squfof(const uint64_t& number) {
	const uint32_t sqrt = std::sqrt(number);
	if ( sqrt * sqrt == number ) {
		return sqrt;
	}

	test_value = number;
	sqrt_test_value = std::sqrt(test_value);

	// Principal form
	BQF form(0, sqrt_test_value, 1);
	form = form.rho_inverse();

	// Search principal cycle
	for ( uint32_t i = 0; i < 4 * std::sqrt(2 * sqrt_test_value); i += 2 ) {
		// Even step
		form = form.rho();

		uint64_t sqrt_c = std::sqrt(form.c);
		if ( sqrt_c * sqrt_c == form.c ) { // Square form found
			// Inverse square root
			BQF form_inverse(0, -form.b, sqrt_c);
			form_inverse = form_inverse.rho_inverse();

			// Search ambiguous cycle
			uint64_t previous_b = 0;
			do {
				previous_b = form_inverse.b;
				form_inverse = form_inverse.rho();
			} while ( form_inverse.b != previous_b );

			// Symmetry point
			const uint64_t g = std::gcd(number, form_inverse.a);
			if ( g != 1 ) {
				return g;
			}
		}

		// Odd step
		form = form.rho();
	}

	if ( number % 2 == 0 ) {
		return 2;
	}
	return 0; // Failed to factorise, possibly a prime number
}

int main() {
	std::random_device random;
	std::mt19937 generator(random());
	const uint64_t lower_limit = 100'000'000'000'000'000;
	std::uniform_int_distribution<uint64_t> distribution(lower_limit, 10 * lower_limit);

	for ( uint32_t i = 0; i < 20; ++i ) {
		uint64_t test = distribution(random);
		uint64_t factor = squfof(test);

		if ( factor == 0 ) {
			std::cout << test << " - failed to factorise" << std::endl;
		} else {
			std::cout << test << " = " << factor << " * " << test / factor << std::endl;
		}
		std::cout << std::endl;
   }
}