CS260 Study Guide

2a. Define the meaning of a one-way function

• What is a one-way function?
• How are one-way functions useful for constructing hash functions?
• What is an inverse image?
• What is preimage resistance?

A function $y=f(x)$ over some domain takes input values where, for every input value x, there is one and only one output value y. The inverse image of a value $y=f(x)$ is the set of values x that can be recovered from y. Therefore, every output value y of a function always has an inverse image associated with it. A one-way function is a function where it is relatively easy to compute $f(x)$ but computationally infeasible to compute the inverse image. Hash functions are deterministic one-way functions that convert variable length messages to fixed length codes. Such constructions are useful for designing hash functions because the goal is to create a fixed-length code from a variable-length message where the code:

1. is easy to compute and
2. cannot be used to determine the original message.

The one-way property of hash functions is often also referred to as the preimage resistance property.

To review, see:

• One Way Functions
• Hash Functions

2b. Explain collision resistance

• What is collision resistance?
• How does the pigeonhole principle apply to hash functions?
• What is the difference between collision resistance and second preimage resistance?
• What is the avalanche effect?

The goal of a hash function is to take variable-length messages and map them into fixed-length codes. In practical applications, most messages will be much longer than the fixed-length code. The pigeonhole principle automatically implies that two different messages will inevitably be mapped into the same code (that is, a "collision" will occur). Collision resistance is where a hash function $H(x)$ must be resistant to finding such collisions.

Second preimage resistance is defined as follows: Given a preimage x and its hash value $h=H(x)$, it should be computationally infeasible to find a second preimage y such that $h=H(y)$ where yx. Second preimage resistance is a weaker form of collision resistance. A stronger statement is to say that it is computationally infeasible to find any pair (x,y) where $H(x)=H(y)$, which is the definition of collision resistance. The avalanche effect, also an important concept for hash functions, is where a small change in the message results in a large change in the hash value (this property is sometimes referred to as "near-collision resistance").

To review, see:

• Hash Functions
• The Importance of Collision Resistance

2c. Explain how hash functions are applied in practice

• What is a blockchain?
• How are hash functions applied in practice?
• What is "proof of work"?

A blockchain is a digital ledger that keeps track of transactions by successively adding consecutive records in the form of a "chain". Hash functions are central to the construction of a blockchain because a hash of a previous transaction record (a "block") is integrated into the next transaction record. Using this construction, if any block in the blockchain is altered, all subsequent blocks would have to be altered for subsequent hashes to encompass the alteration. However, since many copies of the blockchain exist, this implies that at least 51 percent of all blockchain copies would also have to be altered to give the impression that the modified transaction was valid. The security of a blockchain lies in the computational infeasibility of modifying the hashes and then applying those modifications to 51 percent of all blockchains. The first generation of blockchains applied proof of work to determine the hash of the current transaction combined with the hash of the previous block. As should be clear from the material in this unit, the Secure Hash Algorithm (SHA) is a standard family of hash functions applied in many applications. For example, in the Bitcoin blockchain, a miner is rewarded bitcoins for being the first to find the SHA-256 hash containing a nonce at the beginning of the hash. Finding a valid hash containing a nonce is known as proof of work. Make sure you understand the blockchain concept and how hash functions are applied in this context.

Another important application of hash functions you must recall is user authentication, where a user's information is used to authenticate the user (for example, a password). It is safer for a system to store the hash of a password rather than the password itself. Given the computational difficulty of inverting a hash, recovering a password from the stored hash should be difficult. When a user attempts a login, the hash of the input password can be compared against the stored hash for authentication.

To review, see:

• Introduction to Blockchain
• Proof of Work

2d. Describe the Merkle-Damgard construction

• How can good hash functions be constructed?
• What is a compression function?
• What are some features of the Merkle-Damgard construction?

Hash functions are one-way functions, so they must be easily computed. At the same time, they must be collision-resistant. One approach to achieving these goals is by iterating a simple compression function a specified number of times. A compression function is a function that outputs a smaller fixed-length hash from a larger input sequence.

The Merkle-Damgard construction is one where a compression function is applied iteratively by creating a hash value from the concatenation of an input block with the hash value of the previous internal unit. Since the original input message is broken up into blocks of fixed length, the final input block is not guaranteed to have the correct length. Therefore, the input message may need to be padded with zeros to achieve the specified length. You should make sure to understand the Merkle-Damgard construction and how the compression converts larger sequences into shorter fixed-length sequences.

To review, see:

