Y by
I keep seeing a certain type of problem in UIL Number Sense, though I can't figure out how to do it (I aim to do it in my head in about 7-8 seconds).
The problem is x^((p+1)/2) mod p, where p is prime.
For example 11^15 mod 29
I know it technically doesn't work this way, but using fermats little theorem (on √x^(p+1)) always gives either the number itself, x, or the modular inverse, p-x.
By using the theorem i mean √x^28 mod 29 = 1, and then youre left with √x^2 mod 29 or x, but then its + or -.
I was wondering if there is a way to figure out whether its + or -, a slow or fast way if its slow maybe its possible to speed it up.
The problem is x^((p+1)/2) mod p, where p is prime.
For example 11^15 mod 29
I know it technically doesn't work this way, but using fermats little theorem (on √x^(p+1)) always gives either the number itself, x, or the modular inverse, p-x.
By using the theorem i mean √x^28 mod 29 = 1, and then youre left with √x^2 mod 29 or x, but then its + or -.
I was wondering if there is a way to figure out whether its + or -, a slow or fast way if its slow maybe its possible to speed it up.