Ẹ̀rọ Ìṣírò Ìpín Fermat

Nípa ẹ̀rọ ìṣirò yìí

Ọ̀nà ìpín Fermat ń lo òtítọ́ pé a lè kọ odindi àìdọ́gba N kankan bí ìyàtọ̀ ti onígun-mẹ́rin méjì, N = a² − b² = (a−b)(a+b). Algorithm náà bẹ̀rẹ̀ ní a = ⌈√N⌉ ó sì ń fi 1 kún a ní ìgbésẹ̀ kọ̀ọ̀kan, ó ń ṣàyẹ̀wò bóyá a² − N fúnra rẹ̀ jẹ́ onígun-mẹ́rin pípé (b²); ní ìgbà tí ó bá jẹ́ bẹ́ẹ̀, N pín sí (a−b)(a+b) lẹ́sẹkẹsẹ. Ẹ̀rọ ìṣírò yìí ń ṣe ìyípo yẹn ó sì ń fi gbogbo ìgbésẹ̀ tí ó gbé láti rí àwọn ìpín hàn.

Ọ̀nà náà ń dé ìparí ní ìgbésẹ̀ díẹ̀ gan-an nígbà tí àwọn ìpín méjì N bá sún mọ́ ara wọn — àìlera rẹ̀ pàtàkì ni ó tún jẹ́ lílò rẹ̀ pàtàkì jùlọ nínú ayé gidi: àwọn akẹ́kọ̀ọ́ cryptography àti àwọn olùwádìí ààbò ń lo ìpín Fermat láti fi hàn ìdí tí RSA modulus fi gbọ́dọ̀ jẹ́ ṣíṣe láti inú àwọn àkọ́kọ́ tí ó jìnnà sí ara wọn, nítorí àwọn àkọ́kọ́ tí a yàn tí wọ́n sún mọ́ ara wọn jù ń jẹ́ kí modulus rọrùn láti fọ́. Ó tún jẹ́ ìdárayá àṣà nínú iṣẹ́ ẹ̀kọ́ number theory fún ṣíṣàfihàn ìrònú ìyàtọ̀ onígun-mẹ́rin.