> P:=PolynomialRing(Integers()); > f:=x^5-2*x^4-8*x^2-x-6; > g:=x^2+1; > g^3; x^6 + 3*x^4 + 3*x^2 + 1 > g^50; x^100 + 50*x^98 + 1225*x^96 + 19600*x^94 + 230300*x^92 + 2118760*x^90 + 15890700*x^88 + 99884400*x^86 + 536878650*x^84 + 2505433700*x^82 + 10272278170*x^80 + 37353738800*x^78 + 121399651100*x^76 + 354860518600*x^74 + 937845656300*x^72 + 2250829575120*x^70 + 4923689695575*x^68 + 9847379391150*x^66 + 18053528883775*x^64 + 30405943383200*x^62 + 47129212243960*x^60 + 67327446062800*x^58 + 88749815264600*x^56 + 108043253365600*x^54 + 121548660036300*x^52 + 126410606437752*x^50 + 121548660036300*x^48 + 108043253365600*x^46 + 88749815264600*x^44 + 67327446062800*x^42 + 47129212243960*x^40 + 30405943383200*x^38 + 18053528883775*x^36 + 9847379391150*x^34 + 4923689695575*x^32 + 2250829575120*x^30 + 937845656300*x^28 + 354860518600*x^26 + 121399651100*x^24 + 37353738800*x^22 + 10272278170*x^20 + 2505433700*x^18 + 536878650*x^16 + 99884400*x^14 + 15890700*x^12 + 2118760*x^10 + 230300*x^8 + 19600*x^6 + 1225*x^4 + 50*x^2 + 1 > g^6+f; x^12 + 6*x^10 + 15*x^8 + 20*x^6 + x^5 + 13*x^4 - 2*x^2 - x - 5 > Factorization(f); [ , , ] > g^10 mod f; 71428567*x^4 + 71428584*x^3 + 214285712*x^2 + 71428584*x + 142857145 > PRho:=function(n,f,s) function> a:=s; b:=s; i:=1; function> repeat function|repeat> a:=Evaluate(f,a) mod n; function|repeat> b:=Evaluate(f,b) mod n; function|repeat> b:=Evaluate(f,b) mod n; function|repeat> g:=GCD(b-a,n); function|repeat> "a[",i,"] is",a; function|repeat> "a[",2*i,"] is",b; function|repeat> "gcd(",b,"-",a,",n) is",g," function|repeat> "; function|repeat> i:=i+1; function|repeat> until g gt 1; function> "Factorization of",n,"found after",i,"iterations:"; function> return [g,n/g]; function> end function; > PRho(1001,x^2+1,1); a[ 1 ] is 2 a[ 2 ] is 5 gcd( 5 - 2 ,n) is 1 a[ 2 ] is 5 a[ 4 ] is 677 gcd( 677 - 5 ,n) is 7 Factorization of 1001 found after 3 iterations: [ 7, 143 ] > PRho(11111111111,x^2+1,1); a[ 1 ] is 2 a[ 2 ] is 5 gcd( 5 - 2 ,n) is 1 a[ 2 ] is 5 a[ 4 ] is 677 gcd( 677 - 5 ,n) is 1 a[ 3 ] is 26 a[ 6 ] is 10066388903 gcd( 10066388903 - 26 ,n) is 1 a[ 4 ] is 677 a[ 8 ] is 8489829266 gcd( 8489829266 - 677 ,n) is 1 a[ 5 ] is 458330 a[ 10 ] is 1568055199 gcd( 1568055199 - 458330 ,n) is 1 a[ 6 ] is 10066388903 a[ 12 ] is 1767633107 gcd( 1767633107 - 10066388903 ,n) is 1 a[ 7 ] is 3010420821 a[ 14 ] is 1624549405 gcd( 1624549405 - 3010420821 ,n) is 1 a[ 8 ] is 8489829266 a[ 16 ] is 4036111304 gcd( 4036111304 - 8489829266 ,n) is 1 .... lots of similar lines deleted .... a[ 162 ] is 5911324716 a[ 324 ] is 7723670751 gcd( 7723670751 - 5911324716 ,n) is 21649 Factorization of 11111111111 found after 163 iterations: [ 21649, 513239 ] > n:=Random(10^30); PRho(n,x^2+1,1); a[ 1 ] is 2 a[ 2 ] is 5 gcd( 5 - 2 ,n) is 1 a[ 2 ] is 5 a[ 4 ] is 677 gcd( 677 - 5 ,n) is 4 Factorization of 105267583022218829777235235916 found after 3 iterations: [ 4, 26316895755554707444308808979 ] > n:=Random(10^30); PRho(n,x^2+1,1); a[ 1 ] is 2 a[ 2 ] is 5 gcd( 5 - 2 ,n) is 1 a[ 2 ] is 5 a[ 4 ] is 677 gcd( 677 - 5 ,n) is 4 Factorization of 424121595531477875537217532172 found after 3 iterations: [ 4, 106030398882869468884304383043 ] > /* > This is boring -- when the number has a small prime factor like 2 PRho > finds that factor quickly. Let us restrict our attention to numbers > that do not have small prime factors. > */ > p:=RandomPrime(25); q:=RandomPrime(25); PRho(p*q,x^2+1,1); a[ 1 ] is 2 a[ 2 ] is 5 gcd( 5 - 2 ,n) is 1 a[ 2 ] is 5 a[ 4 ] is 677 gcd( 677 - 5 ,n) is 1 a[ 3 ] is 26 a[ 6 ] is 210066388901 gcd( 210066388901 - 26 ,n) is 1 a[ 4 ] is 677 a[ 8 ] is 1135265866335 gcd( 1135265866335 - 677 ,n) is 1 a[ 5 ] is 458330 a[ 10 ] is 665491108937 gcd( 665491108937 - 458330 ,n) is 1 a[ 6 ] is 210066388901 a[ 12 ] is 328637310901 gcd( 328637310901 - 210066388901 ,n) is 1 a[ 7 ] is 1741417655994 a[ 14 ] is 1667314112179 gcd( 1667314112179 - 1741417655994 ,n) is 1 a[ 8 ] is 1135265866335 a[ 16 ] is 824578995124 gcd( 824578995124 - 1135265866335 ,n) is 1 .... lots of similar lines deleted ..... a[ 392 ] is 1823378635225 a[ 784 ] is 1294746878299 gcd( 1294746878299 - 1823378635225 ,n) is 68053 Factorization of 1879670748517 found after 393 iterations: [ 68053, 27620689 ] > p:=RandomPrime(25); q:=RandomPrime(25); PRho(p*q,x^2+1,1); a[ 1 ] is 2 a[ 2 ] is 5 gcd( 5 - 2 ,n) is 1 a[ 2 ] is 5 a[ 4 ] is 677 gcd( 677 - 5 ,n) is 1 a[ 3 ] is 26 a[ 6 ] is 210066388901 gcd( 210066388901 - 26 ,n) is 1 .... lots of similar lines deleted ..... a[ 1580 ] is 22258912696451 a[ 3160 ] is 25501826574316 gcd( 25501826574316 - 22258912696451 ,n) is 1 a[ 1581 ] is 48756700382763 a[ 3162 ] is 120172051972019 gcd( 120172051972019 - 48756700382763 ,n) is 29403457 Factorization of 164397109767017 found after 1582 iterations: [ 29403457, 5591081 ] > p:=RandomPrime(25); q:=RandomPrime(25); PRho(p*q,x^2+1,1); a[ 1 ] is 2 a[ 2 ] is 5 gcd( 5 - 2 ,n) is 1 a[ 2 ] is 5 a[ 4 ] is 677 gcd( 677 - 5 ,n) is 1 .... a few similar lines deleted ..... a[ 316 ] is 281043617839 a[ 632 ] is 319521572045 gcd( 319521572045 - 281043617839 ,n) is 210499 Factorization of 328738603789 found after 317 iterations: [ 210499, 1561711 ] > /* > Now let's keep the same number and try x^2+3 in place of x^2+1 > */ > PRho(p*q,x^2+3,1); a[ 1 ] is 4 a[ 2 ] is 19 gcd( 19 - 4 ,n) is 1 a[ 2 ] is 19 a[ 4 ] is 132499 gcd( 132499 - 19 ,n) is 1 .... similar lines deleted ..... a[ 288 ] is 11111416131 a[ 576 ] is 136552822207 gcd( 136552822207 - 11111416131 ,n) is 210499 Factorization of 328738603789 found after 289 iterations: [ 210499, 1561711 ] > /* > So in this case x^2+3 actually worked a little better than x^2+1 > But it was just a fluke. You can't tell which will be better. > > Now I'm going to stick with x^2+3 and try a different starting value. > */ > PRho(p*q,x^2+3,5); a[ 1 ] is 28 a[ 2 ] is 787 gcd( 787 - 28 ,n) is 1 a[ 2 ] is 787 a[ 4 ] is 54883070598 gcd( 54883070598 - 787 ,n) is 1 .... similar lines deleted ..... a[ 67 ] is 189606602796 a[ 134 ] is 25785966545 gcd( 25785966545 - 189606602796 ,n) is 210499 Factorization of 328738603789 found after 68 iterations: [ 210499, 1561711 ] > /* > It really was a fluke that the starting value of 5 combined with the polynomial > x^2+3 found this factorization so quickly. It is no reason to use x^2+3 and 5 all > the time. > */ > load "tut8data.txt"; Loading "L:\win\Magma\MATH2068\tut8data.txt" > p:=RandomPrime(30); q:=RandomPrime(30); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 126047303490227507 found after 16718 iterations: [ 283119901, 445208207 ] Time: 0.063 > time BPRho(p*q,x^2+1,1); Factorization of 126047303490227507 found after 24743 iterations: [ 283119901, 445208207 ] Time: 0.047 > /* > In this case, BPRho was better. I have noticed the following phenomenon: > Suppose that BPRho takes b steps to complete, and suppose that > PRho takes p steps to complete. Let t be the largest power of 2 > less than b. Then p is a small integer multiple of b-t. > In the example above, b = 24743, t = 16384 and p = 16718 = 2*(b-t). > */ > p:=RandomPrime(30); q:=RandomPrime(30); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 28105684254940771 found after 6932 iterations: [ 36017053, 780343807 ] Time: 0.031 > time BPRho(p*q,x^2+1,1); Factorization of 28105684254940771 found after 7562 iterations: [ 36017053, 780343807 ] Time: 0.016 > /* > Again BPRho wins. This time b = 7562 gives t = 4096 and b - t = 3466. > And p = 6932 = 2*(b-t) again. > */ > p:=RandomPrime(30); q:=RandomPrime(30); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 378098277500193577 found after 20406 iterations: [ 358320383, 1055196119 ] Time: 0.078 > time BPRho(p*q,x^2+1,1); Factorization of 378098277500193577 found after 53174 iterations: [ 358320383, 1055196119 ] Time: 0.109 > /* > PRho wins. Here b = 53174, t = 32768, b - t = 20406 = p > */ > p:=RandomPrime(30); q:=RandomPrime(30); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 435203627406645079 found after 25305 iterations: [ 602353559, 722505281 ] Time: 0.094 > time BPRho(p*q,x^2+1,1); Factorization of 435203627406645079 found after 58073 iterations: [ 602353559, 722505281 ] Time: 0.125 > /* > PRho wins again. b = 58073, t = 32768, b - t = 25305 = p > */ > p:=RandomPrime(30); q:=RandomPrime(30); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 29849780369941523 found after 3092 iterations: [ 28873433, 1033814731 ] Time: 0.016 > time BPRho(p*q,x^2+1,1); Factorization of 29849780369941523 found after 4869 iterations: [ 28873433, 1033814731 ] Time: 0.016 > /* > Dead heat. b = 4869, t = 4096, b - t = 773, and p = 3092 = 4*(b-t) > */ > p:=RandomPrime(45); q:=RandomPrime(45); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 667395984352836396350387 found after 317980 iterations: [ 50148620891, 13308361675657 ] Time: 1.500 > time BPRho(p*q,x^2+1,1); Factorization of 667395984352836396350387 found after 603783 iterations: [ 50148620891, 13308361675657 ] Time: 1.500 > /* > Dead heat. b = 603783, t = 524288, b - t = 79495, and p = 317980 = 4*(b-t) > */ > p:=RandomPrime(45); q:=RandomPrime(45); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 73487444272326491974915021 found after 3080519 iterations: [ 3969572198687, 18512686152083 ] Time: 14.891 > time BPRho(p*q,x^2+1,1); Factorization of 73487444272326491974915021 found after 4403242 iterations: [ 18512686152083, 3969572198687 ] Time: 11.703 > /* > BPRho wins. b = 4403242, t = 4194304, b - t = 208938 and p is NOT > a multiple of b-t. What is happening? > In this case BPRho found the factor 18512686152083 whereas PRho found the > factor 3969572198687. In such cases we can't say anything. > */ > p:=RandomPrime(45); q:=RandomPrime(45); n:=p*q; > time PRho(p*q,x^2+1,1); Factorization of 965257454320781613701508179 found after 3306278 iterations: [ 33995469128041, 28393708899419 ] Time: 15.781 > time BPRho(p*q,x^2+1,1); Factorization of 965257454320781613701508179 found after 7500582 iterations: [ 33995469128041, 28393708899419 ] Time: 20.734 > /* > PRho wins. b = 7500582, t = 4194304, b - t = 3306278 = p. > Maybe it is the case that when an extremely large number of iterations > is required then BPRho is more likely to win. But I'm not convinced. > */ > /* > 10^2530 - 1 has to be divisible by 2531. So the repunit > with 2530 digits is divisible by 2531. > */ > rrr:=(10^2530 -1) div 9; > rrr; 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\ 11111111111111111111111111111111111111 > IsDivisibleBy(rrr,2531); true > /* > Let us check that rrr above really does have 2530 digits ... > */ > #IntegerToString(rrr); 2530 > /* > But is it the smallest? The order of 10 modulo 2531 must be a divisor of 2530, > and it could well be less than 2530. If k is the order of 10 mod 2531 then > the repunit (10^k-1)/9 will be divisible by 2531. > */ > Factorization(2530); [ <2, 1>, <5, 1>, <11, 1>, <23, 1> ] > IsDivisibleBy((10^5-1) div 9,2531); false > IsDivisibleBy((10^11-1) div 9,2531); false > IsDivisibleBy((10^23-1) div 9,2531); false > IsDivisibleBy((10^10-1) div 9,2531); false > IsDivisibleBy((10^22-1) div 9,2531); false > IsDivisibleBy((10^46-1) div 9,2531); true > /* > The order of 10 mod 2531 is 46. > */ > Modorder(10,2531); 46 > n:=73; > for i:=1 to 72 do for> i,"has order",Modorder(i,73),"modulo 73"; for> end for; 1 has order 1 modulo 73 2 has order 9 modulo 73 3 has order 12 modulo 73 4 has order 9 modulo 73 5 has order 72 modulo 73 6 has order 36 modulo 73 7 has order 24 modulo 73 8 has order 3 modulo 73 9 has order 6 modulo 73 10 has order 8 modulo 73 11 has order 72 modulo 73 12 has order 36 modulo 73 13 has order 72 modulo 73 14 has order 72 modulo 73 15 has order 72 modulo 73 16 has order 9 modulo 73 17 has order 24 modulo 73 18 has order 18 modulo 73 19 has order 36 modulo 73 20 has order 72 modulo 73 21 has order 24 modulo 73 22 has order 8 modulo 73 23 has order 36 modulo 73 24 has order 12 modulo 73 25 has order 36 modulo 73 26 has order 72 modulo 73 27 has order 4 modulo 73 28 has order 72 modulo 73 29 has order 72 modulo 73 30 has order 24 modulo 73 31 has order 72 modulo 73 32 has order 9 modulo 73 33 has order 72 modulo 73 34 has order 72 modulo 73 35 has order 36 modulo 73 36 has order 18 modulo 73 37 has order 9 modulo 73 38 has order 36 modulo 73 39 has order 72 modulo 73 40 has order 72 modulo 73 41 has order 18 modulo 73 42 has order 72 modulo 73 43 has order 24 modulo 73 44 has order 72 modulo 73 45 has order 72 modulo 73 46 has order 4 modulo 73 47 has order 72 modulo 73 48 has order 36 modulo 73 49 has order 12 modulo 73 50 has order 36 modulo 73 51 has order 8 modulo 73 52 has order 24 modulo 73 53 has order 72 modulo 73 54 has order 36 modulo 73 55 has order 9 modulo 73 56 has order 24 modulo 73 57 has order 18 modulo 73 58 has order 72 modulo 73 59 has order 72 modulo 73 60 has order 72 modulo 73 61 has order 36 modulo 73 62 has order 72 modulo 73 63 has order 8 modulo 73 64 has order 3 modulo 73 65 has order 6 modulo 73 66 has order 24 modulo 73 67 has order 36 modulo 73 68 has order 72 modulo 73 69 has order 18 modulo 73 70 has order 12 modulo 73 71 has order 18 modulo 73 72 has order 2 modulo 73 > /* > I see that > 1 occurs 1 time, > 2 occurs 1 time, > 3 occurs 2 times, > 4 occurs 2 times, > 6 occurs 2 times, > 8 occurs 4 times, > 9 occurs 6 times, > 12 occurs 4 times, > 18 occurs 6 times, > 24 occurs 8 times, > 36 occurs 12 times, > 72 occurs 24 times. > > It is easy to check, using the formula for the Euler phi function, > that the number of times d occurs is EulerPhi(d), in every case. > For example, EulerPhi(18)=18*(1/2)*(2/3)=6, > EulerPhi(24)=24*(1/2)*(2/3)=8 > EulerPhi(8)=8*(1/2)=4 > and so on. > > I suppose one could also get magma to tell one the values > of EulerPhi(d), for all d in the set of divisors of 72. > */ > for d in { i : i in [1..72] | IsDivisibleBy(72,i) } do for> "phi(",d,") is",EulerPhi(d); for> end for; phi( 1 ) is 1 phi( 18 ) is 6 phi( 2 ) is 1 phi( 36 ) is 12 phi( 3 ) is 2 phi( 4 ) is 2 phi( 72 ) is 24 phi( 6 ) is 2 phi( 24 ) is 8 phi( 8 ) is 4 phi( 9 ) is 6 phi( 12 ) is 4 > n:=29; > for i:=1 to 28 do for> i,"has order",Modorder(i,29),"modulo 29"; for> end for; 1 has order 1 modulo 29 2 has order 28 modulo 29 3 has order 28 modulo 29 4 has order 14 modulo 29 5 has order 14 modulo 29 6 has order 14 modulo 29 7 has order 7 modulo 29 8 has order 28 modulo 29 9 has order 14 modulo 29 10 has order 28 modulo 29 11 has order 28 modulo 29 12 has order 4 modulo 29 13 has order 14 modulo 29 14 has order 28 modulo 29 15 has order 28 modulo 29 16 has order 7 modulo 29 17 has order 4 modulo 29 18 has order 28 modulo 29 19 has order 28 modulo 29 20 has order 7 modulo 29 21 has order 28 modulo 29 22 has order 14 modulo 29 23 has order 7 modulo 29 24 has order 7 modulo 29 25 has order 7 modulo 29 26 has order 28 modulo 29 27 has order 28 modulo 29 28 has order 2 modulo 29 > /* > 1 occurs EulerPhi(1) = 1 time, > 2 occurs EulerPhi(2) = 1 time, > 4 occurs EulerPhi(4) = 2 time2, > 7 occurs EulerPhi(7) = 6 times, > 14 occurs EulerPhi(14) = 6 times, > 28 occurs EulerPhi(28) = 12 times. > These are all correct. e.g. EulerPhi(28)=28*(1/2)*(6/7)=12. > */ > for i:=1 to 12 do for> i,"has order",Modorder(i,13),"modulo 13"; for> end for; 1 has order 1 modulo 13 2 has order 12 modulo 13 3 has order 3 modulo 13 4 has order 6 modulo 13 5 has order 4 modulo 13 6 has order 12 modulo 13 7 has order 12 modulo 13 8 has order 4 modulo 13 9 has order 3 modulo 13 10 has order 6 modulo 13 11 has order 12 modulo 13 12 has order 2 modulo 13 > /* > 1 occurs 1 time -- correct, > 2 occurs 1 time -- correct, > 3 occurs 2 times -- correct, > 4 occurs 2 times -- correct, > 6 occurs 2 times -- correct, > 12 occurs 4 times -- correct. > */ > for i:=1 to 72 do for> i,Log(r,F!i); for> end for; 1 0 2 8 3 6 4 16 5 1 6 14 7 33 8 24 9 12 10 9 11 55 12 22 13 59 14 41 15 7 16 32 17 21 18 20 19 62 20 17 21 39 22 63 23 46 24 30 25 2 26 67 27 18 28 49 29 35 30 15 31 11 32 40 33 61 34 29 35 34 36 28 37 64 38 70 39 65 40 25 41 4 42 47 43 51 44 71 45 13 46 54 47 31 48 38 49 66 50 10 51 27 52 3 53 53 54 26 55 56 56 57 57 68 58 43 59 5 60 23 61 58 62 19 63 45 64 48 65 60 66 69 67 50 68 37 69 52 70 42 71 44 72 36 > /* > So, for example, the log of 72 is 36, the log of 71 is 44, the log of 70 is 42, > and so on. > */ > Modexp(5,36,73); 72 > Modexp(5,44,73); 71 > Modexp(5,42,73); 70 > Modexp(5,52,73); 69 > Modexp(5,37,73); 68 > /* > For example, 5^37 reduced mod 73 equals 68. So we say that the discrete > logarithm to the base 5 (relative to 73) of 68 equals 37. > */ > F109:=FiniteField(109); > PrimitiveElement(F109); 6 > for a in F109 do for> if a ne 0 then for|if> "The discrete log of",a,"modulo 109 is",Log(a); for|if> end if; for> end for; The discrete log of 1 modulo 109 is 0 The discrete log of 2 modulo 109 is 57 The discrete log of 3 modulo 109 is 52 The discrete log of 4 modulo 109 is 6 The discrete log of 5 modulo 109 is 76 The discrete log of 6 modulo 109 is 1 The discrete log of 7 modulo 109 is 40 The discrete log of 8 modulo 109 is 63 The discrete log of 9 modulo 109 is 104 The discrete log of 10 modulo 109 is 25 The discrete log of 11 modulo 109 is 83 The discrete log of 12 modulo 109 is 58 The discrete log of 13 modulo 109 is 67 The discrete log of 14 modulo 109 is 97 The discrete log of 15 modulo 109 is 20 The discrete log of 16 modulo 109 is 12 The discrete log of 17 modulo 109 is 93 The discrete log of 18 modulo 109 is 53 The discrete log of 19 modulo 109 is 75 The discrete log of 20 modulo 109 is 82 The discrete log of 21 modulo 109 is 92 The discrete log of 22 modulo 109 is 32 The discrete log of 23 modulo 109 is 33 The discrete log of 24 modulo 109 is 7 The discrete log of 25 modulo 109 is 44 The discrete log of 26 modulo 109 is 16 The discrete log of 27 modulo 109 is 48 The discrete log of 28 modulo 109 is 46 The discrete log of 29 modulo 109 is 34 The discrete log of 30 modulo 109 is 77 The discrete log of 31 modulo 109 is 14 The discrete log of 32 modulo 109 is 69 The discrete log of 33 modulo 109 is 27 The discrete log of 34 modulo 109 is 42 The discrete log of 35 modulo 109 is 8 The discrete log of 36 modulo 109 is 2 The discrete log of 37 modulo 109 is 5 The discrete log of 38 modulo 109 is 24 The discrete log of 39 modulo 109 is 11 The discrete log of 40 modulo 109 is 31 The discrete log of 41 modulo 109 is 45 The discrete log of 42 modulo 109 is 41 The discrete log of 43 modulo 109 is 30 The discrete log of 44 modulo 109 is 89 The discrete log of 45 modulo 109 is 72 The discrete log of 46 modulo 109 is 90 The discrete log of 47 modulo 109 is 17 The discrete log of 48 modulo 109 is 64 The discrete log of 49 modulo 109 is 80 The discrete log of 50 modulo 109 is 101 The discrete log of 51 modulo 109 is 37 The discrete log of 52 modulo 109 is 73 The discrete log of 53 modulo 109 is 49 The discrete log of 54 modulo 109 is 105 The discrete log of 55 modulo 109 is 51 The discrete log of 56 modulo 109 is 103 The discrete log of 57 modulo 109 is 19 The discrete log of 58 modulo 109 is 91 The discrete log of 59 modulo 109 is 47 The discrete log of 60 modulo 109 is 26 The discrete log of 61 modulo 109 is 10 The discrete log of 62 modulo 109 is 71 The discrete log of 63 modulo 109 is 36 The discrete log of 64 modulo 109 is 18 The discrete log of 65 modulo 109 is 35 The discrete log of 66 modulo 109 is 84 The discrete log of 67 modulo 109 is 95 The discrete log of 68 modulo 109 is 99 The discrete log of 69 modulo 109 is 85 The discrete log of 70 modulo 109 is 65 The discrete log of 71 modulo 109 is 78 The discrete log of 72 modulo 109 is 59 The discrete log of 73 modulo 109 is 56 The discrete log of 74 modulo 109 is 62 The discrete log of 75 modulo 109 is 96 The discrete log of 76 modulo 109 is 81 The discrete log of 77 modulo 109 is 15 The discrete log of 78 modulo 109 is 68 The discrete log of 79 modulo 109 is 23 The discrete log of 80 modulo 109 is 88 The discrete log of 81 modulo 109 is 100 The discrete log of 82 modulo 109 is 102 The discrete log of 83 modulo 109 is 70 The discrete log of 84 modulo 109 is 98 The discrete log of 85 modulo 109 is 61 The discrete log of 86 modulo 109 is 87 The discrete log of 87 modulo 109 is 86 The discrete log of 88 modulo 109 is 38 The discrete log of 89 modulo 109 is 28 The discrete log of 90 modulo 109 is 21 The discrete log of 91 modulo 109 is 107 The discrete log of 92 modulo 109 is 39 The discrete log of 93 modulo 109 is 66 The discrete log of 94 modulo 109 is 74 The discrete log of 95 modulo 109 is 43 The discrete log of 96 modulo 109 is 13 The discrete log of 97 modulo 109 is 4 The discrete log of 98 modulo 109 is 29 The discrete log of 99 modulo 109 is 79 The discrete log of 100 modulo 109 is 50 The discrete log of 101 modulo 109 is 9 The discrete log of 102 modulo 109 is 94 The discrete log of 103 modulo 109 is 55 The discrete log of 104 modulo 109 is 22 The discrete log of 105 modulo 109 is 60 The discrete log of 106 modulo 109 is 106 The discrete log of 107 modulo 109 is 3 The discrete log of 108 modulo 109 is 54 > /* > The primitive root used was 6. (It was printed out above.) > So now let us check a few of the answers: > */ > Modexp(6,22,109); 104 > Modexp(6,13,109); 96 > Modexp(6,28,109); 89 > UnsetLogFile();