3,039

Four Algorithmic Journeys Part 1: Spoils of the Egyptians

  • A9 Videos
  • 10 videos
  • 9,895 views
  • Last updated on Nov 5, 2012
The First Journey covers the origins of the binary exponentiation algorithm and its use in different contexts, e.g. cryptography, linear recurrences, shortest path problems. The concept of semigroup and the family of related algorithms it determines; the mathematics underlying the parallel map-reduce technique.

Topics * Egyptian Multiplication algorithm. Recursive representation.
* Derivation of the iterative algorithm.
* From multiplication to power. The abstract setting. Semigroups. Raising to 0 power. Monoids. Summation, products, reduction. Associativity and commutativity and their relation to parallelism.
* Fibonacci Numbers. O(log n) computation of linear recurrence. Transitive closure. Shortest path.
* Prime numbers. Eratosthenes and his sieve.
* Perfect Numbers. Euclid's Theorem on perfect numbers.
* Mersenne and his friends. Mersenne primes. Fermat. Little Fermat Theorem. Euler and the proof of Little Fermat. Euler phi-function. Euler's theorem.
* Application to cryptography. RSA public-key cryptosystem.
The First Journey covers the origins of the binary exponentiation algorithm and its use in different contexts, e.g. cryptography, linear recurrences, shortest path problems. The concept of semigroup and the family of related algorithms it determin...
Play all

Loading...

to add this to Watch Later

Add to

Loading playlists...