Re: really? (lame question about primes)

From	David Brown <david.brown@hesbynett.no>
Newsgroups	comp.programming
Subject	Re: really? (lame question about primes)
Date	2015-09-02 14:03 +0200
Organization	A noiseless patient Spider
Message-ID	<ms6oer$ctv$1@dont-email.me> (permalink)
References	(4 earlier) <_RfFx.418341$bt.398932@fx32.am4> <87y4gqmc0c.fsf@bsb.me.uk> <72950765-94b6-453f-8271-bce769c9ea28@googlegroups.com> <v67dua9hl4qonlcajvo5j4ftpbk9c69g0p@4ax.com> <eIxFx.410097$GZ.317970@fx21.am4>

Show all headers | View raw

On 02/09/15 09:38, Richard Heathfield wrote:
> On 02/09/2015 08:12, Robert Wessel wrote:
> 
> <snip>
> 
>> The probabilistic primality tests return some probability of the
>> number being prime or composite, and you can run them multiple times
>> to generate any probability you want.  For example, one iteration
>> Miller-Rabin will return "composite" 75% of the time if the number is
>> non-prime.  Apply 50 iterations of that and the odds of accepting a
>> composite number as prime is about 1 in 2**100.
> 
> Rubbish! It's *exactly* 1 in 2**100. :-)
> 
> Putting it another way, you are:
> 
> 99.999999999999999999999999999921% likely to get a prime.
> 
> I only use 20 iterations, so I have 1 in 2**40 chance of getting a
> composite by mistake, which means I'm only 99.9999999999% likely to get
> a prime.
> 
> 2**40 is 1099511627776. For comparison, my chance of winning the UK
> National Lottery is roughly 1 in 14000000 - I am, therefore, over 75,000
> times as likely to win the Lottery* as I am to get a composite number by
> mistake.

Just make sure you don't do 19.93 iterations - as we know, 1 in a
million chances crop up 9 times out of 10.

> 
> *Or would be, if I ever bought a ticket.
> 

I got a letter the other day telling me I had one the European Lottery,
even though I had not bought a ticket - all I had to do was send them my
bank details and my mother's maiden name so that they could transfer the
winnings.

Thread

really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-08-31 12:07 -0700
  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-08-31 23:23 +0100
    Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 01:18 -0700
      Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-01 11:01 +0200
        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 12:20 +0100
          Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-01 15:48 +0100
            Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:26 -0700
              Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:12 -0500
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 08:38 +0100
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:03 +0200
          Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:24 -0700
            Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 22:27 +0100
              Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 15:02 -0700
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 23:20 +0100
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:22 +0200
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 17:18 -0700
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:19 +0100
                Re: really? (lame question about primes) James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-02 12:42 +0000
                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 14:21 +0100
                Re: really? (lame question about primes) Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-02 17:45 +0200
                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 18:06 +0100
                Re: really? (lame question about primes) James Dow Allen <jdallen2000@yahoo.com> - 2015-09-03 17:05 -0700
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-04 02:18 +0200
                Re: really? (lame question about primes) Chad <cdalten@gmail.com> - 2015-09-03 22:37 -0700
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-03 23:49 -0700
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-04 00:18 -0700
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-04 08:25 +0100
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 14:36 +0100
                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 16:49 +0100
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 17:32 +0100
            Re: really? (lame question about primes) Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 22:55 +0000
              Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:15 +0200
          Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 03:19 +0200
            Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:37 +0100
              Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 11:24 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 10:42 +0100
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-02 03:01 -0700
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 12:28 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:12 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:19 +0100
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 14:56 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 15:47 +0200
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 16:27 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 16:37 +0200
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 17:01 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 10:55 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:05 +0100
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 11:49 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:54 +0100
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 13:22 +0200
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-03 13:58 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:34 +0100
  Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-08-31 23:10 -0500

csiph-web