MFP Method for Deterministic
Structural Factorization
Abstract
This article presents a comparison between three distinct versions of the MFP (Pattern-
Based Factorization Method), implemented in C++ using parallelism and optimization
techniques. Each version applies the decimal structure of the number, combined with
multiple k in {1, 3, 7, 9}, and a redistribution based on the equation n*k = 10*A + d0. The
goal is to evaluate computational efficiency, complete factorization capability, and the
reliability of the extracted divisors.
Code 1: MFP with GMP, i Blocks, and Dynamic Parallelism
Structure: Uses threads with distribution of i blocks. The variable nk = n * k is used to derive
the decimal base A and digit d0. Each divisor is tested in the form d = d0 + 10*i.
Formulations and Logic:
1. Compute nk = n * k
2. Derive A and d0: nk = 10*A + d0
3. For each i, form d = d0 + 10*i
4. Check two conditions simultaneously:
- A - i is divisible by d (i.e., A mod d = i mod d)
- n is divisible by d
Formal Demonstration:
If n*k = 10*A + d0 then any divisor d of n must satisfy the congruence A - i ≡ 0 mod d for
some i such that d = d0 + 10*i. This reduces the search space for real divisors to an
arithmetic sequence.
#include <cstddef>
#include <iostream>
#include <vector>
#include <thread>
#include <atomic>
#include <mutex>
#include <chrono>
#include <gmp.h>
Class MFPFirstDivisor {
Public:
Explicit MFPFirstDivisor(const std::string &s) {
Mpz_init_set_str(n_, s.c_str(), 10);
}
~MFPFirstDivisor() {
Mpz_clear(n_);
}
Void run() {
Auto t0 = std::chrono::steady_clock::now();
Unsigned long d = findFirstDivisor();
Auto t1 = std::chrono::steady_clock::now();
Std::chrono::duration<double> dt = t1 – t0;
If (d == 0) {
Char *s = mpz_get_str(nullptr, 10, n_);
Std::cout << “Primo: “ << s << “\n”;
Std::free(s);
} else {
Std::cout << “Divisor: “ << d << “\n”;
}
Std::cout << “Tempo: “ << dt.count() << “ s\n”;
}
Private:
Mpz_t n_;
Std::atomic<bool> found_{false};
Std::mutex mtx_;
Unsigned long found_d_{0};
Const std::vector<int> ks_{1,3,7,9};
Const std::vector<int> small_primes_{2,3,5};
Static constexpr unsigned long block_size = 231;
Unsigned long findFirstDivisor() {
// 1) check small primes
For (int p : small_primes_) {
If (mpz_divisible_ui_p(n_, p) && mpz_cmp_ui(n_, p) != 0) {
Return p;
}
}
// 2) prepare per-k data
Struct Kdata {
Mpz_t A;
Unsigned long d0;
Unsigned long i_max;
Unsigned long num_blocks;
Std::vector<unsigned int> offs;
};
Std::vector<Kdata> K(ks_.size());
For (size_t ki = 0; ki < ks_.size(); ++ki) {
Int k = ks_[ki];
Mpz_init(K[ki].A);
Mpz_t nk, root;
Mpz_inits(nk, root, NULL);
Mpz_mul_ui(nk, n_, k);
Mpz_fdiv_q_ui(K[ki].A, nk, 10);
K[ki].d0 = mpz_fdiv_ui(nk, 10);
If ((K[ki].d0 & 1) == 0 || K[ki].d0 % 5 == 0) {
Mpz_clears(nk, root, NULL);
Continue;
}
Mpz_sqrt(root, nk);
Unsigned long r = mpz_get_ui(root);
Double ck = (k==1?1.0k==3?2.0/3k==7?4.0/7:0.5)));
K[ki].i_max = static_cast<unsigned long>(r * ck / 10.0);
For (unsigned int off = 0; off < block_size; ++off) {
Unsigned long d = K[ki].d0 + off*10;
If ((d & 1) == 0 || d % 3 == 0 || d % 5 == 0 || d % 7 == 0 || d % 11 == 0) continue;
K[ki].offs.push_back(off);
}
K[ki].num_blocks = K[ki].i_max / block_size;
Mpz_clears(nk, root, NULL);
}
// 3) dynamic scheduling across 8 threads
Std::vector<std::atomic<unsigned long>> blockCtr(ks_.size());
Std::vector<std::thread> threads;
Threads.reserve(8);
For (int t = 0; t < 8; ++t) {
Threads.emplace_back([&]() {
While (!found_.load()) {
Bool idle = true;
For (size_t ki = 0; ki < ks_.size() && !found_.load(); ++ki) {
Unsigned long b = blockCtr[ki].fetch_add(1, std::memory_order_relaxed);
If (b < K[ki].num_blocks) {
Idle = false;
For (unsigned int off : K[ki].offs) {
Unsigned long I = b * block_size + off;
If (I > K[ki].i_max) break;
Unsigned long d = K[ki].d0 + i*10;
If (d <= 1 || mpz_cmp_ui(n_, d) <= 0) continue;
If (!mpz_divisible_ui_p(n_, d)) continue;
Unsigned long a_mod = mpz_fdiv_ui(K[ki].A, d);
If (a_mod != (I % d)) continue;
Std::lock_guard<std::mutex> lk(mtx_);
If (!found_.load()) {
Found_d_ = d;
Found_.store(true);
}
Return;
}
}
}
If (idle) break;
}
});
}
For (auto &th : threads) th.join();
For (auto &kd : K) {
Mpz_clear(kd.A);
}
Return found_d_;
}
};
Int main() {
Const char *tests[] = {
“91”,
“169”,
“2199023255551”,
“9007199254740991”,
“147573952589676412927”,
Nullptr
};
For (int I = 0; tests[i]; ++i) {
Std::cout << “Analisando n = “ << tests[i] << “\n”;
MFPFirstDivisor f(tests[i]);
f.run();
std::cout << “-------------------------\n”;
}
Return 0;
}
Analisando n = 91
Primo: 91
Tempo: 0.00137177 s
Analisando n = 169
Primo: 169
Tempo: 0.00497777 s
Analisando n = 2199023255551
Divisor: 13367
Tempo: 0.00701538 s
Analisando n = 9007199254740991
Divisor: 6361
Tempo: 0.00734277 s
Analisando n = 147573952589676412927
Divisor: 193707721
Tempo: 0.536191 s
[Program finished]
Code 2: MFP with __int128, Direct q Analysis, and Pthreads
Structure: Reformulates the problem focusing on q (number of decimal redistributions). For
each q, it attempts to derive i directly via the inverted redistribution equation.
Formulations and Logic:
1. Start from nk = 10*A + d0
2. Rearrange the redistribution equation: A - i = q*d → i = (A - q*d0)/(10*q + 1)
3. Validate if i is a positive integer and if d = d0 + 10*i satisfies:
- A - i is divisible by d
- n is divisible by d
Proof: The equation A - i = q*d comes directly from the decimal redistribution structure. If
we can find a q such that (A - q*d0) is divisible by (10*q + 1), then the resulting i leads us to
the true divisor.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdatomic.h>
#include <math.h>
#include <time.h>
Typedef unsigned __int128 u128;
Static void print_u128(u128 x){
Char buf[50]; int i=49; buf[i]=’\0’;
If(!x){ puts(“0”); return; }
While(x){ buf[--i]=’0’+x%10; x/=10; }
Puts(buf+i);
}
Static u128 str_to_u128(const char* s){
U128 n=0; while(*s) n=n*10+(*s++-‘0’); return n;
}
Typedef struct {
U128 n;
Int k;
Unsigned long q_ini, q_end;
} job_t;
#define THREADS 8
Static pthread_t pool[THREADS];
Static job_t jobs[THREADS];
Static atomic_ulong d_found;
Static void* worker(void* arg){
Job_t* J = (job_t*)arg;
U128 n = J->n;
Int k = J->k;
If(!k){ return NULL; }
U128 nk = n * (u128)k;
Unsigned d0 = (unsigned)(nk % 10);
If((d0&1)==0 || d0%5==0) return NULL;
U128 A = nk / 10;
For(unsigned long q=J->q_ini; q<=J->q_end && !d_found; ++q){
Unsigned long denom = 10UL*q+1;
U128 numer = A – (u128)q*d0;
If(numer % denom) continue;
U128 I = numer / denom;
Unsigned long d = d0 + 10UL*(unsigned long)I;
If(d<=1 || (u128)d>=n) continue;
U128 Ai = A – I;
If(Ai % d) continue;
If(n % d) continue;
If(!atomic_exchange(&d_found,d)){
Printf(“ k=%d q=%lu d=%lu i=”,k,q,d); print_u128(i);
}
Break;
}
Return NULL;
}
Static void exec_pool(int active){
For(int t=0;t<active;++t) pthread_create(&pool[t],NULL,worker,&jobs[t]);
For(int t=0;t<active;++t) pthread_join(pool[t],NULL);
}
Static void testar(u128 n){
Printf(“\n=== n = “); print_u128(n);
// divisão por 2, 3 e 5
For(int p : (int[]){2, 3, 5}) {
If(n % p == 0 && n != p){
Printf(“Divisor: %d\n”, p);
Return;
}
}
Struct timespec t0,t1;
Clock_gettime(CLOCK_MONOTONIC,&t0);
D_found=0;
Int ks[4]={1,3,7,9};
Int jt=0;
For(int idx=0; idx<4; ++idx){
Int k=ks[idx];
U128 nk = n*(u128)k, A=nk/10;
Unsigned long qmax = (unsigned long)(2.0*sqrt((double)A));
Unsigned long mid = qmax/2;
Jobs[jt++] = (job_t){n,k,1,mid};
Jobs[jt++] = (job_t){n,k,mid+1,qmax};
}
Exec_pool(jt);
Clock_gettime(CLOCK_MONOTONIC,&t1);
Double dt = (t1.tv_sec-t0.tv_sec)+(t1.tv_nsec-t0.tv_nsec)/1e9;
If(!d_found) puts(“Nenhum divisor encontrado.”);
Printf(“Tempo (parede): %.6f s\n”, dt);
}
Int main(){
Const char* lista[]={
“91”,”169”,”2199023255551”,”9007199254740991”,
“147573952589676412927”,”590295810358705651711”,
“9444732965739290427391”,NULL};
For(int i=0; lista[i]; ++i) testar(str_to_u128(lista[i]));
Return 0;
}
=== n = 91
K=7 q=9 d=7 i=0
Tempo (parede): 0.001207 s
=== n = 169
K=7 q=9 d=13 i=1
Tempo (parede): 0.007162 s
=== n = 2199023255551
K=3 q=4010 d=164511353 i=16451135
Tempo (parede): 0.004818 s
=== n = 9007199254740991
K=1 q=636 d=1416003655831 i=141600365583
Tempo (parede): 0.001398 s
=== n = 147573952589676412927
K=1 q=19370772 d=761838257287 i=76183825728
Tempo (parede): 1.313835 s
=== n = 590295810358705651711
K=3 q=14 d=12559485326780971313 i=1255948532678097131
Tempo (parede): 0.002723 s
=== n = 9444732965739290427391
K=1 q=229804 d=4109906205215351 i=410990620521535
Tempo (parede): 0.044874 s
[Program finished]
Code 3: MFP with Recursive Factorization, GMP, and Wheel Mod 2310
Structure: Similar to Code 1, but includes filtering of d using the 2310 wheel (product of
2*3*5*7*11). After finding a divisor, it applies recursive division until the number is fully
factored.
Formulations and Logic:
1. nk = 10*A + d0
2. i iterates over values filtered by the wheel
3. For each d = d0 + 10*i, validate:
- A - i is divisible by d
- n is divisible by d
4. Once a valid divisor is found, apply:
- n → d and n/d recursively until primes are obtained
Demonstration: The redistribution structure ensures that the divisors are congruent with
the decimal base of nk. Filtering via the wheel ensures that tested candidates are non-trivial
and avoids false positives.
Import subprocess
Import os
# Garante que o diretório existe
Os.makedirs(‘/mnt/data’, exist_ok=True)
# Código C++ reestruturado com wheel mod2310 (2,3,5,7,11)
Cpp_code = r’’’
#include <iostream>
#include <vector>
#include <thread>
#include <atomic>
#include <mutex>
#include <chrono>
#include <gmp.h>
Class MFPFactorizer {
Public:
MFPFactorizer(const std::string& s) {
Mpz_init_set_str(n_, s.c_str(), 10);
}
~MFPFactorizer() {
Mpz_clear(n_);
}
Void factor() {
Auto t0 = std::chrono::steady_clock::now();
factorRecursive(n_);
auto t1 = std::chrono::steady_clock::now();
std::chrono::duration<double> dt = t1 – t0;
std::cout << “Tempo total: “ << dt.count() << “ s\n\n”;
}
Private:
Mpz_t n_;
Std::atomic<bool> found_{false};
Std::mutex mtx_;
Unsigned long found_d_{0};
Const std::vector<int> ks_{1,3,7,9};
Const std::vector<int> small_primes_{2,3,5};
Bool checkSmallPrimes(const mpz_t n) {
For(int p : small_primes_) {
If (mpz_divisible_ui_p(n, p) && mpz_cmp_ui(n, p) != 0) {
printResult(p);
return true;
}
}
Return false;
}
Void factorRecursive(const mpz_t n) {
If (mpz_cmp_ui(n, 1) <= 0) return;
If (checkSmallPrimes(n)) return;
Found_.store(false);
Found_d_ = 0;
Std::vector<std::thread> threads;
For(int k : ks_) {
Threads.emplace_back(&MFPFactorizer::searchK, this, n, k);
}
For(auto& t : threads) t.join();
Unsigned long d = found_d_;
If (d == 0) {
Char* s = mpz_get_str(NULL,10,n);
Std::cout<<”Primo: “<<s<<”\n”;
Free(s);
} else {
printResult(d);
mpz_t d_mpz; mpz_init_set_ui(d_mpz,d);
factorRecursive(d_mpz);
mpz_clear(d_mpz);
mpz_t q; mpz_init(q);
mpz_divexact_ui(q,n,d);
factorRecursive(q);
mpz_clear(q);
}
}
Void printResult(unsigned long d) {
Std::cout<<”Divisor: “<<d<<”\n”;
}
Void searchK(const mpz_t n, int k) {
If (found_.load()) return;
Mpz_t nk, A, root;
Mpz_inits(nk, A, root, NULL);
Mpz_mul_ui(nk,n,k);
Mpz_fdiv_q_ui(A,nk,10);
Unsigned int d0 = mpz_fdiv_ui(nk,10);
If ((d0 & 1)==0 || d0 % 5 == 0) {
Mpz_clears(nk,A,root,NULL);
Return;
}
Mpz_sqrt(root,nk);
Unsigned long r = mpz_get_ui(root);
Mpz_clear(root);
Double ck = (k==1?1.0k==3?2.0/3k==7?4.0/7:0.5)));
Unsigned long i_max = static_cast<unsigned long>(r * ck / 10.0);
// wheel mod 2310: block = 2310/gcd(10,2310)=231
Const unsigned long block = 231;
Std::vector<unsigned int> offs;
Offs.reserve(block);
For(unsigned int off=0; off<block; ++off) {
Unsigned long d = d0 + off*10;
If ((d&1)==0) continue;
If (d%3==0d%5==0d%7==0) continue;
If (d%11==0) continue;
Offs.push_back(off);
}
Unsigned long num_blocks = i_max / block;
For(unsigned long b=0; b<num_blocks && !found_.load(); ++b){
Unsigned long base=b*block;
For(unsigned int off:offs){
If (found_.load()) break;
Unsigned long I = base+off;
Unsigned long d = d0 + i*10;
If (d<=1 || mpz_cmp_ui(n,d)<=0) continue;
If (!mpz_divisible_ui_p(n,d)) continue;
Unsigned long a_mod = mpz_fdiv_ui(A,d);
If (a_mod != (I % d)) continue;
Std::lock_guard<std::mutex> lk(mtx_);
If (!found_.load()){
Found_d_ = d;
Found_.store(true);
}
Break;
}
}
// tail
Unsigned long start_tail = num_blocks*block;
For(unsigned long i=start_tail; i<=i_max && !found_.load(); ++i){
Unsigned long d = d0 + i*10;
If (d<=1 || mpz_cmp_ui(n,d)<=0) continue;
If (!mpz_divisible_ui_p(n,d)) continue;
Unsigned long a_mod = mpz_fdiv_ui(A,d);
If (a_mod != (I % d)) continue;
Std::lock_guard<std::mutex> lk(mtx_);
If (!found_.load()){
Found_d_ = d;
Found_.store(true);
}
Break;
}
Mpz_clears(nk,A,NULL);
}
};
Int main(){
Const char* tests[] = {
“91”,”169”,”2199023255551”,”9007199254740991”,
“147573952589676412927”,nullptr
};
For(int i=0; tests[i]; ++i){
Std::cout<<”Analisando n=”<<tests[i]<<”\n”;
MFPFactorizer f(tests[i]);
f.factor();
}
Return 0;
}
‘’’
# Escreve e compila
Path = ‘/mnt/data/mfp_gmp_wheel2310.cpp’
With open(path, ‘w’) as f:
f.write(cpp_code)
comp = subprocess.run(
[“g++”,”-O3”,”-std=c++17”,”-march=native”,path,”-lgmp”,”-
o”,”/mnt/data/mfp_gmp_wheel2310.out”],
Capture_output=True, text=True
)
Print(“Compile stdout:\n”, comp.stdout)
Print(“Compile stderr:\n”, comp.stderr)
# Executa e mostra resultados
If os.path.exists(‘/mnt/data/mfp_gmp_wheel2310.out’):
Outp = subprocess.run(
[“/mnt/data/mfp_gmp_wheel2310.out”], capture_output=True, text=True
)
Print(“Program output:\n”, outp.stdout)
R:
Analisando n=91
Divisor: 13
Primo: 13
Primo: 7
Tempo total: 0.00368324 s
Analisando n=169
Divisor: 13
Primo: 13
Primo: 13
Tempo total: 0.00246891 s
Analisando n=2199023255551
Divisor: 13367
Primo: 13367
Primo: 164511353
Tempo total: 0.00269045 s
Analisando n=9007199254740991
Divisor: 6361
Primo: 6361
Divisor: 69431
Primo: 69431
Primo: 20394401
Tempo total: 0.00439212 s
Analisando n=147573952589676412927
Divisor: 193707721
Primo: 193707721
Primo: 761838257287
Tempo total: 0.225671 s
Conclusion
Code 2 is the fastest for finding a single divisor. Code 1 is robust with arbitrary precision
and efficient parallelism. Code 3 is the most complete and fastest for large numbers, offering
total factorization with the elimination of trivial divisors via modular wheel.
Each version has ideal applications:
- Code 1 for distributed primality testing;
- Code 2 for fast detection of composites;
- Code 3 for complete factorization and use in cryptography and RSA evaluation.
These three approaches show that the MFP structure can be refined for either speed or
exhaustiveness, depending on application needs.
**9. ACKNOWLEDGMENTS**
I thank the Great Architect of the Universe, my parents Helvio Polegato and Fátima I. L.
Polegato, my wife Tayrine S. B. Polegato, and the friends and family who supported me on
this journey.
**References**
1. Riesel, H. (2008). *Prime Numbers and Computer Methods for Factorization*.
2. Apostol, T.M. (1976). *Introduction to Analytic Number Theory*.
3. Ribenboim, P. (1989). *The Book of Prime Number Records*.
4. Polegato, M.F. (2024). *Redistribuição Decimal e Detecção de Primalidade*.
5. Polegato, M.F. (2024). *Método Modular 12*. Núcleo do Conhecimento.
https://www.nucleodoconhecimento.com.br/matematica/desvendando-padroes,
DOI: 10.32749/nucleodoconhecimento.com.br/matematica/desvendando-padroes
6. Polegato, M.F. (2022). *Fermat’s Library* – https://fermatslibrary.com/p/2e0648ef
7. Polegato, M.F. (2025). *Fermat’s Library* – https://fermatslibrary.com/p/a16a871a