Want another? A number that could be a mersenne prime cannot be one if the exponent isn't a prime also.
Proof: For every number with a non-prime exponent E, take two possible factors that compose E as K and F. Now:
11111...111 (F 1's behind each other) times 10000...(F-1 zeroes)...000010000...(F-1 zeroes)...000010000...(F-1 zeroes)...000001 with K-1 times the repeat (and thus K ones) will equal the candidate number.
You can also prove it more mathematically:
sum from (I = 0) to (K-1) over (2^F-1) * 2^(I*F) Written out, the series goes: = (2^F-1) * 2^0 + (2^F-1) * 2^F... = (2^F-1) * 1 + 2^2F - 2^F... = 2^F - 1 + 2^2F - 2^F... = 2^2F - 1... = 2^(F*K) = 2^E
In issue 75 of Linux Format, on the shelves now, we have an interview with Perl king Larry Wall. Here are a few of the questions we asked Larry, along with his answers:
LXF: Did you leave O'Reilly after the dotcom boom was ending, when people stopped buying books so much?
Larry Wall: O'Reilly had run into really tough times because of the plunge in book sales, which was already starting before 9/11 but very much accelerated at that point. So I knew that I was... that I was one of their fluffier employees from a standpoint of their core business, so I was not at all surprised to get laid off. People sometimes say, "Well aren't you angry at Tim O'Reilly for laying you off?" and I say, "No, you don't understand."
The years that he hired me he essentially paid me to do what I want to do. He essentially gave me a scholarship for those years, and I'm completely grateful for that, for what he was able to do, and so that's my feeling about Tim O'Reilly. I'm on very good terms with him.
LXF: What do you find particularly excites you about Perl 6 - apart from the idea of finishing it!
LW: I think it would have to be the parts that are designed to evolve faster even than Perl 5 could evolve. Perl has always been somewhat about evolvability. That's partly why we have sigils [$, @, %] on the front of our variables, so they are often in separate name spaces from the verbs. And we added a lot of extensibility to Perl 5, which was why we ended up with the CPAN, which is the envy of all the other languages.
Nevertheless, there were many ways in which Perl 5 was running into its limits, and these were both syntactic limits and semantic limits. We had ways of mutating the language, but only very crudely. We had a mechanism called source filters, but the trouble is that the granularity was far too large, because it was from here to the end of the script. You could filter through a filter, and that meant that every source filter had to reparse Perl to do anything with it. You couldn't stack them, because they would interfere with each other.
In Perl 6 we actually give the programmer control over the individual grammar rules and even sub-rules, so that you can replace little bits and pieces of the grammar. It's a kind of encapsulation, in the sense that you're only changing the parts that you are concerned about in a way that does not influence the rest of the grammar. This lets different kinds of grammatical mutability sneak into the language, and lets people experiment with different syntaxes and different ways of attaching those syntaxes to new kinds of semantics. And then we can have a lovely Darwinian gene pool that will pick the winners and also pick the losers, and that will contribute to the evolvability of Perl 6.
Part of the new evolvability design is the notion that we need better control over interface versions, so that different modules can for instance have requirements on other modules, and if two modules require the same module but happen to require different versions of that module, those can both coexist. Unless of course those two modules require some kind of exclusive access to a resource that cannot be shared. They'll have to negotiate then.
When I say, "Use module::dog" I get Fido version 1 and when he says "Use module::dog" he gets Fido version 2. But in either case a lexically scoped alias of dog means this in my particular case. And beyond that, perhaps [we can] even provide mechanisms so that modules themselves can be polymorphic with respect to their own version numbers. So you can say, "Yes, I know I'm pulling in version 2 but I know that you know how to emulate version 1. And I have to stick with version 1. Or maybe that's implicit: you say: " I want version 1, you might get version 1 or you might get version 2 emulating version 1". So we allow modules to then mutate their interface and their set of semantics over time, and yet have a way to identify a certain set of semantics that can be locked
They differ only in the number of ones. The point why they are mersenne primes is BECAUSE they have this property. Since these numbers are relatively often prime, it's a lame (*cough*, ok, cheap) way to get to very large prime numbers.
So, all you have to store to know the number is the number of binary digits. Conveniently, that's the exponent in power-of-2 notation.
You can write down the exponent in 4 bytes, I sure hope. If you want to type it out in notepad, try using the notation I provided. It fits in 15 bytes with ease.
Well... the server is at mersenne.org. I somehow expect them to have found a mersenne prime, which with 10 million digits takes about 15 bytes to store in plain-text, and only 4 if you store it efficiently:
2^35000000-1 => that's in normal form. You only have to store the exponent, the rest is constant. Since it's smaller than 4294967296 you can store it in a normal int (4 bytes), and since it's larger than 16777216 you can't store it in 3 bytes.
Finding common divisors is usually done with the formula of Euclides. That brings it down to iirc the log of the number, which is just 10000000.
A very good (but not perfect) sieve for primes with no false negatives is the Lucas-Lehmer primality test. I expect them to use that for first selection runs.
For a full certainty, the only cause (I think) you have is to repetitively try to divide it by another and figuring out you keep stuff left. I am quite certain they're using distributed computing for that.
1985 - Release of Windows 1.0, after a long period of waiting. 1995 - Release of Windows '95, after a long period of waiting. 2005 - Well... We're still waiting after all...
Lesson 1 in forensics: Secure the data carriers as read-only devices so you don't mess it up more than you already did. Common advice is to pull the plug (don't shut down properly) to make sure the shutdown process doesn't wreck anything.
Lesson 2: Making sure the computer doesn't know what you did anymore requires using a method to destroy the physical harddisk. There is almost no software method secure enough to make it actually impossible. Try Mt Doom, a forge or a sledgehammer.
Practical advice for your particular case: Make a full copy of the disk, making sure it isn't mounted by the OS as a coincidence (IE: don't use windows, use linux or a unix only after making sure it doesn't mount it etc). Get a license of actual forensic software that can rip apart the system restore files (if pre-sp2 it's better since they store all link files to documents you use as well, if after that's sorry, but you can still get a lot of information from it) and the IE logs. You also want the system logs plus a capable viewer and if possible, the registry. Also, get a full searchable and indexed list of all files on the disk plus the information stored with them in the form of access dates etc. Using NTFS is a small plus, since it keeps time in 100-nanosecond intervals (so, it's more like dependant on the accuracy of your system clock) as opposed to FAT(12/16/32) which uses 2-second intervals.
67 million degenerates to about 4500 people buying the DVD, around 15000 seeing it in the cinema and 668 people ripping their own copy to the net, now being forced to pay $100.000 each. That adds up to 4500 * $22 + 15000 * $7 + 668 * $100.000 = $67M.
I've stopped playing a simulated race game more than once, then to get in my real car and to be amazed by the light rendering, the very good anti-aliasing, bump mapping and the incredible polygon rate. Also, the accuracy of skidding was completely incredible...
Sadly, the price of new tires was also incredible.
- Take the file, determine (guess) the header size - Note a bunch of values in hex, BCD and binary that could be useful. If it's an ancient Unix file, add octal notation. These things include the header size guess, the file size, a guess of an average content size etc. - Guess what the values could mean, taking note of offsets. - Try to fish out stuff behind the header by looking at repetitions, and determine block structure for those blocks. Determine how to find them from the header (jumping through headers, constant offset, encoded offset) - When you can't find a direct relation, try with a constant offset from the found address. Microsoft (yep, I've been doing some myself in the past) used to love a 20 byte offset in the pointers. - Deconstruct the entire file that way, recursively - Know existing filetypes, preferably by heart. When you see 0xFF 0xC0, you should know that it's possibly a JPEG header. Same for text "GIF89a", bitmap headers and so on. For Microsoft embedded JPEGs, also expect 0xFF 0xD1 and RGB encoded JPG's (yes, that's horror. All things that may be named.jpeg are actually JFIF files, which requires CMY encoding). - Write down your guesses multiple times, use markers and a laser printer, and don't mind the looks on your co-workers if they see you pondering over a hex output for over an hour.
We are sorry to report that your XBox 360 crashed during the final race online of the world online championship of World Rally Cup 2006 V3. Would you like to play Patience, Minesweeper or Reboot?
I was hoping for a nice technical article for once, that would illustrate how to make your own search engine and how to make it fast on indexing and searching through millions of pages.
The only game I've wanted to buy in the past 3 years was Locomotion, and that went out of sale around here because nobody seemed to agree with me. It dropped from 50 euro to 15 within a few weeks, and then it appears to have just vanished when I tried to buy it. Aside from that, my recent game buys include C&C 2, Red Alert (re-buy, I lost one cd of my original copy (which I've bought for 99 guilders when it was first out, that's like 50 euros)) 1, C&C1, Diablo and Diablo 2. Games I want to buy are Locomotion (still...) and Diablo 2 : LoD. Oh, and Fallout 2, but that seems to have not been on sale for quite some time.
Screw off with all those new-fangled games that work like crap compared to old games. They've lost their replay values so I'm not going to buy 50 euros for a single shot of fun.
- Anything you can do, an attacker can do as well.
So, ANY possible scheme that does not have centralized control will be flawed, since I can do anything you can and can thus claim I'm you. The only way to show you're not me is by showing something that differs you from me. By showing something that differs, you know that there are two people claiming to be X. Which is real?
The fact is so basic that there were even game shows about it. "Who in the three" was based on three people sitting next to eachother, one of which was person X with actual profession X, and the other two claimed to be (and could have a different profession or something). The point was, you could only try to figure out who was being dishonest by figuring out which one lied, through sweat, slight disruption in speech and so on. Computers don't hesitate.
So, any scheme will be flawed. It either requires an existing connection between sender and receiver (which is not safe, proof by inverse induction) or is susceptible to MITM. Since you have an inverted base case, your induction case is also inverted and thus true (since you can't get the first connection safe, you can't get any subsequent connection safe).
1. The north pole is defined by magnetic north. If the magnetic north shifts, so does the north pole. It isn't moving south because it's the definition of north.
2. Even if you interpreted it as the author intended, Siberia is not south of the US. It's to the west, east or north (through the north pole is the shorter route), but not to the south.
Slashdot Mirror
For the record, example:
2^15-1 is composite, because 15 is composite:
15 = 3 * 5
2^15-1 = 111111111111111 binary, equals 11111 * 10000100001, equals 111 * 1001001001001. In decimal, that's 32767 = 31 * 1057 = 7 * 4681.
Can you do a googolplex?
Want another? A number that could be a mersenne prime cannot be one if the exponent isn't a prime also.
... ... ... ...
;)
Proof: For every number with a non-prime exponent E, take two possible factors that compose E as K and F. Now:
11111...111 (F 1's behind each other) times 10000...(F-1 zeroes)...000010000...(F-1 zeroes)...000010000...(F-1 zeroes)...000001 with K-1 times the repeat (and thus K ones) will equal the candidate number.
You can also prove it more mathematically:
sum from (I = 0) to (K-1) over (2^F-1) * 2^(I*F)
Written out, the series goes:
= (2^F-1) * 2^0 + (2^F-1) * 2^F
= (2^F-1) * 1 + 2^2F - 2^F
= 2^F - 1 + 2^2F - 2^F
= 2^2F - 1
= 2^(F*K)
= 2^E
Hope you enjoyed it
That's not prime. Its an even number of ones, which is trivially breakable into:
111111111.................11111111 (5*10^299 ones) * 100000......00000001 (with 5*10^299 - 1 zeroes).
Do I get a nobel prize now?
You just get more when rooting with a larger prime... Formulae like big primes...
(cleverly avoiding girl jokes by completely forgetting about them)
Monday, December 19, 2005 - 11:39 AM, (135 Reads)
In issue 75 of Linux Format, on the shelves now, we have an interview with Perl king Larry Wall. Here are a few of the questions we asked Larry, along with his answers:
LXF: Did you leave O'Reilly after the dotcom boom was ending, when people stopped buying books so much?
Larry Wall: O'Reilly had run into really tough times because of the plunge in book sales, which was already starting before 9/11 but very much accelerated at that point. So I knew that I was... that I was one of their fluffier employees from a standpoint of their core business, so I was not at all surprised to get laid off. People sometimes say, "Well aren't you angry at Tim O'Reilly for laying you off?" and I say, "No, you don't understand."
The years that he hired me he essentially paid me to do what I want to do. He essentially gave me a scholarship for those years, and I'm completely grateful for that, for what he was able to do, and so that's my feeling about Tim O'Reilly. I'm on very good terms with him.
LXF: What do you find particularly excites you about Perl 6 - apart from the idea of finishing it!
LW: I think it would have to be the parts that are designed to evolve faster even than Perl 5 could evolve. Perl has always been somewhat about evolvability. That's partly why we have sigils [$, @, %] on the front of our variables, so they are often in separate name spaces from the verbs. And we added a lot of extensibility to Perl 5, which was why we ended up with the CPAN, which is the envy of all the other languages.
Nevertheless, there were many ways in which Perl 5 was running into its limits, and these were both syntactic limits and semantic limits. We had ways of mutating the language, but only very crudely. We had a mechanism called source filters, but the trouble is that the granularity was far too large, because it was from here to the end of the script. You could filter through a filter, and that meant that every source filter had to reparse Perl to do anything with it. You couldn't stack them, because they would interfere with each other.
In Perl 6 we actually give the programmer control over the individual grammar rules and even sub-rules, so that you can replace little bits and pieces of the grammar. It's a kind of encapsulation, in the sense that you're only changing the parts that you are concerned about in a way that does not influence the rest of the grammar. This lets different kinds of grammatical mutability sneak into the language, and lets people experiment with different syntaxes and different ways of attaching those syntaxes to new kinds of semantics. And then we can have a lovely Darwinian gene pool that will pick the winners and also pick the losers, and that will contribute to the evolvability of Perl 6.
Part of the new evolvability design is the notion that we need better control over interface versions, so that different modules can for instance have requirements on other modules, and if two modules require the same module but happen to require different versions of that module, those can both coexist. Unless of course those two modules require some kind of exclusive access to a resource that cannot be shared. They'll have to negotiate then.
When I say, "Use module::dog" I get Fido version 1 and when he says "Use module::dog" he gets Fido version 2. But in either case a lexically scoped alias of dog means this in my particular case. And beyond that, perhaps [we can] even provide mechanisms so that modules themselves can be polymorphic with respect to their own version numbers. So you can say, "Yes, I know I'm pulling in version 2 but I know that you know how to emulate version 1. And I have to stick with version 1. Or maybe that's implicit: you say: " I want version 1, you might get version 1 or you might get version 2 emulating version 1". So we allow modules to then mutate their interface and their set of semantics over time, and yet have a way to identify a certain set of semantics that can be locked
The point behind a mersenne prime is that, in binary, it's always like this:
1 1
111111111111111111.................11111111111111
They differ only in the number of ones. The point why they are mersenne primes is BECAUSE they have this property. Since these numbers are relatively often prime, it's a lame (*cough*, ok, cheap) way to get to very large prime numbers.
So, all you have to store to know the number is the number of binary digits. Conveniently, that's the exponent in power-of-2 notation.
You can write down the exponent in 4 bytes, I sure hope. If you want to type it out in notepad, try using the notation I provided. It fits in 15 bytes with ease.
Well... the server is at mersenne.org. I somehow expect them to have found a mersenne prime, which with 10 million digits takes about 15 bytes to store in plain-text, and only 4 if you store it efficiently:
2^35000000-1 => that's in normal form. You only have to store the exponent, the rest is constant. Since it's smaller than 4294967296 you can store it in a normal int (4 bytes), and since it's larger than 16777216 you can't store it in 3 bytes.
Finding common divisors is usually done with the formula of Euclides. That brings it down to iirc the log of the number, which is just 10000000.
A very good (but not perfect) sieve for primes with no false negatives is the Lucas-Lehmer primality test. I expect them to use that for first selection runs.
For a full certainty, the only cause (I think) you have is to repetitively try to divide it by another and figuring out you keep stuff left. I am quite certain they're using distributed computing for that.
Their computers can calculate a prime number with 10,000,000 digits, but they can't even serve a webpage? Jeez... where are your priorities?
You swapped two words: Now we have to hope that [b]Windows Vista[/b] comes out in time for [b]quantum computing[/b].
I can definately say that the process isn't like that with my employer. First solicitation for me and I was hired straight away.
Microsoft is for those years:
1985 - Release of Windows 1.0, after a long period of waiting.
1995 - Release of Windows '95, after a long period of waiting.
2005 - Well... We're still waiting after all...
Lesson 1 in forensics: Secure the data carriers as read-only devices so you don't mess it up more than you already did. Common advice is to pull the plug (don't shut down properly) to make sure the shutdown process doesn't wreck anything.
Lesson 2: Making sure the computer doesn't know what you did anymore requires using a method to destroy the physical harddisk. There is almost no software method secure enough to make it actually impossible. Try Mt Doom, a forge or a sledgehammer.
Practical advice for your particular case: Make a full copy of the disk, making sure it isn't mounted by the OS as a coincidence (IE: don't use windows, use linux or a unix only after making sure it doesn't mount it etc). Get a license of actual forensic software that can rip apart the system restore files (if pre-sp2 it's better since they store all link files to documents you use as well, if after that's sorry, but you can still get a lot of information from it) and the IE logs. You also want the system logs plus a capable viewer and if possible, the registry. Also, get a full searchable and indexed list of all files on the disk plus the information stored with them in the form of access dates etc. Using NTFS is a small plus, since it keeps time in 100-nanosecond intervals (so, it's more like dependant on the accuracy of your system clock) as opposed to FAT(12/16/32) which uses 2-second intervals.
If you need more help, please do ask.
No, that's after the court sues.
67 million degenerates to about 4500 people buying the DVD, around 15000 seeing it in the cinema and 668 people ripping their own copy to the net, now being forced to pay $100.000 each. That adds up to 4500 * $22 + 15000 * $7 + 668 * $100.000 = $67M.
I've stopped playing a simulated race game more than once, then to get in my real car and to be amazed by the light rendering, the very good anti-aliasing, bump mapping and the incredible polygon rate. Also, the accuracy of skidding was completely incredible...
Sadly, the price of new tires was also incredible.
- Take the file, determine (guess) the header size
- Note a bunch of values in hex, BCD and binary that could be useful. If it's an ancient Unix file, add octal notation. These things include the header size guess, the file size, a guess of an average content size etc.
- Guess what the values could mean, taking note of offsets.
- Try to fish out stuff behind the header by looking at repetitions, and determine block structure for those blocks. Determine how to find them from the header (jumping through headers, constant offset, encoded offset)
- When you can't find a direct relation, try with a constant offset from the found address. Microsoft (yep, I've been doing some myself in the past) used to love a 20 byte offset in the pointers.
- Deconstruct the entire file that way, recursively
- Know existing filetypes, preferably by heart. When you see 0xFF 0xC0, you should know that it's possibly a JPEG header. Same for text "GIF89a", bitmap headers and so on. For Microsoft embedded JPEGs, also expect 0xFF 0xD1 and RGB encoded JPG's (yes, that's horror. All things that may be named
- Write down your guesses multiple times, use markers and a laser printer, and don't mind the looks on your co-workers if they see you pondering over a hex output for over an hour.
We are sorry to report that your XBox 360 crashed during the final race online of the world online championship of World Rally Cup 2006 V3. Would you like to play Patience, Minesweeper or Reboot?
VI is still at 6, and that in the roman period.
Emacs is at least at 22...
Go ahead, mod me down.
The numbers rate how much hardware you sell, not how much hot air.
If you sell hot air in the US, do you have to add a warning: "Warning - contents may be hot" to it?
I was hoping for a nice technical article for once, that would illustrate how to make your own search engine and how to make it fast on indexing and searching through millions of pages.
Of course, I was wrong.
The only game I've wanted to buy in the past 3 years was Locomotion, and that went out of sale around here because nobody seemed to agree with me. It dropped from 50 euro to 15 within a few weeks, and then it appears to have just vanished when I tried to buy it. Aside from that, my recent game buys include C&C 2, Red Alert (re-buy, I lost one cd of my original copy (which I've bought for 99 guilders when it was first out, that's like 50 euros)) 1, C&C1, Diablo and Diablo 2. Games I want to buy are Locomotion (still...) and Diablo 2 : LoD. Oh, and Fallout 2, but that seems to have not been on sale for quite some time.
Screw off with all those new-fangled games that work like crap compared to old games. They've lost their replay values so I'm not going to buy 50 euros for a single shot of fun.
> frustration publishers have with second-hand game sales.
If you'd make a DECENT GAME to start with, I wouldn't want to sell it.
There are two basic facts underlying encryption:
- Anything you can do, an attacker can do as well.
So, ANY possible scheme that does not have centralized control will be flawed, since I can do anything you can and can thus claim I'm you. The only way to show you're not me is by showing something that differs you from me. By showing something that differs, you know that there are two people claiming to be X. Which is real?
The fact is so basic that there were even game shows about it. "Who in the three" was based on three people sitting next to eachother, one of which was person X with actual profession X, and the other two claimed to be (and could have a different profession or something). The point was, you could only try to figure out who was being dishonest by figuring out which one lied, through sweat, slight disruption in speech and so on. Computers don't hesitate.
So, any scheme will be flawed. It either requires an existing connection between sender and receiver (which is not safe, proof by inverse induction) or is susceptible to MITM. Since you have an inverted base case, your induction case is also inverted and thus true (since you can't get the first connection safe, you can't get any subsequent connection safe).
Guess what a key signing party is for?
1. The north pole is defined by magnetic north. If the magnetic north shifts, so does the north pole. It isn't moving south because it's the definition of north.
2. Even if you interpreted it as the author intended, Siberia is not south of the US. It's to the west, east or north (through the north pole is the shorter route), but not to the south.