Theory of numbers: Quadratic residues
Vložit
- čas přidán 10. 09. 2024
- This lecture is part of an online undergraduate course on the theory of numbers.
We define quadratic residues (squares) and describe their basic properties, in particular Euler's criterion. The we describe fast algorithms to test whether a number is a quadratic residue, and if so to find its square root.
For the other lectures in the course see • Theory of numbers
In my case, p is HUGE.
Notes:
(1) If a^n ≡ 1 mod p (omitted hereafter) with n odd, then sqrt(a) ≡ a^{(1-n)/2}
(2) 18:30 If a^p ≡ 1 and p ≡ 3 mod 4, then by Euler’s criterion, a^{(p-1)/2} ≡ 1 and by (1) sqrt(a) ≡ a^{(1-n)/2} ≡ a^{(3-p)/4} ≡ a^{(1+p)/4} since a^{(p-1)/2} ≡ 1.
(3) To find the square root of -1 for the case p ≡ 1 mod 4, we observe that -1 ≡ g^{(p-1)/2} ≡ ( g^{(p-1)/4} )^2 ≡ ( g^{(p-1)/4} * g*{(p-1)/2} )^2 ( g is a primitive root) and there’s in total (p-1)/2 numbers in (Z/pZ)* that has the form: g to the power (p-1)/4 or (p-1)/4 + (p-1)/2. Hence guessing solution of square root of -1 is actually very efficient.
(4) If a^{2^m} ≡ 1, let g be a primitive root and g^{2^n * r} ≡ 1 and a = g^{2^k *s}, r, s odd. Then we have ( g^{2^k *s} )^{2^m} = g^{ 2^(k+m) *s} ≡ 1 whence r divides s and k = n - m, i.e. a ≡ g^{2^(n-m) *rt}, t odd.
Then it’s easy to check that a*g^{2^k *r} has order dividing 2^(m-1) (missing r in the video). Then sqrt(a) ≡ sqrt( a*g^{2^k *r} ) / g^{ 2^(k-1) *r } and you have an algorithm that works inductively.
In practice we first find a primitive root and calculate g^{ 2^(n-m) *r} up to g^{ 2^(n-1) *r} (just by squaring). Then calculate order of a*g^{ 2^k *r}, say 2^m’, and repeat the algorithm for 2^m’. Note that if a*g^{ 2^k *r} has order strictly smaller than 2^(m-1) then applying algorithm for 2^(m-1) will fail, so checking the order of a*g^{ 2^k *r} at every step is necessary.
(5) Finally for general a, we just solve x, y such that x*2^n + y*r = 1 and apply (1) and (4).
Solution to cubic root:
Almost the same argument carries through:
(1) If n is 1 or 2 mod 3, then crt(a) ≡ a^{(1-p)/3} or a^{(2-p)/3}. (crt = cubic root)
(2) If a has order 3^m, write p-1 = 3^n *r and a ≡ g^{ 3^k *rt}, r, t are not 0 mod 3. Then either a*g^{ 3^k *r} or a*g^{ 3^k *2r } has order dividing 3^(m-1) and the algorithm carries on inductively.
(3) Finally solve x, y for x*3^n + y*r = 1 and use (1), (2) to find crt(a).
It’s obvious that this works for any prime q smaller than p (no need to care primes larger than p) and for composite just take the roots of prime power separately.
24:28 Why must n be greater than m if a is a square? This seems to be true as in the following case: if p=19 and a = 18, we have ord(a)=2 so m = 1. Also, p-1=18 = 2 x 9 so n = 1, and in this case there is no number x such that x^2 = 18 mod 19.
Thanks for the videos. Number theory's never been my strong suit, but this series is making it a lot clearer.
It occurrs to me that the integers mod p are a field where half of the nonzero values are quadratic residues. And that's true of the reals, too (the positive half are residues). With the reals, we get a lot of value from introducing a square root for one of the nonresidues (i = sqrt(-1)). Is there some value to defining a square root for one of the nonresidues mod p? I know it can't be the same value for every p, so it's probably not as useful, but I'm curious.
If mod p there is no square root of -1, then adjoining a square root of -1 gives you a new field of size p^2. In abstract algebra terms: the polynomial x^2+1 is irreducible in (F_p)[x], and F_p is a field, so (F_p)[x] is a PID, so x^2+1 generates a maximal ideal, and adjoining sqrt(-1) to F_p is the same as taking the quotient of (F_p)[x] by this maximal ideal.
All finite fields can be obtained by generalizing this idea: just throw in new solutions to polynomial equations you can't already solve. In particular, this applies to quadratic non-residues. In general the polynomial you use must be irreducible (regarding quadratic residues, this is easier to show, because whether or not a quadratic polynomial factorizes is easier to check, because it's only quadratic), but different polynomials can give you the same field (the resulting "new" numbers are Galois conjugates, i.e., they have the same minimal polynomial over the field they live in). One systematic way to choose such polynomials is to use Conway polynomials. There's also a slightly fancier way using splitting fields of certain polynomials coming from Frobenius maps that is often presented in Galois theory courses.
Hello Professor, thank you very much for this course, i have just a problem with the générators of (Z/13Z)*, we found in this course 6 generators, but in the course of primitive roots we found that the number of generatos is equal to phi(p-1) that is phi(12)=4. Thank you again and excuse me for disturbance
I think that 5 and 8 are not primitive roots (5^4 = 1 modulo 13 and same thing for 8)
Around 20:52, it seems like guessing will help find a square root of -1, but not necessarily a primitive root. But around 24:40 it seems like you do treat g like it's a primitive root, so I'm a little confused. Thank you for your videos, they are great!
On looking again, I'm pretty sure g just has to be a quadratic non-residue. This you can find by guessing. Also, at 24:58, the order of ag^{2^{n-m} b} divides 2^{m-1}, i.e. I think there should be a 'b' in there.
Is it just me wondering why at 25: 12, ag^{2^{n-m}} has order dividing 2^{m-1}? I thought you have to have (ag^{2^{n-m}})^{2^{m-1}} congruent to 1 mod p. But I cannot see why that is true. Anyone care to take a look at it?
I'm pretty sure he meant ag^{2^{n-m} b}. It follows since a^{2^{m-1}} and g^{2^{n-1} b} are congruent to -1 mod p.
@@stevenhaker477 Thank you, Steve, for taking your time to reply. I actually thought about there might be a b missing in the exponent of g. However, if that is the case, then it would simply be a^2 because one line above, Richard actully wrote "a=g^{2^{n-m}b}" there. Moreover, right after that at 25:44 he put the square root of g^{2{n-m}} in the denominator. If that is the same as a, then why bother to do all that if you can find the square root of a already? I got really confused on this part. Maybe Richard himself can explain a little bit more to us mortals:) @Richard E. Borcherds
@@huaizhongr He uses "odd" twice, but I think he is referring to two different odd numbers. The first one he calls b, but the second one I think is d*b, where d is odd and unknown to us. Then a=g^( d b 2^(n-m)). If we knew d, we could just take g^( d b 2^(n-m-1)) for the square root of a, and as you say we wouldn't have to bother with the rest. If d were even, then we could write a = g^( (d/2) b 2^(n-m+1)) and have a^(2^(m-1)) = 1 mod p.
By the way, I think that what Professor Brocherds is describing is essentially Tonelli's method. See L. Dickson's classic "History of the Theory of Numbers", Volume 1, pp 215-216 for a simple explanation. It's available online at archive dot org.
@@stevenhaker477 Thank you, Steve! I'll look at Dickson first and see if that can clarify my mind.
YEEEE