• Overview
• Recipes for Hash Functions

2e. Compose programs to implement Secure Hash Algorithm (SHA)

• How can Python be used to implement hash functions?
• What hash functions are included in hashlib?
• What is the Python syntax for computing SHA hashes?

Python modules exist that are useful for cryptographic applications. The hashlib module is of particular interest as it can be used to implement a variety of Secure Hash Algorithms (SHA), such as SHA256, SHA384, and SHA512. The syntax for setting up hash computation such as SHA256 looks like:

from hashlib import sha256

It is important to understand how to use the method calls within hashlib to compute a given hash. Additionally, it is important to understand how to write code to exhibit the properties of hash functions. For instance, you should be able to write code that demonstrates the avalanche effect or write code that would test for a collision. In this way, you can use the theory of how hash functions work to create practical implementations.

To review, see:

• The Security of SHA
• Python Exercise

Unit 2 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• avalanche effect
• blockchain
• collision resistance
• compression function
• hash function
• inverse image
• Merkle-Damgard construction
• one-way function
• preimage resistance
• proof of work
• second preimage resistance
• Secure Hash Algorithm (SHA)
• user authentication

4a. Explain the differences between symmetric and asymmetric encryption

• What is asymmetric cryptography?
• How does asymmetric cryptography differ from symmetric cryptography?
• What are some applications of asymmetric cryptography?

Asymmetric cryptography, also known as public key cryptography, is a process where two different keys are used for encryption and decryption. Recall that symmetric cryptography requires all parties to use the same key for encryption and decryption. With asymmetric cryptography, one of the keys is known publicly and does not need to be kept secret. To communicate and maintain confidentiality with a receiver, you encrypt using the receiver's public key and only the receiver can decrypt your message using their own secret, private key.

Public key cryptosystems are usually based upon some number theoretic problem considered computationally difficult to solve (and therefore, assumed to be computationally secure). This unit introduces RSA as the first example of an asymmetric system. Public key systems can be used for encryption for confidentiality, but as subsequent units demonstrate, they can also be used for authentication and as a means for creating digital signatures. They can also be used to distribute keys for use in a symmetric system. This is because symmetric systems tend to be more modular and are intended to be fast for high data throughput. Asymmetric systems tend to be more computationally intensive since they are based upon difficult number theoretic problems. This way, shorter datastreams such as keys can be transmitted using a public key system. Once distributed, a symmetric system can be used for larger datastreams.

To review, see:

• Introduction to Public Key Cryptography
• The RSA Cryptosystem

4b. Describe how the factoring problem relates to the RSA cryptosystem

• Why is factoring important in the RSA cryptosystem?
• How is factoring used in RSA?
• Why is RSA considered to be computationally secure?

Given a composite integer N, factoring is the process of determining at least one factor of N. The factoring of a composite number is believed to be a computationally difficult problem to solve as the number N becomes large. In addition to the public key, part of the public information used to encrypt in the RSA cryptosystem is a large composite number. If this number can be factored, the private key can be determined, and the ciphertext can be decrypted. As long as factoring is a difficult problem to solve, the RSA system can be considered computationally secure. The number field sieve is the most efficient known classical algorithm for factoring large integers. You should understand the time complexity of algorithms such as a brute force search and the number field sieve.

The private key, d, for RSA, is constructed by choosing a large composite number, N, and a public key, e. You must understand how to create the private key for RSA. The Euler totient function $𝜙(N)$ is the number of positive integers less than N that are relatively prime to N. When $N=pq$ is a product of two prime numbers, p and q (which are kept secret), the Euler totient function takes on a very simple form: $𝜙(N)=(p-1)(q-1)$. Therefore, if p and q are known, then $𝜙(N)$ is easy to compute. The relationship between the public key, e, and the private key, d, for RSA must obey:

$ed = 1 \text{ mod 𝜙(N)}$

Hence, e and d are multiplicative inverses in the congruence modulo $𝜙(N)$. If e and $𝜙(N)$ are known, then d can be efficiently computed using the extended Euclidean algorithm, and constructing the private key is a straightforward calculation. This is why p and q must be kept secret. To determine the private key when the public key and N are known, either N must be factored, or the Euler totient function of N must be determined. However, factoring N is considered to be computationally difficult using classical computational techniques.

