Fooling Around with Primes
rjo_
Posts: 1,825
Hi guys[noparse]:)[/noparse]
Let's face it. You can't really consider yourself to be a geek unless you mess around with prime numbers... and the Propeller is not exactly the architecture you would pick if you wanted to produce prime numbers in great abundance with great speed...
...or is it?
A few years ago I came up with what I consider to be history's most elegant algorithm for producing prime numbers... I'm not claiming to be modest or even the first to consider it (that is almost never the case[noparse]:)[/noparse], only that I hadn't seen it before.
I might be a little prejudiced about the "beauty" thing. For sure, if it isn't the "most beautiful algorithm," it is at least "most congenial." And when you look at the algorithm in Spin, it has to be "most cuddly."
I'm including the Spin version not just because it is so darned cute but also because if you are anything like me, then you occasionally have a problem looking at other people's assembly code. So, if you are like me... take a look at the Spin code until you understand the core logic... then look at the PASM version to see how it is implemented in assembly code... this is a first pass at the assembly... there are all kinds of things that could be done to improve it.
In terms of machine requirements... the algorithm requires only the sequential addition of #1, testing for numeric equivalence, and minimal flow control. So, the Prop is actually over-built for this algorithm.
Both versions are functional. If you experiment with either version, you will quickly come to the conclusion that without parallelizing, the algorithm is pretty much worthless. This is true.
But if you consider parallelizing it, you will also see that the system requirements of bandwidth, processor density, and memory are easily described in terms of linear relationships. So, while the PropI is a bit of a none starter. At the very least, the PropI is a very useful tool for studying the system requirements. In this case, the Propeller's "determinism" allows you to easily consider system requirements right down to machine instructions.
This allows you to easily consider how to "scale" the problem.
An inexpensive, multi-PropII system might easily hold its own for numbers up to around 100,000,000.
Enjoy[noparse]:)[/noparse]
Let's face it. You can't really consider yourself to be a geek unless you mess around with prime numbers... and the Propeller is not exactly the architecture you would pick if you wanted to produce prime numbers in great abundance with great speed...
...or is it?
A few years ago I came up with what I consider to be history's most elegant algorithm for producing prime numbers... I'm not claiming to be modest or even the first to consider it (that is almost never the case[noparse]:)[/noparse], only that I hadn't seen it before.
I might be a little prejudiced about the "beauty" thing. For sure, if it isn't the "most beautiful algorithm," it is at least "most congenial." And when you look at the algorithm in Spin, it has to be "most cuddly."
I'm including the Spin version not just because it is so darned cute but also because if you are anything like me, then you occasionally have a problem looking at other people's assembly code. So, if you are like me... take a look at the Spin code until you understand the core logic... then look at the PASM version to see how it is implemented in assembly code... this is a first pass at the assembly... there are all kinds of things that could be done to improve it.
In terms of machine requirements... the algorithm requires only the sequential addition of #1, testing for numeric equivalence, and minimal flow control. So, the Prop is actually over-built for this algorithm.
Both versions are functional. If you experiment with either version, you will quickly come to the conclusion that without parallelizing, the algorithm is pretty much worthless. This is true.
But if you consider parallelizing it, you will also see that the system requirements of bandwidth, processor density, and memory are easily described in terms of linear relationships. So, while the PropI is a bit of a none starter. At the very least, the PropI is a very useful tool for studying the system requirements. In this case, the Propeller's "determinism" allows you to easily consider system requirements right down to machine instructions.
This allows you to easily consider how to "scale" the problem.
An inexpensive, multi-PropII system might easily hold its own for numbers up to around 100,000,000.
Enjoy[noparse]:)[/noparse]
zip
3K
Comments
If you give me a few hours I'll show you a somewhat more geeky version...
Actually, I feel nerdy. I could give you a Miller-Rabin-test fro primality. But this one is much too strong for 32 bit numbers. If you want to find primes of a a size of a few hundred bits then we'll talk about that.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys
I am also not professing to be an expert about primes[noparse]:)[/noparse]
My only point is that if someone like me... can figure out an architecture that works just fine... imagine if a person was an expert and this was his only job.
Then consider where half the brains went, when one of the World's premiere intelligence organizations was simply disbanded.
(Hint: they all speak Russian fluently[noparse]:)[/noparse]
To look at this the way I do... you have to extrapolate and interpolate... what if you built a machine that was taylor made for the algorithm? Or if you aren't into building , what if you went shopping for an architecture that most closely met the hardware requirements here and simply assembled the pieces? It wouldn't cost very much and the programmer could be a high school kid learning on the job.
You have to admit, it is cuddly[noparse]:)[/noparse]
You're not gonna run out on us, are you, Rich, like you did in your "I broke public-key encryption" thread?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
And rather than talk about it... I thought I should just code it. Then the issue was... what to say.
All of this takes time... and I just ran out of time.
I will never run out on you guys.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
I don't know about anyone else, but even (2^1024)² is a VERY large number... and 1024bit RSA keys are close to being insecure.
Personally, I use 8192 bit keys. and (2^8192)² ? Thats a stupidly huge number. In fact, to give you an idea of how huge... storing it would take 16386 bits...
Post Edited (OwenS) : 4/15/2009 9:53:42 PM GMT
Finding prime numbers is not the challenge facing those seeking to break public key cryptography. That's relatively easy. The challenge is to factor a product of two huge primes into its constituent parts. This is because the public key (used to encode a message) is such a product, and the private key (used to decode the message) can be determined by an attacker if he were able to factor the product on his own. This is what has proven intractible for the largest numbers in a reasonable amount of time (so far as is publicly known), although the required size of the product continues to climb as computing power becomes greater.
Now, if you were to find a "magic bullet" that could factor a 1024-bit composite number in a couple hours or so, you'd be onto something. Many mathematicians have tried...
-Phil
Now that's really cuddly if you are right.
Let's assume that we need at least one instruction per cycle. Meaning at least 4 * n! cycles for the whole program. I would not like to let n grow too much even on the prop. Maybe eleven or twelve...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys
If I can identify all the primes smaller than some number n, then I can build a table of all the products of two primes smaller than n2.· When I've done that, factoring is simply a table lookup.· This has been known for decades, and therefore someone has had decades to build such a table.· Such a table would contain three fields for each entry:· the product, and the two constituent primes (or pointers to them, in another table).
Therefore I'd bet someone has such a table available by now,·for primes up to, say, 24096 -- and that someone can then break public-key encryptions in seconds, with keys up to 28192.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
Now that's a statement! In this forum we are usually talking about 29 bytes per cog or 216 bytes per prop. Maybe even 224 bytes per Flash or up to 235 per SDHC card.
Chip should find out how this table is implemented. The entries are extremely small. I mean, our universe contains about 2260 atoms giving a storage capacity of more than 23800 table entries per atom.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys
Sorry, I meant to write O(n²) there. Still horribly huge though [noparse];)[/noparse]
Oh yeah, and to give people an idea of the scale of 2^4096 numbers: A Zettabyte, or 2^60 bytes, would take more energy to store in the most primitive way theoretically possible than it would take to boil the Earth's oceans
Post Edited (OwenS) : 4/15/2009 9:56:37 PM GMT
because the uppercase Roman letters A-Z are used). Since string theory works
at a scale far smaller than the atoms, and since it uses many more dimensions,
such storage may indeed be possible.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Assuming this algorithm took only O(n) time - which is bloody impressive - you would still need to go through 2358 values a second in order to compute a table of all primes below 2^8192 it in a googol (10^100) years.
In a googol years, the atoms in the universe will have decayed. The point at which the universe's energy is so finely distributed as heat to be unusable comes far far before then.
Put simply, the huge integer factorization problem involves numbers so huge to be positively ridiculous
-Phil
Post Edited (Phil Pilgrim (PhiPi)) : 4/15/2009 10:37:29 PM GMT
My interest in the timing issue has nothing to do with this application. Synthesis and analysis of all kinds would benefit from having a common clock... but even if you don't have a common clock, most of the time, whatever you lose on the timing... you could get back by adding more Props[noparse]:)[/noparse] ... that's not absolutely true, but close enough.
In terms of this application, I'm thinking about it... the next step in the beauty contest is to interleave the cogs and then put everything into cog ram. This would smooth out the scalability argument, but it would also limit each Prop to about 1500 primes. So, the advantage of using multiple props to make this particular argument would be to increase the number of primes by 1500 primes/prop. I'm thinking that in terms of arguments, if it isn't compelling with one Prop... then it wouldn't be any more convincing with 32.
On the other hand, I do think there are lots of applications for multi-prop boards. And it is never too early to start. 32 Props and a total cost less than $200 is really a compelling idea[noparse]:)[/noparse] I would would love to have one... just for the bragging rights[noparse]:)[/noparse]
One strategy I have seen work for development purposes is Phildapil's approach. He basically took feedback... then took pre-orders. Aside from the fact that you can't really say when the product will be delivered (which everyone understands) it is a nice way to go. You get people's interest, give them something to look forward to, and have them rooting you on the whole way. I haven't been on the forum for two weeks... if you did this already, I missed it.
Rich
However, let us consider instead only the primes below, say, 2256.· If you knew all these, you could build a table of all products of two primes, and could break immediately all public-key encryptiions with keylength up to 512 bits.
I maintain that these could have been computed in the last twenty years by a continuous effort.· And if they could have been, it's a lead pipe cinch they have been.· There are agencies with nearly unlimited funding and absolutely unlimited desire to break encryptions.· One of them has an acronym mysteriously said to stand for No Such Agency.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
But remember that none of these are really critical enough for it to be financially viable to crack them. If you are worried about it being broken, you play it conservative. With my VPN, I play it ultra conservative, even though theres nothing of value on there.
2256 is about 1077. So below that number there will be about 1077/(ln(1077) - 1) = 1077/176, or around 1075 primes. There are about 1068 atoms in our galaxy. So just where were you planning to store this table again?
-Phil
But... let's get this down to a scalable solution. We wouldn't have to sacrifice too many stars to get enough atoms to store 2^32 bits... and we can all agree that if someone is using primes on the order of 2^256, they aren't getting those primes from a galactic sieve and they aren't using magic. (and of course no one ever asks them to prove that they are actually using primes[noparse]:)[/noparse]
The question is ... of the 10^75 primes... how many are actually knowable and where do the known primes come from?
While I agree that the incidence of primes flattens and can be calculated out to very large numbers(As Phil has done here)...I would also suggest that in actual practice with very large primes, the number which can actually be be known, decreases very dramatically, regardless of the algorithm one uses to find them... (other than brute force).
So, in this sense, the utility of public key encryption effectively decreases beyond a certain bit depth.
Once you leave absolute determinism and enter algorithmic projection, the actual number of primes isn't important... only the number of very large primes, which can be known, is important.
http://forums.parallax.com/forums/default.aspx?f=25&m=343952
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
There are methods for finding large primes.· Whether they find all of'em in a given range isn't important.· What is important is that anyone who wants to use large primes for encryption must choose them from the ones that are findable and have been found.· This is exactly the set of primes that a cryptanalyst must know, and it will be the same set·for the encryptor as for the cryptanalyst.· Thus, any code-breaking person or organization (given time & money, both abundant for certain code-breakers) can know all the primes anyone else knows, and he can build a table of their products, and he can break anything anyone can encrypt who uses primes for encrypting.
Therefore I consider it extremely probable that someone can break those encryptions.· There are at least two organizations I'd bet on.· One of'em is ours, and the other isn't.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
-Phil
In a more serious vein, a book like
Prime Numbers: A Computational Persepective (Crandall and Pomerance, 2nd Ed. Springer, 2005)
surveys fronts where this mathematics is progressing. Stating the obvious on page 2, they say, "In a very real sense, there are no large numbers. Any explicit integer can be said to be "small". And so on. So much for the number of atoms in our puny Universe. The cover of the book shows a small segment of a chart that was actually micro-printed with the 7.2 million decimal digits of the 41st Mersenne prime, 2^24036583 - 1.
Once when I was collecting references on Cordic algorithms, I ran across a somewhat paranoid web site, cryptoMaverick.com. I don't find that URL now. But it professed that the NSA or what have you had probably long ago cracked the prime factorization problem (sound familiar?) And no table of values necessary. And they are probably checking your "secure" Amazon purchases right now. The author did not have a suggestion on what basis CORDIC would reduce a 500 digit factorization to 20 seconds, and I was trying to imagine how one could concoct a CORDIC successive approximation with a "small" helper table to, say, make some path on the Zeta function converge to x=1/2, and viol