Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] SPRP

Expand Messages
  • Jonathan Zylstra
    The statement on the web site is unclear ... It should be at most 1/4 of the bases a fail to prove that a given number n is composite, so 3/4 of them should
    Message 1 of 3 , Apr 30, 2003
      The statement on the web site is unclear ...
      It should be at most 1/4 of the bases 'a' fail to prove that a given
      number n is composite, so 3/4 of them should prove compositeness,
      assuming n is actually composite.

      The actual name of the test is the "Miller-Rabin psuedoprimality test"

      see http://www.cacr.math.uwaterloo.ca/hac/
      Here, you can download the "Handbook of Applied Cryptography" - see
      Chap. 4, which refers to choosing public key parameters - i.e. finding
      numbers which are prime. I find this entire book to be an excellent
      reference - it gives clear description and algorithms, and also gives
      plenty of good references.

      Jonathan A. Zylstra
      jzylst01@...

      On Tue, 29 Apr 2003, Jon Perry wrote:

      > 'It has been proven ([Monier80] and [Rabin80]) that the strong probable
      > primality test is wrong no more than 1/4th of the time (3 out of 4 numbers
      > which pass it will be prime). '
      >
      > From:
      >
      > http://www.utm.edu/research/primes/prove/prove2_3.html
      >
      > How does this work, surely I can create a list of n for which it fails...
      >
      > Jon Perry
      > perry@...
      > http://www.users.globalnet.co.uk/~perry/maths/
      > http://www.users.globalnet.co.uk/~perry/DIVMenu/
      > BrainBench MVP for HTML and JavaScript
      > http://www.brainbench.com
      >
      >
      >
      > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      > The Prime Pages : http://www.primepages.org/
      >
      >
      >
      > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
      >
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.