On the other hand, determining the Euler totient function would entail determining the number of positive integers less than N that are relatively prime to N. This problem is at least as difficult as the factoring problem. The Euclidean algorithm is efficient for computing the greatest common divisor of two integers. The extended Euclidean algorithm is efficient for solving the linear Diophantine equation $ax+by = gcd(a,b)$. You must understand how the Euclidean algorithm is used for computing the GCD and how the extended Euclidean algorithm is used to compute the private key.

To review, see:

• Prime Factorization
• Factoring Techniques

4c. Apply the RSA cryptosystem

• How do you encrypt a message using RSA?
• How do you decrypt a message using RSA?
• How are encryption and decryption achieved as the numbers become large?

Once the number theory of RSA is understood, encryption and decryption are theoretically quite straightforward. Given a composite number, N, a public key, e, a private key, d, and a message, m, the message is encrypted as:

$c = m^e \text{ mod N}$.

To decrypt the ciphertext, compute the following:

$m = c^d \text{ mod N}$.

For small numbers, such a calculation is easily implemented in a language such as Python:

$m = c**d % N$.

However, as the numbers become large (as they routinely do in cryptographic applications), the exponentiation operation will quickly exceed the numerical precision of most computers. Steps must be taken to deal with this issue. In this course, you must understand the repeated squaring algorithm, a method used to efficiently perform the exponentiation of large numbers by computing repeated squares. You must be able to compute the Euler totient function, understand how to compute private keys, apply the extended Euclidean algorithm to compute private keys, and apply the Euclidean algorithm to compute the GCD.

To review, see:

• Modular Arithmetic
• The Basics
• The RSA Algorithm

4d. Compose programs to implement the RSA cryptosystem

• What are the steps to creating the RSA cryptosystem?
• How are these steps implemented in Python?
• How do you connect the theory to implementing the code?

RSA, a public-key encryption algorithm that uses a pair of keys to encrypt and decrypt data, involves three components to achieve confidentiality:

1. Key generation: generate public and private keys
2. Encryption: exponentiation using the public key
3. Decryption: exponentiation using the private key

The theoretical side of RSA means you should understand concepts related to Fermat's little theorem and the Euler totient function. The practical side of RSA means you should understand how to implement the above steps. In other words, you should have code that can compute the Euler totient function, test for primality, factor composite numbers, implement the Euclidean algorithm, implement the extended Euclidean algorithm, and implement the repeated squaring algorithm. Given this suite of tools, you should be able to implement the RSA cryptosystem and run tests to ensure that steps a-c above can be achieved.

To review, see:

• Putting It All Together

Unit 4 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• asymmetric cryptography
• Euclidean algorithm
• Euler totient function
• extended Euclidean algorithm
• factoring
• number field sieve
• public key cryptography
• repeated squaring algorithm
• RSA

6a. Solve problems involving cyclic groups

• What is a finite group?
• What is a cyclic group?
• What is the order of an element in a cyclic group?

A group is a mathematical concept that is central to many cryptographic systems. By definition, a group is a set G along with some operator that acts on pairs of elements from the G. A group must obey the closure property, must obey the associative property, must have an identity element for the group operator, and every element in the group must have an inverse. A finite group is a group where the set G contains a finite number of elements.

A generator is an element from which all other elements in a group can be generated by successively applying the group operator. A cyclic group is a group that contains a generator. Furthermore, every element in a finite cyclic group has an order which means that it will return to the identity element after successive applications of the group operator. The number of applications of the group operator to return an element to the identity element is called the order of an element. For example, in a congruence modulo p where p is a prime number (a finite cyclic group), a generator will have an order equal to p-1. You should understand generators and the order of an element within a finite cyclic group, such as a congruence modulo p.

To review, see:

• Introduction to Cyclic Groups

6b. Describe the discrete logarithm problem

• What is the discrete logarithm problem (DLP)?
• Why are finite cyclic groups relevant to the DLP?
• Why can cryptographic systems be built upon the DLP?

Given a prime number, p, a congruence modulo p, a generator 𝛼, and the equation

$y = 𝛼^x \text{ (mod p)}$

when the value y is given, the discrete logarithm problem (DLP) determines the value x. A congruence modulo p is a finite cyclic group when p is prime, so the theory of finite cyclic groups is quite relevant to the DLP. Logarithms are exponents, so conceptually, this problem is similar to what you may be used to from basic algebra. The main difference is that the DLP takes place over a congruence modulo p; hence, determining the value of the exponent x can be more challenging. This problem is considered to be computationally difficult to solve and is a good candidate for building cryptographic systems. You should be prepared to compute the value of x via a brute-force search. You should also be prepared to execute Python instructions, such as

alpha **x % p

