Repository navigation
Expand file tree
/
Copy pathcomplex_space_factorization.cpp
More file actions
2749 lines (2521 loc) · 122 KB
/
Copy pathcomplex_space_factorization.cpp
File metadata and controls
2749 lines (2521 loc) · 122 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// =====================================================================
// complex_space_factorization.cpp
//
// A unified factorization engine for the complex-space program:
//
// * "Complex Space Factorization" (Viole) -- strip geometry,
// combined trial-division / vertical-Fermat / horizontal-Fermat
// traversal (Sec. 4), the iterated-average GCD method (Sec. 5) and
// its remainder sieve (Sec. 5.2).
// * "The Complete Fermat Sieve by Terminal Digit -- a corrected and
// verified reference" -- the corrected
// terminal-digit sieve, both parity lanes, including the
// N = 5 (mod 10) case that the 8-class table excludes.
// * "Fermat Sieve Using Complex Numbers" -- the original
// per-lane (R,i) terminal-digit tables.
// * Complex space.md -- the squared
// complex space identity sqrt(N^2 + (2ab)^2) = a^2 + b^2,
// used here as an exact integer certificate.
//
// ---------------------------------------------------------------
// THE CENTRAL OBSERVATION THIS FILE IS BUILT ON
// ---------------------------------------------------------------
//
// Write N = a^2 - b^2 = (a-b)(a+b), so a = (p+q)/2 and b = (q-p)/2.
// The terminal-digit sieve asks which (a mod 10, b mod 10) classes can
// occur for a given N mod 10. That is exactly the statement
//
// a^2 - N must be a square modulo 10,
//
// together with the lane condition, which is "a^2 - N is a square
// modulo 4". In other words the corrected terminal-digit sieve is
// precisely the quadratic-residue sieve at the single modulus 20.
//
// Once seen that way it generalises: for ANY modulus m,
//
// a admissible <=> (a^2 - N) mod m is a square mod m.
//
// Measured survival fractions (see --selftest):
//
// modulus 10 alone -> 2.5x reduction
// wheel 2^6*3^3*5^2*7*11*13*17
// -> ~4,000x reduction
//
// So the digit sieve, generalised to a CRT wheel, is worth three to
// four orders of magnitude rather than a factor of 2.5. Everything
// below is organised around that wheel.
//
// ---------------------------------------------------------------
// ALGORITHM
// ---------------------------------------------------------------
//
// Stage 0 Reduction: powers of 2, perfect powers, wheel-30 trial
// division to B1, strong probable-prime test.
//
// Stage 1 A race of deterministic streams over all worker threads,
// stopping at the first split. This is the paper's Sec. 4
// "combined method", made concrete:
//
// TD trial division climbing from B1 (top of strip)
// VF wheel-sieved vertical Fermat from (bottom of strip)
// ceil(sqrt(N)) upward
// HF wheel-sieved horizontal Fermat (middle of strip,
// from b = 1 upward optional, see below)
// IA iterated-average GCD accelerator (Sec. 5 / 5.2)
// with the every-5th-integer sieve (optional)
// LM Lehman multiplier sweep: the same (completeness)
// wheel-sieved scan applied to 4kN
//
// Stage 2 Recurse on both cofactors until everything is prime.
//
// Worst-case cost is O(N^(1/3)) arithmetic operations: TD covers every
// prime below N^(1/3) and LM covers every remaining case, which is
// Lehman's theorem. Racing TD against VF alone would only give
// O(N^(3/8)). The wheel reduces the constant on VF/LM by ~4,000x.
//
// Fidelity note: HF and IA are implemented faithfully to the paper and
// are available via flags, but they are OFF by default because VF
// strictly dominates them. With p,q = sqrt(N)(1 -+ e), the vertical
// scan length is j ~ b^2 / (2 sqrt(N)), i.e. quadratically shorter than
// the horizontal scan length b. See the benchmark table in
// Prime Factorization/Unified Complex Space Factorization.md.
//
// ---------------------------------------------------------------
// BUILD
// ---------------------------------------------------------------
// g++ -std=c++17 -O3 complex_space_factorization.cpp -lgmpxx -lgmp -pthread -o csf
//
// MSYS2 / MinGW-w64 is a supported target. uint64_t there is
// unsigned long long and unsigned long is only 32 bits, so every 64-bit
// value that meets an mpz goes through big_from_u64 / u64_from_big /
// divisible_by_u64 rather than gmpxx's unsigned long overloads.
//
// RUN THIS BEFORE COMMITTING any code that puts a uint64_t near a BigInt.
// It needs no Windows box:
//
// sed 's/std::uint64_t/unsigned long long/g' complex_space_factorization.cpp > probe.cpp
// g++ -std=c++17 -fsyntax-only probe.cpp # must report 0 errors
//
// On LP64 unsigned long long is a distinct type from unsigned long, so
// that substitution reproduces the MinGW overload set exactly. It is not
// advisory: ctm_stream shipped with seven ambiguous-overload sites --
// BigInt(CH * STEP), BigInt(chunk_index) and three `R += STEP` in the mpz
// walk -- which built clean on Linux, broke every MinGW build, and which
// this probe reproduces exactly, at the same seven lines. The trap is
// that LP64 hides the whole class of bug, so a clean local build proves
// nothing here.
//
// RUN
// ./csf <N> [options]
// ./csf --selftest
//
// Options:
// --threads=T worker threads (0 = hardware concurrency)
// --b1=B stage-0 trial division bound (default 1000000)
// --no-lehman disable the Lehman multiplier stream
// --hf enable the horizontal (b-driven) Fermat stream
// --ia enable the iterated-average GCD stream (Sec. 5/5.2)
// --digit-only restrict the sieve to modulus 20, i.e. the corrected
// terminal-digit sieve alone (for comparison)
// --no-sieve disable sieving entirely (for comparison)
// --quiet print only the factorization
// --verbose print stream statistics
// =====================================================================
#include <gmpxx.h>
#include <algorithm>
#include <atomic>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits>
#include <mutex>
#include <numeric>
#include <optional>
#include <random>
#include <sstream>
#include <stdexcept>
#include <string>
#include <thread>
#include <vector>
using BigInt = mpz_class;
// ---------------------------------------------------------------------
// Basic helpers
// ---------------------------------------------------------------------
static inline BigInt isqrt_floor(const BigInt& n) {
BigInt r;
mpz_sqrt(r.get_mpz_t(), n.get_mpz_t());
return r;
}
static inline BigInt isqrt_ceil(const BigInt& n) {
BigInt r = isqrt_floor(n);
if (r * r < n) ++r;
return r;
}
static inline bool is_perfect_square(const BigInt& x, BigInt* root = nullptr) {
if (x < 0) return false;
if (mpz_perfect_square_p(x.get_mpz_t()) == 0) return false;
if (root) *root = isqrt_floor(x);
return true;
}
static inline bool is_probable_prime(const BigInt& n) {
return mpz_probab_prime_p(n.get_mpz_t(), 30) != 0;
}
static inline std::uint64_t umod(const BigInt& n, std::uint64_t m) {
// Every modulus used here is < 2^32 (build_wheel caps W), so the cast to
// unsigned long is exact on LLP64 as well as LP64.
return static_cast<std::uint64_t>(
mpz_fdiv_ui(n.get_mpz_t(), static_cast<unsigned long>(m)));
}
// ---------------------------------------------------------------------
// Portable 64-bit <-> mpz helpers.
//
// On LP64 (Linux, macOS) uint64_t IS unsigned long, so gmpxx's unsigned
// long overloads cover everything and plain BigInt(x) compiles. On LLP64
// (MinGW-w64, MSVC) unsigned long is 32 bits and uint64_t is unsigned long
// long, which gmpxx has no constructor for: BigInt(x) is then ambiguous,
// and mpz_*_ui / mpz_get_ui silently truncate to 32 bits.
//
// These three helpers are used everywhere a 64-bit value meets an mpz, so
// the same source is correct on both models.
// ---------------------------------------------------------------------
static inline BigInt big_from_u64(std::uint64_t v) {
BigInt r;
mpz_import(r.get_mpz_t(), 1, -1, sizeof(v), 0, 0, &v);
return r;
}
// Saturating export: returns `cap` when z does not fit in 64 bits.
static inline std::uint64_t u64_from_big(const BigInt& z, std::uint64_t cap) {
if (mpz_sgn(z.get_mpz_t()) <= 0) return 0;
if (mpz_sizeinbase(z.get_mpz_t(), 2) > 64) return cap;
std::uint64_t v = 0;
std::size_t words = 0;
mpz_export(&v, &words, -1, sizeof(v), 0, 0, z.get_mpz_t());
return words ? v : 0;
}
// Exact export of a value known to fit 128 bits.
static inline __uint128_t u128_from_big(const BigInt& z) {
__uint128_t v = 0;
std::size_t words = 0;
mpz_export(&v, &words, -1, sizeof(v), 0, 0, z.get_mpz_t());
return v;
}
// Least non-negative representative of x mod m, for small positive m.
static inline BigInt mod_pos_small(const BigInt& x, long m) {
BigInt r = x % m;
if (mpz_sgn(r.get_mpz_t()) < 0) r += m;
return r;
}
static inline bool divisible_by_u64(const BigInt& n, std::uint64_t d) {
if (d <= static_cast<std::uint64_t>(std::numeric_limits<unsigned long>::max()))
return mpz_divisible_ui_p(n.get_mpz_t(), static_cast<unsigned long>(d)) != 0;
return mpz_divisible_p(n.get_mpz_t(), big_from_u64(d).get_mpz_t()) != 0;
}
// Set of squares modulo m. For a perfect square x, x mod m must lie in
// this set; that is the whole content of the sieve.
static std::vector<std::uint8_t> squares_mod(std::uint64_t m) {
std::vector<std::uint8_t> s(m, 0);
for (std::uint64_t r = 0; r < m; ++r) s[(r * r) % m] = 1;
return s;
}
// ---------------------------------------------------------------------
// Corrected complete Fermat terminal-digit sieve
//
// N = R^2 - i^2, p = R - i, q = R + i.
// Lane A: N = 1 (mod 4) <=> R odd, i even
// Lane B: N = 3 (mod 4) <=> R even, i odd
//
// Indexed by N mod 10 alone the admissible (R,i) mod 10 classes number 8
// for N ending in 1,3,7,9 (four from each lane) and 18 for N ending in 5.
// Because we always know N mod 4 we use the lane directly: 4 classes for
// N coprime to 10, 9 classes for 5 | N.
//
// The 5 | N branch is the one the published 8-class table excludes. It
// is included here so the routine is total: any caller that has not
// already stripped the factor 5 still gets a sound (not empty) sieve.
// ---------------------------------------------------------------------
struct DigitPair { int a10; int b10; };
static std::vector<DigitPair> fermat_digit_pairs(const BigInt& N) {
const int n10 = static_cast<int>(umod(N, 10));
const int n4 = static_cast<int>(umod(N, 4));
bool a_even;
if (n4 == 3) a_even = true; // Lane B
else if (n4 == 1) a_even = false; // Lane A
else throw std::runtime_error("fermat_digit_pairs: N must be odd");
const bool b_even = !a_even;
const bool five_divides_N = (n10 == 5);
std::vector<DigitPair> pairs;
for (int da = 0; da <= 9; ++da) {
if (((da % 2) == 0) != a_even) continue;
for (int db = 0; db <= 9; ++db) {
if (((db % 2) == 0) != b_even) continue;
const int p10 = ((da - db) % 10 + 10) % 10;
const int q10 = (da + db) % 10;
// p and q are odd. When 5 does not divide N neither p nor q
// may end in 5 or 0, so both must end in 1, 3, 7 or 9. When
// 5 does divide N exactly one of them carries the 5, so that
// restriction must be lifted -- this is the correction.
auto odd_digit = [](int d) { return d % 2 == 1; };
auto coprime10 = [](int d) { return d == 1 || d == 3 || d == 7 || d == 9; };
if (!odd_digit(p10) || !odd_digit(q10)) continue;
if (!five_divides_N && (!coprime10(p10) || !coprime10(q10))) continue;
if ((p10 * q10) % 10 == n10) pairs.push_back({da, db});
}
}
return pairs;
}
// ---------------------------------------------------------------------
// Generalised quadratic-residue wheel
//
// The terminal-digit sieve is the m = 20 case of:
//
// a is admissible <=> (a^2 - M) mod m is a square mod m
//
// We build a CRT wheel from several coprime prime powers and materialise
// the sorted list of admissible residues modulo W = prod(m_i). The list
// is built by CRT composition, so construction costs O(output), not O(W).
//
// A second tier of small prime moduli is applied per-candidate; those are
// cheaper to test than to fold into W.
// ---------------------------------------------------------------------
struct Wheel {
std::uint64_t W = 1;
std::vector<std::uint32_t> residues; // admissible a mod W, sorted
std::vector<std::uint32_t> sec_mod; // second-tier moduli
std::vector<std::vector<std::uint8_t>> sec_ok;
// Division-free walk of the residue list.
//
// The secondary test is ok[s][(base_mod[s] + residues[i]) % p_s]. Doing
// that modulo per residue per modulus was the whole cost of the scan:
// an integer division is ~20-40 cycles against ~2 for an add, and it is
// far worse on a GPU, where integer division is emulated.
//
// residues[] is fixed for a given N, so the per-step increment
// step[s][i] = (residues[i] - residues[i-1]) mod p_s
// can be precomputed once and amortised over every block. Walking then
// costs one add and one conditional subtract: since step < p and
// cur < p, the sum is below 2p and a single subtract renormalises.
//
// A chunk starting at an arbitrary index pays one division to seed
// cur[s], then none for the rest of the chunk. This is also exactly the
// shape a GPU kernel wants: a coalesced byte read and an add.
// sec_res[i * sec_mod.size() + s] = residues[i] mod sec_mod[s].
//
// Absolute, not incremental. Since base_mod[s] < p and sec_res < p, the
// live residue is (base_mod[s] + sec_res) with one conditional subtract
// -- no division anywhere in the scan, and no loop-carried dependency,
// so residues are independent and the loop vectorises.
//
// Interleaved so one 64-byte line carries every modulus for several
// consecutive residues. Independence + coalesced reads + the branchless
// fold below are exactly the three properties a GPU kernel needs; the
// CUDA port in complex_space_factorization_cuda.cu reuses this table
// verbatim.
std::vector<std::uint8_t> sec_res;
double density = 1.0;
bool empty() const { return residues.empty(); }
};
// Admissible residues of a modulo m for a^2 - M = square.
static std::vector<std::uint32_t> admissible_mod(const BigInt& M, std::uint64_t m) {
const std::vector<std::uint8_t> sq = squares_mod(m);
const std::uint64_t Mm = umod(M, m);
std::vector<std::uint32_t> out;
for (std::uint64_t r = 0; r < m; ++r) {
const std::uint64_t v = ((r * r) % m + m - Mm) % m;
if (sq[v]) out.push_back(static_cast<std::uint32_t>(r));
}
return out;
}
// Extended gcd based CRT for two coprime moduli.
static std::uint64_t crt_pair(std::uint64_t r1, std::uint64_t m1,
std::uint64_t r2, std::uint64_t m2) {
// Return the unique x in [0, m1*m2) with x = r1 (mod m1), x = r2 (mod m2).
// Requires gcd(m1, m2) = 1.
const long long m = static_cast<long long>(m2);
// m1^{-1} (mod m2) by extended Euclid.
long long old_r = static_cast<long long>(m1 % m2), r = m;
long long old_s = 1, sc = 0;
while (r != 0) {
const long long q = old_r / r;
long long tmp = old_r - q * r; old_r = r; r = tmp;
tmp = old_s - q * sc; old_s = sc; sc = tmp;
}
const long long inv = ((old_s % m) + m) % m;
const long long diff = static_cast<long long>((r2 + m2 - r1 % m2) % m2);
long long t = static_cast<long long>((static_cast<__int128>(diff) * inv) % m);
if (t < 0) t += m;
return r1 + m1 * static_cast<std::uint64_t>(t);
}
static Wheel build_wheel(const BigInt& M,
std::uint64_t residue_budget,
bool digit_only,
bool disabled) {
Wheel w;
if (disabled) {
w.W = 1;
w.residues = {0};
w.density = 1.0;
return w;
}
// Primary moduli, most selective first. 2^k and 5^k subsume the
// corrected terminal-digit sieve (modulus 20 = 4 * 5).
std::vector<std::uint64_t> primary;
if (digit_only) {
primary = {4, 5}; // exactly the digit sieve
} else {
primary = {64, 27, 25, 7, 11, 13, 17};
}
std::vector<std::uint32_t> cur = {0};
std::uint64_t curW = 1;
for (std::uint64_t m : primary) {
std::vector<std::uint32_t> am = admissible_mod(M, m);
if (am.empty()) { w.W = curW; w.residues.clear(); return w; }
// Stop growing if the composed list would exceed the budget or
// overflow 32-bit residues.
// Two independent caps. residue_budget bounds the materialised list;
// 0xFFFFFFFF bounds W itself, because residues are stored as uint32.
// The modulus cap binds first with the default moduli, so raising
// --wheel past ~2^18 has no effect -- W is already maximal.
const __uint128_t newW = static_cast<__uint128_t>(curW) * m;
const __uint128_t newN = static_cast<__uint128_t>(cur.size()) * am.size();
if (newW > 0xFFFFFFFFull || newN > residue_budget) break;
std::vector<std::uint32_t> next;
next.reserve(static_cast<std::size_t>(newN));
for (std::uint32_t r1 : cur)
for (std::uint32_t r2 : am)
next.push_back(static_cast<std::uint32_t>(crt_pair(r1, curW, r2, m)));
cur.swap(next);
curW = static_cast<std::uint64_t>(newW);
}
std::sort(cur.begin(), cur.end());
w.W = curW;
w.residues = std::move(cur);
w.density = static_cast<double>(w.residues.size()) / static_cast<double>(w.W);
if (!digit_only) {
// Second tier: applied per surviving candidate.
for (std::uint32_t p : {19u, 23u, 29u, 31u, 37u, 41u, 43u, 47u}) {
if (w.W % p == 0) continue;
std::vector<std::uint8_t> ok(p, 0);
const std::vector<std::uint8_t> sq = squares_mod(p);
const std::uint64_t Mp = umod(M, p);
std::size_t cnt = 0;
for (std::uint32_t r = 0; r < p; ++r) {
const std::uint64_t v = ((1ull * r * r) % p + p - Mp) % p;
if (sq[v]) { ok[r] = 1; ++cnt; }
}
w.sec_mod.push_back(p);
w.sec_ok.push_back(std::move(ok));
w.density *= static_cast<double>(cnt) / static_cast<double>(p);
}
// Precompute the per-residue increments (see Wheel::sec_step).
const std::size_t R = w.residues.size();
const std::size_t NS = w.sec_mod.size();
w.sec_res.assign(R * NS, 0);
for (std::size_t s2 = 0; s2 < NS; ++s2) {
const std::uint32_t p = w.sec_mod[s2];
for (std::size_t i = 0; i < R; ++i)
w.sec_res[i * NS + s2] = static_cast<std::uint8_t>(w.residues[i] % p);
}
}
return w;
}
// ---------------------------------------------------------------------
// Squared complex space certificate (Complex space.md, footnote 1)
//
// A complex factor (a + bi) squares to n + 2abi, and the right triangle
// it represents gives the exact integer identity
//
// sqrt(N^2 + (2ab)^2) = a^2 + b^2.
//
// We use it as an independent check on every split the engine reports:
// it must hold exactly, in integers, or the split is rejected.
// ---------------------------------------------------------------------
static bool certify_complex_square(const BigInt& N, const BigInt& a, const BigInt& b) {
if (a <= b || b < 0) return false;
if ((a - b) * (a + b) != N) return false;
const BigInt two_ab = 2 * a * b;
const BigInt hyp2 = N * N + two_ab * two_ab;
BigInt hyp;
if (!is_perfect_square(hyp2, &hyp)) return false;
return hyp == a * a + b * b;
}
// ---------------------------------------------------------------------
// Shared result slot
// ---------------------------------------------------------------------
struct Found {
std::atomic<bool> done{false};
std::mutex mu;
BigInt factor;
std::string source;
BigInt cert_a, cert_b;
bool certified = false;
bool ready() const { return done.load(std::memory_order_relaxed); }
void submit(const BigInt& N, const BigInt& f, const char* src,
const BigInt* a = nullptr, const BigInt* b = nullptr) {
if (f <= 1 || f >= N) return;
if (N % f != 0) return;
std::lock_guard<std::mutex> lk(mu);
if (done.load()) return;
factor = f;
source = src;
if (a && b) {
cert_a = *a; cert_b = *b;
certified = certify_complex_square(N, *a, *b);
}
done.store(true, std::memory_order_release);
}
};
struct Stats {
std::atomic<std::uint64_t> vf_candidates{0}; // survived the wheel
std::atomic<std::uint64_t> vf_scanned{0}; // residues visited
std::atomic<std::uint64_t> td_tested{0};
std::atomic<std::uint64_t> hf_candidates{0};
std::atomic<std::uint64_t> ia_gcds{0};
std::atomic<std::uint64_t> yp_steps{0};
std::atomic<std::uint64_t> ctm_steps{0};
std::atomic<std::uint64_t> lm_candidates{0};
};
// ---------------------------------------------------------------------
// Generic wheel-sieved Fermat scan
//
// Finds x in [x_lo, x_hi] with x^2 - M a perfect square, then offers
// gcd(|x-y|, N) and gcd(x+y, N) as splits of N.
//
// vertical Fermat M = N, x = a, y = b
// horizontal Fermat M = -N, x = b, y = a
// Lehman multiplier M = 4kN, x = a, y = b
//
// All three are the same scan; only M and the interval differ. This is
// the paper's Sec. 4 "run every method simultaneously" made literal --
// the methods are one routine pointed at different parts of the strip.
// ---------------------------------------------------------------------
// Chunked, work-stealing variant for the unbounded vertical/horizontal
// streams: residue indices are handed out by an atomic counter so that
// low x (short scans, the balanced-semiprime case) is always covered
// first regardless of thread count.
static void fermat_scan_chunked(const BigInt& N,
const BigInt& M,
const Wheel& w,
const BigInt& x_lo,
const BigInt& x_hi,
Found& found,
std::atomic<std::uint64_t>& next_chunk,
std::atomic<std::uint64_t>& cand_counter,
std::atomic<std::uint64_t>& scan_counter,
const char* src) {
if (w.empty() || x_hi < x_lo) return;
const std::uint64_t W = w.W;
const std::uint64_t R = w.residues.size();
const std::uint64_t CHUNK = std::min<std::uint64_t>(R, 4096);
const std::uint64_t chunks_per_block = (R + CHUNK - 1) / CHUNK;
const BigInt base0 = x_lo - big_from_u64(umod(x_lo, W));
BigInt x, t, y, g, base;
std::vector<std::uint64_t> base_mod(w.sec_mod.size());
std::uint64_t cur_blk = std::numeric_limits<std::uint64_t>::max();
std::uint64_t local_cand = 0, local_scan = 0;
bool exhausted = false;
while (!found.ready() && !exhausted) {
const std::uint64_t c = next_chunk.fetch_add(1, std::memory_order_relaxed);
const std::uint64_t blk = c / chunks_per_block;
const std::uint64_t k = c % chunks_per_block;
if (blk != cur_blk) {
cur_blk = blk;
base = base0 + big_from_u64(blk) * big_from_u64(W);
if (base > x_hi) break;
for (std::size_t i = 0; i < w.sec_mod.size(); ++i)
base_mod[i] = umod(base, w.sec_mod[i]);
}
const std::uint64_t i0 = k * CHUNK;
const std::uint64_t i1 = std::min(R, i0 + CHUNK);
// Bounds as base-relative OFFSETS, so the hot loop never touches an
// mpz. base is the largest multiple of W at or below x_lo, so
// x_lo - base < W < 2^32; and when x_hi - base exceeds W no residue
// in this block can reach it.
std::uint64_t lo_off = 0, hi_off = std::numeric_limits<std::uint64_t>::max();
if (base < x_lo) lo_off = u64_from_big(x_lo - base, W);
{
const BigInt span = x_hi - base;
if (mpz_sgn(span.get_mpz_t()) < 0) { exhausted = true; break; }
hi_off = u64_from_big(span, std::numeric_limits<std::uint64_t>::max());
}
// Seed the division-free walk: one modulo per modulus per chunk,
// then add-and-conditionally-subtract for every residue after that.
const std::size_t NS = w.sec_mod.size();
std::uint32_t smod[16], bmod[16];
const std::uint8_t* okp[16];
for (std::size_t s = 0; s < NS; ++s) {
smod[s] = w.sec_mod[s];
okp[s] = w.sec_ok[s].data();
bmod[s] = static_cast<std::uint32_t>(base_mod[s] % smod[s]);
}
for (std::uint64_t i = i0; i < i1; ++i) {
const std::uint32_t r = w.residues[i];
if (r < lo_off) continue;
if (r > hi_off) { exhausted = true; break; }
++local_scan;
// Branchless fold. The early-exit form tested ~2 moduli per
// residue, but each test is a coin-flip branch and a mispredict
// costs more than the check itself. Folding all NS lookups with
// & leaves one well-predicted branch (survivors are ~1 in 300).
// On a GPU the same rewrite removes warp divergence.
const std::uint8_t* rm = &w.sec_res[i * NS];
unsigned okm = 1u;
for (std::size_t s = 0; s < NS; ++s) {
std::uint32_t c = bmod[s] + rm[s];
const std::uint32_t p = smod[s];
c -= (c >= p ? p : 0);
okm &= okp[s][c];
}
if (!okm) continue;
// Survivor: only now is an mpz built. This is the host/device
// split -- everything above is machine words and maps directly
// onto a GPU kernel that emits surviving offsets.
++local_cand;
x = base + r;
t = x * x - M;
if (t < 0) continue;
if (!is_perfect_square(t, &y)) continue;
BigInt d = x > y ? x - y : y - x;
mpz_gcd(g.get_mpz_t(), d.get_mpz_t(), N.get_mpz_t());
if (g > 1 && g < N) {
if (M == N) found.submit(N, g, src, &x, &y);
else if (M == -N) found.submit(N, g, src, &y, &x);
else found.submit(N, g, src);
break;
}
BigInt s2 = x + y;
mpz_gcd(g.get_mpz_t(), s2.get_mpz_t(), N.get_mpz_t());
if (g > 1 && g < N) { found.submit(N, g, src); break; }
}
if ((local_scan & 0xFFFF) == 0 && found.ready()) break;
}
scan_counter += local_scan;
cand_counter += local_cand;
}
// ---------------------------------------------------------------------
// Trial division stream -- the top of the factor strip.
// Wheel-30 residues, climbing from `start` to `limit`.
// ---------------------------------------------------------------------
// Trial division over p in [start, limit], chunked by an atomic counter so a
// thread that exhausts its own arc of the strip can migrate here rather than
// idle. Wheel-30 residues.
static void trial_division_stream(const BigInt& N,
std::uint64_t start,
std::uint64_t limit,
Found& found,
std::atomic<std::uint64_t>& next_block,
std::atomic<std::uint64_t>& counter) {
static const std::uint64_t W30[8] = {1, 7, 11, 13, 17, 19, 23, 29};
const std::uint64_t TURNS = 1u << 14;
const std::uint64_t base0 = (start / 30) * 30;
std::uint64_t tested = 0;
while (!found.ready()) {
const std::uint64_t blk = next_block.fetch_add(1, std::memory_order_relaxed);
if (blk > limit / (TURNS * 30) + 1) break;
const std::uint64_t lo = base0 + blk * TURNS * 30;
if (lo > limit) break;
const std::uint64_t hi = std::min(limit, lo + TURNS * 30 - 1);
for (std::uint64_t base = lo; base <= hi; base += 30) {
for (std::uint64_t off : W30) {
const std::uint64_t d = base + off;
if (d < start || d < 7) continue;
if (d > limit) { counter += tested; return; }
++tested;
if (divisible_by_u64(N, d)) {
found.submit(N, big_from_u64(d), "trial-division");
counter += tested;
return;
}
}
if ((tested & 0xFFFFF) == 0 && found.ready()) { counter += tested; return; }
}
}
counter += tested;
}
// ---------------------------------------------------------------------
// Lehman multiplier stream -- the completeness guarantee.
//
// If N has no prime factor below N^(1/3), then for some k in
// [1, N^(1/3)] there are a, b with a^2 - b^2 = 4kN and
//
// ceil(sqrt(4kN)) <= a <= ceil(sqrt(4kN)) + N^(1/6) / (4 sqrt(k)).
//
// Each k is just another wheel-sieved Fermat scan, this time on 4kN.
// Geometrically: multiplying by k re-scales the complex space so that a
// different part of the factor strip is brought down to the near-vertical
// region where Fermat's method is efficient.
// ---------------------------------------------------------------------
// A small-window sieved scan. The Lehman windows are short
// (N^(1/6) / (4 sqrt k)), so a residue-list wheel would cost far more to
// build and to skip past than the window itself. Here the same
// quadratic-residue condition is applied incrementally, one modulus at a
// time, directly over the window.
struct SmallSieve {
static constexpr std::uint32_t MODS[9] = {64, 27, 25, 7, 11, 13, 17, 19, 23};
std::vector<std::uint8_t> ok[9];
std::uint64_t start_mod[9];
// k-independent, so built once per thread rather than once per k.
std::vector<std::uint8_t> sq[9];
std::vector<std::uint32_t> sqr[9]; // r^2 mod m, also k-independent
SmallSieve() {
for (int i = 0; i < 9; ++i) {
const std::uint32_t m = MODS[i];
sq[i] = squares_mod(m);
sqr[i].resize(m);
for (std::uint32_t r = 0; r < m; ++r) sqr[i][r] = (r * r) % m;
ok[i].assign(m, 0);
}
}
// Per k: only the M-dependent shift changes. This used to rebuild
// squares_mod for all nine moduli on every k -- allocating nine vectors
// and redoing O(m^2) work per multiplier, with k running to N^(1/3).
void rebuild(const BigInt& M, const BigInt& lo) {
for (int i = 0; i < 9; ++i) {
const std::uint32_t m = MODS[i];
const std::uint32_t Mm = static_cast<std::uint32_t>(umod(M, m));
for (std::uint32_t r = 0; r < m; ++r)
ok[i][r] = sq[i][(sqr[i][r] + m - Mm) % m];
start_mod[i] = umod(lo, m);
}
}
};
constexpr std::uint32_t SmallSieve::MODS[9];
static void lehman_stream(const BigInt& N,
std::uint64_t k_max,
Found& found,
std::atomic<std::uint64_t>& next_k,
std::atomic<std::uint64_t>& counter) {
// Integer 6th root, rounded up: the Lehman window width scale.
BigInt n16;
mpz_root(n16.get_mpz_t(), N.get_mpz_t(), 6);
++n16;
SmallSieve ss;
BigInt x, t, y, g, d;
std::uint64_t local = 0;
while (!found.ready()) {
const std::uint64_t k = next_k.fetch_add(1, std::memory_order_relaxed);
if (k < 1 || k > k_max) break;
const BigInt M = 4 * big_from_u64(k) * N;
const BigInt lo = isqrt_ceil(M);
// span = n16 / (4 sqrt k), rounded up. Using floor(sqrt(k)) makes
// the divisor no larger than the true one, so the window is a
// superset of Lehman's -- never a miss.
std::uint64_t sk = static_cast<std::uint64_t>(std::sqrt(static_cast<double>(k)));
if (sk < 1) sk = 1;
BigInt span = n16 / (4 * big_from_u64(sk)) + 2;
const std::uint64_t span_u = u64_from_big(span, std::numeric_limits<std::uint64_t>::max());
ss.rebuild(M, lo);
std::uint64_t cur[9];
for (int i = 0; i < 9; ++i) cur[i] = ss.start_mod[i];
for (std::uint64_t off = 0; off <= span_u; ++off) {
bool pass = true;
for (int i = 0; i < 9; ++i) {
if (!ss.ok[i][cur[i]]) { pass = false; break; }
}
if (pass) {
++local;
x = lo + big_from_u64(off);
t = x * x - M;
if (t >= 0 && is_perfect_square(t, &y)) {
d = x > y ? x - y : y - x;
mpz_gcd(g.get_mpz_t(), d.get_mpz_t(), N.get_mpz_t());
if (g > 1 && g < N) { found.submit(N, g, "lehman"); counter += local; return; }
d = x + y;
mpz_gcd(g.get_mpz_t(), d.get_mpz_t(), N.get_mpz_t());
if (g > 1 && g < N) { found.submit(N, g, "lehman"); counter += local; return; }
}
}
for (int i = 0; i < 9; ++i) {
if (++cur[i] == SmallSieve::MODS[i]) cur[i] = 0;
}
if ((off & 0xFFFF) == 0 && found.ready()) break;
}
}
counter += local;
}
// ---------------------------------------------------------------------
// Yellow-path stream (Complex Space Factorization, Sec. 4, Figure 8)
//
// The "key complex number" is (r + (r-3)i) with r = ceil(sqrt(N)), and the
// traversal runs down the 135-degree line through it. Writing m = r - 3
// and S = r + m, the path is
//
// R_j = r + j i_j = m - j P_j = R - i = 2j + 3 R + i = S
//
// so one index j drives all three of the paper's methods at once:
//
// vertical Fermat is V_j = R_j^2 - N a perfect square?
// horizontal Fermat is H_j = i_j^2 + N a perfect square?
// trial division does P_j divide N?
//
// Two facts make the step cheap (both verified in --selftest):
//
// 1. V and H advance by ADDITION alone:
// V_{j+1} = V_j + 2 R_j + 1 H_{j+1} = H_j - 2 i_j + 1
//
// 2. V and H are linearly linked:
// H_j = V_j - P_j * S + 2N
// so a single state variable carries both tests.
//
// The path stops when P_j * S > N, i.e. at j_max = (N/S - 3)/2, which is
// asymptotically sqrt(N)/4 (measured: 0.2500 * sqrt(N)). That bound is
// exactly complete: a factor p is caught by the trial-division leg when
// p <= 2 j_max + 3 ~ sqrt(N)/2, and otherwise p > sqrt(N)/2 forces
// j_true = (sqrt(q) - sqrt(p))^2 / 2 <= sqrt(N)/4, so the vertical leg
// catches it. The two legs cover each other precisely -- which is what
// Figure 8 shows geometrically.
//
// Cost is sqrt(N)/4 iterations of a very tight loop: a few additions, two
// wheel lookups, one small division. No multiplication, no square root in
// the common case. Note what fusing costs, though: because a = r + j is
// locked to p = 2j + 3, the wheel can suppress the isqrt but cannot skip
// the iteration, so this stream cannot exploit the ~420,000x the decoupled
// vertical scan gets. It is a bounded, tight-constant fallback, not a
// replacement for the race.
// ---------------------------------------------------------------------
static void yellow_path_stream(const BigInt& N,
Found& found,
std::atomic<std::uint64_t>& next_chunk,
std::atomic<std::uint64_t>& counter,
bool ctm_owns_top,
const BigInt* rsa_R_hi = nullptr) {
const BigInt r = isqrt_ceil(N);
if (r < 4) return;
const BigInt m = r - 3;
if (m < 1) return;
const BigInt S = r + m;
BigInt jmax_big = (N / S - 3) / 2;
if (jmax_big < 0) return;
std::uint64_t jmax = u64_from_big(jmax_big, std::numeric_limits<std::uint64_t>::max());
// STOP AT THE CROSSOVER WITH CTM, not at j_max.
//
// The vertical leg and CTM's descending walk cover the SAME factors --
// both reach exactly t in [1,2], writing the smaller factor as
// p = sqrt(N)/t -- but from opposite ends of that range. Steps to reach
// a factor, in units of sqrt(N):
//
// t 1.0 1.2 1.408 1.6 1.9 2.0
// yellow 0.000 0.017 0.0591 0.112 0.213 0.250
// CTM 0.100 0.080 0.0592 0.040 0.010 0.000
//
// They cross at t = 1.4082, which is j = 0.237 * j_max. Past that the
// path is walking ground CTM gets to sooner, and at its own endpoint,
// t = 2, it needs 0.25*sqrt(N) where CTM needs ~0. Cutting there caps
// the worst case at 0.0592*sqrt(N) instead of 0.2500 -- 4.22x.
//
// Only when CTM is actually running. Its trial leg then reaches just
// p ~ 0.118*sqrt(N) rather than 0.5*sqrt(N), and what covers the rest
// is the separate td stream, which owns (b1, cross] with
// cross = 2*j_max+3 -- so nothing is dropped either way.
// --rsa caps R at 1.06066*sqrt(N), so the path need go no deeper than
// that -- 0.06066*sqrt(N) against the general 0.25*sqrt(N).
if (rsa_R_hi && *rsa_R_hi > r) {
const std::uint64_t jr = u64_from_big(*rsa_R_hi - r,
std::numeric_limits<std::uint64_t>::max());
if (jr < jmax) jmax = jr;
}
if (ctm_owns_top && jmax > 16) {
const std::uint64_t cut = (jmax / 1000) * 237 + ((jmax % 1000) * 237) / 1000;
if (cut > 0) jmax = cut;
}
// Admissible-residue tables: R for V = R^2 - N, i for H = i^2 + N.
static const std::uint32_t MODS[7] = {64, 27, 25, 7, 11, 13, 17};
std::vector<std::uint8_t> okR[7], okI[7];
for (int t = 0; t < 7; ++t) {
const std::uint32_t mm = MODS[t];
const std::vector<std::uint8_t> sq = squares_mod(mm);
const std::uint64_t Np = umod(N, mm);
const std::uint64_t Nn = umod(-N, mm);
okR[t].assign(mm, 0); okI[t].assign(mm, 0);
for (std::uint32_t x = 0; x < mm; ++x) {
const std::uint64_t v1 = ((1ull*x*x) % mm + mm - Np) % mm; // x^2 - N
const std::uint64_t v2 = ((1ull*x*x) % mm + mm - Nn) % mm; // x^2 + N
okR[t][x] = sq[v1] ? 1 : 0;
okI[t][x] = sq[v2] ? 1 : 0;
}
}
// Chunk size sets how many independent bracket starts the path is cut
// into. Nothing here is a ladder: R_j, i_j, V_j, H_j and P_j are all
// closed forms in j, so a bracket can begin at ANY j and every j is
// visited exactly once whatever the cut. The only variable cost is the
// per-chunk start -- two squares plus fourteen modulos -- and measured
// against the step it drives (mpz, as this stream actually runs):
//
// bits start step ratio
// 40 211.3ns 87.1ns 2.4
// 62 211.6ns 87.2ns 2.4
// 96 211.6ns 87.9ns 2.4
// 112 213.5ns 87.0ns 2.5
//
// The ratio is flat in N -- both ends grow together -- so a chunk of
// ~120 already holds the start under 2%, at every size.
//
// 1<<16 was a CPU tuning choice and caps the path at j_max/65536 starts:
// only ~3,800 at 60 bits, nowhere near enough to fill a device. 1<<8 is
// free on CPU -- min-of-11 wall times are 4/4, 54/54 and 126/127 ms on
// the three cases below -- and gives ~1e6 starts at 60 bits, ~1e9 at 96.
// The per-chunk atomic costs 16 ns fully contended against ~22,000 ns of
// chunk work, so it stays far under 1%.
const std::uint64_t CHUNK = 1u << 8;
// P_j = R_j - i_j = 2j + 3 is a MACHINE WORD, not a bignum: it runs to
// 2*j_max+3 = N/S ~ sqrt(N)/2, so it fits 64 bits for any N below 2^128.
// Forming it as an mpz (P = R - I) and calling mpz_divisible_p costs a
// subtraction, two increments and a general division every step; passing
// the machine word to divisible_by_u64 reaches mpz_divisible_ui_p, which
// divides by a PRECOMPUTED reciprocal because the divisor is one limb.
// Measured per step, trial-division leg only:
//
// 96-bit N 112-bit N
// P = R - I (mpz), mpz_divisible_p 28.77ns 44.01ns
// P = 2j+3 (u64), divisible_by_u64 5.90ns 10.03ns
// ... and skipping 3 | P or 5 | P 3.44ns 3.52ns
//
// The skip is sound only when N itself is coprime to 3 and 5: then no P
// sharing those factors can divide N. When it is not, those P must still
// be tested, so the skip is switched off rather than assumed.
const bool p_fits64 =
jmax <= (std::numeric_limits<std::uint64_t>::max() - 3) / 2;
const bool skip35 = !divisible_by_u64(N, 3) && !divisible_by_u64(N, 5);
const bool m_fits64 = mpz_sizeinbase(m.get_mpz_t(), 2) <= 64;
const std::uint64_t m_w =
m_fits64 ? u64_from_big(m, std::numeric_limits<std::uint64_t>::max())
: std::numeric_limits<std::uint64_t>::max();
BigInt R, I, V, H, y, g, P;
std::uint64_t local = 0;
while (!found.ready()) {
const std::uint64_t c = next_chunk.fetch_add(1, std::memory_order_relaxed);
const std::uint64_t j0 = c * CHUNK;
if (j0 > jmax) break;
std::uint64_t j1 = std::min(jmax, j0 + CHUNK - 1);
// i_j = m - j must stay non-negative. The incremental walk used to
// notice that via `if (I < 0) break`; with I gone from the hot loop
// the bound is applied to j up front instead.
if (m_fits64 && j1 > m_w) j1 = m_w;
// One seed per chunk, walking up. Seeding at the chunk's MIDDLE and
// running both ways was tried -- every quantity is a closed form in
// j, so from 95 + 82i the next point is 96 + 81i going up and
// 94 + 83i going down, with the residues advancing -1/+1 to match,
// and one seed then covers two half-spans instead of one span.
//
// It is correct (same factorizations on all 294 differential cases)
// and it is SLOWER, because the thing it halves is already small: