forked from bbuhrow/yafu
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME
244 lines (190 loc) · 10.5 KB
/
README
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
-------------------------------------------------------------------------------
OVERVIEW
-------------------------------------------------------------------------------
YAFU (with assistance from other free software) uses the most powerful modern
algorithms (and implementations of them) to factor input integers in a
completely automated way. The automation within YAFU is state-of-the-art,
combining factorization algorithms in an intelligent and adaptive methodology
that minimizes the time to find the factors of arbitrary input integers.
YAFU has been referenced several times in the academic literature. If you have
academic work that requires integer factorization, YAFU might be able to help.
YAFU is most optimized for general inputs up to 160 digits in size, although
there is support for inputs much larger than that, if they have a special
form. There are also specialized functions for handling lists of inputs and
ranges of contiguous smaller inputs.
YAFU is primarily a command-line driven tool. You provide the number to factor
and, via screen output and log files, YAFU will provide you the factors.
But that's not all! You also get an interactive environment similar to MATLAB
or PARI/GP, where you can type commands and store results. The functionality
of this interface is limited, but perhaps useful, and I have plans to make it
better. YAFU also provides a vast amount of flexibility, through many many
options and a very capable expression interpreter. If you know what you are
doing, or if you read the documentation enough, you can customize the operation
of YAFU a great deal. You should have received a copy of docfile.txt, which
explains in some detail all of the available functions, how to use them,
and how to influence their behavior. A community of factorization enthusiasts
can be found at mersenneforum.org, many of whom are willing and able to
answer questions.
-------------------------------------------------------------------------------
INSTALLATION
-------------------------------------------------------------------------------
No installation necessary, just put the binary in whatever location you like
and run it. Files that YAFU generates are placed alonside the binary, and
directories/files that YAFU needs are with respect to the binary location
(such as the ggnfs sievers, see below)
Which precompiled version should I use?
As of version 2.12, the following precompiled versions are available:
yafu-x64-sse41.exe
yafu-x64-avx2.exe
yafu-x64-avx512.exe
yafu-x64-avx512-ifma.exe
SSE41, AVX2, AVX512, and AVX512-IFMA refer to instruction set extensions that
the versions respectively support. SIQS, ECM, and yafu's prime sieve
all get progressively faster with more modern extensions.
See here for more information:
https://en.wikipedia.org/wiki/Advanced_Vector_Extensions
https://en.wikipedia.org/wiki/AVX-512#CPUs_with_AVX-512
Pick the best one that your cpu supports.
Roughly speaking:
If you have an Intel Ice Lake, Tiger Lake, Rocket Lake, or Sapphire Rapids cpu, use avx512-ifma.
If you have an Intel SkylakeX or certain Cannon Lake or Cascade Lake cpus, use avx512.
If you have an Intel Haswell CPU or newer (newer than 2013), use avx2.
If you have a Zen4 or Zen5 AMD cpu, use avx512-ifma.
If you have another AMD cpu newer than 2015, use avx2.
Otherwise use sse41.
If you have something other than Intel or AMD, (e.g., powerPC, Arm),
then yafu may not work for you.
Support and an active user community can be found here:
https://www.mersenneforum.org/node/58
-------------------------------------------------------------------------------
INSTALLATION WITH NUMBER FIELD SIEVE (NFS) SUPPORT
-------------------------------------------------------------------------------
To run the general or special number field sieve using YAFU, you will need to
provide ggnfs executable files and make the location of these files known to
YAFU at runtime. The easiest way to obtain the files is through Jeff
Gilchrist's website: http://gilchrist.ca/jeff/factoring/index.html
Download the .zip file for your OS and unzip it to a directory on your
computer. The easiest way to let yafu know where these are is to create/modify
a yafu.ini file (which should appear in the same directory as your YAFU
executable) to contain a line specifying ggnfs_dir in the following way:
ggnfs_dir=<location relative to yafu executable>
For instance, if your ggnfs executables were located adjacent to
the yafu folder in the directory tree, in a folder called ggnfs-bin, then the
line would be:
ggnfs_dir=..\ggnfs-bin\
The ggnfs executables accomplish the sieving portion of NFS. The other phases
are all handled internally to YAFU via a supporting library, msieve. Here are
some quick references on for more information about the number field sieve
or msieve:
http://mathworld.wolfram.com/NumberFieldSieve.html
http://en.wikipedia.org/wiki/General_number_field_sieve
http://sourceforge.net/projects/msieve/
-------------------------------------------------------------------------------
BUILD INFORMATION
-------------------------------------------------------------------------------
Pre-compiled binaries are provided for windows. However, anyone
is welcome to compile from source for your own system. If you can make a
binary which beats the performance of one of the pre-compiled versions for a
particular architecture, I'd love to hear about it!
Linux 64 bit OS (including Windows Subsystem for Linux, WSL)
=============
make yafu [NFS=1] [USE_SSE41=1] [USE_AVX2=1] [USE_BMI2=1] [SKYLAKEX=1] [ICELAKE=1]
I've built and tested with gcc and icc. Enable either by using
COMPILER=gcc or COMPILER=icc on the make line.
Optionally enable GNFS factorizations by setting NFS=1 during make. This will
require the makefile to be edited to point to the libmsieve.a library. By
default, it is assumed to be located at ../msieve/ relative to the Makefile.
YAFU now requires several other projects to be built before yafu. These are:
gmp (https://gmplib.org/)
gmp-ecm (http://ecm.gforge.inria.fr/)
msieve (https://sourceforge.net/projects/msieve/)
ytools (https://github.com/bbuhrow/ytools)
ysieve (https://github.com/bbuhrow/ysieve)
Here are some terse notes on how to build these dependencies prior to yafu. Specific
arguments to "make" in some cases could change depending on your system.
GMP
./configure --prefix="/path/to/a/gmp/install/location/"
make
make install
GMP-ECM
autoreconf -i
./configure --prefix="/path/to/a/ecm/install/location/" --with-gmp="/path/to/a/gmp/install/location/"
make
make install
MSIEVE
edit makefile to add the following to CFLAGS:
-I/path/to/a/gmp/install/location/include/ -L/path/to/a/gmp/install/location/lib
make all NO_ZLIB=1 VBITS=128
YTOOLS
make
YSIEVE
edit makefile to add the following to CFLAGS:
-I/path/to/a/gmp/install/location/include/ -L/path/to/a/gmp/install/location/lib
make USE_AVX2=1 USE_BMI2=1
YAFU
edit makefile to add the following to CFLAGS:
-I/path/to/a/gmp/install/location/include/ -L/path/to/a/gmp/install/location/lib
-I/path/to/a/ecm/install/location/include/ -L/path/to/a/ecm/install/location/lib
-I/path/to/ytools/base/dir -L/path/to/ytools/base/dir
-I/path/to/ysieve/base/dir -L/path/to/ysieve/base/dir
-I/path/to/msieve/base/dir -L/path/to/msieve/base/dir
make yafu [NFS=1] [USE_SSE41=1] [USE_AVX2=1] [USE_BMI2=1] [SKYLAKEX=1] [ICELAKE=1]
Some support can be had here:
http://www.mersenneforum.org/forumdisplay.php?f=96
If your computer supports them, yafu can make use of several modern instruction
set extensions, including SSE41, AVX2, and AVX512 (various extensions).
SKYLAKEX will add support for AVX512F and AVX512BW.
ICELAKE will add support for AVX512F, AVX512BW, and AVX512IFMA.
Primarily these are used in SIQS. If you have AVX512 on your cpu, yafu will
also use AVX-ECM as the default ECM implementation. For a standalone
version of AVX-ECM, please refer to:
https://github.com/bbuhrow/avx-ecm
WINDOWS MS Visual Studio
=============
Build files are available for several versions of MSVC, but really only
build.vc22 should be used.
You will need several other visual studio projects installed and built
before attempting to build yafu.
As of yafu version 2.12 (Nov. 2024) I get these from these locations:
mpir: https://github.com/BrianGladman/mpir
ecm: https://gitlab.inria.fr/zimmerma/ecm/-/releases
or https://github.com/sethtroisi/gmp-ecm
pthreads: https://github.com/BrianGladman/pthreads (needed for msieve)
msieve: https://sourceforge.net/projects/msieve/
ytools: https://github.com/bbuhrow/ytools
ysieve: https://github.com/bbuhrow/ysieve
These all come with MSVC build files that should work.
To configure yafu once its dependencies are built, use the
libs_and_extensions.props file in the build.vc22 directory.
Here you can supply directories to the builds, relative to yafu's
project directories (e.g., build.vc22\ecm)
A little farther down in the libs_and_extensions.props file, edit
the PreprocessorDefinitions line with any instruction set extensions you
want to enable for yafu's build.
I have also had success installing and using the free Intel compiler inside
visual studio 2022.
MINGW-64
=============
YAFU might build in mingw-64 environment. I haven't tried in a long time;
good luck. If you get this to work, please let me know.
OTHER
=============
If you build yafu on other platforms or using other IDE's or
compilers, please let me know about it.
-------------------------------------------------------------------------------
HELP INFORMATION
-------------------------------------------------------------------------------
Detailed documentation is available in docfile.txt, which can be viewed during
an interactive YAFU session by typing 'help'. The default yafu.ini also
contains descriptions of available options.
If you want to see the docfile from within the program, it needs to be in the
same directory as the executable.
Check back at https://github.com/bbuhrow/yafu for updates.
---------------------------------------------------------------
MISC INFORMATION
---------------------------------------------------------------
Here's a fun test case for factor(), which uses many of the
algorithms in yafu
factor(2056802480868100646375721251575555494408897387375737955882170045672576386016591560879707933101909539325829251496440620798637813)
neat example for ecm:
140870298550359924914704160737419905257747544866892632000062896476968602578482966342704