The purpose of this assignment is to get familiar with generating prime numbers, the multiple precision math library (called BIGNUM) of openssl, and modular arithematics with BIGNUM.
To use openssl on nunki.usc.edu, please see the additional notes on openssl.
Compiling:
make hw7an executable named hw7 is created.
Commandline Syntax & Program
Output
<TR><TD COLSPAN=3 ALIGN=LEFT BGCOLOR="#000000" WIDTH=100%>
<FONT COLOR="#ffffff"><A NAME="rndsearch">
<B>Random-Search</B></A></FONT>
</TD>
</TR>
<TR><TD COLSPAN=3 ALIGN=LEFT>
For this assignment,
you are required to implement the Random-Search algorithm outlined here.
It's slightly different from the lecture slides to make grading
more manageable.
Random-Search(k,maxitr): 1) n = RndOddNum(k) 2) if (TrialDivision(n) == "fail") goto step (1) 3) if (Miller-Rabin(n,maxitr) == "prime") return(n) goto step (1)Letx = ceil(k/8). RndOddNum(k) first reads x bytes from rndfile and converts the data into a BIGNUM representation using BN_bin2bn() (first byte read is the most significant byte in BIGNUM). RndOddNum(k) then sets both bit zero (the least significant bit) and bit k-1 to one, sets all bits from k and above to zero in the BIGNUM, and returns the resulting BIGNUM. Please make sure that exactly x bytes of rndfile are consumed. If k=5, and the byte you read is 0xca (which is 1100 1010 in binary), RndOddNum(k) should return a 5-bit integer 0x1b (which is 0001 1011 in binary and 27 in decimal).
TrialDivision(n) tries all prime numbers that are less than or equal to sqrt(n) in primesfile in increasing order to see if it is a divisor of n. It returns "fail" if a prime divisor is found. Otherwise, it returns "pass". (It should return "error" if there are not enough prime numbers in primesfile.)
Finally, Miller-Rabin(n,maxitr) is specified above.
<TR><TD COLSPAN=3 ALIGN=LEFT BGCOLOR="#000000" WIDTH=100%>
<FONT COLOR="#ffffff"><A NAME="maurer">
<B>Maurer's Algorithm</B></A></FONT>
</TD>
</TR>
<TR><TD COLSPAN=3 ALIGN=LEFT>
For this assignment,
you are required to implement Maurer's Algorithm outlined here.
It's slightly different from the lecture slides to make grading
more manageable.
Maurer(k):
1) if (k <= 20) do forever {
1.1) n = RndOddNum(k)
1.2) if (TrialDivision(n) == "pass") return n
}
2) c = 0.1, m = 20
3) B = c * k^2 (not used)
4) (generate a fraction r, the size of q relative to n)
4.1) if (k <= 2m) r = 0.5
4.2) if (k > 2m) do forever {
4.2.1) r = RndByte() / 255.0
4.2.2) r = 0.5 + r / 2.0
4.2.3) if (k*(1-r) > m) break;
}
5) (recursion) q = Maurer(floor(r*k)+1)
6) num_bits_in_q = BN_num_bits(q)
I = floor(2^(k-2) / q)
7) do forever {
7.1) R = RndOddNum(k+1-num_bits_in_q)
R = (R mod I) + I + 1
n = 2Rq+1
7.2) if (TrialDivision(n) != "fail") {
num_bits_in_n = BN_num_bits(n)
7.2.1) do {
a = RndOddNum(num_bits_in_n)
} while (a <= 1 or a >= n-1))
7.2.2) b = a^{n-1} mod n
if (b == 1) {
b = a^{2R} mod n
d = gcd(b-1,n)
if (d == 1) return(n)
}
}
}RndOddNum() and
TrialDivision() are defined above.
RndByte() simply reads exactly one byte from rndfile and returns the data as an octet (or unsigned char).
<TR><TD COLSPAN=3 ALIGN=LEFT BGCOLOR="#000000" WIDTH=100%>
<FONT COLOR="#ffffff"><A
NAME="testdata"><B>Test Data & Sample Output</B></A>
</FONT>
</TD>
</TR>
<TR><TD COLSPAN=3 ALIGN=LEFT>
primes
Running the "hw7 primes -n=7" command should generate 4 prime numbers, i.e., 2, 3, 5, and 7. The output file is provided here as primes.n7.Running the "hw7 primes -n=1048576" (1048576 = 220) command should generate 82025 prime numbers. The output file is provided here as primes.n220.
trialdiv
Running the "hw7 trialdiv -n=13 -p=primes.n220" or the "hw7 trialdiv -n=532212456847 -p=primes.n220" command should produce the "n passes trial division test" message.Running the "hw7 trialdiv -n=667 -p=primes.n220" command should produce the "n is composite by trial division (mod 23 = 0)" message.
millerrabin
Running the "hw7 millerrabin -n=13 -t=20 -p=primes.n220" command should get an error message saying that either maxitr is too large or that there is not enough primes in primes.n220.Running the "hw7 millerrabin -n=532212456847 -t=20 -p=primes.n220" command result in Miller-Rabin declaring n to be a prime number. The output file is provided here as mrprime.k40.
Running the "hw7 millerrabin -n=667 -t=20 -p=primes.n220" command result in Miller-Rabin declaring n to be a composite number since a strong witness of 2 is found.
Running the "hw7 millerrabin -n=532212456849 -t=20 -p=primes.n220" command result in Miller-Rabin declaring n to be a composite number since a strong witness of 2 is found. The output file is provided here as mrcomp.k40.
rndsearch
A sample 220 bytes long rndfile is provided here as rnd.220.Please click on the links below to see sample output of the corresponding commands:
hw7 rndsearch -k=10 -t=10 -p=primes.n220 -r=rnd.220 > rs.10 hw7 rndsearch -k=11 -t=10 -p=primes.n220 -r=rnd.220 > rs.11 hw7 rndsearch -k=12 -t=10 -p=primes.n220 -r=rnd.220 > rs.12 hw7 rndsearch -k=13 -t=10 -p=primes.n220 -r=rnd.220 > rs.13 hw7 rndsearch -k=14 -t=10 -p=primes.n220 -r=rnd.220 > rs.14 hw7 rndsearch -k=128 -t=10 -p=primes.n220 -r=rnd.220 > rs.128
maurer
Please click on the links below to see sample output of the corresponding commands:hw7 maurer -k=10 -p=primes.n220 -r=rnd.220 > ma.10 hw7 maurer -k=24 -p=primes.n220 -r=rnd.220 > ma.24 hw7 maurer -k=32 -p=primes.n220 -r=rnd.220 > ma.32 hw7 maurer -k=64 -p=primes.n220 -r=rnd.220 > ma.64 hw7 maurer -k=96 -p=primes.n220 -r=rnd.220 > ma.96 hw7 maurer -k=128 -p=primes.n220 -r=rnd.220 > ma.128
The commandline syntax for hw7 is as follows:
hw7 primes -n=maxval
hw7 trialdiv -n=number -p=primesfile
hw7 millerrabin -n=number -t=maxitr -p=primesfile
hw7 rndsearch -k=numbits -t=maxitr -p=primesfile -r=rndfile
hw7 maurer -k=numbits -p=primesfile -r=rndfile
Square bracketed items are optional. Follows the UNIX convention that commandline options can come in any order. (Note: a commandline option is a commandline argument that begins with a - character in a commandline syntax specification.) If an input file is not specified, the program reads from stdin. Unless otherwise specified, output of the program goes to stdout and error messages go to stderr. number is in decimal and all output numeric values are in decimal.
The meaning of the commands are:
The output for various commands are as follows.
|
||||||||||||||||||||||||||||||||||||||||
| primesfile Format | ||||||||||||||||||||||||||||||||||||||||
|
If there are m primes between 2 and
maxval, inclusive, the output file must contain
exactly m+1 words (a word is 4-bytes long and in
big endian representation).
The first word you must output is maxval. It is followed by all the prime numbers, in increasing order, between 2 and maxval, inclusive.
|
||||||||||||||||||||||||||||||||||||||||
| Miller-Rabin | ||||||||||||||||||||||||||||||||||||||||
For this assignment,
you are required to implement the Miller-Rabin test outlined here.
It's slightly different from the lecture slides to make grading
more manageable. Specifically,
step (2.1) below has been changed
to use a specified sequence of prime numbers from primesfile.
Miller-Rabin(n,maxitr):
1) write n-1 = 2sr such that r is odd
2) for (i=1; i <= maxitr; i++) {
2.1) a = the ith smallest prime number
2.1.1) if (a > n-1) return("failure")
2.2) compute y = ar mod n
2.3) if (y != 1 and y != n-1) {
2.3.1) for (j=1; j <= s-1 and y != n-1; j++) {
2.3.1.1) y = y2 mod n
2.3.1.2) if (y == 1) return("composite")
}
2.3.2) if (y != n-1) return("composite")
}
}
3) return("prime")
|
||||||||||||||||||||||||||||||||||||||||
| Grading Guidelines | ||||||||||||||||||||||||||||||||||||||||