Background: #bbbbff
Foreground: #000
PrimaryPale: #FF8C69
PrimaryLight: #cc66ff
PrimaryMid: #440044
PrimaryDark: #410
SecondaryPale: #ffc
SecondaryLight: #fe8
SecondaryMid: #db4
SecondaryDark: #002244
TertiaryPale: #99aacc
TertiaryLight: #aaaaff
TertiaryMid: #000
TertiaryDark: #8B7355
Cryptography has a fascinating history. Here is a brief summary. For more info, read [[here|http://en.wikipedia.org/wiki/Cryptography]].
!One Key, Two Methods
From ancient Greeks and Romans up to World Wars I and II, everybody assumed that only one type of encryption/decryption is possible: ''symmetric-key cryptography'' -- a cipher with only 1 single key, and 2 methods (encrypt/decrypt) that undo each other. Putting in steps:
# ''//Somehow//'' A and B each holds the same key.
# A puts message in a box, locks by the key, and sends to B.
# B receives the box, unlocks by the key, reads the message from A.
# ''//Assumption//'': without the key, the box cannot be unlocked.
This works good if ''//assumption//'' is OK, and ''//somehow//'' can be worked out. Let's examine each in turn.
The ''//assumption//'' believes in the existence of ''unbreakable cipher''. The skill of [[lock-picking|http://en.wikipedia.org/wiki/Lock_picking]] implies this is doubtful. Surely you can make the lock (or cipher) very complicated, thus giving the lock-pickers (or codebreakers) a challenge, but this is a cat-and-mouse chase. During WWII the Germans used a mechanical device with complicated connections (the [[Enigma|http://en.wikipedia.org/wiki/Enigma_machine]]) to encrypt all military messages, assuming that no human can ever break their code. They were right: no human effort could -- but the British recruited a brilliant mathematician Alan Turing who eventually deduced how the Enigma works, and constructed an electronic machine (non-human) to break the code -- here is the [[story|http://www.pbs.org/wgbh/nova/decoding/]].
The ''//somehow//'' is technically known as the ''[[Key Distribution Problem|http://en.wikipedia.org/wiki/Key_distribution]]'': how do A and B get the same key at the beginning? For example, the ATM card pin number is a form of symmetric-key cryptography: you key in the PIN to identify yourself, and the bank uses the PIN to verify you. But how did the bank send you the PIN? Perhaps by registered mail -- safe enough? The German military changed their Enigma keys almost everyday, resulting in some keys being reused -- a loophole exploited by the British codebreakers.
For a cipher, the encrypt and decrypt methods are mechanical, never-changing, and applied repeatedly -- so their secrets cannot be kept for too long. Thus the job of codebreakers is to deduce the key from whatever information available. A good cipher leaks very few or no information, so the only hope for a codebreaker is: //try ''every'' key// -- similar to trying every permutation for a combination-lock. Therefore the strength of ''symmetric-key cipher'' depends on the size of ''key space'': how many key permutations are there?
If the key space is ''//infinite//'', the cipher will be ''//unbreakable//''. This is the case for [[one-time pad|http://en.wikipedia.org/wiki/One-time_pad]], which uses, effectively, an infinitely long random key. This is proven to be truly unbreakable (by mathematician Claude Shannon in 1945), but the key distribution problem is the worst: how do A and B agree on an infinitely long random key? For the spies before the age of computers, each gets a palm-size notepad with pages and pages of random digits. Each page is a ''pad''. Upon receiving an encrypted message of length n, the first n random digits are used to decrypt the message. These n digits will be crossed out, and the next message of length m will use the next m random digits. When all digits of a page have been crossed out, the page is simply burnt away -- hence ''one-time pad''. Nowadays spies can simply store the pad in ~USB-drives.
!One Method, Two Keys
Modern cryptography arises from the discovery of ''asymmetric-key cryptography'' (also called ''public-key cryptography''): a cipher with only 1 method, but 2 keys (public/private) that are inverses of each other. Putting in steps:
# B sends A the public key ''e'' with no encryption -- anyone can read ''e'', e.g. via [[SSL Certificate]].
# A applies key ''e'' to the message through a known method, sends to B -- anyone can google the method, e.g. [[RSA|Key pairs for RSA]].
# B applies the private key ''d'' to the received message with the same method, recovers the original.
# ''//Assumption//'': Someone who knows the method and public key ''e'' still cannot deduce the private key ''d''.
Thus the ''asymmetric-key cryptography'' require no key distribution, a big advantage over ''symmetric-key cryptography''. However, it relies on one ''//assumption//'', also known as the ''Trapdoor property'' or ''One-way function''. About this assumption:
* it is not ''//strictly//'' true: for ''RSA'' method using modulus ''n'', it is mathematically possible to compute ''d'' from ''e'' if the prime factorization of ''n'' is known.
* it is ''//almost//'' true: for ''RSA'', factorization of ''n'', usually a 1024-bit binary number, is impractical for any super-computers with known methods.
In 1994, a mathematician at MIT, Peter Shor, found a fast [[integer factorization algorithm|http://en.wikipedia.org/wiki/Shor%27s_algorithm]] which, in theory, can break the ''RSA''. However, the algorithm relies on massive parallel computations that can only be realized on ''//quantum computer//''. Lucky for ''RSA'', no one has the slightest idea of how to start building a quantum computer.
!More Info
Beyond Discovery: The Code War
http://www.beyonddiscovery.org/content/view.asp?I=3420
We are looking at the equation: ''x = x#e#d'' with operation ''#'' replaced by addition modulo ''n'': ''+'' under ''mod n''. That is:
''x = x + e + d (mod n)''
Given a modulus ''n'', can we find a pair of public key ''e'' and private key ''d'' to satisfy this equation?
!Additive Inverses
Anyone who knows about modular arithmetic can answer this question: yes. Because the equation implies:
''0 = e + d (mod n)'', so ''d = -e (mod n) = n - e''.
In fact, the remainders under modular addition forms a group ''(Z/n,+)''. Therefore, given modulus ''n'', any remainder in the range 1,2,...,(n-1) can be ''e'', then ''d=n-e'', the ''additive inverse'' of ''e'' (mod ''n'').
For example, taking modulus ''n=6'', picking ''e=1'', then ''d=5'':
|!Possible data for modulus 6|!Encrypt by +1 (mod 6)|!Decrypt by +5 (mod 6)|
|0|0+1=1|1+5=6=0|
|1|1+1=2|2+5=7=1|
|2|2+1=3|3+5=8=2|
|3|3+1=4|4+5=9=3|
|4|4+1=5|5+5=10=4|
|5|5+1=6=0|0+5=5|
|''Encryption and Decryption in Cyclic Add modulo 6''|c
!Is This Secure?
Since ''Encrypt by +e (mod n)'' is made public, the private key ''d=n-e'' can be easily computed. This method of encryption and decryption is not secure at all.
Historically, this cyclic add method is used in cryptography by keeping everything secret: ''e'' and ''n'' are known only to the sender, perhaps through a face-to-face meeting with the receiver. For example, the ''Caesar Cipher'' just encrypts by shifting each alphabet by 1 unit, and decrypts by shifting back:
|!Message|!Encrypt|!Decrypt|
|~AttackAtDawn|~BuubdlBuEbxo|~AttackatDawn|
|''Caesar Cipher''|c
I guess even you can crack this type of code without much effort.
We are looking at the equation: ''x = x#e#d'' with operation ''#'' replaced by exponentiation modulo ''n'': ''^'' under ''mod n''. That is:
''x = x ^ e ^ d (mod n)'' or ''x = (x^^e^^)^^d^^ (mod n)'' or ''x = x^^(e*d)^^ (mod n)''
Given a modulus ''n'', can we find a pair of public key ''e'' and private key ''d'' to satisfy this equation?
In general, the arithmetics of modulo ''n'' forms a [[Ring|Group, Ring and Field]] ''(Z/n,+,*)'': only addition is nice, multiplication is bad. We cannot even cancel ''x'' on both sides of the equation. So we must turn our attention to specific modulus n.
!Exponent Inverses for Modulo Prime
If the modulus is a prime ''p'', then ''(Z/p,+,*)'' is a [[Field|Group, Ring and Field]]. In particular, the nonzero remainders under multiplication is a group: ''(Z/p^^*^^,*)''. Also, we have ''Fermat's Little Theorem'':
For prime ''p'', ''a^^p^^=a (mod p)'' for any remainder ''a''.
So all we need is to solve: ''e*d = p''. Since ''p'' is prime, this implies ''e=1 and d=p'', or ''e=p and d=1''. These keys are useless for encryption and decryption.
All hope is not lost -- we just need to think harder. ''Fermat's Little Theorem'' can also be written as:
For prime ''p'', ''a^^(p-1)^^=1 (mod p)'' for any remainder ''a''.
This is because ''(Z/p^^*^^,*)'' is a group, and cancellation is allowed. This also implies:
''(a^^(p-1)^^)^^k^^=1^^k^^=1 (mod p)'' for any integer ''k''
or ''a^^[k*(p-1)]^^=1 (mod p)''
or ''a^^[k*(p-1)+1]^^=a (mod p)''
Now we need to solve: ''e*d = k*(p-1)+1'', or ''e*d - k*(p-1) = 1''. Upon seeing this, a math expert will say: choose e relatively prime to (p-1) -- because any common divisor of ''e'' and ''(p-1)'' must also divide ''e*d - k*(p-1)'', which is 1.
Therefore, given prime modulus ''p'', any ''e'' relatively prime to ''(p-1)'' will do, and d=e^^-1^^ (mod (p-1)), the multiplicative inverse of ''e'' in ''mod (p-1)''.
For example, taking prime modulus ''p=11'', then (p-1)=10, so pick ''e=3'' which relatively prime to 10, and ''d=7'' because 3*7=21=1 (mod 10).
|!Possible data for modulus 11|!Encrypt by ^3 (mod 11)|!Decrypt by ^7 (mod 11)|
|1|1^^3^^=1|1^^7^^=1|
|2|2^^3^^=8|8^^7^^=(8*8)^^3^^*8=(64)^^3^^*8=(9)^^3^^*8=(-2)^^3^^*8=-64=2 (mod 11)|
|3|3^^3^^=27=5|5^^7^^=(5*5)^^3^^*5=(3)^^3^^*5=(5)*5=25=3 (mod 11)|
|4|4^^3^^=16*4=5*4=20=9|9^^7^^=(9*9)^^3^^*9=(4)^^3^^*9=16*36=(5)*(3)=15=4 (mod 11)|
|5|5^^3^^=25*5=3*5=15=4|4^^7^^=(4*4)^^3^^*4=(5)^^3^^*4=25*20=(3)*(-2)=-6=5 (mod 11)|
|''Encryption and Decryption in Cyclic Exponent modulo 11''|c
!Is This Secure?
Since ''Encrypt by ^e (mod p)'' is made public, the private key ''d=e^^-1^^ mod (p-1)'' can be computed, at least by number theorists -- or as clever as Euler, see recipe below. This method of encryption and decryption is hopeful, but still not secure enough for bank transactions.
!Computing Multiplicative Inverse
For a prime modulus ''p'', the multiplicative inverse can be computed via help from ''Fermat's Little Theorem'': ''a^^p^^=a (mod p)''.
However, the key pair above are related by: ''e*d = 1 (mod p-1)'', and (p-1) is not prime when p is prime.
Is there a similar little theorem in non-prime modulus?
Euler proved the little theorem in 1736, and in 1760 he found its generalization, now called ''Euler's Theorem'':
For any modulus ''n'', ''a^^φ(n)^^=1 (mod n)'' for remainder ''a relatively prime to n'' .
The ''Euler phi-function'': ''φ(n)'' = number of remainders relatively prime to n.
When the modulus ''n'' is a prime ''p'', ''φ(p) = p-1'' since all the number 1,2,...(p-1) cannot divide a prime p, thus giving ''Fermat's Little Theorem'':
For prime modulus ''p'', ''a^^(p-1)^^=1 (mod p)'' for any remainder ''a''.
|!n|!Remainders relatively prime to n|!φ(n)|
|2|1|1|
|3|1,2|2|
|4|1,3|2|
|5|1,2,3,4|4|
|6|1,5|2|
|7|1,2,3,4,5,6|6|
|8|1,3,5,7|4|
|9|1,2,4,5,7,8|6|
|10|1,3,7,9|4|
|''Euler's phi-function φ(n)''|c
''Euler's Theorem'' can be re-written as: ''a*a^^(φ(n)-1)^^=1 (mod n)'' for ''a'' relatively prime to ''n''.
This gives an explicit formula for the multiplicative inverse of e mod (p-1): ''d = e^^(φ(p-1)-1)^^ (mod p-1)''.
|!prime modulus p|!p-1|!Possible e for encrypt|!φ(p-1)|!Compute d for decrypt|!Verify: e*d = 1 (mod p-1)|
|5|4|3|2|3^^(2-1)^^=3^^1^^=3 (mod 4)|3*3=9=1 (mod 4)|
|7|6|5|2|5^^(2-1)^^=5^^1^^=5 (mod 6)|5*5=25=1 (mod 6)|
|11|10|3|4|3^^(4-1)^^=3^^3^^=27=7 (mod 10)|3*7=21=1 (mod 10)|
|13|12|7|4|7^^(4-1)^^=7^^3^^=(49)*7=(1)*7=7 (mod 12)|7*7=48=1 (mod 12)|
We are looking at the equation: ''x = x#e#d'' with operation ''#'' replaced by multiplication modulo ''n'': ''*'' under ''mod n''. That is:
''x = x * e * d (mod n)''
Given a modulus ''n'', can we find a pair of public key ''e'' and private key ''d'' to satisfy this equation?
!Multiplicative Inverses
If you know about modular arithmetic, let's see what the equation implies. First you can only cancel ''x'' on both sides if multiplication in ''mod n'' forms a group -- this is the case only when the modulus is ''prime'', see [[Group, Ring and Field]].
Taking a prime modulus ''p'', the nonzero remainders of modulus p under multiplication forms a group ''(Z/p^^*^^,*)''. We can cancel ''x'' on both sides to obtain:
''1 = e * d (mod p)'', which means ''d'' is the multiplicative inverse of ''e'' in ''Z/p^^*^^'' (in a group, inverse always exists).
Therefore, given prime modulus ''p'', any remainder in the range 1,2,...,(p-1) can be ''e'', then ''d=e^^-1^^'', the ''multiplicative inverse'' of ''e'' (mod ''p'').
For example, taking prime modulus ''n=7'', pick ''e=3'', then ''d=5'', because 3*5=15=1 (mod 7):
|!Possible data for modulus 7|!Encrypt by *3 (mod 7)|!Decrypt by *5 (mod 7)|
|1|1*3=3|3*5=15=1|
|2|2*3=6|6*5=30=2|
|3|3*3=9=2|2*5=10=3|
|4|4*3=12=5|5*5=25=4|
|5|5*3=15=1|1*5=5|
|''Encryption and Decryption in Cyclic Multiply modulo 7''|c
!Is This Secure?
Since ''Encrypt by *e (mod p)'' is made public, the private key ''d=e^^-1^^ (mod p)'' can be computed, at least by those who have studied group theory -- or as clever as Fermat, see the recipe below. This method of encryption and decryption is probably secure for kids, but certainly not for bank transactions!
!Computing Multiplicative Inverse
Around 1640, Pierre de Fermat discovered this surprising result in modular multiplication:
If ''p'' is a prime, ''a^^p^^ = a (mod p)'' for any remainder ''a''.
This shows repeated multiplication, or exponentiation, in modular arithmetic is quite interesting: with a prime modulus ''p'', if you multiply any remainder by itself repeatedly for p times, you'll get back the original remainder!
Since ''Z/p^^*^^'' is a group under modular multiplication, we can cancel one ''a'' on both sides, giving:
''a^^(p-1)^^ = 1 (mod p)''
This is usually called ''Fermat's Little Theorem''. Since all prime p > 1, we can further write:
''a*a^^(p-2)^^ = 1 (mod p)''
which gives an explicit formula for the multiplicative inverse of a mod p.
Therefore, by the little theorem, the formula for private key is: ''d = e^^(p-2)^^ (mod p)''.
|!prime modulus p|!Possible e for encrypt|!Compute d for decrypt|!Verify: e*d = 1 (mod p)|
|5|3|3^^(5-2)^^=3^^3^^=3*3*3=(9)*3=(4)*3=12=2 (mod 5)|3*2=6=1 (mod 5)|
|7|3|3^^(7-2)^^=3^^5^^=(3*3)^^2^^*3=(9)^^2^^*3=(2)^^2^^*3=4*3=12=5 (mod 7)|3*5=15=1 (mod 7)|
|7|4|4^^(7-2)^^=4^^5^^=(4*4)^^2^^*4=(16)^^2^^*4=(2)^^2^^*4=4*4=16=2 (mod 7)|4*2=8=1 (mod 7)|
|11|5|5^^(11-2)^^=5^^9^^=(5*5)^^4^^*5=(25)^^4^^*5=(3)^^4^^*5=81*5=4*5=20=9 (mod 11)|5*9=45=1 (mod 11)|
|11|7|7^^(11-2)^^=7^^9^^=(7*7)^^4^^*7=(49)^^4^^*5=(5)^^4^^*7=(3)^^2^^*7=63=8 (mod 11)|7*8=56=1 (mod 11)|
This ''Little Theorem'' was stated in a letter from Fermat to the amateur mathematician Frenicle de Bessy dated October 1640. No proof was provided. The first proof was given by Euler in 1736, almost a century after Fermat's announcement. Leibniz had given an identical proof in an unpublished work about 50 years prior to Euler's. Eleven years later in 1747, Euler will give another proof of the same theorem.
/***
|!''Name:''|!''E''asily ''A''daptable ''S''ource ''E''ditor|
|''Description:''|this framework allows you to easily create commands that work on the current tiddler text selection in edit mode|
|''Version:''|0.1.0|
|''Date:''|13/01/2007|
|''Source:''|http://yann.perrin.googlepages.com/twkd.html#E.A.S.E|
|''Author:''|[[Yann Perrin|YannPerrin]]|
|''License:''|[[BSD open source license]]|
|''~CoreVersion:''|2.x|
|''Browser:''|Firefox 1.0.4+; Firefox 1.5; InternetExplorer 6.0|
***/
////Messages Definition
//{{{
config.messages.Ease = {
noselection:"nothing selected",
asktitle:"enter the new tiddler title",
exists:" already exists, please enter another title",
askForTagsLabel:"enter the new tiddler tags",
tiddlercreated:" tiddler created"
}
//}}}
////
//{{{
if (!window.TWkd) window.TWkd={context:{}};
if (!TWkd.Ease)
TWkd.Ease = function (text,tooltip){
this.text = text;
this.tooltip = tooltip;
this.modes = [];
this.addMode = function(modeDefinition) {this.modes.push(modeDefinition);};
this.handler = function(event,src,title) {
TWkd.context.command = this;
TWkd.context.selection=this.getSelection(title);
if (this.modes.length==1) {
this.modes[0].operation();
}
else {
var popup = Popup.create(src);
if(popup) {
for (var i=0; i<this.modes.length; i++) {
createTiddlyButton(createTiddlyElement(popup,"li"), this.modes[i].name, this.modes[i].tooltip, this.OperateFromButton, null, 'id'+i, null);
}
Popup.show(popup,false);
event.cancelBubble = true;
if (event.stopPropagation) event.stopPropagation();
return false;
}
}
};
};
TWkd.Ease.prototype.OperateFromButton = function(e){
var commandMode=this.getAttribute('Id').replace('id','');
TWkd.context.command.modes[commandMode].operation();
};
TWkd.Ease.prototype.getTiddlerEditField = function(title,field){
var tiddler = document.getElementById(story.idPrefix + title);
if(tiddler != null){
var children = tiddler.getElementsByTagName("*")
var e = null;
for (var t=0; t<children.length; t++){
var c = children[t];
if(c.tagName.toLowerCase() == "input" || c.tagName.toLowerCase() == "textarea"){
if(!e) {e = c;}
if(c.getAttribute("edit") == field){e = c;}
}
}
if(e){return e;}
}
} // closes getTiddlerEditField function definition
TWkd.Ease.prototype.getSelection = function(title,quiet) {
var tiddlerTextArea = this.getTiddlerEditField(title,"text");
var result = {};
if (document.selection != null && tiddlerTextArea.selectionStart == null) {
tiddlerTextArea.focus();
var range = document.selection.createRange();
var bookmark = range.getBookmark();
var contents = tiddlerTextArea.value;
var originalContents = contents;
var marker = "##SELECTION_MARKER_" + Math.random() + "##";
while(contents.indexOf(marker) != -1) {
marker = "##SELECTION_MARKER_" + Math.random() + "##";
}
var selection = range.text;
range.text = marker + range.text + marker;
contents = tiddlerTextArea.value;
result.start = contents.indexOf(marker);
contents = contents.replace(marker, "");
result.end = contents.indexOf(marker);
tiddlerTextArea.value = originalContents;
range.moveToBookmark(bookmark);
range.select();
}
else {
result.start=tiddlerTextArea.selectionStart;
result.end=tiddlerTextArea.selectionEnd;
}
result.content=tiddlerTextArea.value.substring(result.start,result.end);
result.source=title;
if (!result.content&&!quiet) displayMessage(config.messages.Ease.noselection);
return(result);
}//closes getSelection function definition
// replace selection or insert new content
TWkd.Ease.prototype.putInPlace=function(content,workplace) {
var tiddlerText = this.getTiddlerEditField(workplace.source,"text");
tiddlerText.value = tiddlerText.value.substring(0,workplace.start)+content+tiddlerText.value.substring(workplace.end);
}
// asking for title
TWkd.Ease.prototype.askForTitle = function(suggestion) {
if (!suggestion)
suggestion = "";
var newtitle;
while (!newtitle||store.tiddlerExists(newtitle))
{
if (store.tiddlerExists(newtitle))
displayMessage(newtitle+config.messages.Ease.exists);
newtitle = prompt(config.messages.Ease.asktitle,suggestion);
if (newtitle==null)
{
displayMessage(config.messages.Ease.titlecancel);
return(false);
}
}
return(newtitle);
}//closes askForTitle function definition
// creation of a new tiddler
TWkd.Ease.prototype.newTWkdLibTiddler = function(title,content,from,askForTags){
var tiddler = new Tiddler();
tiddler.title = title;
tiddler.modifier = config.options.txtUserName;
tiddler.text = content;
(from) ? tiddler.tags = [from] : tiddler.tags=[];
if (askForTags)
tiddler.tags = prompt(config.messages.Ease.askForTagsLabel,'[['+from+']]').readBracketedList();
store.addTiddler(tiddler);
//store.notifyAll();
displayMessage(title+config.messages.Ease.tiddlercreated);
}
if (!TWkd.Mode)
TWkd.Mode = function (name,tooltip,ask,operation) {
this.name = name;
this.tooltip = tooltip;
this.ask = ask;
this.operation = operation;
};
//}}}
Based on this fact:
If the odd number ''2^^n^^+1'' is prime, then ''n=2^^k^^'', a pure even.
Pierre de Fermat (1601 – 1665) studied the following question:
Given a pure even ''2^^n^^'', will the odd number ''F~~n~~ = 2^^<html>2<sup>n</sup></html>^^+1'' be prime?
!Fermat Numbers
Fermat probably started with the following compilation:
|!n|!2^^n^^|!2^^2<html><sup>n</sup></html>^^|!F~~n~~ = 2^^<html>2<sup>n</sup></html>^^+1|!Factorization of F~~n~~|
|0| 1| 2| 3| prime F~~0~~|
|1| 2| 4| 5| prime F~~1~~|
|2| 4| 16| 17| prime F~~2~~|
|3| 8| 256| 257| prime F~~3~~|
|4| 16| 65536| 65537| prime F~~4~~|
|5| 32| 4294967296| 4294967297|??|
|''Factorization of F~~n~~ by Fermat''|c
Obviously, Fermat was stuck at F~~5~~. So he couldn't answer his question, but he made a conjecture.
!Fermat Primes
Pierre de Fermat wrote to Marin Mersenne on December 25, 1640 that:
//If I can determine the basic reason why 3, 5, 17, 257, 65537, ..., are prime numbers,
I feel that I would find very interesting results, for I have already found marvelous things [along these lines] which I will tell you about later.//
Thus Fermat asserted that all F~~n~~ are primes, although he had no proof of this.
In 1732 Euler discovered 641 divides F~~5~~. It only takes two trial divisions to find this factor because Euler showed that:
Every divisor of a Fermat number F~~n~~ with n > 2 has the form k(2^^n+2^^)+1.
In the case of F~~5~~ this is k(2^^7^^)+1 = 128k+1, so he tried 257 and 641 (129, 385, and 513 are not primes).
|!n|!2^^n^^|!F~~n~~ = 2^^<html>2<sup>n</sup></html>^^+1|!Factorization of F~~n~~|!When|!Who|
|5| 32| 4294967297|641*6700417|1732|Euler|
|6| 64| 18446744073709551617|274177*67280421310721|1880|Clausen and Landry|
|7| 128| 340282366920938463463374607431768211457|59649589127497217*5704689200685129054721|1975|Morrison and Brillhart|
With computers, it is shown that all known F~~n~~ for n > 4 are composite, although not all such F~~n~~ are completely factorized.
!Use of Fermat Primes
In 1796, the German teen prodigy Gauss made a discovery that led him to study math further:
The ''regular 17-gon'' is ''constructible'' (by ruler and compass) -- because ''17'' is a ''Fermat prime''!
This is a surprising connection of Fermat primes with geometric constructions. Indeed, what Gauss discovered was more general:
If the Fermat number ''F~~n~~'' is ''prime'', then the ''regular F~~n~~-gon'' can be constructed by ruler and compass.
From this Gauss claimed that:
A ''regular n-gon'' is constructible by ruler and compass if and only if the odd factors of ''n'' are distinct ''Fermat primes''.
However, Gauss only gave the proof for the ''if''-part -- perhaps the ''only-if'' part was left as an exercise. The ''only-if'' part was completed by Wantzel in 1837.
Why? The connection between Fermat primes and geometric constructions belongs to Galois' group theory. Indeed, the group structure of the roots of the equation ''x^^n^^ = 1'' determines its solvability, which is related to ruler and compass constructions.
|!n|!regular n-gon|!Factorization of n|!ruler and compass construction possible?|!Comment|
|3| equilateral triangle| 3 = F~~0~~|yes|known to Greeks|
|4| square| 4 = 2^^2^^|yes|no odd factor|
|5| regular pentagon| 5 = F~~1~~|yes|known to Greeks|
|6| regular hexagon| 6 = 2 F~~0~~|yes|known to Greeks|
|7| regular 7-gon| 7 is prime| no|known to Greeks, but not why|
|8| regular 8-gon| 8 = 2^^3^^|yes|no odd factor|
|9| regular 9-gon| 9 = F~~0~~^^2^^| no|not distinct Fermat primes|
|10| regular 10-gon| 10 = 2 F~~1~~|yes||
|11| regular 11-gon| 11 is prime| no|Greeks didn't know why|
|12| regular 12-gon| 12 = 4 F~~0~~|yes||
|13| regular 13-gon| 13 is prime| no|Greeks didn't know why|
|14| regular 14-gon| 14 = 2*7| no||
|15| regular 15-gon| 15 = F~~0~~F~~1~~|yes|distinct Fermat primes|
|16| regular 16-gon| 16 = 2^^4^^|yes|no odd factor|
|17| regular 17-gon| 17 = F~~2~~|yes|Gauss 1732|
|''Ruler and Compass construction of Regular n-gons''|c
Factoring Fermat numbers is extremely difficult as a result of their large size. This advances the study of primality testing and factorization of special forms.
!Use of Fermat Numbers
Current evidence is that: of the Fermat numbers ''F~~n~~=2^^<html>2<sup>n</sup></html>^^+1'', only F~~0~~, F~~1~~, F~~2~~, F~~3~~, F~~4~~ are primes, all F~~n~~ with n > 4 are composite. However, even when F~~n~~ are composite, they are still useful -- they can tell something about primes.
Observe the following pattern of factorization (repeated use of difference of squares) and its relationship with Fermat numbers:
|!Factorization|!Putting x=2|
|x^^2^^-1 = (x-1)(x+1)|2^^2^^-1=F~~0~~|
|x^^4^^-1 = (x^^2^^-1)(x^^2^^+1)=(x-1)(x+1)(x^^2^^+1)|2^^4^^-1=F~~0~~F~~1~~|
|x^^8^^-1 = (x^^4^^-1)(x^^4^^+1)=(x^^2^^-1)(x^^2^^+1)(x^^4^^+1)=(x-1)(x+1)(x^^2^^+1)(x^^4^^+1)|2^^8^^-1=F~~0~~F~~1~~F~~2~~|
|x^^16^^-1 = (x^^8^^-1)(x^^8^^+1)=...=(x-1)(x+1)(x^^2^^+1)(x^^4^^+1)(x^^8^^+1)|2^^16^^-1=F~~0~~F~~1~~F~~2~~F~~3~~|
|x^^32^^-1 = (x^^16^^-1)(x^^16^^+1)=...=(x-1)(x+1)(x^^2^^+1)(x^^4^^+1)(x^^8^^+1)(x^^16^^+1)|2^^32^^-1=F~~0~~F~~1~~F~~2~~F~~3~~F~~4~~|
|x^^64^^-1 = (x^^32^^-1)(x^^32^^+1)=...=(x-1)(x+1)(x^^2^^+1)(x^^4^^+1)(x^^8^^+1)(x^^16^^+1)(x^^32^^+1)|2^^64^^-1=F~~0~~F~~1~~F~~2~~F~~3~~F~~4~~F~~5~~|
This pattern can be continued, giving the result:
2^^<html>2<sup>n</sup></html>^^ = F~~0~~F~~1~~F~~2~~.....F~~n-1~~ + 1
This is a very spectacular result: pure even = product of pure odds + 1, since all Fermat numbers are odd. Adding 1 to both sides and re-arranging is even more revealing:
F~~n~~ - F~~0~~F~~1~~F~~2~~.....F~~n-1~~ = 2
A math expert will see this and say, "ah, no ''two'' Fermat numbers share the same ''prime'' factor!".
Why? Well, all Fermat numbers are odd. If an odd prime p divides F~~n~~ and one of its smaller Fermat numbers, p divides the left side, so p also divides the right side, which is 2. However, no odd prime p can divide 2, therefore F~~n~~ must be relatively prime to all the smaller Fermat numbers. Examination of the factorization of F~~n~~ will confirm this fact.
There are countless Fermat numbers, each with its own distinct prime factors -- hence the number of primes must be ''infinite''.
This is a sweet alternative to Euclid's proof (300 BC) of the infinite supply of primes. The strategy is similar: Euclid added 1 to the product of all smaller primes than a given prime ''p''.
!Finite Interleaving - Periodic
The normal weekdays: 1, 2, 3, 4, 5, 6, 7, ... is a cyclic sequence with ''period'' 7.
The skipping workdays: 1, 3, 5, 7, 2, 4, 6, ... is a cyclic sequence with interleaving. The ''order'' of interleave is 2, because the next term is obtained by adding 2 to the previous term, in modulo 7 arithmetic.
The Beatles has a song titled //Eight Days a Week//. In this fancy world, the weekdays are counted as: 1, 2, 3, 4, 5, 6, 7, 8, .... with ''period'' 8.
If you work one day, sleep the next day, your work-days count as: 1, 3, 5, 7, .... or 2, 4, 6, 8, ..... You'll get 2 interleaving sub-sequence of ''order'' 2, each being shorter, with ''period'' 4.
Why? Let's see. The sequence 1, 2, ...., p has ''period'' p. When interleaving with ''order'' d, starting from a, the successive terms will be: a+d, a+2d, .... If for some integer k, a+kd ≡ a (mod p), we shall end up with a sub-sequence of period k. However, this means kd ≡ 0 (mod p), or kd = pq for some q. Since this is true independent of the starting value a, the various starting values will give n sub-sequences, each with period k. This means p = nk, so n divides p. Since kd = pq = (nk)q, or d = nq, n also divides d. Therefore n is a common divisor of p, d. For the smallest period k, n is the greatest common divisor of p, d, i.e. n = gcd(p,d). It follows that the period k = p/n = p/ gcd(p,d).
Hence we have:
<<<
@@bgcolor(#9DEB95):''Finite Interleaving Theorem''@@:
For the finite sequence 1,2,...,p of ''period'' p, interleaving with ''order'' d (0 < d < p) will give ''gcd(d,p)'' sub-sequences each of period ''p/gcd(p,d)''.
<<<
!Using Prime Periods
If the period p is a ''prime'', gcd(p,d)=1 for all d (0 < d < p). In this case, interleave with any ''order'' d will give a sequence with original ''prime'' period p.
For the normal weekday sequence of period 7, interleaving with various orders gives:
|!Interleaving order|!Interleaved sequence|!Period|!Comment|
|! 1| 1,2,3,4,5,6,7,...| 7|This is the original sequence|
|! 2| 1,3,5,7,2,4,6,...| 7| next is add 2 (mod 7)|
|! 3| 1,4,7,3,6,2,5,...| 7| next is add 3 (mod 7)|
|! 4| 1,5,2,6,3,7,4,...| 7| next is add 4 (mod 7)|
|! 5| 1,6,4,2,7,5,3,...| 7| next is add 5 (mod 7)|
|! 6| 1,7,6,5,4,3,2,...| 7| next is add 6 (mod 7)|
|''Interleaving of period 7 sequence with various orders''|c
!Application of Finite Interleaving
See [[Hard Disk Interleaving]]: old-style hard-disks have 17 sectors per track.
To get started with this blank TiddlyWiki, you'll need to modify the following tiddlers:
* SiteTitle & SiteSubtitle: The title and subtitle of the site, as shown above (after saving, they will also appear in the browser title bar)
* MainMenu: The menu (usually on the left)
* DefaultTiddlers: Contains the names of the tiddlers that you want to appear when the TiddlyWiki is opened
You'll also need to enter your username for signing your edits: <<option txtUserName>>
We can't get too deep into the math, so we shall skip through, highlighting the role of prime numbers in the theory.
The last words of Évariste Galois (1811 - 1832) to his brother was, "Don't cry, Alfred! I need all my courage to die at twenty." Had he been alive today, and knowing all the development of his ideas, this is the story he would like to tell.
!Group
You know everything about adding and subtracting integers? You have no trouble solving 7+x=5 ? OK, let's summarize this knowledge about integer addition: The integers ''Z'' = { 0, ±1, ±2, ...} forms a ''Group'' under the operation ''+''.
In general, a ''Group'' is a system with one operation (say #) which is meaningful and equations are solvable:
* the operation # is meaningful if
** a#b is always inside the system (closed)
** a#b#c makes sense without brackets (associative).
* equations in the system are: a#x=b for any element a,b in the system.
** a#x=a is solvable implies the existence of identity e in the system
** a#x=e is solvable implies the existence of inverse of a in the system
While integers ''Z'' forms a group under ''+'', it doesn't form a group under ''*'': the equation 5*x=7 is not solvable in integers. For that we need to extend the integers to fractions, called rational numbers ''Q''. The non-zero elements of ''Q'', denoted by ''Q^^*^^'', forms a group under ''*''.
So we have at least two group examples: ''Z'' under ''+'', and ''Q^^*^^'' under ''*''.
!Ring
The integers ''Z'' forms a group under ''+'', but not a group under ''*'' -- is there anything good we can get from ''*''? Well, we can always multiply two integers within the system, it is only division that's worrying. Let's forget about division for now, and summarize this knowledge about integer addition and multiplication: The integers ''Z'' forms a ''Ring'' under two operations ''+'' and ''*''.
In general, a ''Ring'' is a system with two operations (say # and *) which are meaningful, one nice, and both consistent. If we call the good operation ''add'' (+), and the other operation ''multiply'' (*) -- just names, may or may not be add or multiply of numbers -- the definition can be rephrased as:
a ''Ring'' ''R'' is a system in which add, subtract and multiply can be done consistently:
* the add, subtract part means ''R'' is a group under ''+'', nice means: a+b = b+a (commutative).
* the multiply part means at least a*b and a*b*c are meaningful in ''R''.
* the consistency part means: a*(b+c) = (a*b)+(a*c), (b+c)*a = (b*a)+(c*a) hold (distributive).
The identity of ''+'' is denoted by 0, and the identity of ''*'', if exists, is denoted by 1.
!Field
Since the fractions (or rational numbers) ''Q'' include all integers ''Z'', ''Q'' surely is also a ring with ''+'' and ''*'', but it is much better: division by nonzero fraction always results in a fraction. Let's summarize this knowledge about rational addition and multiplication: The rational numbers ''Q'' forms a ''Field'' under two operations ''+'' and ''*''.
In general, a ''Field'' is a system with two operations (say + and *) which are meaningful, both nice and consistent. Or equivalently:
a ''Field'' ''F'' is a system in which add, subtract, multiply and divide can be done consistently:
* the add, subtract and nice part means ''F'' under ''+'' is a commutative group, its identity is 0.
* the multiply, divide and nice part means ''F^^*^^'' (''F'' exclude 0) under ''*'' is also a commutative group, its identity is 1.
* the consistent part means distribution of ''*'' over ''+'' is valid, i.e. ''F'' is at least a ring under ''+'' and ''*''.
Integers ''Z'' is a group under ''+'', also a ring under ''+'' and ''*''. Rationals ''Q^^*^^'' is a group under ''*'', and ''Q'' a field under ''+'' and ''*''. But integers and rationals are all infinite sets. Are there examples of group, ring and field that are finite?
!Finite Groups
Let's go back and take a look at division of integers ''Z''. It's not that bad after all -- every child learns how to divide integers.
Given two integers b and a≠0, we can use long division (or division algorithm) to obtain the quotient q and remainder r: b = q*a + r. If remainder r=0, we say a ''divides'' b, or b is ''divisible'' by a, denoted by ''a|b''. This gives rise to the concept of divisibility -- an interesting idea that leads ultimately to primes and factorization.
When a|b, i.e. a divides b, the equation a*x=b is solvable in ''Z''. Since 1*x=b always has a solution (x=b), so 1 divides any b. Since b*x=b always has a solution (x=1) b divides any b. If 1 and b are the only divisor of b, b is called a ''prime''. Breaking down any b into products (i.e. solving x*y=b) is called a ''factorization'' of b. Keep breaking down the factors we eventually reach the primes, giving b its ''prime factorization'' -- which in ''Z'' happens to be unique, up to ordering of factors and ignoring the unit 1.
What can we do about the remainders? Well, for a given integer n, the possible remainders are 0,1,...,(n-1) -- a finite set. Indeed, if we divide every element of ''Z'' by n, we have the set ''Z/n'' = {0,1,2,...,(n-1)} with n elements. Addition in ''Z'' gives a similar addition in ''Z/n'' -- when we add remainders, if the result exceeds n, we just replace the result by it remainder of division by n. This is cyclic math (or add in modulo n). Because ''Z'' is a group under ''+'', ''Z/n'' is also a group under this modulo ''+''. But this group ''(Z/n,+)'' is finite, with n elements only. It is called the ''Cyclic Group'' of order n, denoted by ''C~~n~~''.
For example, the weekdays are ''Z/7'': Sunday is day 0, Monday is day 1, etc.
!Finite Fields
Recall that ''Z'' is a ring under ''+'' and ''*''. Therefore ''Z/n'', the remainders of modulo n, is also a ring under ''+'' and ''*'', when add and multiply always keep only the remainder of division by n. This ring ''Z/n'', although finite, can be quite shocking: for example 3*4=0 (mod 6). This is because 3*4=12, and 6 divides 12. This means, as a ring, ''Z/6'' has zero divisors -- even 0 has nonzero factors! Better to avoid such queer rings.
Let's turn to another direction: can the ring ''Z/n'' be made into a field? A ring is almost a field, if only the multiplication is nice. In ''Z/n'', there is already the multiplication identity 1. So we ask: how to make a multiplicative inverse for every remainder a in ''Z/n''? That is, how to make a*x=1 (mod n) solvable?
Number theorist proceeds like so: if a*x=1 (mod n), this means when n divides the product a*x, there is a remainder 1. If q is the quotient, we have a*x=q*n+1, or a*x - q*n = 1. Upon seeing this, the number theorist says: a and n must be relatively prime.
Why? Because if a common divisor d divides both a and n, then d also divides a*x, and q*n, so d divides (a*x-q*n), meaning d divides 1. Therefore a and n have only a common divisor 1, or a and n are relatively prime.
Given a modulus n, if it is to be relatively prime to every remainder a, n itself must be a prime -- that's the wonder of primes!
This is the first discovery of Galois, with two related results:
# Every prime ''p'' gives a finite field ''(Z/p,+,*)'' with p elements. This finite field is denoted by ''GF(p)''.
# Every prime ''p'' gives a finite group ''(Z/p^^*^^,*)'' with (p-1) nonzero elements.
The smallest finite field ''GF(2)'' is built from the only even prime ''2'':
|!+|!0|!1| |!*|!1||
|!0|0|1| |!1|1||
|!1|1|0| | | ||
This is also called the ''binary field''.
!Reading Disk Sectors
The computer disk is divided into concentric circular tracks. Each circular track is sub-divided into sectors. Each sector is a basic read/write block of data storage on the medium. Suppose the disk manufecturer makes 9 sectors per track, and number the sectors in the usual way: 1,2,3,4,5,6,7,8,9. Remember that a track is circular, so if we linearize it the track looks periodic:
|!Sectors on a (circular) Track|1|2|3|4|5|6|7|8|9|1|2|3|4|5|6|7|8|9|...|
|!Disk Controller (1 read + 1 wait) reading sectors|R|-|X|X|X|X|X|X|X|X|R|-|X|X|X|X|X|X|...|
Each sector is being read/write by the Disk Controller, an electronic interface to the physical disk, which reads the bytes into a buffer. After reading sector #1, say, the buffer is full. The controller must wait for the buffer content to be emptied (i.e. read by the Disk I/O program) before it can refill the buffer. Suppose the situation is 1 Read (R shown above) with 1 Wait (- shown above). By the time the controller is ready, sector #2 has rotated away. The controller will be idle (X shown above) until sector #2 comes around, then read it. Same thing happens when reading successive sectors #3, #4, #5, etc. Can these idle delays be reduced?
Using an interleaving of order 2 (i.e. each next terms is add 2, modulo 9), the sectors can be marked as:
|!Sectors on a (circular) Track, with interleave of order=2|1|3|5|7|9|2|4|6|8|1|3|5|7|9|2|4|6|8|...|
|!Disk Controller (1 read + 4 waits) reading sectors|R|-|-|-|-|R|-|-|-|-|R|-|-|-|-|R|-|-|...|
This would be ideal for a Disk Controller that must wait 4 sectors to pass before it can read again.
An interleave of order 5 (next = add 5, mod 9) would be ideal for the first Disk Controller that must wait 1 sector to pass:
|!Sectors on a (circular) Track, with interleave of order=5|1|6|2|7|3|8|4|9|5|1|6|2|7|3|8|4|9|5|...|
|!Disk Controller (1 read + 1 wait) reading sectors|R|-|R|-|R|-|R|-|R|-|R|-|R|-|R|-|R|-|...|
However, for a Disk Controller that takes 2 waits, an interleave of order 3 still have occasional delays (X) between reads:
|!Sectors on a (circular) Track, with interleave of order=3|1|4|7|2|5|8|3|6|9|1|4|7|2|5|8|3|6|9|...|
|!Disk Controller (1 read + 2 waits) reading sectors|R|-|-|R|-|-|R|-|-|X|R|-|-|R|-|-|R|-|...|
This is because an interleave of order 3 will give 3 shorter sub-sequences: (1,4,7),(2,5,8),(3,6,9). Within sub-sequences, there is no delay, but there will be delay across sub-sequences.
The number of waits for a Disk Controller depends on the Disk I/O program, whose processing time depends on the CPU speed. None of these are known to the Hard Disk Manufacturer, who is now presented with this problem:
//Can the idle delays be avoided for any number of waits? If yes, how many sectors per track will work the best?//
!How many Sectors per Track?
Using the math from [[Finite Interleaving]], the solution to the problem is:
//Yes, by making the sectors per track a ''prime'' number, it can accommodate interleaving of any order, suitable for any number of waits.//
The default standard is 17 sectors per track, for early, primitive hard-drives. Advances in hard-disk technology make the disk geometry more complicated, and the Disk Controller is no longer the deciding factor for the number of sectors per track.
!Interleaving in Modern Drives
This is because while sector read/write is mechanical (need have the sector spin to a spot right under the read/write head), the Disk Controller is electronic. Hard Disk Interleaving is required only when the mechanical spin is //faster// than the electronic response -- which nowadays is rare. With CPU running at ~GHz range, now the electronic response is much faster than the spin rate, and sector interleaving is not required in modern hard drives.
However, the read/write head still needs to move mechanically to read different tracks and cylinders. Simple sequential numbering of tracks and cylinders cause another level of idle waits similar to sequential sectors in the old days. Modern drives use [[Cylinder and Head Skew|http://www.pcguide.com/ref/hdd/geom/tracksSkew-c.html]] to overcome this problem, which is a form of interleaving.
!For more Info
PC Guide: Track Interleaving
http://www.pcguide.com/ref/hdd/geom/tracksInterleaving-c.html
Hard Disk Sector Structures
http://www.dewassoc.com/kbase/hard_drives/hard_disk_sector_structures.htm
!What is Hashing?
In ordinary English, the word ''hash'' means a mess, jumble, or muddle: //a hash of unorganized facts and figures//.
In computer science, ''hashing'' is used for quick data retrieval based on a key, here //quick// means the time to retrieve is constant.
How does a bad concept become good in computing? Well, like our brains computers are equipped with data storage - either in memory or in disks. The storage must be organized so that data can be put in based on a key, and get back data via the same key. Methods of data storage for efficient data put/get are studied in computer science. It turns out that ''hashing'' is only messy on the surface -- underneath it is fast and effective.
!Indexing and Hashing
An example of data storage is a library. A librarian will register a new book, creates an entry in the catalog, giving the book a unique identification number -- the ''key''. Then the book is shelfed to the appropriate location by the identification number -- ''put'' data. To find the book later, look up the catalog, find the identification number, which gives the location on the shelf -- ''get'' data. The catalog is the master ''index''. This data storage method is called ''indexing''.
Imagine a crazy library: with no shelves, only four walls. The librarian, upon receiving a new book, reads the title and author (the ''key''), then throws a dart. Where the dart hits, the assistant will hang the book there (''put'' data). When you ask for a book, you tell the librarian the title and author (the ''key''). He throws a dart -- where it lands the assistant will pick up the book and give to you (''get'' data). No catalog is required for this crazy method of storage, known as ''hashing'' -- because this library with books hanging on walls look like a mess!
''Indexing'' is not messy: the order is in the index. Without an index, ''hashing'' looks messy; but in reality it is not. This is because the dart-throwing, known as ''hash function'', is very precise: //same key, same spot; different keys, different spots// -- at least in theory.
''Hash functions'' surely are wonderful and magical. But first, let us analyze these two data storage methods in practice:
|!Data Storage Method|!Indexing|!Hashing|!Comment|
|!quick data put/get? | slow when index is large| fast computation, always|so, hashing is good?|
|!conceptual capacity? | infinite (index can grow)| fixed (e.g. 4 walls)|ah, hashing not so good ...|
|!any catch? | index needs maintenance| collision will occur|oh, hashing is bad?|
If the data set is known, hash function can be designed to be ''collision-free'', e.g. a compiler hashing keywords in a programming language. These are called ''prefect hashing''. In general, when data is unknown, or unrestricted, hashing will give ''collision'' -- //different keys, but same spot// -- due to fixed size of the function range: usually restricted to a range of values by modular arithmetic. ''Collision'' is bound to occur in most hashing. However, A well-designed ''hash function'' will give a random-looking distribution of keys, with very few collisions.
''Hashing'' offers fast put/get -- and these are frequent operations. This advantage far outweighs the disadvantage of occasional collision, assuming a good hash function. There are many schemes of hashing, each with its own hash function, and its own way of dealing with collision. We shall skip the many ways to deal with hash collision (read [[here|http://en.wikipedia.org/wiki/Hash_collision]] for some ideas) as they are not related to primes. Instead, we shall take a closer look at ''hash functions'' -- how to throw darts by computation.
!Hashing and Prime
Click [[Try Your Own Hashing]] for examples of ''hash functions'': these are mechanical math computations involving constants for add, subtract, multiply, perhaps divide, and taking remainders in modulo arithmetic: to keep the final result within a specific range of values.
''Hashing'' can be related to prime numbers in two places:
#use of prime constants in hash function -- there are some evidence that primes can lower the probability of collision for typical data.
#use of prime modulo in hash computation -- that is, fix the size of hash table to be prime; again, the collision probability can be minimized.
''Hashing'' maps an unlimited number of keys into a finite space (fixed size), so collision is bound to occur, by the <html><b><a title="When there are more pigeons than holes, there must be a hole with at least two pigeons.">pigeon-hole principle</a></b></html>. A well-designed ''hash function'', using primes or not, can make collision rare for typical, common keys.
''Hashing'' aims for fast ''hash computation''. To be really fast, hash constants or modulo can be chosen as ''powers of 2'' (2, 4, 8, 16, ...) for binary data -- just like it is fast to multiply, divide or modulo decimal numbers by powers of 10 (10, 100, 1000, ...). However, this makes the hash value looking not much different from the key -- multiply is left-shift, divide is right-shift, modulo is chop-off. Hence different, but sufficiently similar, keys (like different names but with the same surname) will hit the same spot, resulting in a collision. Choosing ''prime'' constants or modulus can avoid such collisions, but there will be others, as collisions are unavoidable for hashing infinite keys. Moreover, multiply, divide and modulo by a prime will mean real computations, taking many more machine cycles than using powers of 2, thus slowing down the ''hash computation'', contrary to the aim.
The [[Java String HashCode]] implementation takes a compromise: the modulo is 2^^32^^ (since Java int is 32-bit), but the constant is 2^^5^^-1=31, a prime. The ''hashCode'' computation uses the prime 31 only as multiplier, not divisor -- and 31x = 2^^5^^x - x, involving 5 left-shifts and 1 subtraction in binary.
!Other Uses of Hashing
Did you notice that the ''hash function'' is a ''one-way function''? It scrambles the key to a value (throw the dart), but there is no need to unscramble the value back to the key (no unthrow of the dart). This ''one-way property'' is useful in the following:
# ''Digital Signature'' -- When you download a file from Internet, how to ensure that it is good: no missing bytes from download, no extra bytes by virus-hackers, or just some altered bytes due to transmission error? Well, a file is just a long String, which can be taken as a key to a ''hash function'', giving a hash value that serves as a ''digital signature'' of the file. Any missing or extra or changed bytes will alter the key, hashing to a different value. Yes, collision in hashing is unavoidable, so there is a chance that the file is changed but giving the same hash value. To make this rare, you'll use a more complicated ''hash function'' (for this use, fast is not important, only desirable), and produce a longer hash value. For example, [[OpenOffice|http://download.openoffice.org/index.html]] download includes [[MD5 checksum|http://download.openoffice.org/md5sums/]] (with [[Instructions for use|http://www.openoffice.org/dev_docs/using_md5sums.html]]) as digital signature. The ~MD5 checksum is a 128-bit binary number, or 32 hexadecimal digits.<html><p></html>
# ''Password Verification'' -- Passwords are usually not stored in cleartext, for obvious reasons, but instead in digest form. To authenticate a user, the password presented by the user is hashed and compared with the stored hash. For such systems, if you forget the password, even the administrator cannot tell you what it is; the administrator can only reset your password. This mechanism is used in Unix, Linux (e.g. [[crypt(3)|http://en.wikipedia.org/wiki/Crypt_(Unix)]]) and Windows (e.g. [[LM Hash|http://en.wikipedia.org/wiki/LM_hash]] of Microsoft).
These ''cryptographic hash functions'' aim for complexity, making them effectively ''one-way''. Use of primes is generally not a priority in the algorithm. Yet in ''[[SHA-256 Hashing|http://en.wikipedia.org/wiki/SHA_hash_functions]]'' (used in [[SSL Certificate]] digital signatures), square-roots and cube-roots of primes appear as constants in the computation. You can also use one-half of [[RSA|Key pairs for RSA]] (just keep the modulus and public key, throw away the private key), which depends on primes, for ''one-way hashing''.
/***
| Name:|HideWhenPlugin|
| Description:|Allows conditional inclusion/exclusion in templates|
| Version:|6.9.3|
| Date:|30-Sep-2006|
| Source:|http://mptw.tiddlyspot.com/#HideWhenPlugin|
| Author:|Simon Baird <simon.baird@gmail.com>|
For use in ViewTemplate and EditTemplate. Eg
{{{<div macro="showWhen tiddler.tags.contains('Task')">[[TaskToolbar]]</div>}}}
{{{<div macro="showWhen tiddler.modifier == 'BartSimpson'"><img src="bart.gif"/></div>}}}
***/
//{{{
merge(config.macros,{
hideWhen: { handler: function (place,macroName,params,wikifier,paramString,tiddler) {
if (eval(paramString)) {
removeChildren(place);
place.parentNode.removeChild(place);
}
}},
showWhen: { handler: function (place,macroName,params,wikifier,paramString,tiddler) {
config.macros.hideWhen.handler(place,macroName,params,wikifier,'!('+paramString+')',tiddler);
}}
});
//}}}
Who come up with the idea of Public Key Cryptography?
!The Popular Version
In 1976, Whitfield Diffie and Martin Hellman described the idea of public key cryptography, by using a ''trapdoor'' function to make decryption without private key hard. They suggested a plausible trapdoor function, but did not implement it. That was implemented in 1977 by 3 MIT mathematicians, and they devised another algorithm based on easy-to-multiply but hard-to-factorize: the ''RSA'' algorithm.
!The Secret Version
Around 1969 and early 1970s, people in UK's GCHQ (Government Communications Headquarters, i.e. national spies agency) had already developed these ideas, including the RSA algorithm. However, due to secrecy, they could not publish anything then, and could not say anything when the events of 1976/77 unfolded -- they are allowed to talk about it only much later. GCHQ put the RSA algorithm for checking by math experts, and they could not find any flaws. But GCHQ did not trust the new algorithm, so they never implemented and made use of it.
For more information, read:
The Open Secret
[[http://www.wired.com/wired/archive/7.04/crypto_pr.html|crypto_pr.html]]
|!Format|!It will look like this...|!...if you format it like this...|
|Bold-faced type|''text''|{{{''text''}}}|
|Italic text|//text//|{{{//text//}}}|
|Underlined text|__text__|{{{__text__}}}|
|Strike-through text|--text--|{{{--text--}}}|
|Links with wikiwords|EnchiLada (inactive link - no tiddler yet)<br>WikiWord (active link to tiddler)|{{{EnchiLada}}}<br>{{{WikiWord}}}|
|~De-Wikify a ~WikiWord|~WikiWord, ~EnchiLada|{{{~WikiWord, ~EnchiLada}}}|
|Links with brackets|[[How to add background images]]|{{{[[How to add background images]]}}}|
|Pretty links|[[display text|ColorSchemes]] - links to the tiddler of color schemes|{{{[[display text|ColorSchemes]]}}}|
|External links work the same way:|http://groups.google.com/group/TiddlyWiki <br><br>[[TiddlyWiki Google group|http://groups.google.com/group/TiddlyWiki]]|{{{http://groups.google.com/group/TiddlyWiki}}} <br><br> {{{[[TiddlyWiki Google group|http://groups.google.com/group/TiddlyWiki]]}}}|
|Links to local files|To a file on a CD in your D drive: <br><br>To a file on your USB stick on your e drive: <br><br>To a file in your hard drive:|{{{file:///D:/filename.doc/}}}<br><br>{{{file:///E:/filename.doc/}}}<br><br>{{{file:///C:/filepath/filename.doc/}}}|
|Colored text|@@color(green):green colored@@|{{{@@color(green):green colored@@}}}|
|Text with colored background|@@bgcolor(#ff0000):color(#ffffff):red colored@@|{{{@@bgcolor(#ff0000):color(#ffffff):red colored@@}}}|
|Highlighting|@@text@@|{{{@@text@@}}}|
|Superscript|2^^3^^=8|{{{2^^3^^=8}}}|
|Subscript|a~~ij~~ = -a~~ji~~|{{{a~~ij~~ = -a~~ji~~}}}|
''Simple indenting:''
{{{ {{indent{text }}} produces:
{{indent{text
''Numbered lists:''
{{{#item one }}}
{{{##Item 1a}}}
{{{###Item 1ai}}}
produces:
#item one
##Item 1a
###Item 1ai
''Bulleted lists:''
{{{*Bullet one}}}
{{{**Bullet two}}}
{{{***Bullet three}}}
produces:
*Bullet one
**Bullet two
***Bullet level three
''Headlines''
{{{!Text}}} produces:
!Text
{{{!!Text}}} produces:
!!Text
{{{!!!Text}}} produces:
!!!Text
and so on.
''Tables:''
This is the formatting:
{{{|!Table header|!Column Two|}}}
{{{|>| colspan |}}}
{{{| rowspan |left aligned|}}}
{{{|~| right aligned|}}}
{{{|bgcolor(#DC1A1A):colored| centered |}}}
{{{||*lists<br>*within<br>*tables<br><br>and double-spaced too|}}}
{{{|caption|c}}}
This is the result:
|!Table header|!Column Two|
|>| colspan |
| rowspan |left aligned|
|~| right aligned|
|bgcolor(#DC1A1A):colored| centered |
||*lists<br>*within<br>*tables<br><br>and double-spaced too|
|caption|c
To align a cell so that its text displays at the top rather than the center, add {{{vertical-align:top;}}} at the beginning of the cell.
''Images:''
{{{[img[http://farm1.static.flickr.com/39/122259544_6913ca58f3_m.jpg]]}}} is the formatting for:
[img[http://farm1.static.flickr.com/39/122259544_6913ca58f3_m.jpg]]
''Dotted horizontal lines:''
{{{----}}} produces:
----
''Line-by-line blockquotes:''
{{{>level 1}}}
{{{>level 1}}}
{{{>>level 2}}}
{{{>>level 2}}}
{{{>>>level 3}}}
{{{>>>level 3}}}
{{{>>level 2}}}
{{{>level 1}}}
produces:
>level 1
>level 1
>>level 2
>>level 2
>>>level 3
>>>level 3
>>level 2
>level 1
''Extended blockquotes:''
{{{<<<}}}
{{{Extended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotes}}}
{{{<<<}}}
produces:
<<<
Extended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotesExtended blockquotes
<<<
Take any book, and you should find its International Standard Book Numbers (ISBN). It is a code with 10 digits -- the last digit is a ''check digit''. It is designed in such a way that, if the ISBN is copied with specific types of error, that error will be detected.
<html>
<form>
<table width="80%" border="3" bgcolor="#EBBC55">
<tr>
<td align="left">
ISBN (?=check-digit): <INPUT name="isbn" type="text" size="20%" value="0-306-40615-?">
modulus N: <INPUT name="mod" type="text" size="10%" value="11">
</td>
<td><input type="button" value="Go!" height="50"
onClick="Logger.set('isbn.logger'); try {new ISBN(isbn.value, parseInt(mod.value)).run();} catch (error) {alert(error);}">
</td>
</tr>
<tr>
<td colspan="2"><textarea id="isbn.logger" cols="100%" rows="10"></textarea></td>
</tr>
</table>
</form>
</html>
Enter the ISBN as "0-306-40615-?", leaving the check digit with a question mark "?". Press ''Go''. See what the check-digit is, and what errors are detected.
!ISBN
The ISBN check digit is determined by a formula making use of ''Cyclic Math'' in modulus ''n''.
Ignoring the hyphens "-", let ''d~~j~~'' be the ''j-th'' digit, so that the check digit is ''d~~10~~''. The ''check sum'' is calculated by:
check sum = ''10*d~~1~~+9*d~~2~~+8*d~~3~~+7*d~~4~~+6*d~~5~~+5*d~~6~~+4*d~~7~~+3*d~~8~~+2*d~~9~~+d~~10~~ (mod n)''
For a valid ISBN, check sum = ''0 (mod n)''.
The actual ISBN in use takes modulus ''n=11'', a prime. The ISBN check digit can range from 0 to 10, when it is 10, the symbol X is used instead.
!Errors Detected by ISBN
For the example ISBN = 0-306-40615-?, the check digit is ''2'' in modulus ''11''. In this case, the calculation is:
|!ISBN digit|0|3|0|6|4|0|6|1|5|2|
|!multiplier|10|9|8|7|6|5|4|3|2|1|
|!check sum|>|>|>|>|>|>|>|>|>|10*0+9*3+8*0+7*6+6*4+5*0+4*6+3*1+2*5+1*2|
||>|>|>|>|>|>|>|>|>|=0+27+0+42+24+0+24+3+10+2|
||>|>|>|>|>|>|>|>|>|=132 (mod 11) = 0, ISBN checked OK.|
If there is an error in, say, digit 3, the calculation becomes:
|!ISBN digit|0|3|@@9@@|6|4|0|6|1|5|2|
|!multiplier|10|9|8|7|6|5|4|3|2|1|
|!check sum|>|>|>|>|>|>|>|>|>|10*0+9*3+8*9+7*6+6*4+5*0+4*6+3*1+2*5+1*2|
||>|>|>|>|>|>|>|>|>|=0+27+72+42+24+0+24+3+10+2|
||>|>|>|>|>|>|>|>|>|=204 (mod 11) = 6 ≠ 0, ISBN error.|
If there is a transposition error, say digits 4 and 5 are swapped, the calculation becomes:
|!ISBN digit|0|3|0|@@4@@|@@6@@|0|6|1|5|2|
|!multiplier|10|9|8|7|6|5|4|3|2|1|
|!check sum|>|>|>|>|>|>|>|>|>|10*0+9*3+8*0+7*4+6*6+5*0+4*6+3*1+2*5+1*2|
||>|>|>|>|>|>|>|>|>|=0+27+0+28+36+0+24+3+10+2|
||>|>|>|>|>|>|>|>|>|=130 (mod 11) = 9 ≠ 0, ISBN error.|
This error-detection property of ISBN under modulus 11 is closely related to the fact that modular multiplication of 11 forms a group, the multiplicative group of ''GF(11)''. Cyclic multiplication only forms a group under a prime modulus ''p'', ''(Z/p^^*^^, *)''.
In the ISBN interactive, try other modulus instead of 11 to see how the check digit change, and see if digit and transposition errors can be detected. The results should look like:
|!Choices of modulus n|!ISBN for 0-306-40615-?|!Digit errors detected?|!Transposition errors detected?|!Comments|
|11|0-306-40615-2|yes|yes|11 is a prime|
|12|0-306-40615-2|no|no||
|13|0-306-40615-0|yes|yes|13 is a prime|
|10|0-306-40615-0|no|no||
|16|0-306-40615-B|no|no||
|17|0-306-40615-6|yes|yes|17 is a prime|
|5|0-306-40615-0|no|no||
!More Information
Secrets of the ISBN - An Error Detection Method
[[http://www.ee.unb.ca/tervo/ee4253/isbn.html|isbn.html]]
The International Standard Book Numbers work with a check digit, which exploits the fact that 11 is a prime.
http://en.wikipedia.org/wiki/International_Standard_Book_Number
!Infinite Interleaving - Aperiodic
The sequence 1,2,3,... is infinite, without any period. But you can interleave in any order, which is equivalent to splitting the sequence into parts.
Imagine a bank with 5 counters, but only 1 main queue, with customers 1, 2, 3, 4, 5, 6, 7, 8, 9, ... (no ending). Assume the same time for customer service, the counters will serve these customers:
|!Counter 1|1, 6, 11, 16, ...|
|!Counter 2|2, 7, 12, 17, ...|
|!Counter 3|3, 8, 13, 18, ...|
|!Counter 4|4, 9, 14, 19, ...|
|!Counter 5|5, 10, 15, 20, ...|
|''A bank with 5 Counters''|c
Note that all multiples of 5 goes to Counter 5, which is obvious. Other than that:
|!all multiples of 4|4,8,12,16,20,...|in Counters 1,2,3,4,5|
|!all multiples of 3|3,6,9,12,15,...|in Counters 1,2,3,4,5|
|!all multiples of 2|2,4,6,8,10,...|in Counters 1,2,3,4,5|
|''Distribution of multiples for 5 Counters''|c
However, if the bank has only 4 counters instead of 5, the result about multiples is different:
|!Counter 1|1, 5, 9, 13, ...|
|!Counter 2|2, 6, 10, 14, ...|
|!Counter 3|3, 7, 11, 15, ...|
|!Counter 4|4, 8, 12, 16, ...|
|''A bank with 4 Counters''|c
|!all multiples of 3|3,6,9,12,...|in Counters 1,2,3,4|
|!all multiples of 2|2,4,6,8,...|in Counters 2,4 only|
|''Distribution of multiples for 4 Counters''|c
Note that multiples of 2 now spreads over not all the 4 Counters, but only 2 of them.
Why? Let's see. If the infinite sequence 1,2,3,.... is interleaved into p parts, the result looks like:
|!Parts|!Terms|!Comment|
|!Part 1|1, 1+p, 1+2p, 1+3p, 1+4p, 1+5p, .....| x ≡ 1 (mod p)|
|!Part 2|2, 2+p, 2+2p, 2+3p, 2+4p, 2+5p, .....| x ≡ 2 (mod p)|
|!Part 3|3, 3+p, 3+2p, 3+3p, 3+4p, 3+5p, .....| x ≡ 3 (mod p)|
|!....| ....| ...|
|!Part p|p, 2p, 3p, 4p, 5p, ...| x ≡ 0 (mod p)|
|''Infinite sequence interleaved into p Parts''|c
Note that the parts are the different remainders under modulo p. The multiples of k (0 < k < p) are: k, 2k, 3k, ..... Under modulo p, these multiples become: k (mod p), 2k (mod p), 3k (mod p), .... To find out how many parts these multiples of k will spread over is the same as asking: how many multiples of k in mod p are distinct?
For any p, the modulo arithmetic Z~~p~~ = Z/p under addition is a cyclic group G, the additive identity is 0.
For a given k, the multiples of k generates a cyclic subgroup <k> of G, with the same additive identity 0.
This means there is a smallest x such that xk = 0 (mod p), or xk = hp for some h.
Denote this common product by q, i.e. q = hp = xk.
Since q is a multiple of p (q=hp) and also a multiple of k (q = xk), q is a common multiple of p, k.
Since x is the smallest, q is the least common multiple of p, k, i.e. q = lcm(p,k).
Therefore number of distinct remainders of multiples of k in mod p = x = q/k = lcm(p,k)/k = (kp/gcd(p,k))/k = p/gcd(p,k).
We therefore have:
<<<
@@bgcolor(#9DEB95):''Infinite Interleaving Theorem''@@:
For the infinite sequence 1,2,3,... interleaving into p ''parts'', ''multiples'' of k (0 < k < p) will spread over ''p/gcd(p,k)'' parts.
<<<
!Using Prime Parts
If the number of parts p is a ''prime'', gcd(p,k)=1 for all k (0 < k < p). Hence interleaving the infinite sequence into ''prime'' parts guarantees all ''multiples'' of k (0 < k < p) will spread over all the parts.
An example of interleaving 1,2,3,4,5,.... into 7 parts is shown:
|!Part|!Terms|!Comment|!Has 1x?|!Has 2x?|!Has 3x?|!Has 4x?|!Has 5x?|!Has 6x?|
|! 1| 1, 8,@@bgcolor(#F3A1EE):15@@,22,29,36,43,...| x ≡ 1 (mod 7)| yes| yes| yes| yes| yes| yes|
|! 2| 2, 9,16,23,@@bgcolor(#F3A1EE):30@@,37,44,...| x ≡ 2 (mod 7)| yes| yes| yes| yes| yes| yes|
|! 3| 3,@@bgcolor(#F3A1EE):10@@,17,24,31,38,@@bgcolor(#F3A1EE):45@@,...| x ≡ 3 (mod 7)| yes| yes| yes| yes| yes| yes|
|! 4| 4,11,18,@@bgcolor(#F3A1EE):25@@,32,39,46,...| x ≡ 4 (mod 7)| yes| yes| yes| yes| yes| yes|
|! 5| @@bgcolor(#F3A1EE):5@@,12,19,26,33,@@bgcolor(#F3A1EE):40@@,47,...| x ≡ 5 (mod 7)| yes| yes| yes| yes| yes| yes|
|! 6| 6,13,@@bgcolor(#F3A1EE):20@@,27,34,41,48,...| x ≡ 6 (mod 7)| yes| yes| yes| yes| yes| yes|
|! 7| 7,14,21,28,@@bgcolor(#F3A1EE):35@@,42,49,...| x ≡ 0 (mod 7)| yes| yes| yes| yes| yes| yes|
|''Infinite sequence interleaved into 7 Parts''|c
The multiples of 5 are marked, and they spread over all the 7 parts. You can easily verify that this is also true for multiples of 1,2,3,4,6.
!Application of Infinite Interleaving
See [[Memory Bank Interleaving]]: some supercomputers and high-end serves have 5 or 7 banks for parallel memory.
/***
|Name|InlineJavascriptPlugin|
|Source|http://www.TiddlyTools.com/#InlineJavascriptPlugin|
|Version|1.6.0|
|Author|Eric Shulman - ELS Design Studios|
|License|http://www.TiddlyTools.com/#LegalStatements <<br>>and [[Creative Commons Attribution-ShareAlike 2.5 License|http://creativecommons.org/licenses/by-sa/2.5/]]|
|~CoreVersion|2.1|
|Type|plugin|
|Requires||
|Overrides||
|Description|Insert Javascript executable code directly into your tiddler content.|
''Call directly into TW core utility routines, define new functions, calculate values, add dynamically-generated TiddlyWiki-formatted output'' into tiddler content, or perform any other programmatic actions each time the tiddler is rendered.
!!!!!Usage
<<<
When installed, this plugin adds new wiki syntax for surrounding tiddler content with {{{<script>}}} and {{{</script>}}} markers, so that it can be treated as embedded javascript and executed each time the tiddler is rendered.
''Deferred execution from an 'onClick' link''
By including a {{{label="..."}}} parameter in the initial {{{<script>}}} marker, the plugin will create a link to an 'onclick' script that will only be executed when that specific link is clicked, rather than running the script each time the tiddler is rendered. You may also include a {{{title="..."}}} parameter to specify the 'tooltip' text that will appear whenever the mouse is moved over the onClick link text
''External script source files:''
You can also load javascript from an external source URL, by including a src="..." parameter in the initial {{{<script>}}} marker (e.g., {{{<script src="demo.js"></script>}}}). This is particularly useful when incorporating third-party javascript libraries for use in custom extensions and plugins. The 'foreign' javascript code remains isolated in a separate file that can be easily replaced whenever an updated library file becomes available.
''Display script source in tiddler output''
By including the keyword parameter "show", in the initial {{{<script>}}} marker, the plugin will include the script source code in the output that it displays in the tiddler.
''Defining javascript functions and libraries:''
Although the external javascript file is loaded while the tiddler content is being rendered, any functions it defines will not be available for use until //after// the rendering has been completed. Thus, you cannot load a library and //immediately// use it's functions within the same tiddler. However, once that tiddler has been loaded, the library functions can be freely used in any tiddler (even the one in which it was initially loaded).
To ensure that your javascript functions are always available when needed, you should load the libraries from a tiddler that will be rendered as soon as your TiddlyWiki document is opened. For example, you could put your {{{<script src="..."></script>}}} syntax into a tiddler called LoadScripts, and then add {{{<<tiddler LoadScripts>>}}} in your MainMenu tiddler.
Since the MainMenu is always rendered immediately upon opening your document, the library will always be loaded before any other tiddlers that rely upon the functions it defines. Loading an external javascript library does not produce any direct output in the tiddler, so these definitions should have no impact on the appearance of your MainMenu.
''Creating dynamic tiddler content''
An important difference between this implementation of embedded scripting and conventional embedded javascript techniques for web pages is the method used to produce output that is dynamically inserted into the document:
* In a typical web document, you use the document.write() function to output text sequences (often containing HTML tags) that are then rendered when the entire document is first loaded into the browser window.
* However, in a ~TiddlyWiki document, tiddlers (and other DOM elements) are created, deleted, and rendered "on-the-fly", so writing directly to the global 'document' object does not produce the results you want (i.e., replacing the embedded script within the tiddler content), and completely replaces the entire ~TiddlyWiki document in your browser window.
* To allow these scripts to work unmodified, the plugin automatically converts all occurences of document.write() so that the output is inserted into the tiddler content instead of replacing the entire ~TiddlyWiki document.
If your script does not use document.write() to create dynamically embedded content within a tiddler, your javascript can, as an alternative, explicitly return a text value that the plugin can then pass through the wikify() rendering engine to insert into the tiddler display. For example, using {{{return "thistext"}}} will produce the same output as {{{document.write("thistext")}}}.
//Note: your script code is automatically 'wrapped' inside a function, {{{_out()}}}, so that any return value you provide can be correctly handled by the plugin and inserted into the tiddler. To avoid unpredictable results (and possibly fatal execution errors), this function should never be redefined or called from ''within'' your script code.//
''Accessing the ~TiddlyWiki DOM''
The plugin provides one pre-defined variable, 'place', that is passed in to your javascript code so that it can have direct access to the containing DOM element into which the tiddler output is currently being rendered.
Access to this DOM element allows you to create scripts that can:
* vary their actions based upon the specific location in which they are embedded
* access 'tiddler-relative' information (use findContainingTiddler(place))
* perform direct DOM manipulations (when returning wikified text is not enough)
<<<
!!!!!Examples
<<<
an "alert" message box:
><script show>
alert('InlineJavascriptPlugin: this is a demonstration message');
</script>
dynamic output:
><script show>
return (new Date()).toString();
</script>
wikified dynamic output:
><script show>
return "link to current user: [["+config.options.txtUserName+"]]";
</script>
dynamic output using 'place' to get size information for current tiddler:
><script show>
if (!window.story) window.story=window;
var title=story.findContainingTiddler(place).id.substr(7);
return title+" is using "+store.getTiddlerText(title).length+" bytes";
</script>
creating an 'onclick' button/link that runs a script:
><script label="click here" title="clicking this link will show an 'alert' box" show>
if (!window.story) window.story=window;
alert("Hello World!\nlinktext='"+place.firstChild.data+"'\ntiddler='"+story.findContainingTiddler(place).id.substr(7)+"'");
</script>
loading a script from a source url:
>http://www.TiddlyTools.com/demo.js contains:
>>{{{function demo() { alert('this output is from demo(), defined in demo.js') } }}}
>>{{{alert('InlineJavascriptPlugin: demo.js has been loaded'); }}}
><script src="demo.js" show>
return "loading demo.js..."
</script>
><script label="click to execute demo() function" show>
demo()
</script>
<<<
!!!!!Installation
<<<
import (or copy/paste) the following tiddlers into your document:
''InlineJavascriptPlugin'' (tagged with <<tag systemConfig>>)
<<<
!!!!!Revision History
<<<
''2007.02.19 [1.6.0]'' added support for title="..." to specify mouseover tooltip when using an onclick (label="...") script
''2006.10.16 [1.5.2]'' add newline before closing '}' in 'function out_' wrapper. Fixes error caused when last line of script is a comment.
''2006.06.01 [1.5.1]'' when calling wikify() on script return value, pass hightlightRegExp and tiddler params so macros that rely on these values can render properly
''2006.04.19 [1.5.0]'' added 'show' parameter to force display of javascript source code in tiddler output
''2006.01.05 [1.4.0]'' added support 'onclick' scripts. When label="..." param is present, a button/link is created using the indicated label text, and the script is only executed when the button/link is clicked. 'place' value is set to match the clicked button/link element.
''2005.12.13 [1.3.1]'' when catching eval error in IE, e.description contains the error text, instead of e.toString(). Fixed error reporting so IE shows the correct response text. Based on a suggestion by UdoBorkowski
''2005.11.09 [1.3.0]'' for 'inline' scripts (i.e., not scripts loaded with src="..."), automatically replace calls to 'document.write()' with 'place.innerHTML+=' so script output is directed into tiddler content. Based on a suggestion by BradleyMeck
''2005.11.08 [1.2.0]'' handle loading of javascript from an external URL via src="..." syntax
''2005.11.08 [1.1.0]'' pass 'place' param into scripts to provide direct DOM access
''2005.11.08 [1.0.0]'' initial release
<<<
!!!!!Credits
<<<
This feature was developed by EricShulman from [[ELS Design Studios|http:/www.elsdesign.com]]
<<<
!!!!!Code
***/
//{{{
version.extensions.inlineJavascript= {major: 1, minor: 6, revision: 0, date: new Date(2007,2,19)};
config.formatters.push( {
name: "inlineJavascript",
match: "\\<script",
lookahead: "\\<script(?: src=\\\"((?:.|\\n)*?)\\\")?(?: label=\\\"((?:.|\\n)*?)\\\")?(?: title=\\\"((?:.|\\n)*?)\\\")?( show)?\\>((?:.|\\n)*?)\\</script\\>",
handler: function(w) {
var lookaheadRegExp = new RegExp(this.lookahead,"mg");
lookaheadRegExp.lastIndex = w.matchStart;
var lookaheadMatch = lookaheadRegExp.exec(w.source)
if(lookaheadMatch && lookaheadMatch.index == w.matchStart) {
if (lookaheadMatch[1]) { // load a script library
// make script tag, set src, add to body to execute, then remove for cleanup
var script = document.createElement("script"); script.src = lookaheadMatch[1];
document.body.appendChild(script); document.body.removeChild(script);
}
if (lookaheadMatch[5]) { // there is script code
if (lookaheadMatch[4]) // show inline script code in tiddler output
wikify("{{{\n"+lookaheadMatch[0]+"\n}}}\n",w.output);
if (lookaheadMatch[2]) { // create a link to an 'onclick' script
// add a link, define click handler, save code in link (pass 'place'), set link attributes
var link=createTiddlyElement(w.output,"a",null,"tiddlyLinkExisting",lookaheadMatch[2]);
link.onclick=function(){try{return(eval(this.code))}catch(e){alert(e.description?e.description:e.toString())}}
link.code="function _out(place){"+lookaheadMatch[5]+"\n};_out(this);"
link.setAttribute("title",lookaheadMatch[3]?lookaheadMatch[3]:"");
link.setAttribute("href","javascript:;");
link.style.cursor="pointer";
}
else { // run inline script code
var code="function _out(place){"+lookaheadMatch[5]+"\n};_out(w.output);"
code=code.replace(/document.write\(/gi,'place.innerHTML+=(');
try { var out = eval(code); } catch(e) { out = e.description?e.description:e.toString(); }
if (out && out.length) wikify(out,w.output,w.highlightRegExp,w.tiddler);
}
}
w.nextMatch = lookaheadMatch.index + lookaheadMatch[0].length;
}
}
} )
//}}}
!What is Interleaving?
In English, to ''interleave'' is to insert something alternately and regularly between something else: //Interleave carbon paper between pages//.
Every child learns to count the weekdays: 1, 2, 3, 4, 5, 6, 7, 1, 2, .... This is a cyclic sequence, no interleaving.
If you work one day, rest the next day, your work-days count as: 1, 3, 5, 7, 2, 4, 6, 1, 3, ... This is still cyclic, with interleaving.
Compared to a cyclic sequence, an interleaving cycle looks complicated. How can this be useful in computer science? It turns out that smart interleaving can reduce unneccessary delays, and //smart// means using primes!
But first, let's take a closer look at Interleaving.
!Finite and Infinite Interleaving
The example above takes a ''finite'' sequence, 1,2,3,4,5,6,7 and repeats it, making it periodic with a ''period'' 7.
We shall say that the interleaving sequence: 1,3,5,7,2,4,6,... has ''order'' 2, which is the difference between successive terms (in modulo 7).
So this is an example of a period-7 sequence with interleaving of order 2.
We shall be interested in the question: what ''periods'' can accommodate interleaving of any ''order''?
Click [[Finite Interleaving]] for more discussion.
The ''infinite'' sequence 1,2,3,4,5,6,7,8,9,... has no period. But you can interleave by //pulling// alternating 2^^nd^^ numbers to start another sequence, like so:
1, 3, 5, 7, ... (the odds, or remainder = 1 when divided by 2)
2, 4, 6, 8, ... (the evens, or remainder = 0 when divided by 2)
This is an example of interleaving the infinite sequence into 2 ''parts''.
Note that ''multiples'' of 2 are in the evens, but multiples of 3 (3, 6, 9,...) are in both odds and evens. How about multiples of 4? multiples of 5?
In general, the infinite sequence can be interleaved into any number of parts. We shall be interested in the distribution of ''multiples'' in the ''parts''.
Click [[Infinite Interleaving]] for further discussion.
To experiment with interleaving sequences, finite or infinite, open [[Try Your Own Interleaving]].
!Interleaving and Prime
Prime numbers can be important in both types of interleaving:
#From [[Finite Interleaving]] we have this corollary: <html><br></html>For the cyclic sequence 1, 2, 3, ..., p, 1, 2,..., a prime period ''p'' allows good interleaving of any order ''d'', as gcd(p,d)=1.<html><p></html>This is used in [[Hard Disk Interleaving]], with the default standard of 17 sectors per track. However, this feature is only relevant to old-style disk controllers, which are slow compared to the spinning disc. Nowadays, although the disc is spinning very fast, the disk controller can respond even faster. Modern hard disk technology doesn't need interleaving for performance.<html><p></html>
#From [[Infinite Interleaving]] we have this corollary: <html><br></html>The infinite sequence 1, 2, 3, ... interleaving into prime parts ''p'' allows good distribution of any multiples of ''k'', as gcd(p,k)=1.<html><p></html>This is used in [[Memory Bank Interleaving]]: for example, super-computers and high-end servers have parallel access to 5 or 7 memory banks. Personal Computer (PC) technology is starting to have dual-core for CPU, while parallel access to memory banks is still too expensive for general consumers. However, digital cameras, mobile phones, ~MP3/~MP4 players, GPS devices, etc. are ~System-on-Chips (SOC): they are increasingly demanding parallel access to memory/buffer for real-time processing.
!Other Uses of Interleaving
* ''Load Balancing'' -- interleave the use of resources to several components to avoid single-component overload. This is used in technologies like multi-threading, dual-cores, disk-arrays, ~P2P download via torrents, etc. Modern applications, even operating system, are object-based: objects are created to perform tasks. Web applications run on servers, and it is the job of servers to keep objects in a pool so that identical tasks (e.g. transactions) can be shared among identical objects -- how good the server can achieve this load balancing is an important performance indicator of the Web server. Try Google "load balancing interleave" for more information.<html><p></html>
* ''Error Correction'' -- interleave input signals among several error-decoders to avoid bursts of error. This is used in telecommunication signal transmissions (TV signals, Internet, ~WiFi, etc.) since all channels have unavoidable noise. This is also used in CD players and iPods -- reading a hard-disk is still mechanical, and this is error-prone when you're jogging. Standard CD uses [[Cross-interleaved Reed-Solomon coding (CIRC)|http://en.wikipedia.org/wiki/Cross-interleaved_Reed-Solomon_coding]] for error detection/correction. Try Google "error-correction interleave" for more information.
Few of these interleaving applications are based on primes. Most are based on power of 2: interleave into 2 parts, 4 parts, 8 parts, ... Yet note that 2 is a prime (the only even prime), and gcd(power of 2, odd) = 1.
!Simple Interleaving
Whenever you are doing two things at once, you are ''interleaving'': doing a bit of this, doing a bit of that. This is quite common: if there is a need to ''squeeze'' two (or more) things in one ''serial'' channel, some form of interleaving must be applied.
In optical fiber technology, interleaver and deinterleaver are used to squeeze/unsqueeze signals to increase the transmission capacity, see [[this|http://en.wikipedia.org/wiki/Optical_interleaver]].
Such simple interleaving is featured in this story: [[Memoirs of a Space Engineer - Leadpencils|http://www.abc.net.au/science/slab/memoirs/leadpencils.htm]]. Nothing to do with primes, but still worth reading.
The Java programming language supports ''hash'' data structures: Hashtable, ~HashMap, and ~HashSet. Since the data to be hashed can be any Object, all Java Objects have hashCode() method.
!String hashCode
''String'' is an Object in Java, and its hashCode() is [[documented|http://java.sun.com/javase/6/docs/api/java/lang/String.html#hashCode()]]:
<html><pre>
public int <b>hashCode()</b>
Returns a hash code for this string. The hash code for a String object is computed as
s[0]*31<sup>(n-1)</sup> + s[1]*31<sup>(n-2)</sup> + ... + s[n-1]
using int arithmetic, where s[i] is the ith character of the string, n is the length of the string.
</pre></html>
This complicated-looking hash function is in fact a simple loop:
<html><pre>
public int <b>hashCode()</b> {
int h = 0;
int len = this.length();
for (int i = 0; i < len; i++) {
h = 31 * h + this.charAt(i);
}
return h;
}
</pre></html>
The string is the key, hash value is a Java int, 32-bits: from ''Integer.~MIN_VALUE''=-2^^31^^=-2147483648 to ''Integer.~MAX_VALUE'' = 2^^31^^-1=2147483647.
!Computing String hashCode
In your browser, to find the hashCode of a Java string "Joe Miller", try typing this in the address:
{{{javascript:new java.lang.String("Joe Miller").hashCode()}}}
This works for ~FireFox browsers, but may not work for Internet Explorer (which says, "java undefined").
[[Try Your Own Hashing]] simulates this ''String hashCode'' computation in Javascript.
<html>
<textarea id="here" cols="100%" rows="25"></textarea>
<br />
<input type="button" value="OK 1" height="50" onClick="alert('Hello, TiddlyWiki!')">
<input type="button" value="OK 2" height="50" onClick="alert(document.getElementById('here'))">
<input type="button" value="OK 3" height="50" onClick="alert(parseInt)">
<input type="button" value="OK 4" height="50" onClick="alert(Logger)">
<input type="button" value="Hello" height="50" onClick="Logger.set('here');Logger.log('Hello, TiddlyWiki!')">
</html>
The ''RSA'' method is a modification of Cyclic Exponentiation Encryption and Decryption. However, the modulus is not a prime p. Instead, the modulus ''n = pq'', a product of two large primes.
We have seen that, to find key pairs for Cyclic Exponentiation is to look at the equation: ''x = x#e#d'' with operation ''#'' replaced by exponentiation modulo ''n'': ''^'' under ''mod n''. That is:
''x = x ^ e ^ d (mod n)'' or ''x = (x^^e^^)^^d^^ (mod n)'' or ''x = x^^(e*d)^^ (mod n)''
Given a modulus ''n=pq'', where ''p'', ''q'' are ''primes'', can we find a pair of public key ''e'' and private key ''d'' to satisfy this equation?
This is no special name for a product of two primes -- I just call them ''bi-primes''.
!Exponent Inverses for Modulo Bi-prime
Since the modulus ''n'' is not a prime, ''(Z/n,+,*)'' is just a [[Ring|Group, Ring and Field]]: multiplication can be bad. However, we do have ''Euler's Theorem'' for any modulus ''n'':
For any modulus ''n'', ''a^^φ(n)^^=1 (mod n)'' for remainder ''a'' relatively prime to ''n''.
In a ring, multiplication is still closed, so we can first raise both sides to the same power k:
For any modulus ''n'', ''(a^^φ(n)^^)^^k^^=a^^k*φ(n)^^=1^^k^^=1 (mod n)'' for remainder ''a relatively prime to n'' .
And multiply both sides by ''a'':
For any modulus ''n'', ''a^^(k*φ(n)+1)^^=a (mod n)'' for remainder ''a'' relatively prime to ''n''.
For bi-prime ''n=pq'', it can be shown that this is valid even if ''a'' is not relatively prime to ''pq''. Hence:
For any bi-prime modulus ''n=pq'', ''a^^(k*φ(n)+1)^^=a (mod n)'' for any remainder ''a''.
Comparing with our equation, it means: ''e*d = k*φ(n)+1'', or ''e*d=1 (mod φ(n))''.
For the bi-prime ''n=pq'', only 1, p, 2p, ..., (q-1)p, q, 2q, ..., (p-1)q are relatively prime to pq, so:
φ(n)=φ(pq)=(pq-1)- (q-1)-(p-1) = pq-q-p+1=(p-1)(q-1).
Thus the key pair ''e'' and ''d'' are multiplicative inverses in mod φ(n) = mod (p-1)(q-1).
Therefore, given a bi-prime modulus ''n=pq'', any ''e'' relatively prime to ''φ(n)=(p-1)(q-1)'' will do, and ''d=e^^-1^^ (mod (p-1)(q-1))'', the multiplicative inverse of ''e'' in ''mod (p-1)(q-1)''.
Using ''Euler's Theorem'' again for the explicit formula of multiplicative inverse, ''d=e^^φ((p-1)(q-1))-1^^ mod (p-1)(q-1)''.
For example, taking two prime ''p=5'' and ''q=11''. The bi-prime modulus ''n=5*11=55'', and φ(n)=φ(55)=(5-1)(11-1)=40. Pick ''e=3'' which relatively prime to 40, then ''d=27'' because 3*27=81=1 (mod 40). If you count the relatively prime remainders of 40, you'll find φ(40)=φ((p-1)(q-1))=12, from which you can compute ''d''=3^^(12-1)^^ (mod 40)=3^^11^^=(3*3*3)^^3^^*(3*3) =(27)^^3^^*(9)=27*27*27*9=(729)(243)=(9)(3)=''27'' (mod 40).
|!Possible data for modulus 55|!Encrypt by ^3 (mod 55)|!Decrypt by ^27 (mod 55)|
|2|2^^3^^=8|8^^27^^=(8*8)^^13^^*8=(64)^^13^^*8=(9)^^13^^*8=...= (14)*8=112=2 (mod 55)|
|3|3^^3^^=27|27^^27^^=(27*27)^^13^^*27=(14)^^13^^*27=...=49*27=1323=3 (mod 55)|
|14|14^^3^^=196*14=31*14=434=49|49^^27^^=(49*49)^^13^^*49=(36)^^13^^*49=...=(16)*49=784=14 (mod 55)|
|15|15^^3^^=225*15=5*15=75=20|20^^27^^=(20*20)^^13^^*20=(15)^^13^^*20=...=(20)*20=400=15 (mod 55)|
|''Encryption and Decryption in Cyclic Exponent modulo 55''|c
!Is This Secure?
Although ''Encrypt by ^e (mod n)'' is made public, the private key ''d=e^^φ((p-1)(q-1))-1^^ mod (p-1)(q-1)'' can be computed only if the primes factors of ''n=pq'' are known. Note that the public is only given the product ''n'', which is known to be the product of two primes, but the two primes are kept secret. To crack this code you need to factorize the known product ''n''. This is the crux of the RSA scheme, making it secure enough for bank transactions.
!Factorization of Bi-prime
In the example above, the bi-prime is ''55''. You can factorize this bi-prime in your head: ''55=5*11''. You've crack this RSA code!
However, if the bi-prime is ''4294967297'', can you factorize it quickly? This happens to be ''2^^<html>2<sup>5</sup></html>^^+1'', the fifth Fermat Number, or ''F~~5~~''. In 1640, Fermat thought this is a prime, but in 1732 Euler showed that: ''4294967297=641*6700417''.
Currently, there is better factorization methods than trial divisions, but there is no known fast methods to factorize a number, especially when the prime factors involved are large. Experts believe that no such fast methods exist, but there is no proof so far.
To show that bi-prime factorization is hard, when RSA was introduced in 1977, they posed in a magazine an encrypted message with ''e''=9007, but the modulus ''n'' is a 129-digit number, called ''~RSA-129'':
''~RSA-129'' = 1143816257578888676692357799761466120102182 9672124236256256184293570693524573389783059 7123563958705058989075147599290026879543541
In April 1994, an international cooperative group of mathematicians and computer scientists solved this 17-year-old challenge problem by factorizing ~RSA-129:
''~RSA-129'' = 34905295108476509491478496199038 98133417764638493387843990820577 *
32769132993266709549961988190834 461413177642967992942539798288533.
For the full story, read [[The Cracking of RSA-129|http://cauchy.math.okstate.edu/~wrightd/crypt/crypt-intro/]].
The RSA scheme recommends using primes of 100-digits. It is estimated that even if you have an ultra-fast super-computer, to factorize a 200-digit bi-prime will require a time longer than the age of universe.
One way of generating periodic sequences is by cyclic math, like the ''clock'': after 12, we cycle back to 1, 2, 3 ... In cyclic math, numbers are operated (add, subtract, multiply or divide) by keeping only the remainder after division by some integer N, called the modulus.
Most computer systems (and computer languages) generate random numbers based on remainders of division by N (or mod N):
X~~n+1~~ = A X~~n~~ + B (mod N) with X~~0~~ = seed
Since mod N has only a finite number of remainders, the sequence X~~n~~ must repeat. The idea is this: with a given N, choose suitable values of A and B so that sequence X~~n~~ gives the maximum period. How to choose suitable constants A, B to achieve the maximum period? This is a math problem (in group theory), but we can do experiments:
<html>
<form>
<table width="80%" border="3" bgcolor="#C5CDFF">
<tr>
<td align="left">
<b>X<sub>n+1</sub> = A X<sub>n</sub> + B (mod N)</b> with X<sub>0</sub> = seed.<br>
modulus N: <INPUT name="N" type="text" size="10%" value="11">
multiplier A: <INPUT name="A" type="text" size="10%" value="2">
constant B: <INPUT name="B" type="text" size="10%" value="0">
seed X<sub>0</sub>: <INPUT name="seed" type="text" size="10%" value="2">
</td>
<td><input type="button" value="Go!" height="50"
onClick="Logger.set('lcs.logger'); new LCS(parseInt(N.value), parseInt(A.value), parseInt(B.value), parseInt(seed.value)).run();">
</td>
</tr>
<tr>
<td colspan="2"><textarea id="lcs.logger" cols="100%" rows="10"></textarea></td>
</tr>
</table>
</form>
</html>
These computer computer experiments show that results are usually good when N is a prime.
!Mulitplicative congruence
This is a special case of (1), with B = 0, so only multiplications are performed.
X~~n+1~~ = A X~~n~~ (mod N) with X~~0~~ = seed
For a modulus N, since X~~n~~ must be nonzero, the possible remainders are 1 to N-1, hence the maximum period is (N-1).
|!N|!A|!Seed|!Sequence|!Period|!Max Period|!Comments|
|3|2|2|2,4=1,2 ... |2|2|prime 3 gives max period|
|4|2|2|2,4=0 ... |dies|3||
|5|2|2|2,4,8=3,6=1,2 ... |4|4|prime 5 gives max period|
|6|2|2|2,4,8=2 ... |2|5||
|7|2|2|2,4,8=1,2 ... |3|6|prime 7 gives short period|
|7|3|2|2,6,18=4,12=5,15=1,3,9=2 ... |6|6|prime 7 gives max period|
These examples illustrate that to get the maximum period, a prime modulus with a suitable multiplier is essential. Hence a knowledge of primes is important for random number generators based on multiplicative congruences.
For example, in a 32-bit machine, the max signed integer 2^^31^^ - 1 = 2147483647 happens to be a Mersenne prime. This prime has been used in a good random number generator: N = 2147483647, A = 7^^5^^ = 16807, B = 0 (Park and Miller).
!Additive Congruences
This is another special case of (1), with A = 1, so only additions are performed:
X~~n+1~~ = X~~n~~ + B (mod N) with X~~0~~ = seed
For a modulus N, X~~n~~ as remainder can be 0 to N-1, hence the maximum period is N.
|!N|!B|!Seed|!Sequence|!Period|!Max Period|!Comments|
|3|2|2|2,4=1,3=0,2 ... |3|3|gives max period when B=2|
|4|2|2|2,4=0,2 ... |2|4||
|4|3|2|2,5=1,4=0,3,6=2 ...|4|4|gives max period when B=3|
|5|2|2|2,4,6=1,3,5=0,2 ... |5|5|gives max period when B=2|
|6|2|2|2,4,6=0,2 ... |3|6||
|6|5|2|2,7=1,6=0,5,10=4,9=3,8=2 ... |6|6|gives max period when B=5|
|7|2|2|2,4,6,8=1,3,5,7=0,2 ... |7|7|gives max period when B=2|
These examples illustrate that to get the maximum period, a modulus will need a suitable constant B, preferably prime. So a knowledge of primes is also important for random number generators based on additive congruences.
Random number generators in most programming languages are a combination of additive and multiplicative congruences, i.e. using linear congruences with suitable modulus N, multiplier A and constant B. For example, the random number generator of Borland C/C++: N = 2^^32^^, A = 3x7^^2^^x61x2531 = 22695477, B=1.
[[Prime Applications]]
<<newTiddler>>
<<saveChanges>>
<<doPublish>>
<<tiddler ToggleRightSidebar>>
!Array in Memory
Most programming languages support a basic data structure: ''Array'', which is logicallly linear with elements a[j], with index j=1,2,3,...:
|!Array a[j]|!Element 1|!Element 2|!Element 3|!Element 4|!Element 5|....|
|!Logical Structure| a[1]| a[2]| a[3]| a[4]| a[5]|..|
|''Linear Array''|c
How this data structure is stored in memory has a direct impact on the speed of array computations.
Memory are organized into ''bytes''. An array element a[j] will take up some number of bytes -- exactly how many bytes depends on the type of the array element. Let's consider an example in which each array element a[j] takes 3 bytes.
PC has sequential memory, and this 3-bytes array is usually stored as:
|!Memory|!Content|!Comment|
|!Byte 1|@@a[1] byte 1@@|a[1] in contiguous cells|
|!Byte 2|a[1] byte 2|~|
|!Byte 3|a[1] byt3 3|~|
|!Byte 4|@@a[2] byte 1@@|a[2] in contiguous cells|
|!Byte 5|a[2] byte 2|~|
|!Byte 6|a[2] byt3 3|~|
|!Byte 7|@@a[3] byte 1@@|a[3] in contiguous cells|
|!Byte 8|a[3] byte 2|~|
|!Byte 9|a[3] byt3 3|~|
|''3-bytes Array in sequential memory''|c
Sequential memory access is fast for a single CPU. For super-computers and high-end servers, their CPU is often dual-core, or 4-core, even 8-core. The [[Connection Machine|http://en.wikipedia.org/wiki/Connection_Machine]] has up to 2^^16^^=64K ~CPUs connected together. For such CPU structures, sequential memory access is slow.
!Parallel Memory
With some ingenious microelectronics, memory can be organized into ''banks'':
access within each bank is ''sequential'' (normal speed), but access across each bank is ''parallel'' (extremely fast).
Consider storing the 3-bytes array in a 2-bank memory:
|!Memory|!Bank 1|!Bank 2|!Comment|
|!Byte 1|@@a[1] byte 1@@|a[1] byte 2|part of a[1] is across bank|
|!Byte 2|a[1] byte 3|@@a[2] byte 1@@| |
|!Byte 3|a[2] byte 2|a[2] byte 3|part of a[2] is across bank|
|!Byte 4|@@a[3] byte 1@@|a[3] byte 2| |
|!Byte 5|a[3] byte 3|@@a[4] byte 1@@|part of a[3] is across bank |
|''3-bytes Array in 2-bank memory''|c
Since memory access across bank is fast, this gives partial improvement in speeding up array access.
Consider storing the 3-bytes array in a 3-bank memory:
|!Memory|!Bank 1|!Bank 2|!Bank 3|!Comment|
|!Byte 1|@@a[1] byte 1@@|a[1] byte 2|a[1] byte 3|a[1] is across bank|
|!Byte 2|@@a[2] byte 1@@|a[2] byte 2|a[2] byte 3|a[2] is across bank|
|!Byte 3|@@a[3] byte 1@@|a[3] byte 2|a[3] byte 3|a[3] is across bank|
|''3-bytes Array in 3-bank memory''|c
Now each array element (3 bytes) has fast access, but successive array elements a[1], a[2], a[3], ... are still accessed sequentially.
Consider storing the 3-bytes array in a 4-bank memory:
|!Memory|!Bank 1|!Bank 2|!Bank 3|!Bank 4|!Comment|
|!Byte 1|@@a[1] byte 1@@|a[1] byte 2|a[1] byte 3|@@a[2] byte 1@@|a[1] is across bank|
|!Byte 1|a[2] byte 2|a[2] byte 3|@@a[3] byte 1@@|a[3] byte 2|a[2] is across bank|
|!Byte 3|a[3] byte 3|@@a[4] byte 1@@|a[4] byte 2|a[4] byte 3|a[3], a[4] are across bank|
Not only each array element has fast access, even array elements a[1], a[2], a[3], a[4],... are across bank, hence fast access.
The actual byte size of an array element is dependent on the programming language, especially its compiler, which is software. This is an unknown factor to the hardware manufacturer of Memory Banks, who is now presented with a problem:
//Is it possible to have memory banks that can accommodate array elements of any size? If yes, how many banks in memory is desirable?//
!How many Banks in Memory?
Using math from [[Infinite Interleaving]], the solution to the problem is:
//A ''prime'' number of banks in memory will (almost) fit array elements of any size across the banks, except elements with size a multiple of the prime.//
The exception can be taken care of by choosing an ''odd'' prime (any prime > 2), and the language compiler keeps array elements size a ''power of 2'' (1-byte, 2-bytes, 4-bytes, 8-bytes, etc). For example, Java's Virtual Machine (VM) provides array access of byte (8-bits), char or short (16-bits), int or float (32-bits), long or double (64-bits) and object references (addresses) -- all can be fitted nicely in even number of bytes.
This scheme for parallel memory is called ''Prime Degree Interleaving''. Some supercomputers and high-end servers make use of parallel memory of 5 or 7 banks. A small prime is chosen because it is still expensive to manufacture parallel memory -- hence this technology is not used for ~PCs.
!Address Decoding
For sequential memory, the address ''a'' requires no decoding:
|!Memory|!Address|!Comment|
|!Byte 1| 1|address is implicit|
|!Byte 2| 2|~|
|!Byte 3| 3|~|
|!Byte 4| 4|~|
|!Byte 5| 5|~|
|!Byte 6| 6|~|
|!Byte 7| 7|~|
|!...| ...|~|
|''Sequential Memory Addressing''|c
For paralllel memory with 3 banks, the address ''a'' is distributed as:
|!Memory|!Bank 1|!Bank 2|!Bank 3|!Comment|
|!Byte 1| 1| 2| 3|Can you see ''Z/3''?|
|!Byte 2| 4| 5| 6|~|
|!Byte 3| 7| 8| 9|~|
|!Byte 4| 10| 11| 12|~|
|!...| ...| ...| ...|~|
|''3-bank Paralllel Memory Addressing''|c
The logical linear address ''a'' requires some decoding to which Bank, which Byte:
|!Address|!Bank|!Byte|!Comment|
| 1|!Bank 1|!Byte 1|All Byte 1, only Bank varies|
| 2|!Bank 2|!Byte 1|~|
| 3|!Bank 3|!Byte 1|~|
| 4|!Bank 1|!Byte 2|All Byte 2, only Bank varies|
| 5|!Bank 2|!Byte 2|~|
| 6|!Bank 3|!Byte 2|~|
| 7|!Bank 1|!Byte 3|All Byte 3, only Bank varies|
| 8|!Bank 2|!Byte 3|~|
| 9|!Bank 3|!Byte 3|~|
| 10|!Bank 1|!Byte 4|All Byte 4, only Bank varies|
| 11|!Bank 2|!Byte 4|~|
| 12|!Bank 3|!Byte 4|~|
|''3-bank Paralllel Memory Address Decoding''|c
In general, for parallel memory with ''m'' banks, the address ''a'' is decoded as:
bank = ''a mod m'', the ''remainder'', byte = ''a div m'', the ''quotient''.
Since this addressing decoding is to be performed for every memory fetch, it is better if ''m'' is a power of 2 -- rather than a prime ''m''. In binary system, quotient and remainder of power of 2 is simply ''masking'' -- just like in decimals, quotient and remainder of 1123581321 by 10^^5^^=100000 can be done by chopping. Quotient and remainder in modulo prime is much harder compared to this.
Due to this overhead of address decoding, parallel memory is usually implemented in 2-banks, 4-banks, or 8-banks. To accommodate array elements of any size, special compilers are introduced to keep array element size always odd, because gcd(power of 2, odd) = 1.
!For more Info
PC Guide: Memory Interleaving
http://www.pcguide.com/ref/ram/timingInterleaving-c.html
An Analysis of a new Memory System for ~Conflict-Free Access
http://www.scichina.com:8081/sciAe/fileup/PDF/83ya0205.pdf
Based on this fact:
If the odd number ''2^^n^^-1'' is prime, then ''n'' must be prime.
Marin Mersenne (1588 – 1648) studied the following question:
Given a prime ''p'', will the odd number ''M~~p~~ = 2^^p^^-1'' be prime?
!Mersenne Numbers
Mersenne probably started with the following compilation:
|!prime p|!2^^p^^|!M~~p~~=2^^p^^-1|!Factorization of M~~p~~|
| 2| 4| 3| prime M~~2~~|
| 3| 8| 7| prime M~~3~~|
| 5| 32| 31| prime M~~5~~|
| 7| 128| 127| prime M~~7~~|
| 11| 2048| 2047|23*89|
| 13| 8192| 8191| prime M~~13~~|
| 17| 131072| 131071| prime M~~17~~|
| 19| 524288| 524287| prime M~~19~~|
| 23| 8388608| 8388607|47*178481|
| 29| 536870912| 536870911|233*1103*2089|
| 31| 2147483648| 2147483647| prime M~~31~~|
So the answer to Mersenne's question is no: given prime ''p'', ''M~~p~~'' can be prime or composite. However, the story continued.
!Mersenne Primes
In the preface to his //Cogitata ~Physica-Mathematica// (1644), Marin Mersenne stated that:
The numbers 2^^p^^-1 were prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and composite for all other p < 257.
The primes M~~p~~ for p = 2, 3, 5, 7, 13, 17, 19 were well known at that time, but Mersenne was announcing 4 more. It was obvious to Mersenne's peers that he could not have tested all of these numbers (in fact he admitted as such), and they could not test them either. It took three centuries and several mathematical discoveries (such as the Lucas Lehmer test), before the exponents in Mersenne's conjecture had been completely checked. It was determined that he had made five errors (three primes omitted, two composites listed) and the correct list is:
p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127
|!#|!prime p|!M~~p~~|!Number of digits in M~~p~~|!When|!Who|
|1| 2| 3| 1|500 BC|Greek mathematicians|
|2| 3| 7| 1|500 BC|Greek mathematicians|
|3| 5| 31| 2|300 BC|Greek mathematicians|
|4| 7| 127| 3|300 BC|Greek mathematicians|
|5| 13| 8191| 4|1456|anonymous|
|6| 17| 131071| 6|1588|Cataldi|
|7| 19| 524287| 6|1588|Cataldi|
|8| 31| 2147483647| 10|1772|Euler|
|9| 61| 2305843009213693951| 19|1883|Pervushin|
|10| 89| 618970019642690137449562111| 27|1911|Powers|
|11| 107| 162259276829213363391578010288127| 33|1914|Powers|
|12| 127| 170141183460469231731687303715884105727| 39|1876|Lucas|
|''Corrected list of Mersenne Primes with p < 257''|c
!Use of Mersenne Primes
Euclid (300 BC) was interested in numbers of the form 2^^p^^-1 due to the perfect numbers -- a number N whose sum of factors (excluding N) equals to N. Such numbers are not too hard to find, the following are know from antiquity:
|!Perfect Number N|!Sum of its factors|!Factorization of N|
|6|1+2+3=6|6=2*3|
|28|1+2+4+7+14=28|28=4*7|
Those familiar with the powers of 2 (2, 4, 8, 16, ...) will immediately spot a formula: ''2^^(p-1)^^(2^^p^^-1)''. Indeed, put in p = 5, you'll get another perfect number: 16*31 = 496. There are several equivalent ways to write this formula:
''2^^(p-1)^^(2^^p^^-1)'' = ''(2^^p^^/2)(2^^p^^-1)'' = ''(M~~p~~+1)M~~p~~/2''.
Indeed, Euclid provided a proof of this formula, which amounts to an application of Mersenne primes:
For a prime ''p'', if ''2^^p^^-1'' is prime, then ''2^^(p-1)^^(2^^p^^-1)'' is a perfect number.
Why? It is simple to observe that, a pure even N=2^^n^^ is almost perfect -- its factors are 1, 2, 4=2^^2^^, ..., 2^^(n-1)^^, so by the geometric series (sum of terms of same ratio) we have:
factor-sum of N = 1 + 2 + 2^^2^^ + ... + 2^^(n-1)^^ = 2^^n^^ - 1 = N - 1
How about a pure even with an odd prime ''q'', say N=2^^n^^q ? The additional factors are: 2^^n^^, q, 2q, 4q, ...., 2^^(n-1)^^q, so:
factor-sum of N = (1+2+...+2^^n-1^^)+(q+2q+...+2^^n-1^^q) + 2^^n^^ = (1+2+...+2^^n-1^^)(1+q) + 2^^n^^= (2^^n^^-1)(1+q) + 2^^n^^
For perfect number N: (2^^n^^-1)(1+q) + 2^^n^^ = N = 2^^n^^q
Solving for q gives: q = 2^^n^^-1+2^^n^^=2^^(n+1)^^-1. This gives the formula after some symbolic substitutions.
In 1732, Euler proved the converse:
All even perfect numbers are of the form ''2^^(p-1)^^(2^^p^^-1)'', for each Mersenne prime ''2^^p^^-1''.
Therefore each ''Mersenne prime M~~p~~'' corresponds to an ''even Perfect Number'':
|!#|!prime p|!Mersenne prime M~~p~~|!2^^(p-1)^^(2^^p^^-1)|!Perfect Number|
|1| 2| 3| 2*3| 6|
|2| 3| 7| 4*7| 28|
|3| 5| 31| 16*31| 496|
|4| 7| 127| 2^^6^^*127| 8128|
|5| 13| 8191| 2^^12^^(2^^13^^-1)| 33550336|
|6| 17| 131071| 2^^16^^(2^^17^^-1)| 8589869056|
|7| 19| 524287| 2^^18^^(2^^19^^-1)| 34359672832|
|8| 31| 2147483647| 2^^30^^(2^^31^^-1)| 2305843008139952128|
|9| 61| 2305843009213693951| 2^^60^^(2^^61^^-1)| 2658455991569831744654692615953842176|
|10| 89| 618970019642690137449562111| 2^^88^^(2^^89^^-1)| 191561942608236107294793378084303638130997321548169216|
|''Mersenne Primes and Perfect Numbers''|c
It is not know if any odd perfect number exists.
Mersenne's list initiated the study of primality testing of M~~p~~. This is an active area of research even today. The record for the largest Mersenne prime keeps breaking, see [[ GIMPS|www.mersenne.org/]], the ''Great Internet Mersenne Prime Search''.
This is //really// ''funny''
Other special --sorry-- __effects__.
Can we bold like this? <html><b>Hello</b></html> Yes! Just put any valid HTML between {{{<html>}}} and {{{</html>}}}.
This is TiddlyWikiSyntax.
This is [[TiddlyWikiSyntax 2]].
This is ''bold'' (two single quotes), this is //italics// (two slashes).
This is __underline__, this is --strike through--.
This is {{{Monospace}}}.
This is @@Highlighed Text@@.
This is @@color(red):Red colored text@@.
For superscript: e^^ix^^.
For subscript: a~~n~~.
For underscore: a + b__i__ + c__j__ + d__k__.
Below is a horizontal ruler (4 hyphens):
----
For images, the ways are:
{{{
[img[filename]]
[img[filename][link]] link = jump if image is clicked, optional.
[img[title|filename]]
[img[title|filename][link]] title = tool-tip, optional.
}}}
<!--{{{-->
<div class='header' macro='gradient vert [[ColorPalette::PrimaryLight]] [[ColorPalette::PrimaryMid]]'>
<div class='headerShadow'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
<div class='headerForeground'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
</div>
<!-- horizontal MainMenu -->
<div id='topMenu' refresh='content' tiddler='MainMenu'></div>
<!--original MainMenu menu-->
<!-- div id='mainMenu' refresh='content' tiddler='MainMenu'></div -->
<div id='sidebar'>
<div id='sidebarOptions' refresh='content' tiddler='SideBarOptions'></div>
<div id='sidebarTabs' refresh='content' force='true' tiddler='SideBarTabs'></div>
</div>
<div id='displayArea'>
<div id='messageArea'></div>
<div id='tiddlerDisplay'></div>
</div>
<!--}}}-->
|Standard Periodic Table (ref. Wikipedia)|c
|!Period\Group| !1 | !2 |!| !3 | !4 | !5 | !6 | !7 | !8 | !9 | !10 | !11 | !12 | !13 | !14 | !15 | !16 | !17 | !18 |
|!1|bgcolor(#a0ffa0): @@color(red):H@@ |>|>|>|>|>|>|>|>|>|>|>|>|>|>|>|>||bgcolor(#c0ffff): @@color(red):He@@ |
|!2|bgcolor(#ff6666): Li |bgcolor(#ffdead): Be |>|>|>|>|>|>|>|>|>|>||bgcolor(#cccc99): B |bgcolor(#a0ffa0): C |bgcolor(#a0ffa0): @@color(red):N@@ |bgcolor(#a0ffa0): @@color(red):O@@ |bgcolor(#ffff99): @@color(red):F@@ |bgcolor(#c0ffff): @@color(red):Ne@@ |
|!3|bgcolor(#ff6666): Na |bgcolor(#ffdead): Mg |>|>|>|>|>|>|>|>|>|>||bgcolor(#cccccc): Al |bgcolor(#cccc99): Si |bgcolor(#a0ffa0): P |bgcolor(#a0ffa0): S |bgcolor(#ffff99): @@color(red):Cl@@ |bgcolor(#c0ffff): @@color(red):Ar@@ |
|!4|bgcolor(#ff6666): K |bgcolor(#ffdead): Ca ||bgcolor(#ffc0c0): Sc |bgcolor(#ffc0c0): Ti |bgcolor(#ffc0c0): V |bgcolor(#ffc0c0): Cr |bgcolor(#ffc0c0): Mn |bgcolor(#ffc0c0): Fe |bgcolor(#ffc0c0): Co |bgcolor(#ffc0c0): Ni |bgcolor(#ffc0c0): Cu |bgcolor(#ffc0c0): Zn |bgcolor(#cccccc): Ga |bgcolor(#cccc99): Ge |bgcolor(#cccc99): As |bgcolor(#a0ffa0): Se |bgcolor(#ffff99): @@color(green):Br@@ |bgcolor(#c0ffff): @@color(red):Kr@@ |
|!5|bgcolor(#ff6666): Rb |bgcolor(#ffdead): Sr ||bgcolor(#ffc0c0): Y |bgcolor(#ffc0c0): Zr |bgcolor(#ffc0c0): Nb |bgcolor(#ffc0c0): Mo |bgcolor(#ffc0c0): Tc |bgcolor(#ffc0c0): Ru |bgcolor(#ffc0c0): Rh |bgcolor(#ffc0c0): Pd |bgcolor(#ffc0c0): Ag |bgcolor(#ffc0c0): Cd |bgcolor(#cccccc): In |bgcolor(#cccccc): Sn |bgcolor(#cccc99): Sb |bgcolor(#cccc99): Te |bgcolor(#ffff99): I |bgcolor(#c0ffff): @@color(red):Xe@@ |
|!6|bgcolor(#ff6666): Cs |bgcolor(#ffdead): Ba |bgcolor(#ffbfff):^^*1^^|bgcolor(#ffc0c0): Lu |bgcolor(#ffc0c0): Hf |bgcolor(#ffc0c0): Ta |bgcolor(#ffc0c0): W |bgcolor(#ffc0c0): Re |bgcolor(#ffc0c0): Os |bgcolor(#ffc0c0): Ir |bgcolor(#ffc0c0): Pt |bgcolor(#ffc0c0): Au |bgcolor(#ffc0c0): @@color(green):Hg@@ |bgcolor(#cccccc): Tl |bgcolor(#cccccc): Pb |bgcolor(#cccccc): Bi |bgcolor(#cccc99): Po |bgcolor(#ffff99): At |bgcolor(#c0ffff): @@color(red):Rn@@ |
|!7|bgcolor(#ff6666): Fr |bgcolor(#ffdead): Ra |bgcolor(#ff99cc):^^*2^^|bgcolor(#ffc0c0): Lr |bgcolor(#ffc0c0): Rf |bgcolor(#ffc0c0): Db |bgcolor(#ffc0c0): Sq |bgcolor(#ffc0c0): Bh |bgcolor(#ffc0c0): Hs |bgcolor(#ffc0c0): Mt |bgcolor(#ffc0c0): Ds |bgcolor(#ffc0c0): Rg |bgcolor(#ffc0c0): @@color(green):Uub@@ |bgcolor(#cccccc): Uut |bgcolor(#cccccc): Uuq |bgcolor(#cccccc): Uup |bgcolor(#cccccc): Uuh |bgcolor(#fcfecc): @@color(#cccccc):Uus@@ |bgcolor(#ecfefc): @@color(#cccccc):Uuo@@ |
| !Lanthanides^^*1^^|bgcolor(#ffbfff): La |bgcolor(#ffbfff): Ce |bgcolor(#ffbfff): Pr |bgcolor(#ffbfff): Nd |bgcolor(#ffbfff): Pm |bgcolor(#ffbfff): Sm |bgcolor(#ffbfff): Eu |bgcolor(#ffbfff): Gd |bgcolor(#ffbfff): Tb |bgcolor(#ffbfff): Dy |bgcolor(#ffbfff): Ho |bgcolor(#ffbfff): Er |bgcolor(#ffbfff): Tm |bgcolor(#ffbfff): Yb |
| !Actinides^^*2^^|bgcolor(#ff99cc): Ac |bgcolor(#ff99cc): Th |bgcolor(#ff99cc): Pa |bgcolor(#ff99cc): U |bgcolor(#ff99cc): Np |bgcolor(#ff99cc): Pu |bgcolor(#ff99cc): Am |bgcolor(#ff99cc): Cm |bgcolor(#ff99cc): Bk |bgcolor(#ff99cc): Cf |bgcolor(#ff99cc): Es |bgcolor(#ff99cc): Fm |bgcolor(#ff99cc): Md |bgcolor(#ff99cc): No |
*Chemical Series of the Periodic Table
**@@bgcolor(#ff6666): Alkali metals@@
**@@bgcolor(#ffdead): Alkaline earth metals@@
**@@bgcolor(#ffbfff): Lanthanides@@
**@@bgcolor(#ff99cc): Actinides@@
**@@bgcolor(#ffc0c0): Transition metals@@
**@@bgcolor(#cccccc): Poor metals@@
**@@bgcolor(#cccc99): Metalloids@@
**@@bgcolor(#a0ffa0): Nonmetals@@
**@@bgcolor(#ffff99): Halogens@@
**@@bgcolor(#c0ffff): Noble gases@@
*State at standard temperature and pressure
**those in @@color(red):red@@ are gases
**those in @@color(green):green@@ are liquids
**those in black are solids
On the software side, the common [[linear congruence random generators|Linear Congruences]] have been extensively analyzed statistically, and some defects are exposed. It is deemed that they are adequate for ordinary use, but will not be good for serious computer simulations -- for example: climate, XBox computer games, etc.).
!Mersenne Twister
In 1997, two Japanese mathematicians ''Makoto Matsumoto'' and ''Takuji Nishimura'' developed a new type of random number generator based on:
* matrix linear recurrence over the finite field [[GF(2)|Group, Ring and Field]], and
* twisted feedback shift register, a generalization of [[LFSR|Simple Machines]].
This involves the use of Mersenne primes, and they name their new algorithm ''Mersenne Twister'', so that their initials (MT) are hidden in the name. The source code is freely available, hence MT is open-sourced. The authors also make the code platform independent, which means the code is portable to various software or hardware.
MT has been extensively tested in theory and in practice. Its performance is fast with good statistical characteristics. It quickly becomes the (pseudo) random number generator of choice in various software libraries. It is currently used in Ruby, Python, Maple, MATLAB, R (a statistical programming language) and even ~XBox.
This is an application of Mersenne primes in random number generation. The authors (MT) have since improved the code in January 2002.
!Further Information
See http://en.wikipedia.org/wiki/Mersenne_Twister
!Topics
# [[Primes for Random]]
# [[Primes for Secrets]]
# [[Primes for Checks]]
# [[Primes for Speed]]
# [[Primes for Math]]
# [[Primes for Tricks]]
# [[Primes for Nature]]
# [[Primes for Art]]
!About this page
This page is based on [[TiddlyWiki|http://www.tiddlywiki.com/]]: a reusable non-linear personal web notebook.
A ~TiddlyWiki is a blog in a single webpage: if the cursor over bold word shows a link, clicking will expand the word to the heading of a blog, with details. The details may show other links, clicking will expand to more blogs. The upper right corner of a blog has "close", which closes the blog.
!Note
Years ago in ~TiddlyWiki you can "edit" a blog in a browser, and save the changes. Also, you can run Java applet in a browser. Modern browsers have disabled such features due to security concerns. If you find some contents are not working, don't be disapponted.
!Pattern from Polynomials
You may be surprised that primes aligning like beads along diagonals of the spiral: some bead pearls are long, some are short.
If you start the spiral with 41, you'll get:
[img[PrimeSpiral41.gif]]
That long string of circled primes on the diagonal, in sequence, is 41, 43, 47, 53, ..., 1523, 1601. They can be produced by
* either the polynomial: ''x^^2^^ + x + 41'' for ''0≤n≤39'' due to Euler (1772) ,
* or the polynomial ''x^^2^^ - x + 41'' for ''1≤n≤40'' due to Legendre (1798) .
|!x|!x^^2^^ + x + 41|!x^^2^^ - x + 41|
| 0| 0+0+41=41||
| 1| 1+1+41=43| 1-1+41=41|
| 2| 4+2+41=47| 4-2+41=43|
| 3| 9+3+41=53| 9-3+41=47|
| 4| 16+4+41=61| 16-4+41=53|
| 5| 25+5+41=71| 25-5+41=61|
| 6| 36+6+41=83| 36-6+41=71|
|...| ...| ...|
|36| 1296+36+41=1373| 1296-36+41=1301|
|37| 1369+37+41=1447| 1369-37+41=1373|
|38| 1444+38+41=1523| 1444-38+41=1447|
|39| 1521+39+41=1601| 1521-39+41=1523|
|40| | 1600-40+41=1601|
|''Polynomial giving primes''|c
Polynomials like this, which generate long strings of primes, are called ''prime generating polynomials''.
!More information
Wolfram ~MathWorld: ~Prime-Generating Polynomial
http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
Math Games: Prime Generating Polynomials
http://www.maa.org/editorial/mathgames/mathgames_07_17_06.html
!~One-Dimensional Pattern
On the number line, you can mark off the prime numbers, like this:
{{{
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| | | | | | | | | |
}}}
Each vertical line indicates the presence of a prime at that number position. Together, they form a ''spectrum'' for the primes.
!Pattern in Spectrum
There are 78 primes ≤ 400:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
This gives the first of the following ''prime spectrum'':
| 1-400|<<sparkline 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0>>|
| 401-800|<<sparkline 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0>>|
| 801-1200|<<sparkline 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0>>|
|1201-1600|<<sparkline 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0>>|
|1601-2000|<<sparkline 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0>>|
At the start, the primes are dense, but there are fewer primes the further away from start. Still, you can find primes nearby: ''p'' and ''p+2'' are primes -- these are called ''Twin Primes''.
Since a line cannot be extended for too long before running out of space (or paper), it is hard to detect any pattern in 1D distribution of primes, if any.
!Primes and Patterns
Are there patterns in the distribution of primes? To see if there are any, you need to display the primes -- how?
* [[Prime Spectrum]] - a 1D picture of primes.
* [[Ulam Spiral]] - a 2D picture of primes.
* [[Prime Generating Polynomials]] - pattern and polynomials.
!More Patterns
Gruenberger’s prime path
http://bit-player.org/2010/gruenbergers-prime-path
Thanks to Évariste Galois, the teenage math wizard during the French Revolutions, we have the following result:
A finite system within which add, subtract, multiply and division can be consistently done (called a [[Finite Field|Group, Ring and Field]]) must have ''p^^n^^'' elements, where ''p'' is a prime and ''n'' a nonzero whole number.
Such finite fields, or ''Galois Fields'' have extensive applications, ranging from error-detection to error-correction, use of extremely weak signals in communication, and the design of invisible surfaces. Here we take a look at a simple application of Galois Fields: in error-detection.
!Error-detection Schemes
* [[ISBN check digit]]
Prime numbers are the building blocks of numbers for multiplication -- the "atomic" factors: a prime has no non-trivial factors. This property of primes is quite useful in mathematics itself, particularly in the study of numbers.
!The Powers of 2
''2'' is the (only) even prime. The powers of 2 (or ''towers of 2''): 2, 2^^2^^=4, 2^^3^^=8, 2^^4^^=16, 2^^5^^=32, ..., are pure even numbers -- they do not have any odd factors. As a result, 2^^n^^±1 are odd numbers -- how often will they be (odd) primes?
|!n|!2^^n^^|!2^^n^^-1|!2^^n^^+1|!2^^n^^ in binary|!2^^n^^-1 in binary|!2^^n^^+1 in binary|
|1| 2| 1| @@3@@| 10| 1| 11|
|2| 4| @@3@@| @@5@@| 100| 11| 101|
|3| 8| @@7@@| 9| 1000| 111| 1001|
|4| 16| 15| @@17@@| 10000| 1111| 10001|
|5| 32| @@31@@| 33| 100000| 11111| 100001|
|6| 64| 63| 65| 1000000| 111111| 1000001|
|7| 128| @@127@@| 129| 10000000| 1111111| 10000001|
|8| 256| 255| @@257@@| 100000000| 11111111| 100000001|
|9| 512| 511| 513| 1000000000| 111111111| 1000000001|
|10| 1024| 1023| 1025| 10000000000| 1111111111| 10000000001|
|''Primes of 2^^n^^±1 are highlighted''|c
In binary, the ''pure even'' ''2^^n^^'' is just 1 followed by n zeros, and ''2^^n^^-1'' is just n ones.
!One less than Pure Even
Consider odd numbers of the form 2^^n^^-1. Based on the well-known factorization identities:
x^^2^^ - 1 = (x - 1)(x + 1)
x^^3^^ - 1 = (x - 1)(x^^2^^ + x + 1)
x^^5^^ - 1 = (x - 1)(x^^4^^ + x^^3^^ + x^^2^^ + x + 1)
If exponent n has non-trivial factors: ''n=pq'' with p>1 and q>1, then we can apply one of these identities to factorize 2^^n^^-1 = 2^^(pq)^^-1 = (2^^p^^)^^q^^-1:
|!n=pq|!2^^n^^-1|!Factorization of 2^^n^^-1|
| 4=2*2| 15|15=2^^4^^-1=4^^2^^-1=(4-1)(4+1)=3*5|
| 6=2*3| 63|63=2^^6^^-1=8^^2^^-1=(8-1)(8+1)=7*9=3*3*7|
| 8=2*4| 255|255=2^^8^^-1=16^^2^^-1=(16-1)(16+1)=15*17=3*5*17|
| 9=3*3| 511|511=2^^9^^-1=8^^3^^-1=(8-1)(8*8+8+1)=7*73|
| 10=2*5| 1023|1023=2^^10^^-1=32^^2^^-1=(32-1)(32+1)=31*33=3*11*31|
|''Factorization of 2^^n^^-1 when n is composite''|c
Hence we have the this result: If ''n'' is not prime, then the odd number ''2^^n^^-1'' is not prime.
Logically, this is equivalent to: If the odd number ''2^^n^^-1'' is prime, then ''n'' must be prime.
The 17th-century French scholar ''Marin Mersenne'' studied the following question:
Given a prime ''p'', will the odd number ''2^^p^^-1'' be prime?
Nowadays, these odd numbers ''M~~p~~ = 2^^p^^-1'' for prime ''p'' are called [[Mersenne Numbers]] <-- click to find out more.
!One more than Pure Even
Consider odd numbers of the form 2^^n^^+1. If n is composite and has an odd factor, say ''n=pq'' with q ''odd'', then since +1=-(-1)^^q^^ for odd q:
2^^n^^+1 = 2^^pq^^-(-1) = (2^^p^^)^^q^^ - (-1)^^q^^ = (2^^p^^+1)(2^^q^^-2^^q-1^^+....+1)
|!n=pq with q odd|!2^^n^^+1|!Factorization of 2^^n^^+1|
| 3=1*3| 9|9=2^^3^^+1=2^^3^^-(-1)^^3^^=(2+1)(4-2+1)=3*3|
| 5=1*5| 33|33=2^^5^^+1=2^^5^^-(-1)^^5^^=(2+1)(16-8+4-2+1)=3*11|
| 6=2*3| 65|65=2^^6^^+1=4^^3^^-(-1)^^3^^=(4+1)(16-4+1)=5*13|
| 7=1*7| 129|129=2^^7^^+1=2^^7^^-(-1)^^7^^=(2+1)(64-32+16-8+4-2+1)=3*43|
| 9=3*3| 513|513=2^^9^^+1=8^^3^^-(-1)^^3^^=(8+1)(64-8+1)=9*57=3*3*3*19|
| 10=2*5| 1025|1025=2^^10^^+1=4^^5^^-(-1)^^5^^=(4+1)(4^^4^^-4^^3^^+4^^2^^-4+1)=5*205=5*5*41|
|''Factorization of 2^^n^^+1 when n has odd factor''|c
Hence we have the this result: If ''n'' has an odd factor, then the odd number ''2^^n^^+1'' is not prime.
Logically, this is equivalent to: If the odd number ''2^^n^^+1'' is prime, then ''n'' has no odd factors.
This can be re-written as: If the odd number ''2^^n^^+1'' is prime, then ''n=2^^k^^'', a pure even.
The 17th-century French lawyer ''Pierre de Fermat'' studied the following question:
Given a pure even ''2^^n^^'', will the odd number ''2^^<html>2<sup>n</sup></html>^^+1'' be prime?
Nowadays, these odd numbers ''F~~n~~ = 2^^<html>2<sup>n</sup></html>^^+1'' are called [[Fermat Numbers]] <-- click to find out more.
One way to generate primes is known from antiquity: the [[Sieve of Eratosthenes|sieve.html]]. This is a process of elimination. Evolution also involves elimination, in the famous Darwinian principle of ''Survival of fittest''. Can nature produce primes, too?
!Life Cycle of Cicadas (蟬)
There are three distinct stages in the life cycle of a cicada - egg, nymph and adult.
!!!Egg stage
After mating, the female will lay several hundred eggs. She makes a little slit in the bark of the branch as she walks along and pushes the eggs down through her long tail. She deposits 12 or so into each slit and then moves on a few millimeters to make another slit for more eggs, and so on, until all the eggs have been laid.
!!!Nymph stage
The eggs stay in the slits in the bark for many weeks and then hatch into a miniature cicada called a nymph. Because they are so small they can fall down to the ground without injuring themselves and seek shelter underneath the leaf litter. These cicada nypmhs attached themselves to tree roots at depth of 12" -18" in the ground. It's here, underground, that cicadas spend most of their life. The cicada nymph feeds by piercing small tree roots with its needle-like rostrum and sucking up sap.
!!!Adult stage
When the nymphs finally reach full size they dig their way to the surface. They begin a vertical climb - trees, poles, tall grass - where they anchor themselves and begin popping out of their shells. The life of the adult, in contrast to that of the nymph, is very short.
[img[cicada1.jpg]] [img[cicada2.jpg]] [img[cicada3.jpg]]
When the cicadas emerge from their shells, they are pale and soft, and their wings are folded and compressed. As they are exposed to air, their wings unfold, and their bodies darken and harden. At this mature stage, they begin their nearly incessant singing in search for a mate. They have one purpose at this stage, and it ain't eating!
[img[cicada-life-cycle.jpg]]
After the male empties his sperm capacity, he keels over and dies. The female injects her 400-600 eggs into the thin end of a branch and keels over and dies. The eggs hatch in 6 - 8 weeks, when they fall to the ground, and begin grubbing on grass roots. They begin their downward descent, attach to a tree root for another long time. Repeat. Amazing!
!Period of Cicadas Life Cycle
Depending on the species, when cicadas emerge from the ground they live from a few days to a couple of months, the majority live for around two to four weeks. However, their underground live as a nymph can take anything from nine months to 13 or 17 years depending on the species. Most species take around 7 years to re-emerge.
Note that the numbers 7, 13, 17 are primes.
Why these primes for the period of life-cycle for cicadas?
Scientists believe there is a predator that likes to prey on the adult and also emerges periodically after a certain number of years. In biological systems, the coexistence of predator and prey often like to [[Predator-Prey-Cycles|http://en.wikipedia.org/wiki/Lotka%E2%80%93Volterra_equation]]. Perhaps the cicadas find that, by choosing a prime-number cycle, they can keep out of step of the predator more often than otherwise. Evolution might have helped the cicadas to find these primes through elimination of multiples, like the [[Sieve of Eratosthenes|sieve.html]] <-- click to have a play.
For the cicadas, the primes are the secret to their survival.
!More Information
Beckham in his prime number
http://plus.maths.org/issue26/features/sautoy/
Return of the 17 Year Cicadas
http://www.youtube.com/watch?v=RYLxxALTfAQ
Brian Hayes: Bugs That Count
http://www.americanscientist.org/issues/pub/bugs-that-count
!Random Numbers
Nowadays computer games are fast and exciting, but probably you can still find and play the Solitaire Card Game on your PC. The game starts with 52 cards in random order, face down. How does a computer, at the heart a machine that always give the same output with the same input, produce something random?
The surprising fact is: yes, there is no mechanical way to generate truly random numbers.
However, there are methods to generate a list of numbers that looks random -- the list is long and there is no obvious patterns; but if you wait long enough you'll find that the numbers eventually repeat. The length of the non-repeating pattern is called the period. There are computer algorithms that generate periodic number sequences, and prime numbers are involved for very long periods.
Some computer theorists would say these should be called pseudo-random numbers (which are periodic), to distinguish them from truly random numbers (which are non-periodic). We won't be that careful -- we just understand that our generated random numbers are good enough to shuffle the cards in Solitaire.
Having a long period for a number sequence is just one of the many requirements of a random number sequence: patterns of the sequence must pass some statistical tests to ensure how random-like the sequence is. We are not going into the full theory of random number generators -- we just take a look at how primes enter into this process of random number generation.
!How to generate Random Numbers
These are some common methods for random number generation using computer:
* [[Linear Congruences]]
* [[Simple Machines]]
* [[Portable Libraries]]
How to send digital information securely over the Internet? This is the number-one topic in Internet security. This is also is the application of modern cryptography, using prime numbers.
!Cryptography
[[Cryptography]] is all about encryption (scramble plain information to secret) and decryption (unscramble secret to plain information).
For example, during logon to check your email, how to send your password without exposing it to others on the Net? If you are using a web-based email service, you'll notice that the email server changes the protocol from ''http:'' to ''https:'' -- this is secure HTTP protocol, which tells the browser how to encrypt your password. The encrypted password is sent over the Net to the email server. The server then decrypts to recover the password, validates it, and tells the browser if the email logon is successful.
All spies use cryptography for communication. They learn the tricks of encryption and decryption to pass on secrets. Military use cryptography extensively to code and decode their messages, and intelligence must understand cryptography to 'crack the codes'. To make the codes hard to crack, encryption and decryption methods get more and more sophisticated -- meaning more and more tedious for human. Eventually, by World War II, mechanical devices are invented to assist in the encryption and decryption. Later, electronic machines are designed to assist in cracking the code. These electronic machines are the grand-daddy of modern computers.
Therefore, cryptography has been used throughout history. Although math is used in encryption and decryption, the methods are not related to prime numbers. However, none of these spies, military or intelligence before face the same problem of modern-day email server: how to fast encrypt and decrypt thousands of passwords per second, every second?
The answer is really a surprise: use a single, simple method (so it is fast) both to encrypt and decrypt, even the cracking is theoretically simple -- the catch is: cracking is practically impossible. As you'll see, this is where prime numbers come in.
The experts are so confident about the catch that the single, simple method is make known to all -- the method itself is no secret. Upon changing to HTTPS, the browser applies the method with a ''public key'' from the server to encrypt the password. The server applies the same method with a ''private key'' to recover the password. The ''key pair'' (both the public and private keys) is generated by the server. The public key is made public, and the private key is kept private (of course). While it is easy to generate the key pair, it is practically impossible to deduce the private key from a knowledge of the public key and the simple method. This is how your passwords, credit-card details, banking transactions, etc. are protected when you use the Internet.
Refer to [[Public Key Encryption|pkey.html]] for an in-depth discussion. Below is a brief highlight of the main results.
!Key-pair Encryption and Decryption
Nowadays all information is digital -- that is, all data are internally represented by numbers. To encrypt data is to apply a method to the numbers, using a ''public key'' ''e'' (for encrypt). To decrypt is to apply the same method to the encrypted numbers, using a ''private key'' ''d'' (for decrypt). How to generate such pairs of keys ''d'' and ''e''?
The generation of key pairs depends on the method, use both for encryption and decryption. Let the operation of the method be denoted by ''#''. If ''x'' is the original data, ''y'' is the scrambled data, we have: ''y'' = ''x#e'' and ''x'' = ''y#d''. Or, equivalently,
''x'' = ''x#e#d''.
This almost indicates that the operation ''#'' must involve some sort of cyclic math -- you keep changing the data by the ''same'' operation, and arrive back at the original!
Let's consider 3 possible operations in cyclic math of ''modulus n'', i.e. arithmetic of the remainders after integer division by ''n''.
* Key pairs for [[Cyclic Addition]]
* Key pairs for [[Cyclic Multiplication]]
* Key pairs for [[Cyclic Exponentiation]]
None of these provide a secure method of Public Key Encryption, although the third method raises some hopes.
!RSA Scheme
It took 3 brains from MIT (Ron Rivest, Adi Shamir, and Leonard Adleman) to come with a practical method for Public Key Encryption. They named the method by their initials: ''RSA''.
* [[Key pairs for RSA]]
* [[View the RSA public key|SSL Certificate]]
* [[History of RSA]]
Prime numbers can be useful in designs for efficiency. Here are two examples:
#[[Hashing]] - How apparent messiness can be effective for searching.
#[[Interleaving]] - How to break up a regular sequence to avoid delay.
Click and see how primes can help in these areas.
Due to practical issues during implementation, in real life not all ''Hashing'' and ''Interleaving'' schemes are based on primes.
However, it is still interesting to know that primes can be useful for better designs, at least in theory.
A whole number greater than 1 is either a prime or not a prime. This elementary property can be used effectively in magic tricks.
Here, we shall study a card trick call ''Exchange of Packs'', in 3 versions:
* The 1st description involves no primes, and the trick is so simple that even little kids will not be surprised.
* The 2nd description is the same trick, but slightly modified so that little kids may be surprised.
* The 3rd description is the same trick, but so subtly modified that you can fool a few audiences.
All versions involve a magician (you) and two audiences X, Y (simply pick them from the audiences).
!Exchange of Packs - No-trick version
* Beforehand, prepare the 52 cards in two piles: ''reds'' in pile A, ''blacks'' in pile B.
* Give pile A to audience X, pile B to audience Y.
* Ask each to shuffle his/her pile, randomly select a card, look and show only to audiences, then place the card face-down on the other pile (i.e. X's chosen card on pile B, Y's chosen card on pile A).
* Each shuffle his/her pile again.
* Magician collects piles A and B, one on top of the other (no shuffling).
* Then he flips the cards and scan.
** In the black cards there'll be a red card = X's chosen card.
** In the red cards there'll be a black card = Y's chosen card.
Even kids can figure this out. However, this description shows the principle of the trick -- just two ''types'' of cards. There are many variations on how to define the two ''types''.
!Exchange of Packs - Tricker version
* Beforehand, prepare the 52 cards in two piles: ''odds'' in pile A, ''evens'' in pile B.
* //rest the same//
!Exchange of Packs - Magic version
* Beforehand, prepare the 52 cards in two piles: ''primes'' in pile A, ''non-primes'' in pile B.
* //rest the same//
Whether a card is prime depends on its value:
|!Card|!Value|!Prime?|
|Ace|1|??|
|2|2|yes|
|3|3|yes|
|4|4| no|
|5|5|yes|
|6|6| no|
|7|7|yes|
|8|8| no|
|9|9| no|
|10|10| no|
|Jack|11|yes|
|Queen|12| no|
|King|13|yes|
|''Cards and Values''|c
How to treat the Ace cards? There are several options:
# You can take Ace=1 as prime, slightly bending the math definition. This makes pile A a bit bigger than pile B.
# You can take Ace=1 as not a prime, true to the math definition. This makes pile A a bit smaller than pile B.
# You can take red Ace as prime, black Ace as non-prime -- or vice versa, as long as you stick to your own definition. Same size for piles A, B.
# You can take out the 4 Ace cards beforehand -- this also makes the two piles A, B the same size.
For more information on adding extras to make this magic trick perfect, see [[Magic Trick: Prime Pairs|http://www.mrmagician.co.uk/prime-pairs.html]].
You can invent your own variation of this trick. As stated in the no-trick version, this only depends on dividing the cards into two ''types''. For example:
** ''type A'': red primes and black non-primes,
** ''type B'': black primes and red non-primes.
Here is a review of [[Group, Ring and Field]].
!Ring from Ring
It was the investigation of polynomial roots that gets Galois into the study of group, ring and field. We learn about add, subtract, multiply and division of polynomials in our school days. Let's see what's so interesting about polynomials.
A polynomial in x is a symbolic expression for the form: a~~0~~ + a~~1~~x + a~~2~~x^^2^^ + .... + a~~n~~x^^n^^
Here x is just a symbol - we are not going to put any numeric value to x, at least for our simple study of polynomials. The a~~j~~ are coefficients of the corresponding x^^j^^ term. These coefficients a~~j~~ are usually integers, but ''Z(+,*)'' is a ring, and any ring will do. All the polynomials constructed with coefficients from a ''Ring R'' is denoted by ''R[x]''.
We can add, subtract, multiply one polynomial by another. There is also the long division of polynomials, giving a quotient and a remainder. So polynomials behave very much like integers. Indeed, it can be shown that ''R[x]'' is itself a ring -- so this is ring from ring.
A field is just a ring with nice multiplication, so the coefficients can also come from a field. All the polynomials constructed with coefficients from a ''Field F'' is denoted by ''F[x]''.
Note that ''F[x]'' is still a ring, although the nice features of the field ''F'' do give some special properties for this ring.
Without getting into the theory of polynomial rings, let us look at the simplest of such polynomials, built from coefficient of the finite field ''GF(2)'', or ''binary field''.
!Polynomials of GF(2)
A polynomial of GF(2) has coefficients 0 or 1: a~~0~~ + a~~1~~x + a~~2~~x^^2^^ + .... + a~~n~~x^^n^^, with a~~j~~=0 or 1.
They form the ring ''GF(2)[x]''. Up to the 4th coefficient, the polynomials of ''GF(2)[x]'' are:
|!a~~0~~|!a~~1~~|!a~~2~~|!a~~3~~|!p(x)=a~~0~~+a~~1~~x+a~~2~~x^^2^^+a~~3~~x^^3^^|
|0|0|0|0|0|
|1|0|0|0|1|
|0|1|0|0|x|
|1|1|0|0|1+x|
|0|0|1|0|x^^2^^|
|1|0|1|0|1+x^^2^^|
|0|1|1|0|x+x^^2^^|
|1|1|1|0|1+x+x^^2^^|
|0|0|0|1|x^^3^^|
|1|0|0|1|1+x^^3^^|
|0|1|0|1|x+x^^3^^|
|1|1|0|1|1+x+x^^3^^|
|0|0|1|1|x^^2^^+x^^3^^|
|1|0|1|1|1+x^^2^^+x^^3^^|
|0|1|1|1|x+x^^2^^+x^^3^^|
|1|1|1|1|1+x+x^^2^^+x^^3^^|
|''16 polynomials of GF(2)[x] with 4 coefficients''|c
All the polynomials in ''GF(2)[x]'' form a ring. But can these 16 polynomials themselves form a (sub)-ring? Let's see:
* Addition seems no problem: (x)+(1+x) = 1+2x = 1, since 2=0 in GF(2). In fact, each polynomial is its own additive inverse: p(x)+p(x) = 2p(x) = 0.* Multiplication gives some problem: (x)(x^^3^^) = x^^4^^, which is not one of the 16 polynomials.
It turns out that, if the 15 nonzero polynomials are taken as possible remainders of division by 1+x^^3^^+x^^4^^, then multiplication works fine:
(x)(x^^3^^) = x^^4^^ = (1)(1+x^^3^^+x^^4^^)-(1+x^^3^^), remainder -1-x^^3^^=1+x^^3^^ since -1=1 in GF(2).
(1+x^^2^^)(1+x^^3^^) = 1+x^^2^^+x^^3^^+x^^5^^ = (1+x)(1+x^^3^^+x^^4^^) - (x-x^^2^^+2x^^4^^), remainder x+x^^2^^+2x^^4^^=x+x^^2^^.
Further calculations reveal that the remainder multiplication works very nice:
(x)(x^^2^^+x^^3^^) = x^^3^^+x^^4^^ = (1)(1+x^^3^^+x^^4^^)-(1), remainder -1=1. Hence x and x^^2^^+x^^3^^ are inverses.
(1+x)(x^^3^^) = x^^3^^+x^^4^^ = (1)(1+x^^3^^+x^^4^^)-(1), remainder -1=1. Hence 1+x and x^^3^^ are inverses.
(1+x+x^^2^^)(x+x^^2^^+x^^3^^) = x+2x^^2^^+3x^^3^^+2x^^4^^+x^^5^^ = x + x^^3^^ + x^^5^^ = (1+x)(1+x^^3^^+x^^4^^)-(2x^^4^^+1), remainder -1=1. Hence 1+x+x^^2^^ and x+x^^2^^+x^^3^^ are inverses.
It can be shown that all nonzero elements has multiplicative inverses in this ring ''GF(2)[x]'' modulo ''(1+x^^3^^+x^^4^^)'', or ''GF(2)[x]/(1+x^^3^^+x^^4^^)''. Such polynomials whose nonzero remainders have multiplicative inverses are called ''primitive polynomials''.
A ring with nice multiplication is a field. Hence ''GF(2)[x]/(1+x^^3^^+x^^4^^)'' is a field with 2^^4^^=16 elements (15 nonzero), denoted by ''GF(2^^4^^)''.
This is the next discovery of Galois, with two related results:
# For any prime ''p'', the ring ''GF(p)[x]/poly(x)'' is a field with ''p^^n^^'' elements whenever ''poly(x)'' is a primitive polynomial in ''GF(p)[x]'' with degree ''n''. ''GF(p)[x]/poly(x)'' is structurally the same as ''GF(p^^n^^)''.
# For any prime ''p'', there is a field ''GF(p^^n^^)'' whose multiplicative group has ''p^^n^^-1'' nonzero elements. The multiplication is polynomial multiplication in ''GF(p)[x]'' with modular division by a primitive polynomial ''poly(x)'' of degree ''n''.
!n-bit LFSR and GF(2^^n^^)
For p=2, the only even prime, the field ''GF(2^^4^^)'' can be constructed from ''GF(2)[x]/(1+x^^3^^+x^^4^^)''. This is applied to the ''4-bit LFSR'' in the following way:
* Each nonzero element of ''GF(2^^4^^)'' corresponds to a state of ''4-bit LFSR''.
* The primitive polynomial 1+x^^3^^+x^^4^^ implies the 1-based taps are at 3,4.
In general, the ''n-bit LFSR'' is related to the finite field ''GF(2^^n^^)'':
* Each nonzero element of ''GF(2^^n^^)'' corresponds to a state of ''n-bit LFSR''.
* A primitive polynomial of degree n gives the 1-based tap positions, via the term-indexes of coefficient 1.
/***
|''Name:''|Publish Macro|
|''Version:''|0.4 (25 May 2007)|
|''Source''|http://jackparke.googlepages.com/jtw.html#PublishMacro ([[del.icio.us|http://del.icio.us/post?url=http://jackparke.googlepages.com/jtw.html%23PublishMacro]])|
|''Author:''|[[Jack]]|
|''Type:''|Macro|
!Description
Publish tiddlers tagged with these tags <<option txtPublishTags>> (comma seperated) as HTML pages to the subfolder 'publish' (you must create this). Use the [[PublishTemplateHead]] and [[PublishTemplateBody]] templates to style your pages and the [[PublishIndexTemplate]] to define an index page.
!Usage
{{{<<doPublish>>}}} <<doPublish>>
!Revision History
* Original by [[Jack]] 24 May 2006
* Updated 2 Jan 2007
* Refactored 4 Jan 2007
* Small improvements
!Code
***/
//{{{
version.extensions.doPublish = {major: 0, minor: 3,
revision: 0, date: new Date("Jan4, 2007")};
config.macros.doPublish = {label: "publish", prompt: "Publish Tiddlers as HTML files"};
if (config.options.txtPublishTags==undefined) config.options.txtPublishTags="Publish";
config.shadowTiddlers.PublishTemplateHead = '<title>%0 - %1</title>\n<link rel="stylesheet" type="text/css" href="style.css"/>\n<meta name="keywords" content="%3"/>'
config.shadowTiddlers.PublishTemplateBody = '<div class=\'viewer\' id=\'contentWrapper\'><small><a href=\"./publish/index.html\">Home</a> > %1</small><h1>%0</h1>\n<h2>%1</h2>\n%2\n<hr>Tags: %3\n<hr>%4, %5 (created %6)\n</div>\n'
config.shadowTiddlers.PublishIndexTemplate = '<div class=\'viewer\' id=\'contentWrapper\'><small><a href="./publish/index.html">Home</a> > %1</small><h1>%0</h1><h2>%1</h2>\n<ul>%2\n</ul>\n<small>Published: %6</small>\n</div>\n';
config.macros.doPublish.handler = function(place)
{
if(!readOnly)
createTiddlyButton(place,this.label,this.prompt,function () {doPublish(); return false;},null,null,this.accessKey);
}
function doPublish() {
var savedTiddlers = [];
var tiddlers = store.getTiddlers("title");
var place = document.getElementById(story.container)
var HTMLTemplateHead = store.getTiddlerText("PublishTemplateHead");
// We cannot render this template because <title> and other tags fail
var HTMLTemplateBody = store.getTiddlerText("PublishTemplateBody");
HTMLTemplateBody = renderTemplate(HTMLTemplateBody)
HTMLTemplateBody = wiki2Web(HTMLTemplateBody);
var PublishTags = config.options.txtPublishTags || "publish"; PublishTags = PublishTags.split(",")
var PublishFolder = getWikiPath('publish'); if (!PublishFolder) return;
var indexFile = "";
var indexFileTemplate = store.getTiddlerText("PublishIndexTemplate");
// This does not allow <<myMacro>> but wants <div macro="myMacro">
indexFileTemplate = renderTemplate(indexFileTemplate)
// This option allows WIKI-syntax but is limited in it's HTML capabilities
//indexFileTemplate = wikifyStatic(indexFileTemplate)
for (var t = 0; t < tiddlers.length; t++) {
var tiddler = tiddlers[t];
if (tiddler.tags.containsAny(PublishTags)) {
var tiddlerHTML = wikifyStatic(store.getValue(tiddler, 'text'));
var HTML = '<html>\n\<head>\n' + HTMLTemplateHead + '\n</head>\n<body>\n' + HTMLTemplateBody + '\n</body>\n</html>';
HTML = HTML.format([
wikifyPlain("SiteTitle").htmlEncode(),
tiddler.title.htmlEncode(),
wiki2Web(tiddlerHTML),
tiddler.tags.join(", "),
tiddler.modifier,
tiddler.modified.toLocaleString(),
tiddler.created.toLocaleString()
]);
//saveFile(PublishFolder + tiddler.created.formatString("YYYY0MM0DD") + ".html", HTML);
saveFile(PublishFolder + tiddler.title.filenameEncode() + ".html", HTML);
indexFile += "<li><a href=\"" + tiddler.title.filenameEncode() + ".html" + "\" class=\"tiddlyLink tiddlyLinkExisting\">" + tiddler.title + "</a></li>\n";
story.closeTiddler(tiddler.title);
}
}
indexFileTemplate = '<html>\n\<head>\n' + HTMLTemplateHead + '\n</head>\n<body>\n' + indexFileTemplate + '\n</body>\n</html>';
indexFileTemplate = indexFileTemplate.format([wikifyPlain("SiteTitle").htmlEncode(), wikifyPlain("SiteSubtitle").htmlEncode(), "%2", "", "", "", (new Date()).toLocaleString()])
indexFile = indexFileTemplate.replace("%2", indexFile)
indexFile = wiki2Web(indexFile);
saveFile(PublishFolder + "index.html", indexFile)
saveFile(PublishFolder + "style.css", store.getTiddlerText("StyleSheet") + store.getTiddlerText("StyleSheetLayout") + store.getTiddlerText("StyleSheetColors"))
var indexWin = window.open("file://" + PublishFolder.replace(/\\/g, "/") + "index.html", null); indexWin.focus();
}
function renderTemplate(html) {
var result = document.createElement("div");
result.innerHTML = html;
applyHtmlMacros(result,null);
var temp = result.innerHTML;
//result.parentNode.removeChild(result);
return temp;
}
// Convert wikified text to html
function wiki2Web(wikiHTML) {
var regexpLinks = new RegExp("<a .*?tiddlylink=.*?</a>","img");
var result = wikiHTML.match(regexpLinks);
if (result) {
for(i = 0; i < result.length; i++) {
var className = result[i].match(/ class="(.*?)"/i)?result[i].match(/ class="(.*?)"/i)[1]:"";
var tiddlerName = result[i].match(/ tiddlylink="(.*?)"/i)[1];
var url = tiddlerName.htmlDecode().filenameEncode() + ".html";
//var url = tiddler.created.formatString("YYYY0MM0DD") + ".html";
if (!className.match(/tiddlyLinkNonExisting/i))
wikiHTML = wikiHTML.myReplace(result[i], "<a class=\"" + className + "\" href=\"" + url + "\">" + tiddlerName + "</a>");
else
wikiHTML = wikiHTML.myReplace(result[i], "<a class=\"" + className + "\" title=\"Page does not exist\" href=\"#\">" + tiddlerName + "</a>");
}
wikiHTML = wikiHTML.replace(/ href="http:\/\//gi, " target=\"_blank\" href=\"http://");
}
return wikiHTML
}
function getWikiPath(folderName) {
var originalPath = document.location.toString();
if(originalPath.substr(0,5) != 'file:') {
alert(config.messages.notFileUrlError);
if(store.tiddlerExists(config.messages.saveInstructions))
story.displayTiddler(null,config.messages.saveInstructions);
return;
}
var localPath = getLocalPath(originalPath);
var backSlash = localPath.lastIndexOf('\\') == -1 ? '/' : '\\';
var dirPathPos = localPath.lastIndexOf('\\')!=-1?localPath.lastIndexOf('\\'):localPath.lastIndexOf('/');
var subPath = localPath.substr(0,dirPathPos) + backSlash + (folderName ? folderName + backSlash : '');
return subPath;
}
// Replace without regex
String.prototype.myReplace = function(sea, rep) {
var t1 = this.indexOf(sea);
var t2 = parseInt(this.indexOf(sea)) + parseInt(sea.length);
var t3 = this.length;
return this.substring(0, t1) + rep + this.substring(t2, t3)
}
// Convert illegal characters to underscores
String.prototype.filenameEncode = function()
{
return(this.toLowerCase().replace(/[^a-z0-9_-]/g ,"_"));
}
//}}}
Background: #FFcc00
Foreground: #000
PrimaryPale: #FF8C69
PrimaryLight: #cc66ff
PrimaryMid: #440044
PrimaryDark: #410
SecondaryPale: #ffc
SecondaryLight: #fe8
SecondaryMid: #db4
SecondaryDark: #440044
TertiaryPale: #ffff99
TertiaryLight: #EEC591
TertiaryMid: #440044
TertiaryDark: #8B7355
When the browser changes to secure mode (using HTTPS), data send from your browser to the server will be encrypted by Public Key Encryption. The method of encryption is specified in a ''SSL Certificate'', which contains the public key. Most SSL Certificates nowadays use the RSA scheme.
Your browser either obtain these SSL Certificates on-the-fly, or cache them to save downloading them every time. Most browsers allow you to view these SSL Certificates. ''Warning'' - Don't click the wrong button! Always click "Cancel" or "Close" just to read, no modify or delete or clear!
!How to view Public Keys in SSL Certificate in Microsoft IE
Tools > Internet Options, click "Contents" tab.
In Certificates click "Certificates"
click through the tabs, should find some.
click on a row (it becomes highlighted), then click "view".
go to the "Details" tab, scroll and find the Public Key.
!How to view Public Keys in SSL Certificate in Mozilla ~FireFox
Tools > Options > Advanced, click "Encryptions" tab.
In Certificates click "View List", select one, click "View", examine "Details" tab to find the Public Key.
!An Example of RSA Public Key
The RSA Public Key includes both the modulus and exponent (clear in ~FireFox, not-so-clear in IE).
|!RSA Public Key in IE|!RSA Public Key in ~FireFox|
|30 81 89 02 81 81 00|Modulus (1024 bits):|
|e5 19 bf 6d a3 56 61 2d 99 48 71 f6 67 de b9 8d|e5 19 bf 6d a3 56 61 2d 99 48 71 f6 67 de b9 8d|
|eb b7 9e 86 80 0a 91 0e fa 38 25 af 46 88 82 e5|eb b7 9e 86 80 0a 91 0e fa 38 25 af 46 88 82 e5|
|73 a8 a0 9b 24 5d 0d 1f cc 65 6e 0c b0 d0 56 84|73 a8 a0 9b 24 5d 0d 1f cc 65 6e 0c b0 d0 56 84|
|18 87 9a 06 9b 10 a1 73 df b4 58 39 6b 6e c1 f6|18 87 9a 06 9b 10 a1 73 df b4 58 39 6b 6e c1 f6|
|15 d5 a8 a8 3f aa 12 06 8d 31 ac 7f b0 34 d7 8f|15 d5 a8 a8 3f aa 12 06 8d 31 ac 7f b0 34 d7 8f|
|34 67 88 09 cd 14 11 e2 4e 45 56 69 1f 78 02 80|34 67 88 09 cd 14 11 e2 4e 45 56 69 1f 78 02 80|
|da dc 47 91 29 bb 36 c9 63 5c c5 e0 d7 2d 87 7b|da dc 47 91 29 bb 36 c9 63 5c c5 e0 d7 2d 87 7b|
|a1 b7 32 b0 7b 30 ba 2a 2f 31 aa ee a3 67 da db|a1 b7 32 b0 7b 30 ba 2a 2f 31 aa ee a3 67 da db|
|02 03|Exponent (24 bits):|
|01 00 01|01 00 01|
|''Verisign Class 1 Public Primary Certification Authority''|c
In this example, the exponent: ''e'' = 10001 binary = 16^^4^^+1=2^^<html>2<sup>4</sup></html>^^+1=65537=''F~~4~~'', the largest known Fermat prime.
Most SSL Certificates choose a Fermat prime for the exponent ''e''. This is because a (small) prime ''e'' will be relatively prime to the bi-prime modulus ''n'', and the structure of Fermat prime allows efficient use of ''repeating squaring'' for exponentiation. In this example of ''e'' = F~~4~~, repeating squaring 16 times will raise data x to an exponent 2^^16^^=65536 already.
!Machine and States
Another way to produce periodic sequences is to use a cyclic machine: different states of the machine can be mapped to different numbers, and if the machine goes through all its states in a cycle, the numbers will be periodic.
In computer science, a ''machine'' can be very simple: all the light-switches in your home is a simple ''switching-machine''. If the total number of light switches is n, this machine has 2^^n^^ states: depending on whether a light is switched on (1) or off (0). For example, if there are 5 switches in total, a ''state'' can be denoted by 00101, a binary number corresponding to decimal 5. When you go to the kitchen the state will change to 00111, which is decimal 7. This 5-switch machine has 2^^5^^ = 32 states. This light-switch machine is manual: you need to flip the switches to change its state. However, in a similar fashion, the twinkling-lights decorating the Christmas tree is an n-bit machine, and it cycles through its 2^^n^^ states automatically.
Note that the idea of ''binary bits'' and total count of states (''2^^n^^'') arise from the (only) even prime number: ''2''. Nowadays all digital information is based on binary bits -- this can be regarded as an application of the special prime number ''2''.
!Linear Feedback Shift Register (LFSR)
In daily life, if we want to make a choice (e.g. who play first), we flip a coin. Can we flip a digital coin? It turns out that the answer is "yes", using a simple machine called a Linear Feedback Shift Register (LFSR).
An LFSR consists of n-bits, with an initial state being nonzero (not all bits 0), and a clock that ticks. A 4-bit LFSR looks like this (counting bits as b1, b2, b3, b4; b1 = lowest, b4=highest):
|!4-bit LFSR|!b1|!b2|!b3|!b4|!Comment|
||1|1|0|0||
This 4-bit LFSR has initial state b1=1, b2=1, b3=0, b4=0, which can be taken as (b4,b3,b2,b1) 0011 in binary = 3 in decimal.
As the clock ticks, the bits of the state shifts from low to high:
|!4-bit LFSR|!b1|!b2|!b3|!b4|!Comment|
||1|1|0|0||
|shift| |\|\|\|\|
||?|1|1|0|carry = 0|
b4 becomes the carry (the flip bit, 0 or 1), b3 goes to b4, b2 goes to b3, b1 goes to b2. So what is the lowest bit b1 now?
|!4-bit LFSR|!b1|!b2|!b3|!b4|!Comment|
||1|1|0|0||
||^| |\|/|taps: 3,4|
|feedback|>|0 <-|>|xor||
This is where the taps come in. For this 4-bit LFSR, the taps are at bit-3 and bit-4, denoted as taps 3,4. Before the clock ticks, the tap bits (can be more than 2) are combined by the logical operator XOR (exclusive or), to produce the lowest bit b1 after the tick:
|!4-bit LFSR|!b1|!b2|!b3|!b4|!Comment|
||1|1|0|0||
||||\|/|taps: 3,4|
|feedback|>|0 <-|>|xor||
|shift|v|\|\|\|\|
||0|1|1|0|carry = 0|
The states of this 4-bit LFSR change as the clock keeps on ticking:
[img[4-bit LFSR|LFSR-F4.gif][http://en.wikipedia.org/wiki/Linear_feedback_shift_register]]
Note that an LFSR will die if it reaches a state with all bits zero. Therefore ''n-bit LFSR'' only has ''2^^n^^-1'' nonzero states.
You can [[Try Your Own LFSR]], and see how the even prime ''2'' and the concept of polynomials lurks in the math behind LFSR.
/*{{{*/
/* horizontal main menu */
#displayArea { margin: 1em 15.5em 0em 1em; } /* use the full horizontal width */
#topMenu { background: [[ColorPalette::PrimaryMid]]; color: [[ColorPalette::PrimaryPale]]; padding: 0.2em 0.2em 0.2em 0.5em; border-bottom: 2px solid #000000; }
#topMenu br { display: none; }
#topMenu .button, #topMenu .tiddlyLink, #topMenu a { margin-left: 0.25em; margin-right: 0.25em; padding-left: 0.5em; padding-right: 0.5em; color: [[ColorPalette::PrimaryPale]]; font-size: 1.15em; }
#topMenu .button:hover, #topMenu .tiddlyLink:hover { background: [[ColorPalette::PrimaryDark]]; }
/* GIFFMEX TWEAKS TO STYLESHEETPRINT (so that nothing but tiddler title and text are printed) */
@media print {#mainMenu {display: none ! important;}}
@media print {#topMenu {display: none ! important;}}
@media print {#sidebar {display: none ! important;}}
@media print {#messageArea {display: none ! important;}}
@media print {#toolbar {display: none ! important;}}
@media print {.header {display: none ! important;}}
@media print {.tiddler .subtitle {display: none ! important;}}
@media print {.tiddler .toolbar {display; none ! important; }}
@media print {.tiddler .tagging {display; none ! important; }}
@media print {.tiddler .tagged {display; none ! important; }}
@media print {#displayArea {margin: 1em 1em 0em 1em;}}
@media print {.pageBreak {page-break-before: always;}}
a.button{
border: 0;
}
/*Color changes*/
#sidebarOptions input {
border: 1px solid [[ColorPalette::TertiaryPale]];
}
#sidebarOptions .sliderPanel {
background: [[ColorPalette::TertiaryPale]];
}
#sidebarOptions .sliderPanel a {
border: none;
color: [[ColorPalette::PrimaryMid]];
}
#sidebarOptions .sliderPanel a:hover {
color: [[ColorPalette::Background]];
background: [[ColorPalette::TertiaryPale]];
}
#sidebarOptions .sliderPanel a:active {
color: [[ColorPalette::PrimaryMid]];
background: [[ColorPalette::TertiaryPale]];
}
/*Makes sliders bold - or not (seems no effect)*/
.tuduSlider .button{font-weight: bold;}
/* (2) Adjusts the color for all headlines so they are both readable and match my color schemes. */
h1,h2,h3,h4,h5 {
color: #000;
background: [[ColorPalette::TertiaryPale]];
}
table {border:2px solid [[ColorPalette::TertiaryDark]];}
th, thead td {background:[[ColorPalette::SecondaryMid]]; border:1px solid [[ColorPalette::TertiaryDark]]; color:#000;}
td, tr {border:1px solid [[ColorPalette::TertiaryDark]];}
.title {
color: [[ColorPalette::PrimaryMid]];
}
/* (2) Makes text verdana or georgia. */
body {
font-family: verdana;
font-size: 9pt;
}
/* (4) Allows for Greek - one way */
.greek {
font-family: Palatino Linotype;
font-style: normal;
font-size: 150%;
}
/* (5) Shortens the height of the Header */
.headerShadow {
padding: 1.5em 0em 1em 1em;
}
.headerForeground {
padding: 2em 0em 1em 1em;
}
/* (8) Makes ordered and unordered lists double-spaced between items but single-spaced within items. -- or not (has effect) */
/*
.viewer li {
padding-top: 0.5em;
padding-bottom: 0.5em;
}
*/
/*Makes block quotes line-less -- or not (has effect)*/
/*
.viewer blockquote {
border-left: 0px;
margin-top:0em;
margin-bottom:0em;
}
*/
/* Cosmetic fixes that probably should be included in a future TW... */
.viewer .listTitle { list-style-type:none; margin-left:-2em; }
.editorFooter .button { padding-top: 0px; padding-bottom:0px; }
/*Important stuff. See TagglyTaggingStyles and HorizontalMainMenuStyles*/
[[Styles TagglyTagging]]
[[Styles HorizontalMainMenu]]
/*Just colours, fonts, tweaks etc. See MessageTopRight and SideBarWhiteAndGrey*/
body {
background: #eee; }
.headerForeground a {
color: #6fc;}
.headerShadow {
left: 2px;
top: 2px; }
.siteSubtitle {
padding-left: 1.5em; }
.shadow .title {
color: #999; }
.viewer pre {
background-color: #f8f8ff;
border-color: #ddf }
/*Shape of Tiddler display*/
.tiddler {
border-top: 1px solid #ccc;
border-left: 1px solid #ccc;
border-bottom: 3px solid #ccc;
border-right: 3px solid #ccc;
margin: 0.5em;
background:#fff;
padding: 0.5em;
-moz-border-radius: 1em; }
#messageArea {
background-color: #eee;
border-color: #8ab;
border-width: 4px;
border-style: dotted;
font-size: 90%;
padding: 0.5em;
-moz-border-radius: 1em; }
#messageArea .button { text-decoration:none; font-weight:bold; background:transparent; border:0px; }
#messageArea .button:hover {background: #acd; }
.editorFooter .button {
padding-top: 0px;
padding-bottom:0px;
background: #fff;
color: #000;
border-top: 1px solid #ccc;
border-left: 1px solid #ccc;
border-bottom: 2px solid #ccc;
border-right: 2px solid #ccc;
margin-left: 3px;
padding-top: 1px;
padding-bottom: 1px;
padding-left: 5px;
padding-right: 5px; }
.editorFooter .button:hover {
border-top: 2px solid #ccc;
border-left: 2px solid #ccc;
border-bottom: 1px solid #ccc;
border-right: 1px solid #ccc;
margin-left: 3px;
padding-top: 1px;
padding-bottom: 1px;
padding-left: 5px;
padding-right: 5px; }
/*The Tag Box*/
.tagged {
padding: 0.5em;
background-color: #eee;
border-top: 1px solid #ccc;
border-left: 1px solid #ccc;
border-bottom: 3px solid #ccc;
border-right: 3px solid #ccc;
-moz-border-radius: 1em; }
.selected .tagged {
padding: 0.5em;
background-color: #eee;
border-top: 1px solid #ccc;
border-left: 1px solid #ccc;
border-bottom: 3px solid #ccc;
border-right: 3px solid #ccc;
-moz-border-radius: 1em; }
Clint's fix for weird IE behaviour
body {position:static;}
.tagClear{margin-top:1em;clear:both;}
/*}}}*/
/*{{{*/
/* text alignments */
.left
{ display:block;text-align:left; }
.center
{ display:block;text-align:center; }
.right
{ display:block;text-align:right; }
.justify
{ display:block;text-align:justify; }
.indent
{ margin:0;padding:0;border:0;margin-left:2em; }
.floatleft
{ float:left; }
.floatright
{ float:right; }
.clear
{ clear:both; }
.wrap
{ white-space:normal; }
.nowrap
{ white-space:nowrap; }
.hidden
{ display:none; }
.span
{ display:span; }
.block
{ display:blockquote; }
/* font sizes */
.big
{ font-size:14pt;line-height:120% }
.medium
{ font-size:12pt;line-height:120% }
.normal
{ font-size:9pt;line-height:120% }
.small
{ font-size:8pt;line-height:120% }
.fine
{ font-size:7pt;line-height:120% }
.tiny
{ font-size:6pt;line-height:120% }
.larger
{ font-size:120%; }
.smaller
{ font-size:80%; }
/* font styles */
.bold
{ font-weight:bold; }
.italics
{ font-style:italics; }
.underline
{ text-decoration:underline; }
/* multi-column tiddler content (not supported in Internet Explorer) */
.twocolumns
{ display:block; -moz-column-count:2; -moz-column-gap:1em; -moz-column-width:50%;}
.threecolumns
{ display:block; -moz-column-count:3; -moz-column-gap:1em; -moz-column-width:33%}
.fourcolumns
{ display:block; -moz-column-count:4; -moz-column-gap:1em; -moz-column-width:25%}
/* borderless tables */
.borderless, .borderless table, .borderless td, .borderless tr, .borderless th, .borderless tbody
{ border:0 !important; margin:0 !important; padding:0 !important; }
/* thumbnail images (fixed-sized scaled images) */
.thumbnail img { height:5em !important; }
/* grouped content */
.outline
{ display:block; padding:1em; -moz-border-radius:1em; border:1px solid; }
.menubox
{ display:block; padding:1em; -moz-border-radius:1em; border:1px solid; background:#ccccff; color:#000; }
.menubox .button, .menubox .tiddlyLinkExisting, .menubox .tiddlyLinkNonExisting
{ color:#009 !important; }
.groupbox
{ display:block; padding:1em; -moz-border-radius:1em; border:1px solid; background:#ffe; color:#000; }
.groupbox a, .groupbox .button, .groupbox .tiddlyLinkExisting, .groupbox .tiddlyLinkNonExisting
{ color:#009 !important; }
.groupbox code
{ color:#333 !important; }
.borderleft
{ margin:0;padding:0;border:0;margin-left:1em; border-left:1px dotted; padding-left:.5em; }
.borderright
{ margin:0;padding:0;border:0;margin-right:1em; border-right:1px dotted; padding-right:.5em; }
.borderbottom
{ margin:0;padding:1px 0;border:0;border-bottom:1px dotted; margin-bottom:1px; padding-bottom:1px; }
.bordertop
{ margin:0;padding:0;border:0;border-top:1px dotted; margin-top:1px; padding-top:1px; }
/* compact form */
.smallform
{ white-space:nowrap; }
.smallform input, .smallform textarea, .smallform button, .smallform checkbox, .smallform radio, .smallform select
{ font-size:8pt; }
/* colors */
.green { color:#6f6 !important }
.red { color:#f66 !important }
.blue { color:#99f !important }
/*}}}*/
Can we see a table?
|!Table header|!Column Two|
|>| colspan |
| rowspan |left aligned|
|~| right aligned|
|bgcolor(#DC1A1A):colored| centered |
||*lists<br>*within<br>*tables<br><br>and double-spaced too|
|table caption|c
<<<
This is how things should appear ~HaHaHa
This is how things should say, ~HoHoHo
<<<
Link to [[TiddlyWiki Tutorial|file:///C:/jc/www/wiki/tiddly/twfortherestofus.html]]
This is a ''sparkline'' of primes: <<sparkline 2 3 5 7 11 13 17 19 23 29 31>>
Ruby On Rails has the following:
* Use of Ruby
* Use of Framework
** topic for all
** topic for some
** topic for others
* Use of Rails
* Use of Web applications
| <<gradient vert #ffffff #ffdddd #ff8888>>Colors>> | <<gradient vert #ffffff #ddffdd #88ff88>>Interestng>> | <<gradient vert #ffffff #ddddff #8888ff>>CCS is really powerful>> |
<<gradient vert #000000 #660000 #aa2222>>color:#ffffff;font-size:22pt;Cool Color Scheme>>
Link to other documents
# [[Pencil|my docs/my pencil.doc]]
# [[PSS Tax|my docs/my psstax.pdf]]
# [[Proverbs|my docs/Chinese proverb.pps]]
/%
|Name|ToggleRightSidebar|
|Source|http://www.TiddlyTools.com/#ToggleRightSidebar|
|Version|0.0.0|
|Author|Eric Shulman - ELS Design Studios|
|License|http://www.TiddlyTools.com/#LegalStatements <<br>>and [[Creative Commons Attribution-ShareAlike 2.5 License|http://creativecommons.org/licenses/by-sa/2.5/]]|
|~CoreVersion|2.1|
|Type|script|
|Requires||
|Overrides||
|Description||
%/<script label="show/hide right sidebar">
var show=document.getElementById('sidebar').style.display=='none';
if (!show) {
document.getElementById('sidebar').style.display='none';
var margin='1em';
}
else {
document.getElementById('sidebar').style.display='block';
var margin=config.options.txtDisplayAreaRightMargin?config.options.txtDisplayAreaRightMargin:"";
}
place.innerHTML=(show?"Need More Room?":"Need the Sidebar?"); // SET LINK TEXT
place.title=show?"hide sidebar":"show sidebar"; // SET TOOLTIP
document.getElementById('displayArea').style.marginRight=margin;
config.options.chkShowRightSidebar=show;
saveOptionCookie('chkShowRightSidebar');
var sm=document.getElementById("storyMenu"); if (sm) config.refreshers.content(sm);
return false;
</script><script>
if (config.options.chkShowRightSidebar==undefined)
config.options.chkShowRightSidebar=true;
if (!config.options.txtDisplayAreaRightMargin||!config.options.txtDisplayAreaRightMargin.length)
config.options.txtDisplayAreaRightMargin="15em";
var show=config.options.chkShowRightSidebar;
document.getElementById('sidebar').style.display=show?"block":"none";
document.getElementById('displayArea').style.marginRight=show?config.options.txtDisplayAreaRightMargin:"1em";
place.lastChild.innerHTML=(show?"Hide Sidebar":"Show Sidebar"); // SET LINK TEXT
place.lastChild.title=show?"hide sidebar":"show sidebar"; // SET TOOLTIP
place.lastChild.style.fontWeight="normal";
</script>
We shall get our hands on the nuts-and-bolts of ''Hash Functions'' -- how to throw darts by computation.
For these examples, the input key is a String (in Unicode, so it is multilingual), and the result is an integer, i.e. ''hash'': String -> Integer.
The number of Strings is infinite (or at least a very large number if you restrict to Strings up to a certain length), but the number of Integers is finite from modulo arithmetic, hence collisions will occur. We shall take a look at how these ''hash collisions'' relate to primes or non-primes.
!Hashing with Computation (Primes or not)
An example of a real-life ''hash function'', in which prime numbers play a role, is the ''hashCode()'' function for ''Strings'' in the ''Java'' programming language.
Basically, the idea is that every String in Java can be mapped to a signed integer from -2^^31^^ to 2^^31^^-1, or -2147483648 to 2147483647.
As explained in [[Java String HashCode]], the algorithm is documented, which involves using the prime ''31'' as the multiplier. Click the ''Go!'' button below to find out how Java gives the hashCode for 3 names:
<html>
<form>
<table width="80%" border="3" bgcolor="#F2DFCB">
<tr>
<td align="left">
<b>Java HashCode for String s</b>: s[0]*m<sup>(n-1)</sup> + s[1]*m<sup>(n-2)</sup> + ... + s[n-1] where s[i] is the character at position index i.<br>
<b>Java HashCode for String s</b>: (...((s[0]*m + s[1])*m + ....)*m + s[n-1]) where s[i] is the character at position index i.<br>
Multiplier m: <INPUT name="m" type="text" size="5%" value="31">
String Data: <INPUT id="hash.data" name="data" type="text" size="72%" value="Joe Miller,Anna Miller,Zebadiah Miller">
</td>
<td><input type="button" value="Go!" height="50"
onClick="Logger.set('hash.logger');new HashCode(parseInt(m.value)).run(data.value);">
</td>
</tr>
<tr>
<td colspan="2">Result:<br><textarea id="hash.logger" cols="100%" rows="10"></textarea></td>
</tr>
<tr>
<td align="left">
<b>My Hash Function</b><br>
Code: <textarea id="hash.code" name="code" cols="80%" rows="8">
// Example of a Simple Hash Function (can be bad)
function hash(s) { // s = input String
var h = 0; // initiate hash value
for (var j=0; j < s.length; j++) { // loop through chars in s
var c = s.charCodeAt(j); // get character code
h = (h + c) % 100; // add code, keep last 2 digits
}
return h; // return hash value: 0..99
}
</textarea>
</td>
<td><input type="button" value="My Hash!" height="50"
onClick="Logger.set('hash.logger');new HashCode(-1).apply(code.value, data.value);">
</td>
</tr>
</table>
</form>
</html>
You can change the value of multiplier ''m'', say from ''31'' (a prime) to ''32'' (a power of 2), and see the effect on hashing the names.
You can type in your String data, separated by comma, to experiment with hashing your Strings. Try different values for the multiplier m. Even with ''m=31'', there will be collisions, see if you can easily find some examples. An example is already given.
For those with a bit of Javascript programming experience, you can type your own ''hash function'' in the ''Code'' input, and press ''My Hash!'' to see how your own hash function works on the String data.
!Hashing without Computation (almost)
Everyone has his/her favorite tunes. How many songs can you recognize? Probably a fairly large number. How can we easily recognize (i.e. data retrieval of) so many songs? Believe it or not, we all do this by ''Hashing'' -- and easily as no computation is involved!.
We can all recognize a tune by its first few notes, e.g. high-doh, ti, la, so, fa, me, ray, doh (for "Joy to the world, the Lord is come."), which is 17654321 (use 1=doh, etc. Different octaves count as same note, as in modulo arithmetic). The origin of this 7-notes scale of Western music (or the 5-sounds of Chinese: 五聲「宮、商、角、徵、羽」) is lost in antiquity. If we take the first 8 notes, as in this example, the result will be an 8-digit number in base 7 (digit 0=7). There will be 7^^8^^ hash values, or 5,764,801 tunes, more than 5 millions songs! ''Hash collision'' in this case is almost none -- do you recall any two songs starting with the same 8 notes?
This page cannot simulate this wonderful ''tune-hashing'' of our brains -- we can't load .mp3 files to hash. So I'll try something different, but based on the same idea. Instead of musical songs, I'll use textual strings: poems. Like the songs, we can recall a Chinese poem by its first sentence. But instead of 7 (or 5) musical notes, we have 3,000+ Chinese characters -- not practical for fast computation. So I'll twist the idea a bit: scanning the successive character codes, they either increase or decrease. We shall put a 1 for increase, 0 for decrease, like so:
|!Character|!Unicode|!Increase?|!Bit (Binary Digit)|!Hash value (so far)|
|床| 24202| -| -| -|
|前| 21069| no| 0|0|
|明| 26126| yes| 1|01|
|月| 26376| yes| 1|011|
|光| 20809| no| 0|0110 |
|''Hashing'' poem by first sentence, ''hash value'' = 0110 binary = 6 decimal.|c
Click <html><a href="javascript:Logger.set('hash.logger');new HashCode(0).poem(5);">五言詩 Hash</a></html>, and scroll to display above. As there are only 2^^(5-1)^^=2^^4^^=16 hash values, it is all too easy to get a collision with 8 poems.
Click <html><a href="javascript:Logger.set('hash.logger');new HashCode(0).poem(7);">七言詩 Hash</a></html>, and scroll to display above. As there are 2^^(7-1)^^=2^^6^^=64 hash values, you'll need more than 8 poems to encounter some collision.
This hashing algorithm uses only binary decisions, no computations -- the last conversion of binary to decimal is done for us: machines prefer just binary, and our brains can store musical notes "as is". These examples illustrate how effective the ''tune-hashing'' by leading notes is, inside our heads!
We shall see the effect of interleaving on sequences.
First, interleaving is applied to a periodic sequence 1,2,3,...,p,1,2,3,... with ''period'' p.
Then interleaving is applied to the (aperiodic) sequence 1,2,3,4,.... of all natural numbers.
!Finite Interleaving
Click the top button ''Go!'' below to generate Interleave sequences with ''order'' d (0 < d < p) where p is the ''period'' of the finite periodic sequence.
<html>
<form>
<table width="80%" border="3" bgcolor="#F1D7F7">
<tr>
<td align="left">
<b>Finite Interleaving (Periodic)</b><br>
Period p: <input name="p" type="text" size="10%" value="17">
</td>
<td><input type="button" value="Go!" height="50"
onClick="Logger.set('interleave.logger');new Interleave(true, parseInt(p.value)).run();">
</td>
</tr>
<tr>
<td colspan="2">Result:<br><textarea id="interleave.logger" cols="100%" rows="20"></textarea></td>
</tr>
<tr>
<td align="left">
<b>Infinite Interleaving (Aperiodic)</b><br>
Parts p: <input name="n" type="text" size="10%" value="7">
</td>
<td><input type="button" value="Go!" height="50"
onClick="Logger.set('interleave.logger');new Interleave(false, parseInt(n.value)).run();">
</td>
</tr>
</table>
</form>
</html>
Change the ''period'' to other values, say 18, and find out what interleave sequences are generated.
For composite periods, some interleave sequence will have shorter periods. Can you predict what these shorter periods are?
To understand the math behind the scene, read [[Finite Interleaving]].
!Infinite Interleaving
Click the bottom button ''Go!'' above to find out the distribution of ''multiples'' k when the infinite sequence 1,2,3,... is divided into ''p'' parts.
Change the number of ''parts'' to see how the distribution of ''multiples'' is affected.
For composite number of parts, the distribution of some multiples will not be over all parts. Can you predict how many parts for such multiples?
To understand the math behind the scene, read [[Infinite Interleaving]].
You can design your own n-bit LFSR with taps and seed. The 4-bit LFSR example can be tested by: n=4, taps: 3,4 and seed=3.
!LFSR Simulation
Can you build an ''n-bit LFSR'' to go through all the ''2^^n^^-1'' nonzero states in no particular pattern?
<html>
<form>
<table width="80%" border="3" bgcolor="#F5FD33">
<tr>
<td align="left">
bits n: <INPUT name="bits" type="text" size="10%" value="4">
taps a,b,c (1-based): <INPUT name="taps" type="text" size="10%" value="3,4">
seed: <INPUT name="seed" type="text" size="10%" value="3">
</td>
<td><input type="button" value="Go!" height="50"
onClick="Logger.set('lfsr.logger'); new LFSR(toBits(parseInt(seed.value), parseInt(bits.value)), taps.value.split(',')).run();">
</td>
</tr>
<tr>
<td colspan="2"><textarea id="lfsr.logger" cols="100%" rows="10"></textarea></td>
</tr>
</table>
</form>
</html>
Typical results are (any nonzero seed will do, e.g. seed = 3 in decimal):
|!n = Number of bits|!taps (1-based)|!Number of states reached|!Total number of nonzero states|!Comment|
|4|3,4|15|15|all states reached|
|4|1,4|15|15|all states reached|
|4|1,2|4|15||
|4|1,3|7|15||
|4|2,3|8|15||
|5|2,3|9|31||
|5|2,5|31|31|all states reached|
|5|1,3,5|15|31||
|6|1,3,5|15|63||
|6|1,5|21|63||
|6|1,6|63|63|all states reached|
|7|1,7|127|127|all states reached|
These results show that, for a given n, only very specific taps will give an LFSR reaching all nonzero states. In these cases, the carry bit of LFSR flips through 0 and 1, in a pattern that only repeats after 2^^n^^-1 ticks.
!LFSR Taps
Where should the taps of an ''n-bit LFSR'' be placed so that it will change through all its ''2^^n^^-1'' nonzero states? Is this always possible for every n? These are studied in a deep math theory (Galois fields) involving the (only) even prime: ''2''.
In math (abstract algebra), a ''Field'' is a system in which you can add, subtract, multiply and divide consistently. For example, all the fractions (numbers of the form n/m) is an example of a field, which is infinite. The 19th century math genius Évariste Galois discovered that, corresponding to each power ''n'' of a prime ''p'', there is a finite field with ''p^^n^^'' elements, now called Galois Field ''GF(p^^n^^)''. Moreover, each such finite field has its associated [[Primitive Polynomials]] that are of fundamental importance. They are related to LFSR due to the following result:
For the even prime ''2'', a ''primitive polynomials'' of degree ''n'' for the Galois field ''GF(2^^n^^)'' gives the taps for the n-bit LFSR reaching all ''2^^n^^-1'' nonzero states.
|!degree n|!primitive polynomials of degree n in GF(2^^n^^)|!n-bit LFSR|!(1-based) taps for n-bit LFSR|
|1|1+x|1|taps: 1|
|2|1+x+x^^2^^|2|taps: 1,2|
|3|1+x+x^^3^^|3|taps: 1,3|
|3|1+x^^2^^+x^^3^^|3|taps: 2,3|
|4|1+x+x^^4^^|4|taps: 1,4|
|4|1+x^^3^^+x^^4^^|4|taps: 3,4|
|5|1+x^^2^^+x^^5^^|5|taps: 2,5|
|5|1+x+x^^2^^+x^^3^^+x^^5^^|5|taps: 1,2,3,5|
|5|1+x^^3^^+x^^5^^|5|taps: 3,5|
|5|1+x+x^^3^^+x^^4^^+x^^5^^|5|taps: 1,3,4,5|
|5|1+x^^2^^+x^^3^^+x^^4^^+x^^5^^|5|taps: 2,3,4,5|
|5|1+x+x^^2^^+x^^4^^+x^^5^^|5|taps: 1,2,4,5|
|''Primitive Polynomials of GF(2^^n^^)''|c
Can you see how the taps are related to the term-exponents in the primitive polynomial?
Taking the carry bit from LFSR as output, it looks like a random flip of a coin: 1=head, 0=tail. With start-of-art technology in micro-electronics, it is routine to implement a 32-bit LFSR, with period 2^^32^^-1 = 4294967295.
!~Two-Dimensional Pattern
In 1963, the mathematician Stanislaw Ulam, while he was doodling on scratch paper at a boring scientific meeting, wrote down a regular rectangular grid of numbers, starting with 1 at the center, and spiraling out like this:
[img[IntegerSpiral.gif]]
Idly he marked out the primes along this wrapped number line:
[img[UlamSpiralNumeric.gif]]
This is a 2D picture of the prime distribution -- now called the [[Ulam Spiral|http://en.wikipedia.org/wiki/Ulam_spiral]] . Can you spot any patterns?
!Pattern In Spiral
If the applet below is not shown properly, please click [[here|ulam.html]].
<html>
<applet code="ulam.class" archive="ulam.jar" width=600 height=350></applet>
</html>
Since all squares in the Ulam spiral are numbered, you can choose which square to be at the center of the picture. The number of the center square is shown on the left -- you can type the square number yourself, or use the directional keys to shift the center.
The Ulam spiral need not start with 1 -- any number ''n'' will do, the spiral just continues to be ''n+1'', ''n+2'', etc. The starting number ''n'' is shown on the right -- you can type another starting number yourself, or use the up/down triangle keys to increment/decrement the starting number.
You can also zoom in/out of the picture via the magnifying keys.
For more information about this applet, check [[http://www.alpertron.com.ar/ULAM.HTM|ulam.htm]].
<!--{{{-->
<div class='toolbar' macro='toolbar closeTiddler closeOthers +editTiddler permalink references jump'></div>
<div class='title' macro='view title'></div>
<div class='subtitle'><span macro='view modifier link'></span>, <span macro='view modified date [[DD MMM YYYY]]'></span> (<span macro='message views.wikified.createdPrompt'></span> <span macro='view created date [[DD MMM YYYY]]'></span>)</div>
<div class='tagging' macro='tagging'></div>
<div class='tagged' macro='tags'></div>
<div class='viewer' macro='view text wikified'></div>
<div class='tagClear'></div>
<!--}}}-->
A WikiWord is a word that combines upper and lowercase letters. Examples: ~WikiWord, ~GiffMex, ~MainMenu, ~AbrahamLincoln, etc.