integer_factorization

This is a command-line tool to factorize big integers. It calls ecm library to perform integer factorization internally.

Dependencies

1.Install Openssl. Reference Openssl Installation

2.Install Protobuf. Reference Protobuf Installation

3.Install SafeheronCryptoSuites

git clone --recurse-submodules https://github.com/safeheron/safeheron-crypto-suites-cpp.git
cd safeheron-crypto-suites-cpp
mkdir build && cd build
# Run "cmake .. -DOPENSSL_ROOT_DIR=Your-Root-Directory-of-OPENSSL  -DENABLE_TESTS=ON" instead of the command below on Mac OS.
cmake ..  -DENABLE_TESTS=ON
# Add the path to the LD_LIBRARY_PATH environment variable on Mac OS; Ignore it on Linux
export LIBRARY_PATH=$LIBRARY_PATH:/usr/local/lib/
make
make test
sudo make install

4.Install GMP

curl -O https://gmplib.org/download/gmp/gmp-6.2.1.tar.xz
tar -xvf gmp-6.2.1.tar.xz
cd gmp-6.2.1
#./configure [--prefix <Your GMP installation directory>. The default is ‘/usr/local’] 
./configure
#compile the program with:
make
#self test:
make check 
#Install it (under /usr/local by default) with
sudo make install

5.Install ECM

git clone https://gitlab.inria.fr/zimmerma/ecm
cd ecm
autoreconf -i
#./configure [--with-gmp=<Your GMP directory>] [--prefix=<Your ECM installation directory>]
./configure
#compile the program with:
make
#self test:
make check
#Install it (under /usr/local by default) with
sudo make install

Usage

1.Build the tool

#Build it with:
git clone https://github.com/Safeheron/integer-factorization.git
cd integer_factorization
mkdir build && cd build
#Run 'cmake .. -DOPENSSL=<Your Openssl directory>' instead on macOS.
cmake .. 
make
#Then you have the executable factor_ecm in current directory. Run './factor_ecm -h' to get the optional arguments.

2.Examples

./factor_ecm -h
Usage: ./factor_ecm [-ecm ecm path] [-f integer file] [-nn number of integers] [-nbits bits of the integer] [-pbits bits of the factor] [-t number of threads] [-m function mod].
Arguments:
  -ecm: ecm path
  -f: integer file path
  -nn: number of integers
  -nbits: bits of the integer
  -pbits: bits of the factor
  -t: number of threads
  -m: function mod. 1 : factorize; 2 : judge

./factor_ecm -f ../integer.txt -t 2 -m 1  #It will factorize integers in '../integer.txt' using 2 threads in mod 1(which indicates it will find all the time until it found the factor)
************ Start ecm factor **************
ecm: ecm -c 2  25e4 1.3e8 -mpzmod  threads: 2 mod: 1
Read N: 20516775134574293463386438600173753278716008240750650576249365729763125628102671348405911997412158952257655277253682167182886200381157622068173952507303333103349177417443268818106454431443748204204514275821331801045568860154981365985562978878104388851368412221126237125140359457220608180856208378132142917508507440429216084385634118838823122156544602333274176555685721371540955832962361469410212828981796993913067545535906996301081058132908720850439809156180708190309481831711433830359569448504177925567679030870364158379386101561940660995340945300580924898623460227075554075985247847432328246207753714244654428943717
********** Factor found in step 2: 1021791499165844943393503 21
Execute time: 52761 ms.
ecm: ecm -c 2  25e4 1.3e8 -mpzmod  threads: 2 mod: 1
Read N: 22089076386380436133269955687598157394187342337597794924032764587113009861859667214884384347291001313522536150643258821449929456296261677719063898887875351362554892314188941207108554387832021637828157805054942567265342699718490772905082320755252205935916984082165061940962699625892636523961915149765660514129134356056784774031290321604932665256370335699379823448266769063548308372271882504132010751747914783172320794355106911559399394327207118239317911621162576927569810455528328641629204974403536603890384387745722630244166750872380388246118781111683393592735641334560400955946925570451245886691414461265225456630829
********** Factor found in step 2: 944166462774525579599603 28
Execute time: 65564 ms.
...
...
...
ecm: ecm -c 2  25e4 1.3e8 -mpzmod  threads: 2 mod: 1
Read N: 22329492922405839551344627389322222012316384587825136046210613820522478112221825350738423999840506249244831036779948190427197555876197668758155857703974406765381400001748490147791676118494480373405122325444909917899623466970448536637163021668192719347011014848170231430874155793971148260486918405421072003733131793686827998592203973546344582566992303053379689416002878520238353786188918143360133295229748623800809035845787975521351995761445523531618523291811074958708355647968484780774592619692820910051197850366823313335749827328449204051375863811809541700438152028977060727423694832543364995377484423686533211275601
********** Factor found in step 2: 1109422808172602559221987 27
Execute time: 64234 ms.
Total time: 1053991 ms.


