Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Reminder

Prime Numbers and Cryptography

a and b have the same remainders when divided by c

Introduction

Cryptography

Fermat's little theorem

Tools that underline most modern security protocols

If p is prime, then for any integer n coprime with n,

Used by Egyptians 4000 years ago

Sieves Primality Test

Played a crucial role in both world wars

Two main stages : Classic era and Computer era

-It is the fastest method to use for a 100% accuracy in finding prime numbers.

-It's main Drawback is when computing prime numbers above 10 million. Since it takes unreasonably long time.

- Sieves method is quicker and more efficient than the Trial method

- It has a much lower Complexity than the Trial method

-Most efficient method for small primes (below 10 million)

Modern Cryptography

Cryptography goals

Example: User passwords databases in websites

1-Confidentiality: To prevent unauthorized acces to data

Symmetric key cryptography

Example: Online banking

2-Data Integrity: To keep unauthorized parties from manipulating data

3-Authentication: 1-Entity(user) authentication 2-Data origin authentication

Public key cryptography

Example: Purchase orders for big companies

4-Non-repudiation: Prevents an entity from denying previous commitments

Whether

Or

Proof ?

And we iterate the process

And we are done

because we found d=r-1

Analysis of an algorithm

How efficient is an algorithm or piece of code?

Different algorithms that produce the same results

Efficiency covers:

  • Central Processing unit (time) usage
  • memory usage
  • disk usage
  • network usage

We will use the contrapositive !

Probalistic primality test

The probability to be wrong stating p is prime is 0.25^k, k being the number of iteration.

Complexity of Miller-Rabin method in function of the input (n) the number of iterations (x)

After 10 iterations, 99.999905% of chance to be prime!

Prime numbers and Cryptography

Learn more about creating dynamic, engaging presentations with Prezi