DISCRETE LOGARITHM WITH INDEX CALCULUS p = 1000003 primitive root g = 2 p - 1 = 2 * 3 * 166667 Q = 1000 (close to sqrt(p)) a1 a2 at (Q + a)*(Q + b) - p = q1 * q2 * ... * qt Primes qi < B = 60 -15 <= a <= b <= 15 a b Q + a Q + b (Q + a)*(Q + b) - p -14 -14 2 * 17 * 29 2 * 17 * 29 - 3 * 13 * 23 * 31 -14 3 2 * 17 * 29 17 * 59 - 5 * 47^2 -13 15 3 * 7 * 47 5 * 7 * 29 2 * 17 * 53 -12 12 2^2 * 13 * 19 2^2 * 11 * 23 - 3 * 7^2 -12 14 2^2 * 13 * 19 2 * 3 * 13^2 31 * 59 -11 3 23 * 43 17 * 59 - 2^2 * 7^2 * 41 -11 7 23 * 43 19 * 53 - 2^4 * 3 * 5 * 17 -10 14 2 * 3^2 * 5 * 11 2 * 3 * 13^2 7 * 19 * 29 -8 -8 2^5 * 31 2^5 * 31 - 3^2 * 7 * 11 * 23 -8 1 2^5 * 31 7 * 11 * 13 - 3^2 * 19 * 41 -8 15 2^5 * 31 5 * 7 * 29 13 * 23^2 -1 -1 3^3 * 37 3^3 * 37 - 2 * 7 * 11 * 13 -1 0 3^3 * 37 2^3 * 5*3 - 17 * 59 -1 1 3^3 * 37 7 * 11 * 13 - 2 -1 12 3^3 * 37 2^2 * 11 * 23 5 * 13^3 0 0 2^3 * 5*3 2^3 * 5*3 - 3 0 3 2^3 * 5*3 17 * 59 3^4 * 37 0 12 2^3 * 5*3 2^2 * 11 * 23 3^2 * 31 * 43 1 1 7 * 11 * 13 7 * 11 * 13 2 * 3^3 * 37 1 3 7 * 11 * 13 17 * 59 2^5 * 5^3 1 7 7 * 11 * 13 19 * 53 2^2 * 3 * 23 * 29 3 3 17 * 59 17 * 59 2 * 3 * 7 * 11 * 13 Matrix 18 by 22 (overdetermined) [1,2,-1,0,0,0,-1,2,0,-1,2,-1,0,0,0,0,0,0;\ 1,1,0,-1,0,0,0,2,0,0,1,0,0,0,0,-2,0,1;\ 0,-1,1,1,2,0,0,-1,0,0,1,0,0,0,0,1,-1,0;\ 1,4,-1,0,-2,1,1,0,1,1,0,0,0,0,0,0,0,0;\ 0,3,1,0,0,0,3,0,1,0,0,-1,0,0,0,0,0,-1;\ 1,-2,0,0,-2,0,0,1,0,1,0,0,0,-1,1,0,0,1;\ 1,-4,-1,-1,0,0,0,-1,1,1,0,0,0,0,1,0,1,0;\ 0,2,3,1,-1,1,2,0,-1,0,-1,0,0,0,0,0,0,0;\ 1,10,-2,0,-1,-1,0,0,0,-1,0,2,0,0,0,0,0,0;\ 1,5,-2,0,1,1,1,0,-1,0,0,1,0,-1,0,0,0,0;\ 0,5,0,1,1,0,-1,0,0,-2,1,1,0,0,0,0,0,0;\ 1,-1,6,0,-1,-1,-1,0,0,0,0,0,2,0,0,0,0,0;\ 1,3,3,3,0,0,0,-1,0,0,0,0,1,0,0,0,0,-1;\ 1,-2,3,0,1,1,1,0,0,0,0,0,1,0,0,0,0,0;\ 0,2,3,-1,0,1,-3,0,0,1,0,0,1,0,0,0,0,0;\ 1,6,-1,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0;\ 0,3,-4,3,0,0,0,1,0,0,0,0,-1,0,0,0,0,1;\ 0,5,-2,3,0,1,0,0,0,1,0,-1,0,0,-1,0,0,0;\ 0,-1,-3,0,2,2,2,0,0,0,0,0,-1,0,0,0,0,0;\ 0,-5,0,-3,1,1,1,1,0,0,0,0,0,0,0,0,0,1;\ 0,-2,-1,0,1,1,1,0,1,-1,-1,0,0,0,0,0,1,0;\ 0,-1,-1,0,-1,-1,-1,2,0,0,0,0,0,0,0,0,0,2] Linear algebra modulo 166667: 1-dimensional kernel: [0] [116262] [26782] [165980] [47338] [67440] [1484] [129652] [166614] [87540] [1972] [46632] [35916] [24025] [134032] [22446] [65942] [1] g = 2 is primitive root: normalize: discrete logarithms modulo 166667 are: log(-1) = [0] log( 2) = [1] log( 3) = [87610] log( 5) = [125712] log( 7) = [56852] log(11) = [98253] log(13) = [11563] log(17) = [88385] log(19) = [29349] log(23) = [62145] log(29) = [90388] log(31) = [29563] log(37) = [70505] log(41) = [158334] log(43) = [166089] log(47) = [48434] log(53) = [44128] log(59) = [122088] Modulo 3: 2-dimensional kernel: [0 0] [1 0] [0 0] [2 1] [2 2] [2 1] [1 0] [0 0] [2 0] [1 0] [1 0] [2 0] [0 0] [1 0] [0 1] [0 1] [0 0] [0 0] Since g = 2 is primitive root, second coordinate must be 1. Get three possibilities. [0] [0] [0] [1] [1] [1] [0] [0] [0] [2] [0] [1] [2] [1] [0] [2] [0] [1] [1] [1] [1] [0] [0] [0] [2] [2] [2] [1] [1] [1] [1] [1] [1] [2] [2] [2] [0] [0] [0] [1] [1] [1] [0] [1] [2] [0] [1] [2] [0] [0] [0] [0] [0] [0] We can distinguish between them by looking at log(5) = 125712 mod 166667. for(k=0,5,print(k,",", mod(2,1000003)^(125712+k*166667))) k = 0, 502504 mod 1000003 k = 1, 5 mod 1000003 k = 2, 497504 mod 1000003 k = 3, 497499 mod 1000003 k = 4, 999998 mod 1000003 k = 5, 502499 mod 1000003 ===> log(5) = 125712 + 166667 = 292379 which is 2 mod 3. Therefore the first column is the correct one. Chinese Remainder Theorem: 0 1 254277 292379 56852 264920 11563 421719 196016 395479 90388 362897 403839 491668 166089 381768 210795 122088 Modulo 2 find 2-dimensional kernel: [0 1] [1 1] [0 1] [0 1] [0 1] [0 1] [1 0] [0 1] [1 0] [0 1] [1 0] [1 1] [1 0] [0 1] [0 1] [1 0] [1 0] [0 1] We know that log(-1) = (p-1)/2 = 500001 is ODD. In addition g = 2 is primitive root, so log(2) = 1. Therefore, must have the 2nd column. Chinese .... log(-1) = 500001 log( 2) = 1 log( 3) = 254277 log( 5) = 292379 log( 7) = 556853 log(11) = 764921 log(13) = 511564 log(17) = 421719 log(19) = 196016 log(23) = 395479 log(29) = 90388 log(31) = 362897 log(37) = 903840 log(41) = 991669 log(43) = 166089 log(47) = 381768 log(53) = 710796 log(59) = 622089 ======================= Now compute log(61). Try to write 2^k * 61 as x / y modulo 61, with k small and x, y B - smooth Bezout: For k = 5: (2^k * 61 = 1952) -512 * 1952 + 1 * 1000003 = 579 1537 * 1952 + -3 * 1000003 = 215 <------ B - smooth!! -3586 * 1952 + 7 * 1000003 = 149 5123 * 1952 + -10 * 1000003 = 66 -13832 * 1952 + 27 * 1000003 = 17 46619 * 1952 + -91 * 1000003 = 15 -60451 * 1952 + 118 * 1000003 = 2 469776 * 1952 + -917 * 1000003 = 1 -1000003 * 1952 + 1952 * 1000003 = 0 1952 = 215 / 1537 modulo 1000003 2^5 * 61 = 5 * 43 / (29 * 53) modulo 1000003 log(61) = - 5 +log(5) + log(43) - log(29) - log(53) = 657281 modulo 1000003 Check: mod(2,1000003)^657281 = mod(61, 1000003) YES!!!