Pattern-Based Factorization Method
(P.F.M.)
Author: Marlon Fernando Polegato
Consolidated version based on the original document and updated computational tests.
1. Introduction
The Pattern-Based Factorization Method (P.F.M.) aims to identify primes and composites
with high precision, using decimal redistribution with fixed multipliers. It is a deterministic,
efficient method capable of returning actual divisors without relying on prime lists or
classical factorization.
2. Structural Definition of the Method
Given n ∈ ℕ and fixed multipliers k ∈ {1, 3, 7, 9, 11}, define nk = 10A + d, with A = ⌊nk / 10⌋
and d = nk mod 10. Iteratively, update the values: A ← A - i and d ← d + 10i. If d > 1 and d
divides both A and n, then d is a real divisor.
3. General Formulation of P.F.M.
For each fixed k, define:
• nk = 10A + d
• A = ⌊nk / 10⌋, d = nk % 10
• A_i = A - i, d_i = d + 10i
Compositeness criterion: if there exists i ∈ ℕ such that d_i > 1, d_i | A_i and d_i | n, then n is
composite.
4. Theorem of Correctness
If n is composite and ∃ real d such that d | n, then ∃ k ∈ {1, 3, 7, 9, 11} and i ∈ ℕ such that:
• A = dq
• nk = 10A + d
• A mod d = 0 and n mod d = 0 ⇒ d is detected as a real divisor.
Proof: If A = dq, then nk = 10dq + d = d(10q + 1) ⇒ n = nk / k = d(10q + 1)/k.
If k divides (10q + 1), then n ∈ ℕ and d | n. Since k is fixed and d ≤ √nk, the method finds d
within √nk / 10 iterations.
5. Examples
Example 1: n = 57, k = 3 ⇒ nk = 171 ⇒ A = 17, d = 1
Iterations: (A=16, d=11), ..., (A=9, d=71). No divisor found.
With k = 9 ⇒ nk = 513 ⇒ A = 51, d = 3 ⇒ 51 % 3 == 0 and 57 % 3 == 0 ⇒ 3 is a real divisor.
Example 2: n = 252097800621, k = 3 ⇒ nk = 756293401863 ⇒ A = 75629340186, d = 3
A % 3 == 0 and n % 3 == 0 ⇒ 3 is a real divisor found in the first iteration.
6. Core Properties
- Deterministic method
- Uses only decimal structure
- Embedded stopping criterion: A < d or d > √nk
- Returns real divisor if n is composite
7. Scalability and Parallelism
The structure of the P.F.M. allows parallelism by multiplier k and by d ranges. Using
OpenMP, each multiplier can be processed in separate threads. Distinct blocks of A and d
can also be distributed to improve performance. The method avoids unnecessary divisions
and quickly converges to real divisors when they exist.
8. Computational Results
Composites like 252097800621, 9007199254740991, and large primes such as
1125899906842597 were tested. The average time per number was below 2 seconds in
most cases, and below 10 microseconds for small integers.
Untitled20.ipynb
Untitled20.ipynb_
[12]
1min
Cpp_code = r”””
#include <iostream>
#include <vector>
#include <set>
#include <chrono>
#include <cmath>
Using namespace std;
Using namespace std::chrono;
Vector<unsigned long long> mfp_find_all_divisors(unsigned long long n, const vector<int>&
k_list = {1,3,7,9,11}) {
Set<unsigned long long> divisores;
Unsigned long long sqrt_n = (unsigned long long) sqrtl(n);
For (int k : k_list) {
Uint128_t nk = (uint128_t)n * k;
Unsigned long long d0 = nk % 10;
If (d0 == 0) d0 = 1;
Unsigned long long A0 = nk / 10;
If (d0 > 1 && n % d0 == 0) {
Unsigned long long q = n / d0;
If (q > 1) {
Divisores.insert(d0);
If (q != d0 && q != n) divisores.insert(q);
}
}
Unsigned long long max_i = sqrt_n / 10 + 1;
For (unsigned long long I = 0; I < max_i; i++) {
Unsigned long long d = d0 + 10 * I;
If (d > sqrt_n) break;
If (d <= 1) continue;
If (n % d == 0) {
Unsigned long long q = n / d;
If (q > 1) {
Divisores.insert(d);
If (q != d && q != n) divisores.insert(q);
}
}
}
}
Return vector<unsigned long long>(divisores.begin(), divisores.end());
}
Int main() {
Vector<unsigned long long> test_numbers = {
1125899906842597,
2251799813685119,
9007199254740991,
14757395258967641291ULL, // valores ajustados para caber em unsigned long long
5902958103587056517ULL,
2361183241434822606ULL,
9444732965739290427ULL,
2052041569734646011,
14597843287679628085
};
For (int I = 11; I < 100; I += 2)
Test_numbers.push_back(i);
Double total_time = 0.0;
Auto total_start = high_resolution_clock::now();
For (auto n : test_numbers) {
Auto start = high_resolution_clock::now();
Auto divs = mfp_find_all_divisors(n);
Auto end = high_resolution_clock::now();
Double elapsed = duration<double>(end – start).count();
Total_time += elapsed;
Cout << “Número: “ << n << “\n”;
If (!divs.empty()) {
Cout << “MFP: Composto\n”;
For (auto d : divs)
Cout << “ → divisor = “ << d << “\n”;
} else {
Cout << “MFP: Primo\n”;
}
Cout << “Tempo: “ << elapsed << “ s\n\n”;
}
Auto total_end = high_resolution_clock::now();
Double tempo_total = duration<double>(total_end – total_start).count();
Cout << “Resumo:\n”;
Cout << “Tempo total: “ << tempo_total << “ s\n”;
Cout << “Tempo médio por número: “ << tempo_total / test_numbers.size() << “ s\n”;
Return 0;
}
“””
# Salvar, compilar e executar no Colab
With open(“mfp_all_divisors.cpp”, “w”) as f:
f.write(cpp_code)
!g++ -O3 -std=c++17 mfp_all_divisors.cpp -o mfp_all_divisors
!./mfp_all_divisors
Mfp_all_divisors.cpp:57:9: warning: integer constant is so large that it is unsigned
57 | 14597843287679628085
| ^~~~~~~~
Número: 1125899906842597
MFP: Primo
Tempo: 0.178129 s
Número: 2251799813685119
MFP: Primo
Tempo: 0.255465 s
Número: 9007199254740991
MFP: Composto
→ divisor = 6361
→ divisor = 69431
→ divisor = 20394401
→ divisor = 441650591
→ divisor = 129728784761
→ divisor = 1416003655831
Tempo: 0.502565 s
Número: 14757395258967641291
MFP: Composto
→ divisor = 11
→ divisor = 29
→ divisor = 121
→ divisor = 319
→ divisor = 577
→ divisor = 1331
→ divisor = 2237
→ divisor = 3509
→ divisor = 6347
→ divisor = 16733
→ divisor = 24607
→ divisor = 38599
→ divisor = 64873
→ divisor = 69817
→ divisor = 184063
→ divisor = 270677
→ divisor = 713603
→ divisor = 767987
→ divisor = 1290749
→ divisor = 2024693
→ divisor = 2977447
→ divisor = 7849633
→ divisor = 14198239
→ divisor = 22271623
→ divisor = 37431721
→ divisor = 86345963
→ divisor = 156180629
→ divisor = 296204641
→ divisor = 411748931
→ divisor = 1717986919
→ divisor = 3258251051
→ divisor = 4529238241
→ divisor = 8589934589
→ divisor = 35840761561
→ divisor = 49821620651
→ divisor = 94489280479
→ divisor = 170910077857
→ divisor = 394248377171
→ divisor = 662609781917
→ divisor = 1039382085269
→ divisor = 1880010856427
→ divisor = 4956392257853
→ divisor = 7288707601087
→ divisor = 11433202937959
→ divisor = 19215683675593
→ divisor = 20680119420697
→ divisor = 54520314836383
→ divisor = 80175783611957
→ divisor = 211372520431523
→ divisor = 227481313627667
→ divisor = 382325844166109
→ divisor = 599723463200213
→ divisor = 881933619731527
→ divisor = 2325097724746753
→ divisor = 4205584285827199
→ divisor = 6596958095202343
→ divisor = 11087449480817161
→ divisor = 25576074972214283
→ divisor = 46261427144099189
→ divisor = 121961944288988771
→ divisor = 508875698585091079
→ divisor = 1341581387178876481
Tempo: 21.4755 s
Número: 5902958103587056517
MFP: Composto
→ divisor = 19
→ divisor = 97
→ divisor = 1843
→ divisor = 457661
→ divisor = 8695559
→ divisor = 44393117
→ divisor = 843469223
→ divisor = 6998427379
→ divisor = 132970120201
→ divisor = 678847455763
→ divisor = 12898101659497
→ divisor = 3202907272700519
→ divisor = 60855238181309861
→ divisor = 310682005451950343
Tempo: 13.3858 s
Número: 2361183241434822606
MFP: Composto
→ divisor = 2
→ divisor = 6
→ divisor = 73712498
→ divisor = 221137494
→ divisor = 10677444149
→ divisor = 32032332447
→ divisor = 393530540239137101
→ divisor = 1180591620717411303
Tempo: 8.64673 s
Número: 9444732965739290427
MFP: Composto
→ divisor = 3
→ divisor = 13
→ divisor = 39
→ divisor = 47
→ divisor = 141
→ divisor = 611
→ divisor = 811
→ divisor = 1833
→ divisor = 2433
→ divisor = 10543
→ divisor = 31629
→ divisor = 38117
→ divisor = 112979
→ divisor = 114351
→ divisor = 338937
→ divisor = 495521
→ divisor = 1468727
→ divisor = 1486563
→ divisor = 4406181
→ divisor = 5310013
→ divisor = 15930039
→ divisor = 56235251
→ divisor = 69030169
→ divisor = 91625969
→ divisor = 168705753
→ divisor = 207090507
→ divisor = 274877907
→ divisor = 731058263
→ divisor = 1191137597
→ divisor = 2193174789
→ divisor = 2643056797
→ divisor = 3573412791
→ divisor = 4306420543
→ divisor = 7929170391
→ divisor = 12919261629
→ divisor = 34359738361
→ divisor = 45606788561
→ divisor = 55983467059
→ divisor = 103079215083
→ divisor = 136820365683
→ divisor = 167950401177
→ divisor = 592888251293
→ divisor = 1778664753879
→ divisor = 2143519062367
→ divisor = 6353402422729
→ divisor = 6430557187101
→ divisor = 19060207268187
→ divisor = 27865747810771
→ divisor = 82594231495477
→ divisor = 83597243432313
→ divisor = 247782694486431
→ divisor = 298609913868263
→ divisor = 895829741604789
→ divisor = 3881928880287419
→ divisor = 5152609364833219
→ divisor = 11645786640862257
→ divisor = 15457828094499657
→ divisor = 66983921742831847
→ divisor = 200951765228495541
→ divisor = 242172640147161293
→ divisor = 726517920441483879
→ divisor = 3148244321913096809
Tempo: 16.7393 s
Número: 2052041569734646011
MFP: Composto
→ divisor = 3
→ divisor = 4337
→ divisor = 13011
→ divisor = 157715899603001
→ divisor = 473147698809003
→ divisor = 684013856578215337
Tempo: 8.79443 s
Número: 14597843287679628085
MFP: Composto
→ divisor = 5
→ divisor = 565
→ divisor = 2995
→ divisor = 338435
→ divisor = 43133373580391
→ divisor = 4874071214584183
→ divisor = 25836890774654209
→ divisor = 2919568657535925617
Tempo: 20.8377 s
Número: 11
MFP: Primo
Tempo: 5.98e-07 s
Número: 13
MFP: Primo
Tempo: 6.07e-07 s
Número: 15
MFP: Composto
→ divisor = 3
→ divisor = 5
Tempo: 2.446e-06 s
Número: 17
MFP: Primo
Tempo: 4.16e-07 s
Número: 19
MFP: Primo
Tempo: 3.9e-07 s
Número: 21
MFP: Composto
→ divisor = 3
→ divisor = 7
Tempo: 1.33e-06 s
Número: 23
MFP: Primo
Tempo: 3.4e-07 s
Número: 25
MFP: Composto
→ divisor = 5
Tempo: 8.44e-07 s
Número: 27
MFP: Composto
→ divisor = 3
→ divisor = 9
Tempo: 7.26e-07 s
Número: 29
MFP: Primo
Tempo: 3.39e-07 s
Número: 31
MFP: Primo
Tempo: 4.26e-07 s
Número: 33
MFP: Composto
→ divisor = 3
→ divisor = 11
Tempo: 8.87e-07 s
Número: 35
MFP: Composto
→ divisor = 5
→ divisor = 7
Tempo: 8.6e-07 s
Número: 37
MFP: Primo
Tempo: 2.92e-07 s
Número: 39
MFP: Composto
→ divisor = 3
→ divisor = 13
Tempo: 6.61e-07 s
Número: 41
MFP: Primo
Tempo: 2.92e-07 s
Número: 43
MFP: Primo
Tempo: 5.45e-07 s
Número: 45
MFP: Composto
→ divisor = 5
→ divisor = 9
Tempo: 8.8e-07 s
Número: 47
MFP: Primo
Tempo: 2.5e-07 s
Número: 49
MFP: Composto
→ divisor = 7
Tempo: 8.13e-07 s
Número: 51
MFP: Composto
→ divisor = 3
→ divisor = 17
Tempo: 6.4e-07 s
Número: 53
MFP: Primo
Tempo: 3.24e-07 s
Número: 55
MFP: Composto
→ divisor = 5
→ divisor = 11
Tempo: 9.22e-07 s
Número: 57
MFP: Composto
→ divisor = 3
→ divisor = 19
Tempo: 6.72e-07 s
Número: 59
MFP: Primo
Tempo: 3.41e-07 s
Número: 61
MFP: Primo
Tempo: 3.55e-07 s
Número: 63
MFP: Composto
→ divisor = 3
→ divisor = 7
→ divisor = 9
→ divisor = 21
Tempo: 1.541e-06 s
Número: 65
MFP: Composto
→ divisor = 5
→ divisor = 13
Tempo: 9.07e-07 s
Número: 67
MFP: Primo
Tempo: 5.75e-07 s
Número: 69
MFP: Composto
→ divisor = 3
→ divisor = 23
Tempo: 5.96e-07 s
Número: 71
MFP: Primo
Tempo: 2.91e-07 s
Número: 73
MFP: Primo
Tempo: 3.45e-07 s
Número: 75
MFP: Composto
→ divisor = 5
→ divisor = 15
Tempo: 9.1e-07 s
Número: 77
MFP: Composto
→ divisor = 7
→ divisor = 11
Tempo: 6.53e-07 s
Número: 79
MFP: Primo
Tempo: 3.27e-07 s
Número: 81
MFP: Composto
→ divisor = 3
→ divisor = 9
→ divisor = 27
Tempo: 1.122e-06 s
Número: 83
MFP: Primo
Tempo: 3.25e-07 s
Número: 85
MFP: Composto
→ divisor = 5
→ divisor = 17
Tempo: 9.38e-07 s
Número: 87
MFP: Composto
→ divisor = 3
→ divisor = 29
Tempo: 6.55e-07 s
Número: 89
MFP: Primo
Tempo: 3.49e-07 s
Número: 91
MFP: Composto
→ divisor = 7
→ divisor = 13
Tempo: 6.21e-07 s
Número: 93
MFP: Composto
→ divisor = 3
→ divisor = 31
Tempo: 8.69e-07 s
Número: 95
MFP: Composto
→ divisor = 5
→ divisor = 19
Tempo: 8.88e-07 s
Número: 97
MFP: Primo
Tempo: 3.44e-07 s
Número: 99
MFP: Composto
→ divisor = 3
→ divisor = 9
→ divisor = 11
→ divisor = 33
Tempo: 1.489e-06 s
Resumo:
Tempo total: 90.8169 s
Tempo médio por número: 1.68179 s
Produtos pagos do Colab – Cancelar contratos
Cpp_code = r”””
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <omp.h>
#include <gmp.h>
Using namespace std;
Using namespace std::chrono;
Bool mfp_parallel_bidirectional(const mpz_t n, string& divisor_encontrado, const
vector<int>& k_list = {1,3,7,9,11}) {
Mpz_t sqrt_n;
Mpz_init(sqrt_n);
Mpz_sqrt(sqrt_n, n);
Bool found = false;
#pragma omp parallel
{
Mpz_t nk, d0, A0, d, r, q, tmp, d_down, d_up, d_max;
Mpz_inits(nk, d0, A0, d, r, q, tmp, d_down, d_up, d_max, NULL);
// d_down = 0.7 * sqrt(n)
Mpz_mul_ui(d_down, sqrt_n, 7);
Mpz_div_ui(d_down, d_down, 10);
Mpz_mod_ui(tmp, d_down, 10);
If (mpz_cmp_ui(tmp, 0) != 0) mpz_sub(d_down, d_down, tmp);
// d_up = 0.3 * sqrt(n)
Mpz_mul_ui(d_up, sqrt_n, 3);
Mpz_div_ui(d_up, d_up, 10);
Mpz_mod_ui(tmp, d_up, 10);
If (mpz_cmp_ui(tmp, 0) != 0) mpz_add_ui(d_up, d_up, 10 – mpz_get_ui(tmp));
Mpz_set(d_max, sqrt_n);
#pragma omp for schedule(dynamic)
For (int I = 0; I < k_list.size(); i++) {
If (found) continue;
Int k = k_list[i];
Mpz_mul_ui(nk, n, k);
Mpz_mod_ui(d0, nk, 10);
If (mpz_cmp_ui(d0, 0) == 0) mpz_set_ui(d0, 1);
Mpz_fdiv_q_ui(A0, nk, 10);
// Verifica d0 diretamente
Mpz_mod(r, n, d0);
If (mpz_cmp_ui(d0, 1) > 0 && mpz_cmp_ui(r, 0) == 0) {
#pragma omp critical
{
If (!found) {
Divisor_encontrado = mpz_get_str(NULL, 10, d0);
Found = true;
}
}
}
// Busca descendente a partir de 0.7 * sqrt(n)
For (mpz_set(d, d_down); mpz_cmp(d, d0) >= 0 && !found; mpz_sub_ui(d, d, 10)) {
Mpz_mod(r, n, d);
If (mpz_cmp_ui(r, 0) == 0) {
#pragma omp critical
{
If (!found) {
Divisor_encontrado = mpz_get_str(NULL, 10, d);
Found = true;
}
}
Break;
}
}
// Busca ascendente a partir de 0.3 * sqrt(n)
For (mpz_set(d, d_up); mpz_cmp(d, d_max) <= 0 && !found; mpz_add_ui(d, d, 10)) {
Mpz_mod(r, n, d);
If (mpz_cmp_ui(r, 0) == 0) {
#pragma omp critical
{
If (!found) {
Divisor_encontrado = mpz_get_str(NULL, 10, d);
Found = true;
}
}
Break;
}
}
}
Mpz_clears(nk, d0, A0, d, r, q, tmp, d_down, d_up, d_max, NULL);
}
Mpz_clear(sqrt_n);
Return found;
}
Int main() {
Vector<const char*> test_numbers = {
“1522605027922533360535618378132637429718068114961380688657908494580122
963258952897654000350692006139”, // RSA-100
“3579423417972586877499180783256845540300377806578858017546077758107437
777741033357634248309227320117” // RSA-110
};
Double total_time = 0.0;
Auto total_start = high_resolution_clock::now();
For (auto& num_str : test_numbers) {
Mpz_t n;
Mpz_init_set_str(n, num_str, 10);
Auto start = high_resolution_clock::now();
String found_divisor;
Bool composto = mfp_parallel_bidirectional(n, found_divisor);
Auto end = high_resolution_clock::now();
Double elapsed = duration<double>(end – start).count();
Total_time += elapsed;
Cout << “Número: “ << num_str << “\n”;
If (composto) {
Cout << “MFP: Composto\n”;
Cout << “ → divisor encontrado = “ << found_divisor << “\n”;
} else {
Cout << “MFP: Primo\n”;
}
Cout << “Tempo: “ << elapsed << “ s\n\n”;
Mpz_clear(n);
}
Auto total_end = high_resolution_clock::now();
Double tempo_total = duration<double>(total_end – total_start).count();
Cout << “Resumo:\n”;
Cout << “Tempo total: “ << tempo_total << “ s\n”;
Cout << “Tempo médio por número: “ << tempo_total / test_numbers.size() << “ s\n”;
Return 0;
}
“””
# Compilar e executar com OpenMP
With open(“mfp_rsa_bidirectional.cpp”, “w”) as f:
f.write(cpp_code)
!apt-get update -qq
!apt-get install -y libgmp-dev -qq
!g++ -O3 -fopenmp -std=c++17 mfp_rsa_bidirectional.cpp -lgmp -o mfp_rsa_bidirectional
!./mfp_rsa_bidirectional
9. Conclusion
The P.F.M. provides a deterministic, efficient, and self-contained method for primality
detection. Moreover, it is capable of returning real divisors without requiring prime lists or
external projections.
10. 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). *Decimal Redistribution and Primality Detection*.
5. Polegato, M.F. (2024). *Modulo 12 Method*. Núcleo do Conhecimento.
6. Polegato, M.F. (2022). *Fermat’s Library* – https://fermatslibrary.com/p/2e0648ef
7. Polegato, M.F. (2024). *Fermat’s Library* – https://fermatslibrary.com/p/f6e5695f