prime numbers
xxx
I'm looking for a database with the prime numbers with less than 500
digits... Could you help me?
I'm talking about the factorization of "c" with a*b=c with a,b prime
number...
I think I've found a solution but I'd like to try it with very big number
and I don't know how to do it...
Do you have any idea?
flip
news:VYGT9.12504$0v.3...@news1.tin.it...
Do a search on the RSA Factoring Challenge.
Better yet, check out the RSA web site.
If you can factor the n = p * q, you could get up to a millionbucks, but
moreover, international fame!
HTH, Flip
e_minus
just an idea.
thanks
"flip" <flip_...@safebunch.com> wrote in message
news:10422385...@news-1.nethere.net...
Phil Carmody
> hi there,
> I'm looking for a database with the prime numbers with less than 500
> digits... Could you help me?
No, because there is no such thing in existence.
See the "how many" links at
http://primepages.org/
for information why.
> I'm talking about the factorization of "c" with a*b=c with a,b prime
> number...
> I think I've found a solution but I'd like to try it with very big number
> and I don't know how to do it...
> Do you have any idea?
Yes, thank you.
Phil
Steven
I've got lots of ideas :-)
IIRC, Gauss estimated pi(n) to be about n/ln(n). I guess n is sufficiently
large if n=10^500.
According to the formula there are about 10^497 primes with less than 500
digits.
Even if you have the time to factorise all numbers to 10^500, where would
you leave the results?
A 500 digit number can be stored in 200 bytes, so you can fit 3 million of
them on a CD. You'll need 10^490 CD's.
Maybe you could compress the data? Or use DVD's? ;-)
We would all like to hear it if you find a trick to factorise 500 digit
numbers, as would the CIA. ;-)
(BTW, brute force is not a trick!)
Steven
Eric Nielsen
> them on a CD. You'll need 10^490 CD's.
> Maybe you could compress the data? Or use DVD's? ;-)
Choose a very distant reflector somewhere in the universe and broadcast your
data towards that on a high frequency carrier. This method can provide the
storage capacity needed for this project. Unfortunately you will only be
able to read your database sequentially, and access time will be a real
bitch.
Don Reble
> the factorization of "c" with a*b=c with a,b prime number...
> I think I've found a solution but I'd like to try it with very big number
> and I don't know how to do it...
If you're just looking for some big composite numbers
to factor, try these. Each is a product of two primes.
314159265358979323846264338359
7630695327517178007949407615128655499
4741400499726583871645038495115842925660415608197261
9286868949099082884911010610666849485152977311856474989355552828411
32626081769067169327195079594578197878667869074204586899261825625199760662033645499
19815582850657668895264937474920973498844221368805050977725046709798789862612247739337287103136419
10000000000000000000000000000000000000000000000000000592148175127608805635162863653315178187339348009647260957
If you get only the first, you're a beginner.
If you get the last two, you're a pro.
--
Don Reble d...@nk.ca
Steven
"Eric Nielsen" <e...@attbi.com> wrote in message
news:0NRT9.643417$P31.252686@rwcrnsc53...
Don't forget to ask the marsians not to fly through the beam. ;-)
For those who don't grasp the hugeness of 10^500: if we put the mirror at
the other end of the universe (if there's such thing) and modulate 1 bit of
data in 1 wavelength of our lightbeam, we would only be able to store 10^35
bytes of data. We'll need 10^482 of these beams.
Peter Webb
>
I've got a great compression scheme for the data:
Compress it into the string:
"Generate a list of all primes of less than 500 digits".
I know lots of decoders (programs) that if you feed them this
instruction they will generate the list of all 10^497 prime ;)
David C Ullrich
>> A 500 digit number can be stored in 200 bytes, so you can fit 3 million of
>> them on a CD. You'll need 10^490 CD's.
>> Maybe you could compress the data? Or use DVD's? ;-)
>
>Choose a very distant reflector somewhere in the universe and broadcast your
>data towards that on a high frequency carrier. This method can provide the
>storage capacity needed for this project.
Not even close.
> Unfortunately you will only be
>able to read your database sequentially, and access time will be a real
>bitch.
David C. Ullrich
GerardS
One method of prime number compression is just storing the difference between
primes halved. The first two primes (2, 3) cannot be stored, but would be
implicitly known. When the halved differences exceed 255, a halved difference
of zero would indicate that the next two bytes (16 bits) would contain the
halved difference+32. If the halved difference exceeds 32k, then the same mechanism
could be used to indicated that the next three bytes contain the halved
difference+64k+32. If you want to make it simpler, you could eliminate the +32
and +64K+32 parts.
Using this mechasism compresses the primes quite nicely. Every so often, you
could put the real (next) prime number in (say, every millionth one) to speed up
decompression (finding a particular prime).
Of course, there aren't enough CD's in the universe to hold 10^500 primes,
compressed or not.
But you could fit way more than 3 million primes on one CD. _____________Gerard S.
GerardS
|| Eric Nielsen wrote:
||> Steven wrote:
||> A 500 digit number can be stored in 200 bytes, so you can fit 3 million of
||> them on a CD. You'll need 10^490 CD's.
||> Maybe you could compress the data? Or use DVD's? ;-)
||
|| Choose a very distant reflector somewhere in the universe and broadcast your
|| data towards that on a high frequency carrier. This method can provide the
|| storage capacity needed for this project. Unfortunately you will only be
|| able to read your database sequentially, and access time will be a real
|| bitch.
|
| One method of prime number compression is just storing the difference between
| primes halved. The first two primes (2, 3) cannot be stored, but would be
| implicitly known. When the halved differences exceed 255, a halved difference
| of zero would indicate that the next two bytes (16 bits) would contain the
| If the halved difference exceeds 32k, then the same mechanism could be used to
| indicated that the next three bytes contain the halved difference +128k+512.
| If you want to make it simple, you could eliminate the +512 and the +128k+512
xxx
not working...
Could you please answer to nip...@tin.it?
"flip" <flip_...@safebunch.com> ha scritto nel messaggio
news:10422385...@news-1.nethere.net...
xxx
Do you have a working email? I tried the <Ger...@PrairieTech.Net> but it
didn't work....
Mine is nip...@tin.it
"GerardS" <Ger...@PrairieTech.Net> ha scritto nel messaggio
news:v20plvk...@corp.supernews.com...
xxx
Mine is nip...@tin.it...
Thanks
"Peter Webb" <pw...@DIESPAMDIEopticonaustralia.biz> ha scritto nel messaggio
news:3e2008fe$0$7816$afc3...@news.optusnet.com.au...
xxx
Mine is nip...@tin.it
"Steven" <stev...@pandora.be> ha scritto nel messaggio
news:GDQT9.5990$ym5...@afrodite.telenet-ops.be...
flip
I guess I don't understand exactly what you want an answer to.
I told you ofa wonderful site to get factorinf examples from and you can win
money for actually factoring those numbers.
Exactly what are you looking for?
Flip
Remove "_alpha" to email, but what is wrong woth posting to the NG directly?
Steven
Hi xxx,
can't you post here? Maybe others want to follow the discussion too.
regards,
Steven
PS: I have the idea that xxx is not your real name. a bit strange for
someone who wants to remain anonymous to publish his/her e-mail address.
you're not MPD, are you? (Multiple Personality Disorder, previously
schrizofrenia)
GerardS
A follow up:
The first prime whose halved difference that exceeds 255 (257) is after the prime
304,599,508,537.
258 is just before the prime 416,608,696,337.
266 following prime 461690510011,
267 following prime 614487453523, and
270 following prime 738832927927.
These should be the only ones below 10^13. _______________________________Gerard S.
Ronald Bruck
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <v218s3i...@corp.supernews.com>, GerardS
<Ger...@PrairieTech.Net> wrote:
Yes, I used this scheme back in the days of 8" floppy drives which held
only 144KBytes (or 288KBytes in double density). I was interested in
the primes less than 10^8, but a single floppy could only hold primes
up to about 4 million. Actually, every thousand or so primes, I stored
the prime directly (to simplify the extensive summations which would
otherwise be needed to restore the actual value of the prime).
Nowadays it would certainly be faster to execute a sieve than to look
up such data. Even then it was a near thing, with the shortage of
memory being the major constraint.
--Ron Bruck
GerardS
| Ronald Bruckwrote:
I can't imagine that taking an one-byte integer, doubling it, and adding it to
the previous prime number could be slower than doing a bunch of divisions. Of
course, you had to add "1" to a counter and extract the next halved prime
difference, but that is minor compared to going down a list (of already known
primes) and doing a number of divisions. Of course, you could use the old
sieve method, but the number of "cast-outs" and what not seem more overhead
than *2, add to the previous. ________________________________________Gerard S.
fwi...@sbcglobal.net
> | Eric Nielsen wrote:
> |> Steven wrote:
> | [use a speed-of-light delay loop through outer space]
> One method of prime number compression is just storing the difference
between
At the low end that makes sense, but the _average_ spacing between primes
for
all the data is 1/ln(10^500) = 1/(500*ln(10)) = about 1/(500*2.30)
which is about 1 / 1151 . Now 1 prime per 1151 numbers is 1 prime per 1151
/ 2
odd numbers, or about 1 prime per 576 odd numbers. So a better scheme for
that
scale of things is to store a single bit for each odd number telling if it
is prime or not.
500*10^498 / 2 such bits, or (500 / 16) * 10^498 such bytes is still
huge,
about 3.1 * 10^499 bytes or 3.1 * (1000/1024)^3 * 10^(499-3*3) gigabytes or
about 3.1 * (0.931) * 10^490 gigabytes or about 29. * 10^489 gigabytes. If
a
single-sided dvd stores 4.7 gigabytes {I'm not sure about that figure} then
you need
at least (29. / 4.7 ) * 10^489 alias about 6.1 * 10^489 of such DVDs. In
practice,
you'd want to have some multiple of that quantity to allow distant computer
sites to
work in parallel on the chore, and to handle media failures. Also to speed
things up,
you'd want to embed the current prime number as a {200 byte, according to
OP}
byte insertion thousands of times on each DVD, enlarging the number needed
by
a minute fraction.
But remember how cocky they were about Enigma, and take a lesson.
Even a modest-sized warehouse of dvds must help incrementally in factoring
large numbers, if 'large' isn't on the stupendous scale of 500 digits. And
the
needs and abilities of the banking industry should concern you much more
than those of the CIA, as I suspect the former gets a lot more laws passed
than the latter, in America, and with less forethought of either the
practical or the moral variety.
fwi...@sbcglobal.net
> GerardS wrote
> > | Eric Nielsen wrote:
> > |> Steven wrote:
> > |> ...A 500 digit number can be stored in 200 bytes...
> > | [use a speed-of-light delay loop through outer space]
> > One method of prime number compression is just storing the difference
> > between primes halved...
> primes for all the data is 1/ln(10^500) ...
> about 1 prime per 1151 numbers
> or 1 per 576 odd numbers.
Oops! True but irrelevant, since your scheme uses ten bits per prime,
{2^10 = 1024}plus slight overhead for overflow, but my brainchild
of "a single bit for each odd number" takes 72 bytes per prime.
The original post requested all primes less than 500 digits,
and also factorizations. Perhaps they meant 250 digit
primes, for up to 500 digit products.
Gottfried Helms
>
> For those who don't grasp the hugeness of 10^500: if we put the mirror at
> the other end of the universe (if there's such thing) and modulate 1 bit of
> data in 1 wavelength of our lightbeam, we would only be able to store 10^35
> bytes of data. We'll need 10^482 of these beams.
Well, if we had 1 Million universes, then we had still to deal with
10^479 of these solutions?
Wow!
Gottfried :-)
Wim Benthem
wrote:
>
>| Ronald Bruckwrote:
>|
>| Nowadays it would certainly be faster to execute a sieve than to look
>| up such data. Even then it was a near thing, with the shortage of
>| memory being the major constraint.
>
>I can't imagine that taking an one-byte integer, doubling it, and adding it to
>the previous prime number could be slower than doing a bunch of divisions. Of
>course, you had to add "1" to a counter and extract the next halved prime
>difference, but that is minor compared to going down a list (of already known
>primes) and doing a number of divisions. Of course, you could use the old
>sieve method, but the number of "cast-outs" and what not seem more overhead
>than *2, add to the previous. ________________________________________Gerard S.
>
Running a sieve really is about as fast as this decompression. The time
spent on any particular number N is only about log(log(n))
N will have about 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + .... +/(last prime <
sqrt(N))
This sum diverges so slowly, it might just well be taken to be the
constant 4 for all practical purposes.
--
Wim Benthem
xxx
No, I'm not MPD...
XXX is only easier to find... This was the first setting i put on my
newsgroup editor, a long time ago...
My name is Nicola...
What else? About the newsgroup you're right, but my problem was/is that I've
never used it and I'm little scared about the fact that in a week or so
everything will be lost or canceled.
If you can tell me how to keep alive old post and to find them on outlook,
I'll continue to post here...
Cheers
Nicola
"Steven" <stev...@pandora.be> ha scritto nel messaggio
news:SK%T9.6925$ym5...@afrodite.telenet-ops.be...
xxx
> > >
> > > Do a search on the RSA Factoring Challenge.
> > >
> > > Better yet, check out the RSA web site.
> > >
> > > If you can factor the n = p * q, you could get up to a millionbucks,
but
> > > moreover, international fame!
> > >
> > > HTH, Flip
>
I know the RSA web site... that's one reason why I'm here.. Do you know
other people giving away money for the same reason....?
On the other hand, I don't understand the international fame...Who's going
to care about the factoring thing?
xxx
"Wim Benthem" <wben...@wxs.nl> ha scritto nel messaggio
news:oki22vonehmt3avnn...@4ax.com...
Let's imagine that I know how to compress the prime numbers... in a cd o
dvd... doesn't matter...
I still have the problem to find all my prime numbers, isn't it? How can I
compress something I don't know...
I think that this is my real problem...
Nicola
Phil Carmody
> Even a modest-sized warehouse of dvds must help incrementally in factoring
> large numbers, if 'large' isn't on the stupendous scale of 500 digits.
Wrong.
Phil
xxx
<fwi...@sbcglobal.net> ha scritto nel messaggio
news:0G9U9.79$0w3.59...@newssvr12.news.prodigy.com...
no, i really meant 500 digits, but even 250 digits would do the same
thing... in fact, if I know how to find all the prime with less than 250
digits, with the same rules, I'll find all the prime with less than 500
digits... For me It' s the same problem...
But, maybe, the real problem is not this one... I don't want to know how to
store it... at least I don't want to know it right now... (and maybe, i 've
an idea on it).
The problem is this one... If I know how to compress them, I still need
them, and I don't know how to find them...
But I'm starting to think that maybe it's quite difficult... maybe I've to
find another way round...
nicola
Phil Carmody
> Running a sieve really is about as fast as this decompression. The time
> spent on any particular number N is only about log(log(n))
> N will have about 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + .... +/(last prime <
> sqrt(N))
> This sum diverges so slowly, it might just well be taken to be the
> constant 4 for all practical purposes.
Two words:
Sublinear Sieve
Two more words, just in case you're confused:
Pritchard Wheel
Note that in practice, the multiplicative constant dominates, and after
recent (only 10 days ago) discussions on a number theory list, it appears
that modern hard disks beat CPUs when it comes to streaming primes.
However, that's because almost all sieves are ludicrously sub-optimal.
James Van Bushkirk has an Eratosthenes that's at the trillions level is
5 times faster than my Atkins, which is twice as fast as Bernstein's
Atkins, which is twice as fast as Terje Mathisen's Eratosthenes.
i.e. Currently only James can claim to be faster than a hard disk.
At the 10^15 level, my Atkins would probably pull out a lead, and by 10^17
Gallway's Gallway/Atkins sieve would take over. By that stage, hard disks
have become irrelevant.
Phil
flip
Factoring large turns out to be a very complicated thing.
People have been working on this problem for a long time.
If you found a method that can factor n digit numbers, it could present a
method for eliminating RSA cryptography (if the factoring method were
general).
RSA is the most common form of public-key cryptosystems in the world. It is
used by many institutions including banks. Just being able to tell this
community that an attack is now possible, could cause a lot of uproar for
many reasons.
Trust me, your name will become known worldwide.
Does that answer it?
Also on RSA, if your method works do those problems, they were generated
using a random source which was detroyed so the folks at RSA don't even know
the factorizations. Also, they have perhaps the hugest stake in the matter.
So what is the problem, does your method not work on those numbers or what?
Flip
flip
> Hi Steven...
> No, I'm not MPD...
> XXX is only easier to find... This was the first setting i put on my
> newsgroup editor, a long time ago...
> My name is Nicola...
>
> What else? About the newsgroup you're right, but my problem was/is that
I've
> never used it and I'm little scared about the fact that in a week or so
> everything will be lost or canceled.
> If you can tell me how to keep alive old post and to find them on outlook,
> I'll continue to post here...
>
Ever hear of google?
They keep an archive of posts in their newsgroup section as they purchased
deja.
I don't know if there is a time limit on how long posts are kept, but it may
be twenty years.
You can safely post here and then keep a local copy of your replies on your
computer if you are paranoid about it.
Rob Johnson
"xxx" <nip...@tin.it> wrote:
>Hi Steven...
>No, I'm not MPD...
>XXX is only easier to find... This was the first setting i put on my
>newsgroup editor, a long time ago...
>My name is Nicola...
>
>What else? About the newsgroup you're right, but my problem was/is that I've
>never used it and I'm little scared about the fact that in a week or so
>everything will be lost or canceled.
>If you can tell me how to keep alive old post and to find them on outlook,
>I'll continue to post here...
>
>Cheers
>Nicola
You can use Google. Try
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&group=sci.math
to look at this group.
Rob Johnson
r...@whim.org
xxx
It could be interesting...
I'm still working on it... But I have to find out a solution for the
database... I'm starting to think it's useless... and maybe It's possible to
work without it...
And it's so hard... I'm not using big software and excel has some limits..
First of all i have to find out how to solve them, and then, .... I'll
decide what to do!
Thank you for you answer
Nicola
xxx
I usually prefer boards...
Steven
>
> [snip]
>
> Let's imagine that I know how to compress the prime numbers... in a cd
o
> dvd... doesn't matter...
> I still have the problem to find all my prime numbers, isn't it? How can I
> compress something I don't know...
> I think that this is my real problem...
>
> Nicola
>
>
You have to solve both problems.
The storage problem is a very practical one and I think everyone who
realises 10^500 is really a big number understands that it can't be solved.
So why bother about the calculation problem?
Still there?
OK, about big numbers. Let's make some absurdly optimistic assumptions:
1. There have been 10^12 microcontrollers been made (according to Motorola)
2. They're all still in operation (exageration) and available to our task
(absurd)
3. They can factorise a number in 1us (absurd; most microcontrollers can't
even add two 500 digit numbers in that time)
4. You can distribute the calculation over these uCs
So we can factorise 10^18 numbers per second. Only 10^482 seconds needed to
do 10^500 numbers.
That's 3x10^474 years or 3x10^472 centuries.
Did you notice the exponent doesn't change much?
Mathematically this may not be so, but for any practical purpose 10^472 =
10^500 = 10^1000000.
Did I tell you 10^500 is a *RHN* (Real Huge Number)? :-)
It is impossible.
Which means it can't be done.
Steven
xxx
Ok... let's say that maybe the problem is another... and not the storage...
Let's say that I need all the prime numbers... but I don't need to have them
in front of me...
Does a program calculating the prime numbers within an interval exist?
Am I sure about the results?
It should be enough for my purpose...
"Steven" <stev...@pandora.be> ha scritto nel messaggio
news:hMgU9.8166$ym5....@afrodite.telenet-ops.be...
Steven
> Never say never...
> Ok... let's say that maybe the problem is another... and not the
storage...
> Let's say that I need all the prime numbers... but I don't need to have
them
> in front of me...
>
> Does a program calculating the prime numbers within an interval exist?
> Am I sure about the results?
>
> It should be enough for my purpose...
>
>
Hi Nicola,
if you want to learn about proving primality, have a look at
http://www.utm.edu/research/primes/prove/index.html.
Now I'm an engineer rather than a mathematician, so I'll have to read it a
few times to get some understanding of it all (read: "if you have further
questions about this, don't ask me").
The good news is that most participants here *are* knowledgeable
mathematicians who'd be glad to help you out.(*)
Right, guyz/galz? :-)
Regards,
Steven
(*) Better don't mention the 10^500 numbers, though. ;-)
xxx
thanks for the link...
If you are an engineer, I have another question for you... An easy one... I
hope..
I understand why my usual software doesn't like to make product between
numbers with more than 16 digits...
but... do you have some name of software able to do that kind of
calculation?
Nicola
Steven
> >
> > Hi Nicola,
> > if you want to learn about proving primality, have a look at
> > http://www.utm.edu/research/primes/prove/index.html.
> > Now I'm an engineer rather than a mathematician, so I'll have to read it
a
> > few times to get some understanding of it all (read: "if you have
further
> > questions about this, don't ask me").
> > The good news is that most participants here *are* knowledgeable
> > mathematicians who'd be glad to help you out.(*)
> > Right, guyz/galz? :-)
> >
> > Regards,
> >
> > Steven
> >
> > (*) Better don't mention the 10^500 numbers, though. ;-)
> >
> >
> Hi Steven...
> thanks for the link...
> If you are an engineer, I have another question for you... An easy one...
I
> hope..
> I understand why my usual software doesn't like to make product between
> numbers with more than 16 digits...
>
> but... do you have some name of software able to do that kind of
> calculation?
>
> Nicola
>
I did a google search for "huge numbers calculator" and this is the first
link I got:
http://www.1-4a.com/supermultiplier/.
Haven't tested it myself, so I don't know how long your operands may be.
BTW, engineers don't use this kind of programs. We're perfectly happy with 3
or 4 significant digits.
Steven
Mensanator
>From: "Steven" stev...@pandora.be
>Date: 1/12/03 12:35 PM Central Standard Time
>Message-id: <pziU9.8400$ym5...@afrodite.telenet-ops.be>
Some programming languages handle such numbers. I use Python for doing work on
the Collatz Conjecture because every digit is signifigant. It easily handled
the numbers I was testing that had over 53,000 decimal digits.