Ҳисобкунаки рамзи Лежандр

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

Рамзи Лежандр (a/p), ки барои адади бутуни a ва адади соддаи тоқи p муайян шудааст, роҳи фишурдаи посух додан ба саволи бунёдӣ дар назарияи ададҳост: оё қиёси x² ≡ a (mod p) ҳал дорад? Ин ҳисобкунак онро бо истифода аз меъёри Эйлер арзёбӣ мекунад: (a/p) ≡ a^((p-1)/2) (mod p), ки дақиқан ба 1 баробар аст, агар a боқимондаи квадратии mod p бошад, −1 агар боқимондаи ғайриквадратӣ бошад ва 0 агар p ба a тақсим шавад.

Рамзи Лежандр унсури асосии назарияи мутақобилии квадратӣ аст ва дар тамоми назарияи ададҳои ҳисобӣ ва криптография пайдо мешавад — аз ҷумла санҷишҳои соддагӣ, алгоритмҳо барои ҳисоби решаҳои квадратии модулӣ ва сохторҳо дар криптографияи каҷиҳои эллиптикӣ — ҳар ҷо ки муҳим аст, ки оё адад квадрати комил бо модули адади содда аст.