CS260: Factoring by Perfect Squares | Saylor Academy

We have already discussed the factoring problem and various factoring algorithms. The approach most relevant to Shor's algorithm is factoring by perfect squares. Use this material to review this technique.

Source: Jeff Suzuki, https://www.youtube.com/watch?v=XOztXSWzsXM
This work is licensed under a Creative Commons Attribution 4.0 License.

COURSE INTRODUCTION

Course Syllabus

Unit 1: Introduction to Cryptography

Unit 1 Learning Objectives

1.1: Introduction to Encryption and Computational Security

Key Concepts of Cryptography

How Cryptography Works

Key Terms for Network Security

1.2: Block Ciphers vs. Stream Ciphers

Overview

More on Stream Ciphers

1.3: Substitution Cipher

Basic Techniques

Python Exercise

1.4: Transposition Cipher

Basic Techniques

1.5: Random Numbers

The Basics of PRNGs

Python Example

1.6: Perfect Secrecy and the One-Time Pad

Perfect Secrecy a La Shannon

The Main Idea behind the One-Time Pad

More on the One-Time Pad

Unit 1 Assessment

Unit 1 Assessment

Unit 2: Hash Functions

Unit 2 Learning Objectives

2.1: What Is a Hash Function?

Overview

One Way Functions

Hash Functions

Python Exercise

2.2: Collision Resistance

The Importance of Collision Resistance

The Vulnerabilities of MD5

2.3: Merkle-Damgard Construction

Overview

Recipes for Hash Functions

2.4: SHA (Secure Hash Algorithm)

Overview

The Security of SHA

Python Exercise

2.5: Application: Blockchain

Introduction to Blockchain

Proof of Work

Python Exercise

Unit 2 Assessment

Unit 2 Assessment

Unit 3: Symmetric Encryption

Unit 3 Learning Objectives

3.1: Introduction to Symmetric Encryption

Key Concepts

3.2: Feistel Cipher

Combining Transposition and Substitution

The Elegance of the Feistel Cipher

3.3: Data Encryption Standard (DES)

Overview

Applying the Feistel Cipher

3.4: Advanced Encryption Standard (AES)

Beyond DES

Python Implementations

3.5: Triple DES (3DES)

Introduction to 3DES

Contrasting 3DES with AES

A Performance Comparison of DES, AES, and DES

Unit 3 Assessment

Unit 3 Assessment

Unit 4: Asymmetric Encryption

Unit 4 Learning Objectives

4.1: Asymmetric Cryptosystems

Introduction to Public Key Cryptography

4.2: The RSA Cryptosystem

The RSA Cryptosystem

4.3: Integer Factorization

Prime Factorization

Factoring Techniques

Python Exercise

4.4: Congruences Modulo n

Modular Arithmetic

More Immersion into Congruences modulo n