Re: How to Generator Prime Numbers in a short time ?

Unruh <unruh-spam@xxxxxxxxxxxxxx> writes:
Phil Carmody <thefatphil_demunged@xxxxxxxxxxx> writes:

Unruh <unruh-spam@xxxxxxxxxxxxxx> writes:
In my table there are 33859 primes and the biggest prime is 399989, so my
table is exactly the same as your table. What do you mean?

The chances of no prime less than say 1000
dividing it, but some prime between 1000 and 400000 dividing the number is
vanishingly small.

Bullcrap.

The chances of a prime p dividing a number goes roughly as 1/p. The chances
of p dividing that number and no other prime having divided it is much
less than that. (something like 1/pln(p))

Yes, which is why you use thousands of primes to sieve. You don't expect
any individual one to do much, but /en masse/ they're demonstrably quite
effective.

We know this because we've tried it. You are ignorant of this because,
well, I don't know; maybe you just prefer remaining ignorant?

I will drive home the magnitude of your ignorance later.

Is it really worth the time to try dividing by all those
extra primes?

Yes.

Sieving by the extra primes takes time. Running the other primality tests
takes time. It depends critically on whether the extra time taken by the
primality tests wins out over the time taken by the few extra primality
tests.

Yes. THIS IS OUR FREAKING POINT. Running primality tests on 1024-bit
numbers is fairly expensive, several thousand atomic operations. So
many operations you could sieve the range with many small primes.

Not only can we model where we'd expect the cutoff to be - see Bob
Silverman's contribution for the canonical result - we've tried
it, tweaked our parameters, and noticed that the computational model
was in fact pretty accurate.

Do you really find it is worth your while to sieve through 10000 primes (
rather than say 100 primes)?

He does. I do.

? r=1.0;forprime(p=2,1000,r*=(p-1)/p);r*2100
170.0270533643690155420629077
? r=1.0;forprime(p=1000,400000,r*=(p-1)/p);r*170
91.37892341437959479405573343

No idea what these are supposed to mean.

We've done the maths.

What maths? You certainly have not demonstrated any here. You sound like
JSH.

Don't be a twat. If you're too stupid to realise what (p-1)/p might
correspond to in the context of a linear sieve, then I pity you.
If you can't then work out that I'm working out what ratio of numbers
are not divisible by any small primes, then I pity you, your
sister, your pet dogs, your postman, and everyone at ubc.ca.

If you start with a range of 2100 candidates, and sieve with primes
from 2 to 1000, then you'd expect to be left with 170 candidates.

If you sieve 170 candidates with primes from 1000 to 400000, then
you'll expect to be left with 91 candidates.

Therefore the extra sieving saves 79 PRP tests. I.e. it nearly halves
the number of bignum operations that you'd expect to do.

Anyway - back to your astounding ignorance:

The chances of no prime less than say 1000
dividing it, but some prime between 1000 and 400000 dividing the number is
vanishingly small.

The chance of no prime less than 1000 dividing a number, but some
prime between 1000 and 400000 dividing that number is

? (170-91)/170.
0.4647

46 bleedin' percent. Have you been trying to ensure your posts to
sci.crypt include only a vanishingly small proportion of bullcrap?

If 46% is vanishingly small, then a vanishingly small proportion
of people over 60 are male. Congratulations - you don't exist!


Phil
--
The man who is always worrying about whether or not his soul would be
damned generally has a soul that isn't worth a damn.
-- Oliver Wendell Holmes, Sr. (1809-1894), American physician and writer
.

Relevant Pages

  • Re: How to Generator Prime Numbers in a short time ?
    ... dividing it, but some prime between 1000 and 400000 dividing the number is ... The chances of a prime p dividing a number goes roughly as 1/p. ... Sieving by the extra primes takes time. ... primality tests wins out over the time taken by the few extra primality ...
    (sci.crypt)
  • Re: BBC 3 late at night
    ... so chances are a dozen people will be enjoying them. ... I assume that's just an assumption reached by dividing down viewing figures pro-rata? ...
    (uk.tech.digital-tv)
  • Re: How to Generator Prime Numbers in a short time ?
    ... The chances of no prime less than say 1000 ... dividing it, but some prime between 1000 and 400000 dividing the number is ... The man who is always worrying about whether or not his soul would be ... , American physician and writer ...
    (sci.crypt)
  • Re: I just used the whole worthless Bible to wipe my ass
    ... Thanks Bush for dividing us like never before. ... you should learn it and the Koran too.If you want to be ignorant ...
    (alt.politics.bush)
  • Re: I just used the whole worthless Bible to wipe my ass
    ... Thanks Bush for dividing us like never before. ... you should learn it and the Koran too.If you want to be ignorant ...
    (alt.politics.bush)
Quantcast