when the numbers are small. When the numbers are large, you should be prepared to apply the repeated squaring algorithm whose code was developed and applied in previous units.

To review, see:

• The Discrete Logarithm Problem

6c. Apply Diffie-Hellman key exchange

• How can the DLP be applied in cryptographic systems?
• What is Diffie-Hellman (DH) key exchange?
• What information is needed to decrypt the DH key exchange?

Asymmetric cryptography is extremely useful for solving the key distribution problem. The Diffie-Hellman (DH) key exchange protocol is based on the DLP. It allows two parties (for example, Alice and Bob) to exchange information that will lead to computing a key that could be used, for example, in a symmetric cryptographic system.

Diffie-Hellman (DH) key exchange is as follows:

1. Given a prime number, p, a congruence modulo p, and generator 𝛼, Alice chooses a private random integer x from the congruence
2. Bob chooses a private random integer y from the congruence.
3. Alice sends Bob: YA (where YA = 𝛼^x (mod p) )
4. Bob sends Alice: YB (where YB = 𝛼^y (mod p) )
5. Alice computes K = (YB)^x
6. Bob computes K = (YA)^y

The value of K is guaranteed to be the same based upon the laws of exponents within a congruence so that Alice and Bob compute the same key. If YA and YB are intercepted, the DLP would have to be solved to compute the secret values of x and y. Once these values are known, they can readily be computed as $K = 𝛼{xy}\text{ (mod p)}$. Therefore, the security of the DH key exchange is based on the computational security of the DLP. You should be prepared to compute the solution to the DLP for small numbers via a brute force search, and you should be prepared to compute values of YA, YB, and K given a set of values.

To review, see:

• The Diffie-Hellman Algorithm

6d. Create programs to implement a Diffie-Hellman key exchange

• How is DH key exchange implemented in Python?
• What algorithms in this course would be applicable to the DH protocol?
• How are shared keys computed?

Implementing the DH key exchange requires finding a generator and exponentiation within a congruence. It is assumed at this point that you have code for the repeated squaring algorithm and for finding generators within a congruence. Additionally, you must have code to solve the discrete logarithm problem within a congruence modulo p using a brute force approach (for example, by using a loop). If these tools are in place, then you should be able to compute keys, compute secret values for the exponent, and exponentiate using large numbers. Make sure to practice applying your code with test values to ensure you can compute with values in the DH exchange problems.

To review, see:

• Python Implementation

Unit 6 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• cyclic group
• Diffie-Hellman (DH) key exchange
• discrete logarithm problem (DLP)
• finite group
• generator
• order of an element

7a. Explain the Weierstrass form of an elliptic curve

• What is the Weierstrass form of an elliptic curve?
• How are congruences modulo p used when applying the Weierstrass form in cryptographic applications?
• What are some mathematical traits of the Weierstrass form of an elliptic curve?

Elliptic curves can be used to form cryptographic systems. One type of elliptic curve that can be understood, given all you know from this course, is the Weierstrass form:

$y^2=x^3+ax+b \text{ mod p}$

where a and b are parameters that define a specific curve, and p is a prime number. Given a prime value of p, every element in the congruence will have a multiplicative inverse. This property forges a well-posed path to formulating arithmetic operations (such as point addition) on the elliptic curve.

One important point to note about the Weierstrass form is that the same value of x can generate two y values. In an analogy to the square root function for real numbers, both a positive and negative root will satisfy the curve equation. This means that, given some x for which a value y satisfies the equality, then

$text{p-y mod p}$

will also satisfy the equality for the same x. Because of this property, just as with real square root functions, the graph of the Weierstrass form will be symmetric about some y value. You can gain some intuition about the Weierstrass form by choosing a small value of p (such as p=17) along with values of a and b and then plotting some points on the curve.

To review, see:

• Introduction to the Weierstrass Curve

7b. Solve problems involving elliptic curve groups

• What is point addition
• What is the point at infinity?
• How are these concepts related to forming a group on an elliptic curve?

The starting point for performing algebraic operations on an elliptic curve requires point addition, point doubling, and the point at infinity.

• Point addition involves adding two different points, P and Q, contained on the curve: P+Q.
• Point doubling involves adding a point P to itself: P+P.
• Point at infinity: The result of adding a point P and its mirror image P + (-P) = 0. It is used as the identity element for adding points on an elliptic curve.

You should understand that this set of operations leads to a cyclic group. Furthermore, you should understand how a generator can yield all elements within the group defined on the Weierstrass Curve. To do this, it is important to review the equations for point addition and point doubling and understand how they can be applied within a congruence modulo p.

