Fermā faktorizācijas kalkulators

Par šo kalkulatoru

Fermā faktorizācijas metode izmanto faktu, ka jebkuru nepāra veselu skaitli N var uzrakstīt kā divu kvadrātu starpību, N = a² − b² = (a−b)(a+b). Algoritms sākas ar a = ⌈√N⌉ un katrā solī palielina a par 1, pārbaudot, vai a² − N pats ir pilns kvadrāts (b²); tiklīdz tas tā ir, N uzreiz sadalās reizinātājos (a−b)(a+b). Šis kalkulators izpilda šo ciklu un parāda katru soli, ko tas veica, lai atrastu reizinātājus.

Metode konverģē ļoti nedaudzos soļos, kad N abi reizinātāji ir tuvu viens otram — tās galvenais trūkums ir arī tās svarīgākais lietojums reālajā pasaulē: kriptogrāfijas studenti un drošības pētnieki izmanto Fermā faktorizāciju, lai parādītu, kāpēc RSA moduļiem jābūt veidotiem no pirmskaitļiem, kas ir tālu viens no otra, jo pārāk tuvu izvēlēti pirmskaitļi padara moduli triviāli uzlaužamu. Tas ir arī standarta uzdevums skaitļu teorijas kursos kvadrātu starpības spriešanas ilustrēšanai.