faktorimit

Faktorimi është procesi i ndarjes së një objekti matematik në një produkt faktorësh të tij më të vegjël. Në këtë kuptim, faktorimi përdoret kryesisht për dy raste të mëdha: faktorimin e numrave të plotë dhe faktorimin e polinomëve. Në të dyja rastet qëllimi është të zbërthehet një njësi në faktorë që kur multiplikohet rikthen objektin fillestar.

Faktorimi i numrave të plotë (faktorimi primar) përfshin zbulimin e faktorëve prim të një numri n, që bashkuar prodhojnë n: n = p1^a1 p2^a2 ... ku p_i janë numra prim dhe a_i fuqitë. Sipas faktorit themelor të aritmetikës, çdo numër më i madh se 1 ka një faktorim primar të vetëm, pa marrë rendin e faktorëve. Gjetja e këtyre faktorëve është një problem themelor në teorinë e numrave dhe ka implikime të rëndësishme në kriptografi dhe simulime kompjuterike. Megjithatë, për numra të mëdhenj, faktorimi është një problem i ndërlikuar dhe vazhdojnë të zhvillohen teknika të avancuara si metodat me kurva eliptike (ECM), Pollard rho, Pollard p-1 dhe teknika të tjera të zgjeruara (në vendet e mëdha: Number Field Sieve).

Faktorimi i polinomëve përfshin dekompozimin e një polinomi me koeficientët në prodhim të faktorëve polinomiale irreducible. Faktorizimi i polinomëve është themelor në algebrën kompjuterike dhe në zbatimin e algoritmeve të algebërës. Në fushat reale ose rationale, faktorimi i polinomëve është i mundur me mënyra të ndryshme; në fushat finite përdoren algoritme të posaçme si Berlekamp dhe Cantor-Zassenhaus.

Aplikacionet përfshijnë kriptografinë, teorinë e numrave dhe zgjidhjen e ekuacioneve polinomiale. Software specialistë si Magma, Sage ose Mathematica ofrojnë funksionalitete për faktorim.