Dotaz: Faktorizace 196b cisel v C/C++

[Martin Sury]

Dobry den, v ramci sveho programu bych potreboval provadet faktorizaci 196b cisel vzniklych vynasobenim dvou prvocisel. Exisuje pro tento ucel nejaka knihovna v C/C++? Nasel jsem neco napriklad tady:

http://www.frenchfries.net/paul/factoring/source.html

http://www.codeproject.com/Articles/310513/Application-of-Goldbach-Conjecture

Ale nic co jsem zkousel takova cisla nezvladalo, potrebuji aby ten algoritmus byl rozumne rychly, abych na vysledek nemusel cekat hodinu. Predem dekuji za rady.

Odpovědi

[stativ]

Ale nic co jsem zkousel takova cisla nezvladalo, potrebuji aby ten algoritmus byl rozumne rychly, abych na vysledek nemusel cekat hodinu.

Hodinu? Řekl bych, že kdybys zvládl faktorizaci za hodinu, byl bys king.

[Michal Kubeček]

No, aspoň že nechce rovnou 2048 bitů. :-)

[stativ]

No, pokud uvažuji GNFS, nejrychlejší mě známý algoritmus, i tak mi vychází sakra dlouhý čas (prosím o kontrolu):

196b číslo má asi 59 míst. Složitost GNFS je exp(((64/9)*n)^(1/3) * (log(n)^2/3)), kde n je počet desetinných míst. Pokud budu počítat, že čas operace je 2.5E-10 s (střeleno od boku), tak mi to dává 72 490 hodin.

[pavlix]

Ono se to počítá s desítkovým logaritmem, že hraje roli počet desetinných míst?

[stativ]

Neříkal jsem, že vím jak ten algoritmus funguje, ale jen, že o něm vím (=> vím, že existuje). Složitost jsem si našel tady. Jinak samotný algoritmus je popsaný třeba tady.

[stativ]

Každopádně předchozí výpočet je samozřejmě hrubý odhad, složitost bude jiná (protože n se neblíží nekonečnu), nebude to jedna instrukce, a i čas běhu instrukce bude jiný. Pro představu, že to poběží dlouho (pokud jsem se někde při opisu složitosti nesekl) to IMHO stačí.

[pavlix]

Já si říkal, že tam ten přepočet na desítkový řád nemá co dělat. Krásná ukázka umění věci zkomplikovat.

[stativ]

Proč to dělat jednoduše, když to jde složitě…

[lertimir]

Myslím, že ten vzorec je chybně. Správný vzorec výpočetní složitosti je \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\log n)^{\frac{1}{3}}(\log \log n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right] (v TeXovém zápisu) nebo převedeno jako obrázek a jinak zdroj je WolframMathWorld Je tam trochu více logaritmů.

[lertimir]

Tedy jsem slepý, nebo spíše čtu hlavně vzorce, texty okolo už méně. V obvykle uváděném vzorci je n přímo číslo, které je třeba faktorizovat. U vzorce stativa je n počet desetinných cifer tohoto čísla, což udělá první logaritmování.

Mea culpa.

[rastos]

Trocha googlenia mi prinieslo odkaz na diskusiu v ktorej sa hovorí

256 bits is a little over 80 digits. Msieve can do factorizations that size in about 20-25 minutes

A čo je msieve? Projekt na sourceforge

Msieve is a C library implementing a suite of algorithms to factor large integers. It contains an implementation of the SIQS and GNFS algorithms

[Martin Sury]

Dekuji, msieve vypada dobre, na onech strankach je ke stazeni demo, ktere opravdu zvlada faktorizaci 196b cisel behem okamziku. Ja bych tuto funcionalitu potreboval vyuzit v ramci sveho programu, avsak nikde tam nevidim moznost stahnout si tu knihovnu, pouze ukazkovou aplikaci a jeji zdrojaky. Jsem jenom slepy, nebo tam tu knihovnu opravdu nemaji i kdyz tam maji vyslovne napsane "Msieve is a C library ..."?

[chochi]

Soucasti zdrojaku (dokonce hlavni hlavni soucast) je i knihovna

make x86_64
⋮
ar r libmsieve.a common/filter/clique.o common/filter/filter.o common/filter/merge.o common/filter/merge_post.o common/filter/merge_pre.o common/filter/merge_util.o common/filter/singleton.o common/lanczos/lanczos.o common/lanczos/lanczos_io.o common/lanczos/lanczos_matmul0.o common/lanczos/lanczos_matmul1.o common/lanczos/lanczos_matmul2.o common/lanczos/lanczos_pre.o common/lanczos/lanczos_vv.o common/lanczos/matmul_util.o common/smallfact/gmp_ecm.o common/smallfact/smallfact.o common/smallfact/squfof.o common/smallfact/tinyqs.o common/batch_factor.o common/cuda_xface.o common/dickman.o common/driver.o common/expr_eval.o common/hashtable.o common/integrate.o common/minimize.o common/minimize_global.o common/mp.o common/polyroot.o common/prime_delta.o common/prime_sieve.o common/savefile.o common/strtoll.o common/util.o mpqs/gf2.qo mpqs/mpqs.qo mpqs/poly.qo mpqs/relation.qo mpqs/sieve.qo mpqs/sqrt.qo \
        mpqs/sieve_core_generic_32k.qo mpqs/sieve_core_generic_64k.qo mpqs/sieve_core_p4_64_64k.qo mpqs/sieve_core_core_64_32k.qo mpqs/sieve_core_k8_64_64k.qo \
        gnfs/poly/poly.no gnfs/poly/poly_skew.no gnfs/poly/polyutil.no gnfs/poly/root_score.no gnfs/poly/size_score.no gnfs/poly/stage1/stage1.no gnfs/poly/stage1/stage1_roots.no gnfs/poly/stage2/optimize.no gnfs/poly/stage2/optimize_deg6.no gnfs/poly/stage2/root_sieve.no gnfs/poly/stage2/root_sieve_deg45_x.no gnfs/poly/stage2/root_sieve_deg5_xy.no gnfs/poly/stage2/root_sieve_deg6_x.no gnfs/poly/stage2/root_sieve_deg6_xy.no gnfs/poly/stage2/root_sieve_deg6_xyz.no gnfs/poly/stage2/root_sieve_line.no gnfs/poly/stage2/root_sieve_util.no gnfs/poly/stage2/stage2.no gnfs/filter/duplicate.no gnfs/filter/filter.no gnfs/filter/singleton.no gnfs/sieve/sieve_line.no gnfs/sieve/sieve_util.no gnfs/sqrt/sqrt.no gnfs/sqrt/sqrt_a.no gnfs/fb.no gnfs/ffpoly.no gnfs/gf2.no gnfs/gnfs.no gnfs/relation.no gnfs/poly/stage1/stage1_sieve_cpu.no gnfs/poly/stage1/stage1_sieve_cpu.no
ranlib libmsieve.a
⋮

Takze po buildu z toho vyleze staticka knihonva libmsieve.a, kterou staci prilinkovat (se spravne nastavenymi cestami k hlavickovym souborum). Viz napriklad build toho dema:

gcc -D_FILE_OFFSET_BITS=64 -O3 -fomit-frame-pointer -march=k8 -DNDEBUG -D_LARGEFILE64_SOURCE  -Wall -W -DMSIEVE_SVN_VERSION="\"exported\"" -I. -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 demo.c -o msieve  \
        libmsieve.a -lz -lgmp -lm -lpthread

[Martin Sury]

Aha, toho jsem si nevsiml, dekuju. Nepritomnost knihovny jsem usuzoval i z toho, ze jsem k ni mezi readme soubory ani na webu nenasel zadnou dokumentaci. Doufam, ze me i v tomto vyvedete z omylu a nejaka dokumentace existuje:)

[chochi]

Nejlepsi dokumentace jsou zdrojove kody
Ted vazne - v Readme:

Using Msieve
------------

Just to be confusing, there are two things that I call 'Msieve' interchangeably.
The source distribution builds a self-contained static library 'libmsieve.a',
that actually performs factorizations, and also builds a 'msieve' demo
application that uses the library. The library has a very lightweight inter-
face defined in msieve.h, and can be used in other applications. While the
demo application is (slightly) multithreaded, most the library is single-
threaded and all of its state is passed in. The linear algebra code used
in the quadratic- and number field sieve is multithread aware, and the
entire library is supposed to be multithread-safe.

Takze bych to videl, ze je asi nejlepsi se podivat na demo.c a inspirovat se (se 600 radky kodu by to nemusel byt problem).

[Filip Jirsák]

1, 2, 3 To je zase nějaký domácí úkol? Nechcete to raději řešit v jedné diskusi místo ve třech?

[Franta Gajdůšek]

Ano, je, ale myslim ze ty zbyle vlakna s nim nesouvisi. Mozna jedno(1), ale to druhe pochybuju (knihovna ktere se dotycny chce vyhnout je podle zadani explicitne povolena).