Ҳисобкунаки факторизатсияи Ферма

Дар бораи ин ҳисобкунак

Усули факторизатсияи Ферма аз он истифода мекунад, ки ҳар адади бутуни тоқи N-ро метавон ҳамчун фарқи ду квадрат навишт, N = a² − b² = (a−b)(a+b). Алгоритм аз a = ⌈√N⌉ оғоз мекунад ва a-ро дар ҳар қадам 1 зиёд мекунад, месанҷад, ки оё a² − N худаш квадрати комил (b²) аст; дарҳол ки чунин шуд, N фавран ба (a−b)(a+b) таҷзия мешавад. Ин ҳисобкунак ҳамин давраро иҷро мекунад ва ҳар қадамеро, ки барои ёфтани ҷузъҳо гузоштааст, нишон медиҳад.

Усул дар чанд қадам муттаҳид мешавад, вақте ки ду ҷузъи N ба ҳам наздиканд — нуқтаи заифи асосии он низ муҳимтарин истифодаи воқеии он аст: донишҷӯёни криптография ва пажӯҳишгарони амният факторизатсияи Фермаро барои намоиш додани он истифода мебаранд, ки чаро модулҳои RSA бояд аз ададҳои сода сохта шаванд, ки аз ҳам дур аст, зеро ададҳои сода, ки аз ҳад наздик интихоб шудаанд, модулро ночиз вайроншаванда мекунанд. Он ҳамчунин машқи стандартӣ дар курсҳои назарияи ададҳо барои нишон додани тарзи фикрронии фарқи квадратҳост.