<-- Prev

Modular Arithmetic

Next -->
  • Legendre Symbol
    35 pts · 10784 Solves · 44 Solutions
    In Quadratic Residues we learnt what it means to take the square root modulo an integer. We also saw that taking a root isn't always possible.

    In the previous case when p=29p = 29, even the simplest method of calculating the square root was fast enough, but as pp gets larger, this method becomes wildly unreasonable.

    Lucky for us, we have a way to check whether an integer is a quadratic residue with a single calculation thanks to Legendre. In the following, we will assume we are working modulo a prime pp.

    Before looking at Legendre's symbol, let's take a brief detour to see an interesting property of quadratic (non-)residues.

    Quadratic Residue * Quadratic Residue = Quadratic Residue
    Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
    Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue


    Want an easy way to remember this? Replace "Quadratic Residue" with +1+1 and "Quadratic Non-residue" with 1-1, all three results are the same!

    So what's the trick? The Legendre Symbol gives an efficient way to determine whether an integer is a quadratic residue modulo an odd prime pp.

    Legendre's Symbol: (a/p)a(p1)/2mod  p(a / p) \equiv a^{(p-1)/2} \mod p obeys:

    (a/p)=1(a / p) = 1 if aa is a quadratic residue and a≢0mod  pa \not\equiv 0 \mod p
    (a/p)=1(a / p) = -1 if aa is a quadratic non-residue mod  p\mod p
    (a/p)=0(a / p) = 0 if a0mod  pa \equiv 0 \mod p


    Which means given any integer aa, calculating a(p1)/2mod  pa^{(p-1)/2} \mod p is enough to determine if aa is a quadratic residue.

    Now for the flag. Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.

    So Legendre's symbol tells us which integer is a quadratic residue, but how do we find the square root?! The prime supplied obeys p=3mod  4p = 3 \mod 4, which allows us easily compute the square root. The answer is online, but you can figure it out yourself if you think about Fermat's little theorem.

    Challenge files:
      - output.txt

    You must be logged in to submit your flag.


Level Up

level up icon

You are now level Current level

You have solved this challenge
You have not yet solved this challenge
You've solved 0 of 11 challenges in this course (0%)