./factor_ecm -nn 10 -nbits 2048 -pbits 80 -t 2 -m 1  #It will factorize integers generated randomly using 2 threads in mod 2(which indicates it will find a certain number of times even if the factor is not found)
************ Start ecm factor **************
ecm: ecm -c 2  25e4 1.3e8 -mpzmod  threads: 2 mod: 1
Read N: 27230825226322275014954700935470315597330416338858797867602380822771385585071089671312210797608160622828123745692828086812121968175471900458291504808970408016550091020113280232024122887491815809834836704353769780305308879504142743742303532029925770992340704932149297543426720302643540021472460791473733494763886983771167075487437697747672009629662543060938486826224346852496124793220643152962945410753709960865702949845526612417849917775007092454320823732445269614062678951081531829788488778676405651699384357577533158639454682729087328406383949287779374851551903514865477956047208083560556769774622767582889141384521
********** Factor found in step 2: 1151577504818303502213839 18
Execute time: 45831 ms.
ecm: ecm -c 2  25e4 1.3e8 -mpzmod  threads: 2 mod: 1
Read N: 23466558851970097558466409742337451441360191730001576751725318608017764497873352315012411078207467849879244373501146326019409368412994172674081486028223377240280861252504681277065096247711025736256008021670944706959373555969700993932732141532930145802577523842681224827146465382861603580564674472794654970573600556944081874952368849578946809372119534760974882402778688866647564724779665450413344012012797281014893650799001352080041126490360364296762434052672381595430231140839114310649145586264798428751078530649923803230836311449531697021024921478330145012696785429036179460887753135405625661782769775567421073197341
********** Factor found in step 2: 1145184507032445958165643 10
Execute time: 27832 ms.
...
...
...
ecm: ecm -c 2  25e4 1.3e8 -mpzmod  threads: 2 mod: 1
Read N: 25726362103243547140913130324844918202884069672852569838797324894566594524625990061995350958195585081776267496864951916875970195011565749523624246439214447356200778052473869300045074334500302984688116110674530017990881210992601292903195485734784146107932601552423766459622666669056439806626645884799232267386804472058722752329273155279908589063488101724852816393451043864307324056834431121218762945474137934913266395241864150258736065494042835358918431584348051878379769530087463132187385778148453916079790706385087218627574455071815720639765995907915389812518225349271990923647972285015362023291758528654462895983849
********** Factor found in step 2: 976125615367538175435527 74
Execute time: 170341 ms.
Total time: 1270353 ms.


#You will get a factor.txt in current directory which records the found factors when the command finished:
#factor.txt:
ecm -c 2  25e4 1.3e8 -mpzmod threads: 2 mod: 1
A2862FB145AC7CE580E0BFF3CEFF42646050F8C611D36A3026E6EFB433B5CDD9EEFBA893E3F25C23A4951BA20992680162934CBDB6876CC791738C140C6EA6EC82938F7E18C5F0760367CF20883DCAB1D6885E222BBC7A1B5D434FD9FC148E387FA9AD69CE708FDDDE3E963F9AB2AF2046A37D7DBA21BC92E6F2A631C3E7770C77C95FAD6F1DC60D9F0645AEF2CC5D03D2151E35443FE0F90F1E2EAE58489C4450C8281EDCC58DDB409C306797C616954ACABCE4881E40ABDD2689A9F7596F29CD5CB42C752DA9306E7DB87CAC8957E3CA165421CF9E1B7220759A10588B386E33FD8E762E92C9F79D50150EF5FCA5F411DE23B8DFFE47A95D48ADDCF4797565
********** Factor found in step 2: 1021791499165844943393503 21 52761ms
AEFAAC36FA943F40D6C5C8B0A998CB864D2F487DAEB66EACD0080135E7FACDD65675ED624723A9DC6267E8118C9594E05B440461FCC0F82914AC3AEA176E17CE5989AE8B6B0163B4BEAC8D3AD85A0C715F21B7844A998472D88633BFBFC211F68C709AC6742D35BA32A8345B2443FF03B77963B7F4C288F4DCABC881475D88526D64A0B3D58BC99F6D32ABC5C223615E4019EBBB38D21EB10943462DD41B934FE0D112CD655C4CED5A45AD8CB0D1FAF96FC5075DAF8C1A01BFF25D3F3C9B7BF3F63C66F64182359918CA63EC2D76FFAF0F7ED590D59CE119F195B7AC1041CFDE8E11041BBAC8A7777C603536D7815C05595FEAFAB57F1AAE71BD005FF22D3C2D
********** Factor found in step 2: 944166462774525579599603 28 65564ms
...
...
...
B0E2374947433EF1FCB09BACD5D71470AEAE323E4581C803DC825F77E7EEA53CD088755F6CE8BB99B41A10C48251328BCA8998BEA3EFE57A0C9FED0C99F4985BF9FA3FEE7233DEA35B5161C0D1480CFD77BA86CA22A3934B441653AF5F9303C2D47FF717A18DF8308727586DC26C6C638485B05397EAAE357B783122B69A758B27AB56E598E1523B952D1E5AE4279CF21AA4E6061FA8E19737BBCEC849950F6FFD48322181E8DC44151A4EEC956721363621002F9DA2CE29ECA8706621292BE0426D201CA9650DBC4DC65DCD906CF69FAE946D3392CADBF6D5B52974A5EBD71BE4C004444E752C6D2B6881BD51D05F136705FADFBAB9B7770A2D0A25F1DCC151
********** Factor found in step 2: 1109422808172602559221987 27 64234ms
1053991ms