This pages has answers to the practice problems at http://www.math.ufl.edu/~squash/GH/lightning-bolt.frame.pdf has more explanation. n: r_n q_n s_n t_n | n: r_n q_n s_n t_n /-------------------------------------------\ | /-------------------------------------------\ 0: 95 -- 1 0 | 0: 1234 -- 1 0 1: 57 1 0 1 | 1: 321 3 0 1 2: 38 1 1 -1 | 2: 271 1 1 -3 3: 19 2 -1 2 | 3: 50 5 -1 4 4: 0 infty 3 -5 | 4: 21 2 6 -23 \-------------------------------------------/ | 5: 8 2 -13 50 Note 19 = -1 * 95 + 2 * 57 . | 6: 5 1 32 -123 I.e GCD = S * r0 + T * r1 . | 7: 3 1 -45 173 | 8: 2 1 77 -296 | 9: 1 2 -122 469 (lightning 161 133) | 10: 0 infty 321 -1234 n: r_n q_n s_n t_n | \-------------------------------------------/ /-------------------------------------------\ | Note 1 = -122 *1234 + 469 * 321 . 0: 161 -- 1 0 | I.e GCD = S * r0 + T * r1 . 1: 133 1 0 1 | 2: 28 4 1 -1 | 3: 21 1 -4 5 | 4: 7 3 5 -6 | n: r_n q_n s_n t_n 5: 0 infty -19 23 | /-------------------------------------------\ \-------------------------------------------/ | 0: -178 -- 1 0 Note 7 = 5 * 161 + -6 * 133 . | 1: 110 -2 0 1 I.e GCD = S * r0 + T * r1 . | 2: 42 2 1 2 | 3: 26 1 -2 -3 | 4: 16 1 3 5 n: r_n q_n s_n t_n | 5: 10 1 -5 -8 /-------------------------------------------\ | 6: 6 1 8 13 0: 231 -- 1 0 | 7: 4 1 -13 -21 1: 616 0 0 1 | 8: 2 2 21 34 2: 231 2 1 0 | 9: 0 infty -55 -89 3: 154 1 -2 1 | \-------------------------------------------/ 4: 77 2 3 -1 | Note 2 = 21 *[-178] + 34 * 110 . 5: 0 infty -8 3 | I.e GCD = S * r0 + T * r1 . \-------------------------------------------/ | Note 77 = 3 * 231 + -1 * 616 . | I.e GCD = S * r0 + T * r1 . | | n: r_n q_n s_n t_n | n: r_n q_n s_n t_n /-------------------------------------------\ | /-------------------------------------------\ 0: 483 -- 1 0 | 0: 91 -- 1 0 1: 165 2 0 1 | 1: -56 -1 0 1 2: 153 1 1 -2 | 2: 35 -2 1 1 3: 12 12 -1 3 | 3: 14 2 2 3 4: 9 1 13 -38 | 4: 7 2 -3 -5 5: 3 3 -14 41 | 5: 0 infty 8 13 6: 0 infty 55 -161 | \-------------------------------------------/ \-------------------------------------------/ | Note 7 = -3 * 91 + -5 * -56 . Note 3 = -14 * 483 + 41 * 165 . | I.e GCD = S * r0 + T * r1 . I.e GCD = S * r0 + T * r1 . | ================================================================ Let rvec (an "r" with a little arrow over it) be the sequence rvec := (r_0, r_1, r_2, r_3, r_4, ... ). Use the same convention for sequences in general. So we have four sequences; rvec, qvec, svec and tvec. The relation between rvec and qvec is For each n >= 1: D1: r_{n+1} = r_{n-1} - [[q_n]*[r_n]] Now to answer your question. Sequences svec and tvec satisfy the same recurrence relation as rvec. Thus For each n >= 1: D2: s_{n+1} = s_{n-1} - [[q_n]*[s_n]] and t_{n+1} = t_{n-1} - [[q_n]*[t_n]] . There is one difference: We use rvec to compute qvec := (q_0, q_1, q_2, q_3, q_4, ... ). Once we know qvec, we use qvec to compute svec and tvec. Here is LBolt for GCD(161,131): n: r_n q_n s_n t_n /-------------------------------------------\ 0: 161 -- 1 0 1: 131 1 0 1 2: 30 4 1 -1 3: 11 2 -4 5 4: 8 1 9 -11 5: 3 2 -13 16 6: 2 1 35 -43 7: 1 2 -48 59 8: 0 infty 131 -161 \-------------------------------------------/ Note 1 = -48 * 161 + 59 * 131 . I.e GCD = S * r0 + T * r1 . Examining eqn s_{n+1} = s_{n-1} - [[q_n]*[s_n]] for n=5, gives s_6 = s_4 - [[q_5]*[s_5]] . And the numbers from the table give 35 = 9 - [2*[-13]]. So we used 9 - [2*[-13]] to compute 35, the value of s_6. Letting K+1 denote the row-index where r_{K+1} = 0, the GCD is r_K, and the two multipliers are S := s_K and T := t_K. ================================================================ Dear Sets&Logicians As you know, while I recommend symmetric-residues for modular computation, I don't particularly recommend negative remainders for LBolt. Nonetheless, several students asked me about this, so I picked a few small numbers by hitting the keys "randomly" (if I wanted to be scientific, I'd have used a random number generator). Empirically, this small sample suggests that allowing negative remainders is faster (and I believe there is a thm to this effect; see Wikipedia). But is the shorter table worth computing with negative remainders? YOU decide. The LHSide uses the smallest non-negative remainder The RHSide uses the remainder closest to zero (which might be negative), at each stage. at each stage. Non-negative REMAINDERS Closest-to-zero REMAINDERS n: r_n q_n s_n t_n n: r_n q_n s_n t_n /-------------------------------------------------------------------\ /-------------------------------------------------------------------\ 0: 100 -- 1 0 0: 100 -- 1 0 1: 23 4 0 1 1: 23 4 0 1 2: 8 2 1 -4 2: 8 3 1 -4 3: 7 1 -2 9 3: -1 -8 -3 13 4: 1 7 3 -13 4: 0 Infty -23 100 5: 0 Infty -23 100 \___________________________________________________________________/ \___________________________________________________________________/ Multiply r3,s3,t3 by -1 (which is a GInt-unit) for normalization; Rename r4,s4,t4 to GCD,S,T. call the new values GCD,S,T. Note GCD = r0 * S + r1 * T, i.e Note GCD = r0 * S + r1 * T, i.e 1 = [100]*[3] + [23]*[-13]. 1 = [100]*[3] + [23]*[-13]. n: r_n q_n s_n t_n n: r_n q_n s_n t_n /-------------------------------------------------------------------\ /-------------------------------------------------------------------\ 0: 98767654321 -- 1 0 0: 98767654321 -- 1 0 1: 23886757 4134 0 1 1: 23886757 4135 0 1 2: 19800883 1 1 -4134 2: -4085874 -6 1 -4135 3: 4085874 4 -1 4135 3: -628487 7 6 -24809 4: 3457387 1 5 -20674 4: 313535 -2 -41 169528 5: 628487 5 -6 24809 5: -1417 -221 -76 314247 6: 314952 1 35 -144719 6: 378 -4 -16837 69618115 7: 313535 1 -41 169528 7: 95 4 -67424 278786707 8: 1417 221 76 -314247 8: -2 -48 252859 -1045528713 9: 378 3 -16837 69618115 9: -1 2 12069808 -49906591517 10: 283 1 50587 -209168592 10: 0 Infty -23886757 98767654321 11: 95 2 -67424 278786707 \___________________________________________________________________/ 12: 93 1 185435 -766742006 13: 2 46 -252859 1045528713 Multiply r9,s9,t9 by -1 (which is a GInt-unit) for normalization 14: 1 2 11816949 -48861062804 call the new values GCD,S,T. 15: 0 Infty -23886757 98767654321 \___________________________________________________________________/ Note GCD = r0 * S + r1 * T, i.e Rename r14,s14,t14 to GCD,S,T. 1 = [98767654321]*[-12069808] + [23886757]*[49906591517]. Note GCD = r0 * S + r1 * T, i.e 1 = [98767654321]*[11816949] + [23886757]*[-48861062804]. n: r_n q_n s_n t_n n: r_n q_n s_n t_n /-------------------------------------------------------------------\ /-------------------------------------------------------------------\ 0: 29876777743 -- 1 0 0: 29876777743 -- 1 0 1: 4238867577 7 0 1 1: 4238867577 7 0 1 2: 204704704 20 1 -7 2: 204704704 21 1 -7 3: 144773497 1 -20 141 3: -59931207 -3 -21 148 4: 59931207 2 21 -148 4: 24911083 -2 -62 437 5: 24911083 2 -62 437 5: -10109041 -2 -145 1022 6: 10109041 2 145 -1022 6: 4693001 -2 -352 2481 7: 4693001 2 -352 2481 7: -723039 -6 -849 5984 8: 723039 6 849 -5984 8: 354767 -2 -5446 38385 9: 354767 2 -5446 38385 9: -13505 -26 -11741 82754 10: 13505 26 11741 -82754 10: 3637 -4 -310712 2189989 11: 3637 3 -310712 2189989 11: 1043 3 -1254589 8842710 12: 2594 1 943877 -6652721 12: 508 2 3453055 -24338141 13: 1043 2 -1254589 8842710 13: 27 19 -8160699 57518992 14: 508 2 3453055 -24338141 14: -5 -5 158506336 -1117198989 15: 27 18 -8160699 57518992 15: 2 -2 784370981 -5528475953 16: 22 1 150345637 -1059679997 16: -1 -2 1727248298 -12174150895 17: 5 4 -158506336 1117198989 17: 0 Infty 4238867577 -29876777743 18: 2 2 784370981 -5528475953 \___________________________________________________________________/ 19: 1 2 -1727248298 12174150895 Multiply r16,s16,t16 by -1 (which is a GInt-unit) for normalization; 20: 0 Infty 4238867577 -29876777743 call the new values GCD,S,T. \___________________________________________________________________/ Note GCD = r0 * S + r1 * T, i.e Rename r19,s19,t19 to GCD,S,T. 1 = [29876777743]*[-1727248298] + [4238867577]*[12174150895]. Note GCD = r0 * S + r1 * T, i.e 1 = [29876777743]*[-1727248298] + [4238867577]*[12174150895]. n: r_n q_n s_n t_n n: r_n q_n s_n t_n /-------------------------------------------------------------------\ /-------------------------------------------------------------------\ 0: 129876777743 -- 1 0 0: 129876777743 -- 1 0 1: 552338867577 0 0 1 1: 552338867577 0 0 1 2: 129876777743 4 1 0 2: 129876777743 4 1 0 3: 32831756605 3 -4 1 3: 32831756605 4 -4 1 4: 31381507928 1 13 -3 4: -1450248677 -23 17 -4 5: 1450248677 21 -17 4 5: -523962966 3 387 -91 6: 926285711 1 370 -87 6: 121640221 -4 -1144 269 7: 523962966 1 -387 91 7: -37402082 -3 -4189 985 8: 402322745 1 757 -178 8: 9433975 -4 -13711 3224 9: 121640221 3 -1144 269 9: 333818 28 -59033 13881 10: 37402082 3 4189 -985 10: 87071 4 1639213 -385444 11: 9433975 3 -13711 3224 11: -14466 -6 -6615885 1555657 12: 9100157 1 45322 -10657 12: 275 -53 -38056097 8948498 13: 333818 27 -59033 13881 13: 109 3 -2023589026 475826051 14: 87071 3 1639213 -385444 14: -52 -2 6032710981 -1418529655 15: 72605 1 -4976672 1170213 15: 5 -10 10041832936 -2361233259 16: 14466 5 6615885 -1555657 16: -2 -2 106451040341 -25030862245 17: 275 52 -38056097 8948498 17: 1 -2 222943913618 -52422957749 18: 166 1 1985532929 -466877553 18: 0 Infty 552338867577 -129876777743 19: 109 1 -2023589026 475826051 \___________________________________________________________________/ 20: 57 1 4009121955 -942703604 Rename r17,s17,t17 to GCD,S,T. Note 21: 52 1 -6032710981 1418529655 GCD = r0 * S + r1 * T, i.e 22: 5 10 10041832936 -2361233259 1 = [129876777743]*[222943913618] + [552338867577]*[-52422957749]. 23: 2 2 -106451040341 25030862245 24: 1 2 222943913618 -52422957749 25: 0 Infty -552338867577 129876777743 \___________________________________________________________________/ Rename r24,s24,t24 to GCD,S,T. Note GCD = r0 * S + r1 * T, i.e 1 = [129876777743]*[222943913618] + [552338867577]*[-52422957749].