代写FIT3155、代写Python设计程序

日期：2023-05-28 04:52

FIT3155 S1/2023: Assignment 3

(Due midnight 11:55pm on Sunday 28 May 2023)

[Weight: 10 = 5 + 5 marks.]

Your assignment will be marked on the performance/efficiency of your programs. You must

write all the code yourself, and should not use any external library routines that interferes

with the assessable items, except those that are considered standard. The usual input/output

and other unavoidable routines are exempted. Importing random (for q1) and numpy (for

using Matrix and numpy arrays to handle q2) is allowed.

Follow these procedures while submitting this assignment:

The assignment should be submitted online via moodle strictly as follows:

ˆ All your scripts MUST contain your name and student ID.

ˆ Bundle and upload your work as a ⟨studentid⟩.tar.gz or ⟨studentid⟩.zip archive.

– Your archive should extract to a single directory which is your student ID.

– This directory should contain a subdirectory for each of the two questions, named

as: q1/ and q2/.

– Your corresponding scripts and work should be tucked within those subdirectories.

ˆ Submit your zipped-archive electronically via Moodle.

Academic integrity, plagiarism and collusion

Monash University is committed to upholding high standards of honesty and academic

integrity. As a Monash student your responsibilities include developing the knowledge

and skills to avoid plagiarism and collusion. Read carefully the material available at

https://www.monash.edu/students/academic/policies/academic-integrity (click) to understand your responsibilities. As per FIT policy, all submissions will be scanned via MOSS

(click) and/or JPlag (click).

Generative AI not allowed!

This unit fully restricts you from availing/using generative AI to answer these assessed

questions.

1

Question 1: Generating a public key [5 marks]

Background

RSA (Rivest–Shamir–Adleman) is a public-key encryption system that is popular in modern

internet communications. A public key as the word suggests is publicly advertised. A system

using RSA generates a public key in the form of a modulus n and exponent e using two large

prime numbers. While n and e are public, the two prime numbers that were used to generate

them are held secretly away from the public eye. Anyone wanting to communicate with the

system uses the public key information to encrypt any message. A secure message can only

be unlocked using the knowledge of the prime numbers behind the public key. The reliability

of such a cryptosystem is purely due to the infeasibility of factorizing any number (especially

large ones) into its prime factors on classical computers.1

Task on hand

In this exercise, inspired by RSA (but not exactly the same in details), we will be generating

two integers, modulus n and exponent e, as a public key.2

The steps you need to follow to generate n and e are described in the corresponding sections

below. To pull this off, you will have to implement on your own the following:

1. Modular exponentiation with repeated squaring.

2. Miller-Rabin randomized primality test with appropriate level of confidence that the test

is probably correct.

3. Euclid algorithm to compute the greatest common divisor of any two numbers.

You are free to use the built-in basic arithmetic operations (addition, subtraction, multiplication, division and modulo division). However, note, as indicted above (see enumerated item 1),

you will have to implement your own modular exponentiation using repeated squaring method.

Generating the modulus n

In this exercise, the modulus of the public key n = p × q is a product of two special kind of

prime numbers p and q we will use in this exercise.

How are these prime numbers selected in this exercise? Suppose d > 2 ∈ Z

+ is an

input parameter to your program. Then p and q respectively are the smallest two prime integers

of the form 2x − 1 where x ≥ d. For all practical purposes, you are free to assume d ≤ 2000 for

this exercise.

1Unless, in the foreseeable future, a quantum computer with sufficient number of ‘qubits’ becomes a reality,

to be able run a well-established integer factorization algorithm (Shor’s algorithm) on it. It is claimed that what

takes quadrillion years to factorize on a classical computer would only take seconds (!) using Shor’s algorithm

on a quantum computer.

2To keep things simple, we will not worry about the actual encryption and decryption of messages in this

exercise, but for the more keen ones, you are encouraged to explore the mathematics behind these processes

that will inform a fuller implementation of what you started here, for your own further learning.

2

Generating the exponent e

The exponent e is computed using p and q as follows. First a value λ is calculated such that

λ =

(p−1)(q−1)

gcd(p−1,q−1) . (You will have to implement Euclid’s algorithm to compute gcd.)

The exponent e is randomly chosen in the range [3, λ − 1] such that gcd(e, λ) = 1, that is e

and λ are relatively prime.

Strictly follow the specification below to address this question:

Program name: mykeygen.py

Arguments to your program: input integer d ≥ 1

Command line usage of your script:

python mykeygen.py <d>

Output files: You will have to write out two files:

1. publickeyinfo.txt giving information of the modulus n and exponent e.

2. secretprimes.txt giving the information of the two primes p and q

Output formats: See example below.

Example: For d = 10,

publickeyinfo.txt will contain:

# modulus (n)

1073602561

# exponent (e)

3187811

secretprimes.txt will contain:

# p

8191

# q

131071

(Note, in the publickeyinfo.txt file, the exponent is randomly chosen, so its value will

vary each time you run your program with the same argument. Also note that, in both

the output files, the markup lines starting with # should also be printed as shown in the

example above.

Question 2: Implementing Tableau Simplex [5 Marks]

In this exercise you are required to implement Dantzig’s Tableau simplex algorithm to solve a

linear program in its standard form, that was covered in the Week 10 lecture.

Your program will read an input text file (see input format below) specifying a linear

program. The linear program by default will be in a standard form. This means that the goal

3

is always to maximize a given linear objective function, involving decision variables that are

always non-negative, subject to a set of linear constraints on the decision variables that are

expressed in the form: LHS ≤ RHS.

Your goal is to find an optimal set of values for the decision variables and the resultant

evaluation of the objective function given those values. To report these, you will have to

implement the exact same Tableau method that we discussed during the week 10 lecture.

Strictly follow the specification below to address this question:

Program name: mysimplex.py

Argument to your program: Filename of an input file giving the details of the linear program in a specific format (see example below).

Command line usage of your script:

python mysimplex.py <filename of a file specifying LP>

Input format: As an example, if the linear program being considered is the following:

maximize z = x + 2y

subject to the constraints

4x + y ≤ 44

3x + 2y ≤ 39

2x + 3y ≤ 37

y ≤ 9

−x + y ≤ 6

(with the implicit constraints that both x and y decision variables are non-negative (≥ 0)) then the input specification

format for this linear programming problem will be as follows (including the # lines):

# numDecisionVariables

2

# numConstraints

5

#objective

1, 2

# constraintsLHSMatrix

4, 1

3, 2

2, 3

0, 1

-1, 1

# constraintsRHSVector

44

39

37

9

6

Output file name: lpsolution.txt (see format below)

Output format For the above example LP problem specified as input, the output would be

in the following form (including the # lines):

# optimalDecisions

5, 9

# optimalObjective

23

-=o0o=-

END

-=o0o=-

4