This source file includes following definitions.
- division
- monte_carlo
1 #ifndef LIBJMMCG_CORE_FACTORING_HPP
2 #define LIBJMMCG_CORE_FACTORING_HPP
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 #include "gcd.hpp"
25 #include "blatant_old_msvc_compiler_hacks.hpp"
26
27 #include <set>
28 #include <vector>
29
30 namespace jmmcg { namespace factoring {
31
32 using collection_type=std::vector<unsigned long>;
33
34
35
36
37
38
39
40
41
42
43 inline collection_type __fastcall
44 division(const collection_type::value_type x) noexcept(false) {
45 assert(x>collection_type::value_type{});
46 std::set<collection_type::value_type> factors;
47 collection_type::value_type count=1lu, tst_divs=2lu, n=x;
48 while (n!=1) {
49 if (n%tst_divs) {
50 if (n>1) {
51 if (count==1) {
52 ++tst_divs;
53 ++count;
54 } else if (count<3) {
55 tst_divs+=2;
56 ++count;
57 } else {
58 count++&1 ? (tst_divs+=2) : (tst_divs+=4);
59 if ((count>8) && (!(tst_divs%5) || !(tst_divs%7))) {
60 count++&1 ? (tst_divs+=2) : (tst_divs+=4);
61 }
62 }
63 } else {
64 factors.insert(n);
65 return collection_type{factors.begin(), factors.end()};
66 }
67 } else {
68 factors.insert(tst_divs);
69 n/=tst_divs;
70 }
71 }
72 return collection_type{factors.begin(), factors.end()};
73 }
74
75
76
77
78
79
80
81
82
83
84
85
86 inline collection_type __fastcall
87 monte_carlo(const collection_type::value_type y) noexcept(false) {
88 collection_type factors;
89 collection_type::value_type x=5, x_=2, k=1, l=1, n=y, g;
90 b2:
91 if (n&1) {
92 factors.emplace_back(n);
93 return factors;
94 }
95 b3:
96 if ((g=euclid::gcd((x_-x),n))==1) {
97 goto b4;
98 } else if ((g=n)!=0) {
99 return factors;
100 } else {
101 n/=g;
102 x%=n;
103 x_%=n;
104 goto b2;
105 }
106 b4:
107 if (!--k) {
108 x_=x;
109 l<<=1;
110 k=l;
111 }
112 x=(x*x+1)%n;
113 goto b3;
114 }
115
116 } }
117
118 #endif