To review, see:

• The Details Behind Point Addition
• Computing Point Addition

7c. Write programs to implement ECC

• How is point addition implemented in Python?
• How is point doubling implemented in Python?
• How is a mirror image recognized in Python?

To implement ECC, it will be necessary to implement arithmetic operations on the elliptic curve. This unit focuses on the Weierstrass Curve and the equations associated with this curve. For example, to verify a generator, successive additions must be applied until all elements of the group have been generated. This implies that point addition, point doubling, and the point at infinity must be programmed. A key numerical step in implementing point doubling and point addition requires that multiplicative inverses of elements modulo p must be computed. One way to program this step is to apply the extended Euclidean algorithm.

The point at infinity occurs because a point P has been added to its own inverse (-P), which is the mirror image of P. It should be clear that the equation for point addition will be undefined if used to compute P+(-P). Therefore, the mirror image should be checked before applying the P+Q point addition. Such a condition could be encountered, for example, while using a generator to generate all points within the group. So, to create a suite that can implement arithmetic on an elliptic curve, your code must be prepared to compute P+P, P+Q, and handle the condition P+(-P).

To review, see:

• Python Implementation

7d. Apply the elliptic curve discrete logarithm problem

• How is scalar multiplication used in the EC discrete logarithm problem (ECDLP)?
• What is the Elliptic Curve Diffie-Hellman (ECDH) protocol?
• How is the DLP problem related to the ECDLP problem?

Given the cyclic group formulation using the addition of points on an elliptic curve, scalar multiplication can be achieved by successive addition. In other words, given a point P, a computation such as 3P can be achieved by computing P+P+P. Given a generator 𝛼 for this group, the pattern of how group elements will be generated is not known. Assume that $T=K𝛼$, where it takes K "hops" to arrive at the point T on an elliptic curve. If T is given, but K is not, determining K is a computationally difficult problem. In analogy to the DLP, the elliptic curve discrete logarithm problem (ECDLP) refers to determining the value of K (the number of hops).

For the most part, any cryptosystem based upon the DLP can be translated to the ECDLP. One important application of the ECDLP is the Elliptic Curve Diffie-Hellman (ECDH) protocol. Instead of using exponentials, scalar multiplication is used to generate the keys. Alice and Bob still choose secret values x and y, but now Alice forms $YA=x𝛼$ and Bob forms $YB=y𝛼$. Alice sends Bob YA, and Bob sends Alice YB. Both parties can form the quantity $K=xy𝛼$ to achieve the key exchange. For groups containing many points on an elliptic curve, determining x from YA and y from YB is considered computationally difficult. You should be able to generate points on a Weierstrass curve for small values of P. Furthermore, with this code in place, for small values of p, you should be able to determine Alice and Bob's values of x and y if an eavesdropper intercepts YA and YB.

Additionally, given $T=K𝛼$ and the generator 𝛼, you should have code in place to determine K from the value of T using a brute force approach (that is, solve the ECDLP). This framework can also be extended to digital signatures. Elliptic Curve Digital Signature Algorithms (ECDSA) refer to the process where a user's private key from an elliptic curve encryption is used to sign a message.

To review, see:

• Overview
• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Digital Signature Algorithm (ECDSA)

7e. Contrast the computational security of elliptic curves versus discrete logs

• Why is ECC considered to be secure?
• How does the computational security of RSA compare with ECC?
• How does the computational security of DL compare with ECC?

The security of ECC depends upon the computational difficulty of solving the ECDLP. One theme is consistent across public key systems based upon factoring, the DLP, and the ECDLP. The security of these problems is rooted in the difficulty of determining the sequence of how a generator generates all elements of the group. If this problem can be solved, such cryptosystems would be rendered unusable.

It is important to compare the performance of RSA and systems based on the DLP with systems based on the ECDLP. For example, key exchange systems based on the ECDH are considered to be faster than those based on the DH protocol. It is also generally true that the same amount of security can be achieved with fewer bits when using ECC approaches. From the materials in the course, you should be aware that computational security using fewer bits and computational efficiency are two major reasons why ECC techniques have been adopted.

To review, see:

• Public Key System Comparisons

Unit 7 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Digital Signature Algorithms (ECDSA)
• elliptic curve discrete logarithm problem (ECDLP)
• point addition
• point at infinity
• point doubling
• Weierstrass form

10a. Explain quantum operators

