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

"Chen" <forchen_lc@xxxxxxxxxxx> wrote in message
news:1155280331.229665.47100@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Joseph Ashwood wrote:
Sorry, I guess I screwed up the capitalization. He has replied to this
thread already (10 Aug 2006 6:34AM according to my newsreader), and you
replied to him (same day 8:19PM).
I'm terribly sorry about that. It's my fault just notice the context
of the replies, but
ignore the names.
By the way , I replied to him at 11:19 am , can you guess where am I ?

Yeah but you said it only goes to a couple thousand, you should be able
to
initialize a larger table to filter more.
Now I initialize a mucher larger table which contains 4202 primes, upto
39989,
Is it large enough ?

In the time it took you to post that here you could've found all the primes
up to several billion. With such a trivial task it is generally better to
just do it than sit around and decide what is the "optimal" way.

A few rounds of MR should be sufficient. A simple program of mine a while
back was finding several thousand new large primes per week, basically
one
every couple minutes. Just to crushingly over do things I would recommend
that once you have found a probable prime you verify it with log(p)/2 MR
tests, but generally anything over about 10 is considered substantial
overkill.
Once I have found a probable prime I do the the first Miller-Rabin
with a base of 2, then verify it with random bases for another 2 times,
You said verify it with log(p)/2 MR tests. In my program p=1024,
log(p)/2=1.5, does that mean 2 times MR tests is enough?

No I said log of p, p is on the order of 2^1024, the log of which is 1024,
/2 is 512. This is not so much beating a dead horse as beating the dead
horse, then blowing it up, then collecting all the pieces into a pile and
burning it, but at the end of that you can be quite certain the horse is
dead. Since we're only talking a few minutes of processing this conversation
is orders of magnitude longer than actually doing it.
Joe


.

Relevant Pages

  • Re: To Chuck K:
    ... You have a tendency to beat a horse until it's dead, ... I was looking at some of your replies on some of these ... of you writing seemingly endless responses that say very little. ...
    (alt.vacation.las-vegas)
  • Re: ranges of integer polynomials
    ... Let E be a recursively enumerable set of positive integers. ... But gis the intersection of the range of Q with the set of primes. ... an option for automatically quoting the prior message. ... If you read a few replies by the ...
    (sci.math)
  • Re: How to Generator Prime Numbers in a short time ?
    ... Now I initialize a mucher larger table which contains 4202 primes, ... that once you have found a probable prime you verify it with log/2 MR ... with a base of 2, then verify it with random bases for another 2 times, ...
    (sci.crypt)
  • Re: There is no market for real cameras anymore.
    ... >could be built, but at what size, cost & weight? ... For Nikon users: ... the primes are more pleasant to use. ... It was allowed to keep its horse, since horses were so cheap to make. ...
    (rec.photo.equipment.35mm)
  • Re: Alternative Goldbach?
    ... >>> difference of two primes ... >>> sum or difference of two primes ... >> a) implies c), and b) implies c)]. ... Please send replies to the newsgroup. ...
    (sci.math)