19:00 One technique I like to use was given in a paper by HJS Smith (recast by FW Clarke), and it goes like this: As you did, find x with x^2=-1 mod p and x
I think this is called the Hermite-Serret algorithm and can be quite mysterious if one doesn't know the theory behind it :D It can be rephrased as follows: Let x be a square root of -1 mod p, and attempt Euclid's algorithm on the pair (p, x), but stop until our two values r1 and r2 both become < sqrt(p). Then p = r1^2 + r2^2.
I also like that version with continued fractions : Just like in your coment, let's find x with x^2=-1. And let be p_k/q_k convergent of x/p s.t. k is maximum for which q_k
Euler's original proof can be made constructive, too. Given a^2+b^2 = mp for some m > 1, choose c and d such that a = c mod m and b = d mod m, with -m/2 < c,d
BTW the "strange" identity can also be found using determinant product of two matrices: M1 = mat(a, b; - b, a), M2 = mat(c, d; -d, c) det(M1) . det(M2) = det(M1 . M2)
I wonder if you'll cover Tonelli-Shanks in a future episode as a general algorithm for finding sqrt(-1) - I've found it quite awkward to figure out by hand for arbitrary quadratic residue n, although in practice for n=-1 it comes down to calculating a^((p-1)/2) for any quadratic non-residue. It's probably too specific to cover in this course anyway (which I've thoroughly enjoyed!)
The method Prof. Borcherds gave in lecture 25 is essentially Tonelli-Shanks with minor variations: - He tries to find an element of order 2^k (where p-1 = 2^k n with odd n). This is essentially the same as finding a nonresidue (which is needed by Tonelli-Shanks): z is a nonresidue iff z has order a multiple of 2^k, and if z has order a multiple of 2^k, then z^n has order exactly 2^k. - Also, the part where he tries to solve 2^k s + nt = 1 is a small variation of Tonelli-Shanks. In both cases, we split sqrt(d) into an "easy" square root and a "hard" square root. Prof. Borcherds' version solves 2^k s + nt = 1, while Tonelli-Shanks solves 2s + nt = 1, which has the easy solution (s,t) = ((n+1)/2, -1). However, there's no need to use the full Tonelli-Shanks if you just want to find a square root of -1, since you can easily get it from any nonresidue z (which Tonelli-Shanks needs beforehand anyway): if z is a nonresidue, then z^((p-1)/4) is a square root of -1. So we kinda already have a square root of -1 before we even start doing Tonelli-Shanks. In fact, all fast methods we currently know to find square roots involve some randomization. For example, to find a nonresidue, our current best method is just trial and error. Furthermore, from above, we know that finding a nonresidue is at least as hard as finding a square root of -1. But the latter is as hard as representing p as the sum of two squares. Indeed, if you have an m such that m^2 = -1 mod p, then you can compute x + yi = gcd(p, m + i) in Gaussian integers so that p = x^2 + y^2, and conversely if you have p = x^2 + y^2, then (x/y)^2 = -1 mod p. But even for this easier problem, all currently-known fast methods still involve some randomization.
For unique factorization, Mathologer's animation of Zagier's one sentence proof is the most beautiful video you will ever see
19:00 One technique I like to use was given in a paper by HJS Smith (recast by FW Clarke), and it goes like this: As you did, find x with x^2=-1 mod p and x
I think this is called the Hermite-Serret algorithm and can be quite mysterious if one doesn't know the theory behind it :D It can be rephrased as follows:
Let x be a square root of -1 mod p, and attempt Euclid's algorithm on the pair (p, x), but stop until our two values r1 and r2 both become < sqrt(p). Then p = r1^2 + r2^2.
I also like that version with continued fractions : Just like in your coment, let's find x with x^2=-1. And let be p_k/q_k convergent of x/p s.t. k is maximum for which q_k
Euler's original proof can be made constructive, too. Given a^2+b^2 = mp for some m > 1, choose c and d such that a = c mod m and b = d mod m, with -m/2 < c,d
Woahuu! algebraic number theory finally!
BTW the "strange" identity can also be found using determinant product of two matrices:
M1 = mat(a, b; - b, a), M2 = mat(c, d; -d, c)
det(M1) . det(M2) = det(M1 . M2)
I wonder if you'll cover Tonelli-Shanks in a future episode as a general algorithm for finding sqrt(-1) - I've found it quite awkward to figure out by hand for arbitrary quadratic residue n, although in practice for n=-1 it comes down to calculating a^((p-1)/2) for any quadratic non-residue. It's probably too specific to cover in this course anyway (which I've thoroughly enjoyed!)
He does something akin to Tonelli Shanks here: ruclips.net/video/H7WFEGrmMEs/видео.html
The method Prof. Borcherds gave in lecture 25 is essentially Tonelli-Shanks with minor variations:
- He tries to find an element of order 2^k (where p-1 = 2^k n with odd n). This is essentially the same as finding a nonresidue (which is needed by Tonelli-Shanks): z is a nonresidue iff z has order a multiple of 2^k, and if z has order a multiple of 2^k, then z^n has order exactly 2^k.
- Also, the part where he tries to solve 2^k s + nt = 1 is a small variation of Tonelli-Shanks. In both cases, we split sqrt(d) into an "easy" square root and a "hard" square root. Prof. Borcherds' version solves 2^k s + nt = 1, while Tonelli-Shanks solves 2s + nt = 1, which has the easy solution (s,t) = ((n+1)/2, -1).
However, there's no need to use the full Tonelli-Shanks if you just want to find a square root of -1, since you can easily get it from any nonresidue z (which Tonelli-Shanks needs beforehand anyway): if z is a nonresidue, then z^((p-1)/4) is a square root of -1. So we kinda already have a square root of -1 before we even start doing Tonelli-Shanks.
In fact, all fast methods we currently know to find square roots involve some randomization. For example, to find a nonresidue, our current best method is just trial and error.
Furthermore, from above, we know that finding a nonresidue is at least as hard as finding a square root of -1. But the latter is as hard as representing p as the sum of two squares. Indeed, if you have an m such that m^2 = -1 mod p, then you can compute x + yi = gcd(p, m + i) in Gaussian integers so that p = x^2 + y^2, and conversely if you have p = x^2 + y^2, then (x/y)^2 = -1 mod p. But even for this easier problem, all currently-known fast methods still involve some randomization.
yeeeeeeeeeeeee