English subtitles

← 03ps-07 Rabin Miller Primality Test

dummy description

Get Embed Code
1 Language

Showing Revision 1 created 10/24/2012 by Amara Bot.

  1. In lecture, Dave introduce the Rabin-Miller test for primality.
  2. For this assignment, I want you to implement this test.
  3. The Rabin-Miller function your going to write will take in a number
  4. that may be composite or prime and target, which defines the desired probability level.
  5. The default value 128 corresponds to a probability of 1/2^128.
  6. Two useful routines are the module exponentiation function
  7. that we've been using throughout this unit and randrange,
  8. which is a function of the Python library, that returns a random integer
  9. a random integer between start and end.
  10. I haven't provided any tests, but you should be able to find some prime and composite numbers
  11. to test with on your own.
  12. There is some randomness, so there is a small chance the test will return True for a composite number,
  13. but if your target is set high enough--and 128 should be pretty high.
  14. It's very unlikely that this will happen.