Ẹ̀rọ Ìṣirò Àmì Legendre

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

Àmì Legendre (a/p), tí a túmọ̀ fún nọ́mbà odindi a àti nọ́mbà àkọ́kọ́ aláìṣẹ́ p, jẹ́ ọ̀nà kúkúrú láti dáhùn ìbéèrè pàtàkì nínú ẹ̀kọ́ nọ́mbà: ṣé congruence x² ≡ a (mod p) ní ojútùú? Ẹ̀rọ ìṣirò yìí ń ṣírò rẹ̀ nípa lílo àlámọ̀ Euler: (a/p) ≡ a^((p-1)/2) (mod p), èyí tí ó dọ́gba pẹ̀lú 1 bí a bá jẹ́ quadratic residue mod p, −1 bí ó bá jẹ́ non-residue, àti 0 bí p bá pín a gẹ́lẹ́.

Àmì Legendre jẹ́ ohun ìkọ́lé ti ẹ̀kọ́ quadratic reciprocity ó sì farahàn káàkiri ẹ̀kọ́ nọ́mbà ìṣirò àti cryptography — pẹ̀lú àwọn ìdánwò primality, àwọn algorithm fún ṣíṣírò gbòǹgbò onígun modular, àti àwọn ìkọ́lé nínú elliptic-curve cryptography — níbikíbi tí ó bá ṣe pàtàkì bóyá nọ́mbà kan jẹ́ onígun pípé modulo nọ́mbà àkọ́kọ́.