If you're seeing this message, it means we're having trouble loading external resources for Khan Academy.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Randomized Algorithms

3 programs
5 videos
Would access to coin flips speed up a primality test? How would this work?

Randomized algorithms (intro)

How could random numbers speed up a decision algorithm?

Conditional probability warmup

Conditional probability visualized using trees.

Random primality test (warm up)

Introduction to random primality tests & how they will work (warm up).

Level 9: Trial Divison vs Random Division

Build our first random primality test

Fermat's little theorem

Introduction to a key result in elementary number theory using a visualization with beads

Fermat primality test

A quick outline of how & why it works.