factorization.cpp File Reference

Solves factorization and multiplication problems for two prime numbers using multiple QUBO solvers. More...

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/program_options.hpp>
#include <chrono>
#include <iostream>
#include <string>
#include <thread>
#include "qbpp.hpp"
#include "qbpp_abs2.hpp"
#include "qbpp_easy_solver.hpp"
#include "qbpp_grb.hpp"
#include "qbpp_misc.hpp"
#include "qbpp_multiplier.hpp"

Include dependency graph for factorization.cpp:

Go to the source code of this file.

Classes
class	qbpp::factorization::SolHolder
	Solution holder to store the best solution of factorization. More...
class	qbpp::factorization::ABS2Callback
	Class to define ABS2 callback function for factorization. More...
class	qbpp::factorization::GRB_Callback
	Class to define Gurobi callback function for factorization. More...

Namespaces
	qbpp
	Generates a QUBO Expression for the Graph Coloring Problem using QUBO++ library.
	qbpp::factorization
	Namespace for factorization using QUBO++ library.

Functions
std::string	qbpp::factorization::toBinaryString (uint64_t num)
	Converts a number to a binary string. More...
uint64_t	qbpp::factorization::as_uint64 (const qbpp::Sol &sol, const qbpp::Vector< qbpp::Var > &var, bool fix_lsb)
	Converts a vector of Var in a solution to a 64-bit unsigned integer. More...
uint64_t	qbpp::factorization::as_uint64 (const qbpp::SolHolder &sol_holder, const qbpp::Vector< qbpp::Var > &var, bool fix_lsb)
	Converts a vector of Var in a solution holder to a 64-bit unsigned integer. More...
bool	qbpp::factorization::is_prime (uint32_t num)
uint32_t	qbpp::factorization::rand_prime (int size)
	Generates a random prime number of the specified size. More...
int	main (int argc, char *argv[])
	Solves the factorization problem using ABS2 QUBO Solver and Gurobi optimizer from QUBO++ library. More...

Detailed Description

Solves factorization and multiplication problems for two prime numbers using multiple QUBO solvers.

Author

Koji Nakano

This program generates a QUBO model for factorization/multiplication using QUBO++ and solves it simultaneously using various QUBO solvers. Factorization/multiplication QUBO models are designed to simulate a binary multiplier. It supports the ABS2 GPU QUBO solver, the Gurobi optimizer, and the QUBO++ Easy solver. When a better solution is found by a solver, the other solvers are notified via callback functions for further improvement. The QUBO models are designed to simulate a binary multiplier.

Note

While it is impractical to perform factorization/multiplication through QUBO models due to their complexity, these problems are useful for understanding the usage of the QUBO++ library and for demonstrating the capabilities of QUBO solvers.

Version

2024-10-04

Definition in file factorization.cpp.

Function Documentation

main()

int main	(	int	argc,
		char *	argv[]
	)

Solves the factorization problem using ABS2 QUBO Solver and Gurobi optimizer from QUBO++ library.

Parameters

argc	Number of command line arguments.
argv	Command line arguments.

Returns

int Return code.

Generates a QUBO quad_model of the inverse computation of a binary multiplier circuit by and solves it using both ABS2 and Gurobi.

Definition at line 295 of file factorization.cpp.

Here is the call graph for this function: