factorizer 0.9.6

No project description provided

factorizer

This is a simple factorization tool.

Here is the simplest example.

from factorizer import BruteForceFactorizer
divider = BruteForceFactorizer() 
divider.factorize(57) # Devide number in order, starting with 2, 3, 4, 5...
#>>>(3, 19)

Install

Requirements

• boost

if you are using apt, you can install with

apt install libboost-dev

Install

Install with pip and GitHub

pip install git+https://github.com/FullteaOfEEIC/factorizer.git

Install with PyPI

pip install factorizer

Usage

Basic Usage

first, import package

from factorizer import BruteForceFactorizer

BruteForceFactorizer trys dividing given number with 2, 3, 4, 5...

All Methods in this package are listed below.

second, create a object

divider = BruteForceFactorizer()

then, call factorize() method to factorize a number.

divider.factorize(57)
#>>> (3, 19)

You will receive the tuple, whose length are 2 and the product of those are the given number.

That's all!!

Setting Timeout

When you try to factorize some large numbers, what we care is whether the calculation ends in a short period. While we can't predict the required time, we provide time out method instead.

from factorizer import BruteForceFactorizer

divider = BruteForceFactorizer()
facts = divider.factorize(221) # This takes less than 1 second.
print(facts) # >>> (13, 17) 
facts = divider.factorize(144483604528043653279487) # This takes about 40 seconds in my environment.
print(facts) # >>> (2147483647, 67280421310721)

Now you can set timeout for divider.

from factorizer import BruteForceFactorizer

divider = BruteForceFactorizer(timeout=5)
facts = divider.factorize(221)
print(facts) # >>> (13, 17) 
facts = divider.factorize(144483604528043653279487) # This raises timeout error after 5 seconds.
# >>> factorizer.TimeOutError

Factorize Methods

BruteForceFactorizer

This method searches factors by dividing a given number sequential(2, 3, 4, ...sqrt(n)). This is useful when n is small or n has small factors.

from factorizer import BruteForceFactorizer

n = 21
divider = BruteForceFactorizer(timeout=5)
facts = divider.factorize(n)
assert n == facts[0] * facts[1]
print(facts) # >>> (3, 7)

FermatFactorizer

This method searches factors by using Fermat's factorization method. This is useful when two factors of the given numbers are similar sizes.

from factorizer import FermatFactorizer

n = 17094896531810236860130284769490321915294047711310368136394905170386978916759334950349117125605720936295486193376534502996558346954298821541237678202872064373159864453975455700275218336138295073109837853052911442982249175483147894454735060228013876333548456070708161754022653432247114865681934678336369669630310417775703125135381535339600363990582556226874678712573925886711666498382111760727570796847908646797570295191362260110871270300928038772025787352463090061558150045455638071691578922379413464004696514186854056461649591756647526422083918100655183395966280798720122926503397649310956601613684952853243575941193

divider = FermatFactorizer(timeout=5)
facts = divider.factorize(n)
assert n == facts[0] * facts[1]
print(facts) # >>> (130747453251718202865367599610984256344049976791406031337536420100072758990497257029481575106895700732897562067500860599588866977471195605540443529953122402713181190128830424125700106569684526840827976181922955582670800429750099675311621080502576741880521124560628733981949754441379686189254362646041261993641, 130747453251718202865367599610984256344049976791406031337536420100072758990497257029481575106895700732897562067500860599588866977471195605540443529953122402713181190128830424125700106569684526840827976181922955582670800429750099675311621080502576741880521124560628733981949754441379686189254362646041262989473)

PollardsRhoFactorizer

This method searches factors by using Pollard's rho algorithm.

from factorizer import PollardsRhoFactorizer

n = 115792089237316195423570985008687907853269984665640564039457584007913129639937

divider = PollardsRhoFactorizer(c=1, timeout=300)
facts = divider.factorize(n)
assert n == facts[0] * facts[1]
print(facts) # >>> (1238926361552897, 93461639715357977769163558199606896584051237541638188580280321)

RSAPrivateKeyFactorizer

This methods factorize a value of RSA public key using a private key.

from factorizer import RSAPrivateKeyFactorizer

n = 27686602223927069809508667129651371574022939911012945899001963424465432485857959278558567281517986710814493093153793525047594117727967922805090645353064983356364587573528439400605242106130103131384993204101341653150290978652895046371555816803503680877880178698972551411830684046183050273503256489746735122896322889851233107319826830407170825219504026080487291571593984998811061039563352881755150841596074226928497041576188756112952655828168668354006968017555707521724480003190926244967186018315461915028536777617724701916068306698854834025206955234552798984323325634496632645984709079699996404187769159304233647822817
d = 24519437769149139138866335660847545755165653484828286006043516748645401856648854182027545432645741317052553200888752554950064278086138490312456491085827725315522539371158133921466167994259596651442467698644153219537709818896410096455515199158877483530710370808678561483477316661434979292218578919768993187556392027276261818313248453442745589939088057747368431718456807618716287398645113323934099505504696161971119193577301554819446410886001798824782611510559183940960340872731200080537116249824675375515706234728334218799881290646607824216835997567209464899473615916775422544955890417233691031033339957172951014984193
e = 65537

divider = RSAPrivateKeyFactorizer(timeout=5)
facts = divider.factorize(n=n, d=d, e=e)
assert n == facts[0] * facts[1]
print(facts) # >>> (164440261485392965958742019246770416320932920696954972063153653746118661265309225245866288630607809128837646403488126759943170796688209694380633475245468531031317968059042232976590058634563033374276851700592039029913560594799947875803213408972945984053103732205589545833939222174651819219655132052468407371273, 168368755764757999709509937248353083024339876032843327089346146791177263807954202500513372878263241247260384327152524628645952463666883718555038702070451982789684092744140047859634766283935579015168962695374570234745026167687949972650110320372983580614771069456603621708761065756833056697404158656939419138329)

FactorDBFactorizer

Factor DB is a great database to store known factors for many numbers. This method get factors from Factor DB.

from factorizer import FactorDBFactorizer

n = 57

divider = FactorDBFactorizer(timeout=5)
facts = divider.factorize(n)
assert n == facts[0] * facts[1]
print(facts) # >>> (3, 19)