Counting Miller-Rabin Liars\302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.edurestart:In class we looked at the effectiveness of the Miller-Rabin test on a Carmichael number. This worksheet is intended to be a clean presentation of that material.
<Text-field style="Heading 1" layout="Heading 1">Counting Liars</Text-field>We start with using Maple to test if the composite number 561=3x11x17 is shown to be composite with various candidates and the primality tests we have been studying. We first see that with 1<a<560, the Fermat test fails whenever a is relatively prime to 560.n := 561:sequence1 := [seq([i, igcd(i,561),Power(i,560) mod 561], i=2..559)];Thus the 320 invertible elements of Z/561 are all Fermat liars.To use the Miller-Rabin test for n=561, we first note that 560=35*2^4. To test if n=561 is composite with our candidate a chosen so that 1<a<560, we compute a^35, a^70, a^140, a^280, and a^560. The test fails if a^35 =1 mod 561, or if any power before a^560 is -1 mod 561. Otherwise the test shows 561 is composite. We want to identify the Miller-Rabin liars.liarFinder := proc(n)
local numLiars, minus1, k, cand, test1, testDone,
testExponent, liarList:
liarList := []:
numLiars := 0:
minus1 := n-1:
k := minus1:
while ((k mod 2) = 0) do
k := k/2 end do: # Find k, the odd factor of n-1
for cand from 1 to minus1 do
test1 := Power(cand, k) mod n:
if (test1 = 1) then # Test if a^k = 1, if so, liar
numLiars := numLiars +1:
print(cand," is a Miller-Rabin liar for ",n," a^",k," =1"):
liarList := [op(liarList), cand]:
else
testDone := 0:
testExponent := k:
while (testExponent < minus1) do
test1 := Power(cand, testExponent) mod n:
if (test1 = minus1) then #a^testExponent = -1, liar
numLiars := numLiars +1:
print(cand," is a Miller-Rabin liar for ",
n, " a^", testExponent, "=-1"):
liarList := [op(liarList), cand]:
testExponent = minus1:
elif (test1 = 1) then #1 without -1 first, composite
testExponent = minus1:
end if:
testExponent := testExponent*2:
end do:
end if:
end do:
print("for n = ", n, " there are ",numLiars,
" liars under Miller-Rabin"):
liarList:
end proc:(For doing examples efficiently later on, we want also want a procedure that simply prints out the liars.liarFinder2 := proc(n)
local numLiars, minus1, k, cand, test1, testDone,
testExponent, liarList:
liarList := []:
numLiars := 0:
minus1 := n-1:
k := minus1:
while ((k mod 2) = 0) do
k := k/2 end do: # Find k, the odd factor of n-1
for cand from 1 to minus1 do
test1 := Power(cand, k) mod n:
if (test1 = 1) then # Test if a^k = 1, if so, liar
numLiars := numLiars +1:
liarList := [op(liarList), cand]:
else
testDone := 0:
testExponent := k:
while (testExponent < minus1) do
test1 := Power(cand, testExponent) mod n:
if (test1 = minus1) then #a^testExponent = -1, liar
numLiars := numLiars +1:
liarList := [op(liarList), cand]:
testExponent = minus1:
elif (test1 = 1) then #1 without -1 first, composite
testExponent = minus1:
end if:
testExponent := testExponent*2:
end do:
end if:
end do:
liarList:
end proc:liarList := liarFinder(561);liarList := liarFinder2(561);Thus we have 10 Miller-Rabin liars, and this includes the trivial liars 1 and -1.
<Text-field style="Heading 1" layout="Heading 1">Converting the multiplicative group to the additive (log) group with discrete logs</Text-field>Now we would like to see if some group theory helps us see why we have 10 liars rather than 560/4=140 liars.We note that the Miller-Rabin liars are a subset of Fermat liars, and the number of Fermat liars is phi(561).numtheory[phi](561);
ifactor(561);We have noted several times in class that questions become easier if we look at prime components. In this case, Z/561 is the direct product of Z/3, Z/11, and Z/17. Apply this transformation to the list.makeComps := x -> [x mod 3, x mod 11, x mod 17]:liarList2 := map(makeComps, liarList);Notice that we either have (1,{1,4,3,9,5},1) or (2,{6,2,8,7,10},16). The neatness of the solution should indicate that there is a structural reason for the size of the solution.Sidebar on discreet logs and conversion to the multiplicative group.We have noted in class that the invertible elements of Z/p form a cyclic group. This means there is some a<p such that all the numbers form 1 to p-1 can be expressed as a power of a mod p. It is then useful to take discrete logs base a mod p, converting a^b to b. As with more traditional logs, this converts multiplication to addition and exponentiation to multiplication. I want to do this conversion, taking the multiplicative group of Z/3 x Z/11 x Z/17 to the additive group of Z/2 x Z/10 x Z/16Let's work through the conversion with Z/11, the middle factor.I would like to find a generator of the multiplicative group. Maple does this with the numtheory[primroot] command.g2 := numtheory[primroot](11);
numtheory[order](g2,11);I can use the power command to go from a to g2^a. The numtheory[mlog] command goes form g2^a to a.powers := seq([i,Power(g2,i) mod 11], i = 0..10);
mlogs := seq([i,numtheory[mlog](i,g2,11)], i=1..10);Under this conversion from (Z/11,x) to (Z/10,+), we see{1,4,3,9, 5} respectively mapped to {0,2,8,6,4}. Similarly, {6,2,8,7,10} respectively maps to {9,1,3,7,5}. To treat the three components the same, I would like to find generators for the multiplicative groups of Z/2 and Z/17.
I also need to express 16 as a power of the third generator. Since -1 is the square root of 1, I expect the log of -1 to be half of p-1.g1 := numtheory[primroot](3);
g3 := numtheory[primroot](17);
numtheory[mlog](16,g3,17);We can put this together in a function that converts the triples in Z/3 x Z/11 x Z/17 to the triples in the log group. As we convert (2^a, 2^b, 3^c) in Z/3 x Z/11 x Z/17 to (a, b, c) in Z/2 x Z/10 x Z/16, the operation goes form multiplication to addition, while raising to a power goes to multiplication. It is useful to note the logs of 1 and -1.makeMultComps := x -> [numtheory[mlog](x[1],g1,3),
numtheory[mlog](x[2],g2,11), numtheory[mlog](x[3],g3,17)]:liarList3 := map(makeMultComps, liarList2);makeMultComps(makeComps(1));
makeMultComps(makeComps(560));This list becomes all the elements of the form (0, even, 0) + log(either 1 or -1). This is such a nice form that there must be a way to look at the structure and see the answer clearly.
<Text-field style="Heading 1" layout="Heading 1">Recasting Miller-Rabin in the log group</Text-field>Recall the Miller-Rabin test. - factor (n-1) as k*2^m for some odd k. We know a is a witness that n is composite if either:(i) a^(n-1) \342\211\240 1 mod n; or(ii) for some i, we have a^(k*2^i) =1 mod n and a^(k*2^(i-1)) is not 1 or -1 mod n.Equivalently, for a composite number n, a candidate a is a Miller-Rabin liar if either:(i) a^(k) = 1 mod n; or(ii) for some i<m, we have a^(k*2^i) =-1.Using discret logs, we convert to an equivalent problem for the group of logs under addition.The test becomes:We know a is a Miller-Rabin liar if either:(i) log(a) times k is zero in the log group; or(ii) for some i<m we have log(a)*(k*2^i) is the log of -1.kPower := x -> [x[1]*35 mod 2, x[2]*35 mod 10, x[3]*35 mod 16]:liarList4 := map(kPower, liarList3);In the case of n=561, the second condition simplifies. The first component of the log group is in Z/2. A single multiplication by 2 zeroes this out. There are no solutions to (a,b,c)*2^i = (1,5,8) in Z/2 x Z/10 x Z/16 when i > 0.Thus the discrete log version of Miller-Rabin becomes:We know a is a witness that n is composite if either(i) log(a)*k = (0,0,0) in the log group; or(ii) log(a)*(k) is (1,5,8), the log of -1 in the log group.
<Text-field style="Heading 1" layout="Heading 1">Applying the method to a second case</Text-field>The test that this method works is obviously to use it on a second Carmichael number and use it to predict the liars. Consider the case of n = 1105n := 1105;
phin := numtheory[phi](n);
`n factors as` = ifactor(n);
`n-1 factors as` = ifactor(n-1);
`factoring phi(n) ` = ifactor(phin);
`factoring of the phi(p[i])` =
map(x -> ifactor(x-1),numtheory[factorset](n));We notice that the log group of Z/5 x Z/13 x Z/17 under multiplication is Z/4 x Z/12 x Z/16 under addition. In the multiplicative group -1 is the square root of 1. This corresponds to 1/2 in the additive log group.Thus the log of -1 is (2, 6, 8). The odd factor of n-1, k is 3*23 =69.Raising to the 69th power in the multiplicative group corresponds to multiplying by 69 in the log group.Since 23 is relatively prime to 4, 12, and 16, multiplying by 23 in the log group simply scrambles the elements without sending any to 0. Thus we are simply interested in multiplying by 3.The elements of the log group killed with multiplication by 3 have the form (0, {0, 4, 8}, 0). In the log group, the solutions to 2*(a, b, c) = (2, 6, 8) are ({1,3}, {3,9}, {4,8}).In the log group, there are no solutions to 2^i*(a, b, c) = (2, 6, 8) for i > 1.There should be 30 liars, 3 with log of 0, 3 with log of -1, and 8*3 with log of one half the log of -1.The logs of the liars should be:(0, {0,4,8}, 0) + (0, 0, 0) or (0, {0,4,8}, 0) + (2, 6, 8) or (0, {0,4,8}, 0) + ({1,3}, {3,9}, {4,12}).l1 := [[0,0,0], [0,4,0], [0,8,0]]:
l2 := [[2,6,8], [2,10,8], [2,2,8]]:
l3 := [[1,3,4], [3,3,4], [1,9,4], [3,9,4], [1,3,12], [3,3,12], [1,9,12], [3,9,12], [1,7,4], [3,7,4], [1,1,4], [3,1,4], [1,7,12], [3,7,12], [1,1,12], [3,1,12], [1,11,4], [3,11,4], [1,5,4], [3,5,4], [1,11,12], [3,11,12], [1,5,12], [3,5,12]]: We want to produce generators so that we can covert the logs back to the multiplicative group.p := [5,13,17];
g := map(numtheory[primroot],p);backToMult := (logT, p, g) -> [Power(g[1],logT[1]) mod p[1],
Power(g[2],logT[2]) mod p[2], Power(g[3],logT[3]) mod p[3]]: l1mult := map(backToMult, l1,p,g);
l2mult := map(backToMult, l2,p,g);
l3mult := map(backToMult, l3,p,g);We then use the chrem command to apply the Chinese remainder theorem to convert these back to integers.l1int := map(chrem, l1mult, p);
l2int := map(chrem, l2mult, p);
l3int := map(chrem, l3mult, p);
We compare this with the list of liars found more directly and see that it is the same.liarFinder2(1105);
<Text-field style="Heading 1" layout="Heading 1">Exercises</Text-field>1) Find the 54 Miller-Rabin liars when n=1729, and explain why we only expect that many.2) Explain why the Carmichael number 321197185 has no Miller-Rabin liars other than 1 and -1.Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.