• What is superposition?
• What is entanglement?
• What are some properties of quantum operators?

A state vector for a quantum computational system is defined as a vector that contains all the information necessary for performing quantum computations. For example, a single qubit state vector is of the form

|𝜓> = a|0> + b|1>

where $Ia|^2+|b|^2 = 1$. A linear superposition is a linear combination of a set of basis states. In the above single qubit example, the state vector |𝜓> is said to be in a linear superposition of the computational basis kets $|0>$ and $|1>$. The probability of measuring a system in state $|0>$ is $Ia|^2$, and the probability of measuring a system in state $|1> is Ib|^2$. The state vector for a two-qubit system, in general, has the form

|𝜓> = a₀₀|00> + a₀₁|01>+ a₁₀|10>+ a₁₁|11>

where the sum of the amplitude magnitudes squared is now normalized to a value of 1. Higher qubit systems can be built up from tensor products of lower qubit systems; however, it is not always the case that a higher qubit system can be expressed in terms of lower qubit systems. Consider a two-qubit system that looks like

|𝜓> = a₀₀|00> + a₁₁|11>

This system is known as an entangled system and cannot be built up from a tensor product of single qubit states. You should understand the concepts of superposition and entanglement in quantum systems.

Quantum operators are those that operate on state vectors that define a quantum state. Quantum computation applies a set of quantum operators to a state vector to achieve a specific computation. In quantum computation, operators are usually expressed as a matrix that operates on state vectors. Typical operators applied in quantum computation are the Hadamard matrix, Pauli spin matrices, rotation gates, Fourier operators, permutation matrices, Toffoli gates, and CNOT gates. Quantum computation must be reversible, and this constraint implies that all quantum operators must be unitary (that is, the Hermitian adjoint must be equal to the matrix inverse). While this is not a course in quantum computation, you should be familiar with basic concepts involving reversible computation, unitary matrices, and quantum operators.

To review, see:

• Introduction to Quantum Computation
• Cryptographic Implications
• The Deutsch-Jozsa Algorithm and QKD

10b. Apply the order-finding problem to factoring

• What is the order-finding problem?
• How is factoring related to order finding?
• Why is order finding important to cryptography?

Nontrivial roots of unity are defined as nontrivial solutions to the equation

s²=1 mod N

The rearrangement of this equation as

(s+1)(s-1)=s²-1 = 0 mod N

is a path to factoring the composite number N. If the gcd(q,N)=1 for some q in the congruence modulo N, then some m is guaranteed to satisfy

q^m = 1 mod N

where m is the order of q. The order-finding problem is defined as the process of finding m such that

q^m = 1 mod N.

Therefore, finding nontrivial roots of unity to factor N can be translated into the order-finding problem. Since there is currently no known method to predict the successive powers of q, determining the value of m is considered computationally difficult as N becomes large. Since RSA depends upon factoring a composite number N, solving the order-finding problem is directly relevant to cryptography. At this point in the course, you should have code available to compute the order of an element q by computing successive powers (which may involve either successively computing q**m or using your repeated squaring algorithm).

To review, see:

• Cryptographic Implications
• Factoring by Perfect Squares
• Overview of Shor's Algorithm

10c. Explain Shor's algorithm

• What is Shor's algorithm?
• How is order finding related to Shor's algorithm?
• What are some quantum operators used in Shor's algorithm?

There is no known classical factoring algorithm that is computationally efficient. This is why systems such as RSA have been considered to be computationally secure. Shor's algorithm is a quantum-based scheme that is efficient for factoring numbers and solving the discrete logarithm problem. Understanding that some parts of Shor's algorithm can be solved efficiently via classical means is important. For example, verifying that the gcd(q,N)=1 for some value q in the congruence modulo N can readily be performed using the Euclidean algorithm. Shor's algorithm turns the order-finding problem into a period-finding problem and creates quantum operators that can successively exponentiate. The architecture for Shor's approach to solving the order-finding problem involves Hadamard operators, exponentiation operators, and an inverse Fourier operator. The inverse Fourier operator is applied to perform what is known as phase estimation. While this is not a course in quantum computation, you should be familiar with the concepts necessary for understanding how Shor's algorithm works and why it can be used to solve the factoring problem.

To review, see:

• Breaking RSA
• Shor's Quantum Architecture
• Breaking RSA Using Shor's Algorithm

Unit 10 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• linear superposition
• nontrivial roots of unity
• order-finding problem
• quantum computation
• quantum operator
• Shor's algorithm
• state vector