GcatWiki - User contributions [en]

File:XOR5.jpg

2008-06-02T15:22:56Z

JoIgo:

Math Modeling Pages

2008-06-02T15:22:27Z

JoIgo: /* Exclusive disjunction */

This is the place for math modelers to post ideas, papers, examples and computer programs.

Presentation on Sudoku (Aaron and John have seen)

http://www.math-cs.ucmo.edu/~hchen/talks/sudoku.pdf

== Models ==

'''Aaron's Idea'''

''Workin' In, Workin' Out''

[[Image:Hash map.JPG]]

== Papers ==
[http://www.rfc-archive.org/getrfc.php?rfc=1319 MD2 Message-Digest Algorithm]

==Logical negation==

[[Logical negation]] is an [[logical operation|operation]] on one [[logical value]], typically the value of a [[proposition]], that produces a value of ''true'' if its operand is false and a value of ''false'' if its operand is true.

The truth table for '''NOT p''' (also written as '''~p''' or '''¬p''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:40%"
|+ '''Logical Negation'''
|- style="background:paleturquoise"
! style="width:20%" | p
! style="width:20%" | ¬p
|-
| F || T
|-
| T || F
|}
==Logical conjunction==

[[Logical conjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are true.

The truth table for '''p AND q''' (also written as '''p ∧ q''', '''p & q''', or '''p<math>\cdot</math>q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Conjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p · q
|-
| T || T || T
|-
| T || F || F
|-
| F || T || F
|-
| F || F || F
|-

|}

 

In ordinary language terms, if both ''p'' and ''q'' are true, then the conjunction ''p'' ∧ ''q'' is true. For all other assignments of logical values to ''p'' and to ''q'' the conjunction ''p'' ∧ ''q'' is false.

It can also be said that if ''p'', then ''p'' ∧ ''q'' is ''q'', otherwise ''p'' ∧ ''q'' is ''p''.

[[Logical disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' [[if and only if]] both of its operands are false.

The truth table for '''p OR q''' (also written as '''p ∨ q''', '''p || q''', or '''p + q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p + q
|-
| T || T || T
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

Stated in English, if ''p'', then ''p'' ∨ ''q'' is ''p'', otherwise ''p'' ∨ ''q'' is ''q''.

==Exclusive disjunction==

[[Exclusive disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if one but not both of its operands is true.

The truth table for '''p XOR q''' (also written as '''p + q''', '''p ⊕ q''', or '''p ≠ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Exclusive Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ⊕ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

For two propositions, '''XOR''' can also be written as (p = 1 ∧ q = 0)∨ (p = 0 ∧ q = 1).

This is the most efficient way of making an XOR with simple opperations.

[[Image:XOR5.jpg]]

[[Image:XOR.jpg]]

This diagram is the biological representation to: (A'∨B')∧(A∨B)

[[Image:XOR_using_AND_and_NOT_only.jpg]]

The picture above illustrates an XOR gate using only the operations of AND and NOT. While complicated, it appears to be the easiest way to perform an XOR operation with only AND and NOT. There are other ways but seem to involve even more operations. A minimum of 3 ANDs and 4 NOTs appears to be optimal, but is not guaranteed.

[[Image:XOR2.jpg]]

[[Image:XOR3.jpg]]

[[Image:XOR4.jpg]]

==Logical NAND==

The [[logical NAND]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' if and only if both of its operands are true. In other words, it produces a value of ''true'' if and only if at least one of its operands is false.

The truth table for '''p NAND q''' (also written as '''p | q''' or '''p ↑ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NAND'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↑ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || T
|}
 

==Logical NOR==

The [[logical NOR]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are false. In other words, it produces a value of ''false'' if and only if at least one of its operands is true. ↓ is also known as the [[Peirce arrow]] after its inventor, [[Charles Peirce]], and is a [[Sole sufficient operator]].

The truth table for '''p NOR q''' (also written as '''p ⊥ q''' or '''p ↓ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NOR'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↓ q
|-
| T || T || F
|-
| T || F || F
|-
| F || T || F
|-
| F || F || T
|}
 

*[http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#Introduction%20to%20neural%20networks Neural Network Models]
*[http://www.facweb.iitkgp.ernet.in/~niloy/PRESENTATION/ACRI_presentation_97.ppt Cellular Automata Based Authentication]
*MD5 Paper
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1762088 Stochastic model of E. coli AI-2 quorum signal circuit reveals alternative synthesis pathways] Describes a Stochastic Petri Net (SPN) model of AI-2 (Lux), provides XML code and rate constants.

How to break MD5 and other Hash functions.. A paper written by Xiaoyun Wang and her co-authors about how to break MD5 – i.e. how to make collisions occur
http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf
Nostradamus attack – i.e. the bit about predicting who will become president by exploiting MD5
http://www.win.tue.nl/hashclash/Nostradamus/

The following was taken from http://www.freesoft.org/CIE/RFC/1321/4.htm

MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, it need not be a multiple of eight, and it may be arbitrarily large. We imagine the bits of the message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest of the message.

Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)
At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits. Equivalently, this message has a length that is an exact multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the words of the resulting message, where N is a multiple of 16.

Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, low-order bytes first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z. The function F could have been defined using + instead of v since XY and not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.
The functions G, H, and I are similar to the function F, in that they act in "bitwise parallel" to produce their output from the bits of X, Y, and Z, in such a manner that if the corresponding bits of X, Y, and Z are independent and unbiased, then each bit of G(X,Y,Z), H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that the function H is the bit-wise "xor" or "parity" function of its inputs.
This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Step 5. Output
The message digest produced as output is A, B, C, D. That is, we begin with the low-order byte of A, and end with the high-order byte of D.
This completes the description of MD5. A reference implementation in C is given in the appendix.

Summary
The MD5 message-digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the cas Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (XY v XZ v YZ) to (XZ v Y not(Z)) to make g less symmetric.
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

== Engineering agar ==
[http://www.biotech.iastate.edu/lab_protocols/EvoAntiResBact.html A lab for showing antibiotic resistance across Amp concentration gradient]

File:XOR4.jpg

2008-05-29T19:23:14Z

JoIgo:

File:XOR3.jpg

2008-05-29T19:22:01Z

JoIgo:

Math Modeling Pages

2008-05-29T19:21:39Z

JoIgo: /* Exclusive disjunction */

This is the place for math modelers to post ideas, papers, examples and computer programs.

Presentation on Sudoku (Aaron and John have seen)

http://www.math-cs.ucmo.edu/~hchen/talks/sudoku.pdf

== Papers ==
[http://www.rfc-archive.org/getrfc.php?rfc=1319 MD2 Message-Digest Algorithm]

==Logical negation==

[[Logical negation]] is an [[logical operation|operation]] on one [[logical value]], typically the value of a [[proposition]], that produces a value of ''true'' if its operand is false and a value of ''false'' if its operand is true.

The truth table for '''NOT p''' (also written as '''~p''' or '''¬p''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:40%"
|+ '''Logical Negation'''
|- style="background:paleturquoise"
! style="width:20%" | p
! style="width:20%" | ¬p
|-
| F || T
|-
| T || F
|}
==Logical conjunction==

[[Logical conjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are true.

The truth table for '''p AND q''' (also written as '''p ∧ q''', '''p & q''', or '''p<math>\cdot</math>q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Conjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p · q
|-
| T || T || T
|-
| T || F || F
|-
| F || T || F
|-
| F || F || F
|-

|}

 

In ordinary language terms, if both ''p'' and ''q'' are true, then the conjunction ''p'' ∧ ''q'' is true. For all other assignments of logical values to ''p'' and to ''q'' the conjunction ''p'' ∧ ''q'' is false.

It can also be said that if ''p'', then ''p'' ∧ ''q'' is ''q'', otherwise ''p'' ∧ ''q'' is ''p''.

[[Logical disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' [[if and only if]] both of its operands are false.

The truth table for '''p OR q''' (also written as '''p ∨ q''', '''p || q''', or '''p + q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p + q
|-
| T || T || T
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

Stated in English, if ''p'', then ''p'' ∨ ''q'' is ''p'', otherwise ''p'' ∨ ''q'' is ''q''.

==Exclusive disjunction==

[[Exclusive disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if one but not both of its operands is true.

The truth table for '''p XOR q''' (also written as '''p + q''', '''p ⊕ q''', or '''p ≠ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Exclusive Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ⊕ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

For two propositions, '''XOR''' can also be written as (p = 1 ∧ q = 0)∨ (p = 0 ∧ q = 1).

[[Image:XOR.jpg]]

This diagram is the biological representation to: (A'∨B')∧(A∨B)

[[Image:XOR_using_AND_and_NOT_only.jpg]]

The picture above illustrates an XOR gate using only the operations of AND and NOT. While complicated, it appears to be the easiest way to perform an XOR operation with only AND and NOT. There are other ways but seem to involve even more operations. A minimum of 3 ANDs and 4 NOTs appears to be optimal, but is not guaranteed.

[[Image:XOR2.jpg]]

[[Image:XOR3.jpg]]

[[Image:XOR4.jpg]]

==Logical NAND==

The [[logical NAND]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' if and only if both of its operands are true. In other words, it produces a value of ''true'' if and only if at least one of its operands is false.

The truth table for '''p NAND q''' (also written as '''p | q''' or '''p ↑ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NAND'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↑ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || T
|}
 

==Logical NOR==

The [[logical NOR]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are false. In other words, it produces a value of ''false'' if and only if at least one of its operands is true. ↓ is also known as the [[Peirce arrow]] after its inventor, [[Charles Peirce]], and is a [[Sole sufficient operator]].

The truth table for '''p NOR q''' (also written as '''p ⊥ q''' or '''p ↓ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NOR'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↓ q
|-
| T || T || F
|-
| T || F || F
|-
| F || T || F
|-
| F || F || T
|}
 

*[http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#Introduction%20to%20neural%20networks Neural Network Models]
*[http://www.facweb.iitkgp.ernet.in/~niloy/PRESENTATION/ACRI_presentation_97.ppt Cellular Automata Based Authentication]
*MD5 Paper
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1762088 Stochastic model of E. coli AI-2 quorum signal circuit reveals alternative synthesis pathways] Describes a Stochastic Petri Net (SPN) model of AI-2 (Lux), provides XML code and rate constants.

How to break MD5 and other Hash functions.. A paper written by Xiaoyun Wang and her co-authors about how to break MD5 – i.e. how to make collisions occur
http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf
Nostradamus attack – i.e. the bit about predicting who will become president by exploiting MD5
http://www.win.tue.nl/hashclash/Nostradamus/

The following was taken from http://www.freesoft.org/CIE/RFC/1321/4.htm

MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, it need not be a multiple of eight, and it may be arbitrarily large. We imagine the bits of the message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest of the message.

Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)
At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits. Equivalently, this message has a length that is an exact multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the words of the resulting message, where N is a multiple of 16.

Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, low-order bytes first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z. The function F could have been defined using + instead of v since XY and not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.
The functions G, H, and I are similar to the function F, in that they act in "bitwise parallel" to produce their output from the bits of X, Y, and Z, in such a manner that if the corresponding bits of X, Y, and Z are independent and unbiased, then each bit of G(X,Y,Z), H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that the function H is the bit-wise "xor" or "parity" function of its inputs.
This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Step 5. Output
The message digest produced as output is A, B, C, D. That is, we begin with the low-order byte of A, and end with the high-order byte of D.
This completes the description of MD5. A reference implementation in C is given in the appendix.

Summary
The MD5 message-digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the cas Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (XY v XZ v YZ) to (XZ v Y not(Z)) to make g less symmetric.
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

== Engineering agar ==
[http://www.biotech.iastate.edu/lab_protocols/EvoAntiResBact.html A lab for showing antibiotic resistance across Amp concentration gradient]

Math Modeling Pages

2008-05-29T14:27:11Z

JoIgo: /* Exclusive disjunction */

This is the place for math modelers to post ideas, papers, examples and computer programs.

Presentation on Sudoku (Aaron and John have seen)

http://www.math-cs.ucmo.edu/~hchen/talks/sudoku.pdf

== Papers ==
[http://www.rfc-archive.org/getrfc.php?rfc=1319 MD2 Message-Digest Algorithm]

==Logical negation==

[[Logical negation]] is an [[logical operation|operation]] on one [[logical value]], typically the value of a [[proposition]], that produces a value of ''true'' if its operand is false and a value of ''false'' if its operand is true.

The truth table for '''NOT p''' (also written as '''~p''' or '''¬p''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:40%"
|+ '''Logical Negation'''
|- style="background:paleturquoise"
! style="width:20%" | p
! style="width:20%" | ¬p
|-
| F || T
|-
| T || F
|}
==Logical conjunction==

[[Logical conjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are true.

The truth table for '''p AND q''' (also written as '''p ∧ q''', '''p & q''', or '''p<math>\cdot</math>q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Conjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p · q
|-
| T || T || T
|-
| T || F || F
|-
| F || T || F
|-
| F || F || F
|-

|}

 

In ordinary language terms, if both ''p'' and ''q'' are true, then the conjunction ''p'' ∧ ''q'' is true. For all other assignments of logical values to ''p'' and to ''q'' the conjunction ''p'' ∧ ''q'' is false.

It can also be said that if ''p'', then ''p'' ∧ ''q'' is ''q'', otherwise ''p'' ∧ ''q'' is ''p''.

[[Logical disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' [[if and only if]] both of its operands are false.

The truth table for '''p OR q''' (also written as '''p ∨ q''', '''p || q''', or '''p + q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p + q
|-
| T || T || T
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

Stated in English, if ''p'', then ''p'' ∨ ''q'' is ''p'', otherwise ''p'' ∨ ''q'' is ''q''.

==Exclusive disjunction==

[[Exclusive disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if one but not both of its operands is true.

The truth table for '''p XOR q''' (also written as '''p + q''', '''p ⊕ q''', or '''p ≠ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Exclusive Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ⊕ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

For two propositions, '''XOR''' can also be written as (p = 1 ∧ q = 0)∨ (p = 0 ∧ q = 1).

[[Image:XOR.jpg]]

This diagram is the biological representation to: (A'∨B')∧(A∨B)

==Logical NAND==

The [[logical NAND]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' if and only if both of its operands are true. In other words, it produces a value of ''true'' if and only if at least one of its operands is false.

The truth table for '''p NAND q''' (also written as '''p | q''' or '''p ↑ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NAND'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↑ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || T
|}
 

==Logical NOR==

The [[logical NOR]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are false. In other words, it produces a value of ''false'' if and only if at least one of its operands is true. ↓ is also known as the [[Peirce arrow]] after its inventor, [[Charles Peirce]], and is a [[Sole sufficient operator]].

The truth table for '''p NOR q''' (also written as '''p ⊥ q''' or '''p ↓ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NOR'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↓ q
|-
| T || T || F
|-
| T || F || F
|-
| F || T || F
|-
| F || F || T
|}
 

*[http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#Introduction%20to%20neural%20networks Neural Network Models]
*[http://www.facweb.iitkgp.ernet.in/~niloy/PRESENTATION/ACRI_presentation_97.ppt Cellular Automata Based Authentication]
*MD5 Paper
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1762088 Stochastic model of E. coli AI-2 quorum signal circuit reveals alternative synthesis pathways] Describes a Stochastic Petri Net (SPN) model of AI-2 (Lux), provides XML code and rate constants.

How to break MD5 and other Hash functions.. A paper written by Xiaoyun Wang and her co-authors about how to break MD5 – i.e. how to make collisions occur
http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf
Nostradamus attack – i.e. the bit about predicting who will become president by exploiting MD5
http://www.win.tue.nl/hashclash/Nostradamus/

The following was taken from http://www.freesoft.org/CIE/RFC/1321/4.htm

MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, it need not be a multiple of eight, and it may be arbitrarily large. We imagine the bits of the message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest of the message.

Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)
At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits. Equivalently, this message has a length that is an exact multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the words of the resulting message, where N is a multiple of 16.

Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, low-order bytes first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z. The function F could have been defined using + instead of v since XY and not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.
The functions G, H, and I are similar to the function F, in that they act in "bitwise parallel" to produce their output from the bits of X, Y, and Z, in such a manner that if the corresponding bits of X, Y, and Z are independent and unbiased, then each bit of G(X,Y,Z), H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that the function H is the bit-wise "xor" or "parity" function of its inputs.
This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Step 5. Output
The message digest produced as output is A, B, C, D. That is, we begin with the low-order byte of A, and end with the high-order byte of D.
This completes the description of MD5. A reference implementation in C is given in the appendix.

Summary
The MD5 message-digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the cas Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (XY v XZ v YZ) to (XZ v Y not(Z)) to make g less symmetric.
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

== Engineering agar ==
[http://www.biotech.iastate.edu/lab_protocols/EvoAntiResBact.html A lab for showing antibiotic resistance across Amp concentration gradient]

Math Modeling Pages

2008-05-29T14:26:36Z

JoIgo: /* Exclusive disjunction */

This is the place for math modelers to post ideas, papers, examples and computer programs.

Presentation on Sudoku (Aaron and John have seen)

http://www.math-cs.ucmo.edu/~hchen/talks/sudoku.pdf

== Papers ==
[http://www.rfc-archive.org/getrfc.php?rfc=1319 MD2 Message-Digest Algorithm]

==Logical negation==

[[Logical negation]] is an [[logical operation|operation]] on one [[logical value]], typically the value of a [[proposition]], that produces a value of ''true'' if its operand is false and a value of ''false'' if its operand is true.

The truth table for '''NOT p''' (also written as '''~p''' or '''¬p''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:40%"
|+ '''Logical Negation'''
|- style="background:paleturquoise"
! style="width:20%" | p
! style="width:20%" | ¬p
|-
| F || T
|-
| T || F
|}
==Logical conjunction==

[[Logical conjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are true.

The truth table for '''p AND q''' (also written as '''p ∧ q''', '''p & q''', or '''p<math>\cdot</math>q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Conjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p · q
|-
| T || T || T
|-
| T || F || F
|-
| F || T || F
|-
| F || F || F
|-

|}

 

In ordinary language terms, if both ''p'' and ''q'' are true, then the conjunction ''p'' ∧ ''q'' is true. For all other assignments of logical values to ''p'' and to ''q'' the conjunction ''p'' ∧ ''q'' is false.

It can also be said that if ''p'', then ''p'' ∧ ''q'' is ''q'', otherwise ''p'' ∧ ''q'' is ''p''.

[[Logical disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' [[if and only if]] both of its operands are false.

The truth table for '''p OR q''' (also written as '''p ∨ q''', '''p || q''', or '''p + q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p + q
|-
| T || T || T
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

Stated in English, if ''p'', then ''p'' ∨ ''q'' is ''p'', otherwise ''p'' ∨ ''q'' is ''q''.

==Exclusive disjunction==

[[Exclusive disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if one but not both of its operands is true.

The truth table for '''p XOR q''' (also written as '''p + q''', '''p ⊕ q''', or '''p ≠ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Exclusive Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ⊕ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

For two propositions, '''XOR''' can also be written as (p = 1 ∧ q = 0)∨ (p = 0 ∧ q = 1).

[[Image:XOR.jpg]]
This diagram is the biological representation to: (A'∨B')∧(A∨B)

==Logical NAND==

The [[logical NAND]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' if and only if both of its operands are true. In other words, it produces a value of ''true'' if and only if at least one of its operands is false.

The truth table for '''p NAND q''' (also written as '''p | q''' or '''p ↑ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NAND'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↑ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || T
|}
 

==Logical NOR==

The [[logical NOR]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are false. In other words, it produces a value of ''false'' if and only if at least one of its operands is true. ↓ is also known as the [[Peirce arrow]] after its inventor, [[Charles Peirce]], and is a [[Sole sufficient operator]].

The truth table for '''p NOR q''' (also written as '''p ⊥ q''' or '''p ↓ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NOR'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↓ q
|-
| T || T || F
|-
| T || F || F
|-
| F || T || F
|-
| F || F || T
|}
 

*[http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#Introduction%20to%20neural%20networks Neural Network Models]
*[http://www.facweb.iitkgp.ernet.in/~niloy/PRESENTATION/ACRI_presentation_97.ppt Cellular Automata Based Authentication]
*MD5 Paper
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1762088 Stochastic model of E. coli AI-2 quorum signal circuit reveals alternative synthesis pathways] Describes a Stochastic Petri Net (SPN) model of AI-2 (Lux), provides XML code and rate constants.

How to break MD5 and other Hash functions.. A paper written by Xiaoyun Wang and her co-authors about how to break MD5 – i.e. how to make collisions occur
http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf
Nostradamus attack – i.e. the bit about predicting who will become president by exploiting MD5
http://www.win.tue.nl/hashclash/Nostradamus/

The following was taken from http://www.freesoft.org/CIE/RFC/1321/4.htm

MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, it need not be a multiple of eight, and it may be arbitrarily large. We imagine the bits of the message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest of the message.

Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)
At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits. Equivalently, this message has a length that is an exact multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the words of the resulting message, where N is a multiple of 16.

Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, low-order bytes first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z. The function F could have been defined using + instead of v since XY and not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.
The functions G, H, and I are similar to the function F, in that they act in "bitwise parallel" to produce their output from the bits of X, Y, and Z, in such a manner that if the corresponding bits of X, Y, and Z are independent and unbiased, then each bit of G(X,Y,Z), H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that the function H is the bit-wise "xor" or "parity" function of its inputs.
This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Step 5. Output
The message digest produced as output is A, B, C, D. That is, we begin with the low-order byte of A, and end with the high-order byte of D.
This completes the description of MD5. A reference implementation in C is given in the appendix.

Summary
The MD5 message-digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the cas Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (XY v XZ v YZ) to (XZ v Y not(Z)) to make g less symmetric.
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

== Engineering agar ==
[http://www.biotech.iastate.edu/lab_protocols/EvoAntiResBact.html A lab for showing antibiotic resistance across Amp concentration gradient]

Math Modeling Pages

2008-05-29T14:23:55Z

JoIgo: /* Exclusive disjunction */

This is the place for math modelers to post ideas, papers, examples and computer programs.

Presentation on Sudoku (Aaron and John have seen)

http://www.math-cs.ucmo.edu/~hchen/talks/sudoku.pdf

== Papers ==
[http://www.rfc-archive.org/getrfc.php?rfc=1319 MD2 Message-Digest Algorithm]

==Logical negation==

[[Logical negation]] is an [[logical operation|operation]] on one [[logical value]], typically the value of a [[proposition]], that produces a value of ''true'' if its operand is false and a value of ''false'' if its operand is true.

The truth table for '''NOT p''' (also written as '''~p''' or '''¬p''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:40%"
|+ '''Logical Negation'''
|- style="background:paleturquoise"
! style="width:20%" | p
! style="width:20%" | ¬p
|-
| F || T
|-
| T || F
|}
==Logical conjunction==

[[Logical conjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are true.

The truth table for '''p AND q''' (also written as '''p ∧ q''', '''p & q''', or '''p<math>\cdot</math>q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Conjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p · q
|-
| T || T || T
|-
| T || F || F
|-
| F || T || F
|-
| F || F || F
|-

|}

 

In ordinary language terms, if both ''p'' and ''q'' are true, then the conjunction ''p'' ∧ ''q'' is true. For all other assignments of logical values to ''p'' and to ''q'' the conjunction ''p'' ∧ ''q'' is false.

It can also be said that if ''p'', then ''p'' ∧ ''q'' is ''q'', otherwise ''p'' ∧ ''q'' is ''p''.

[[Logical disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' [[if and only if]] both of its operands are false.

The truth table for '''p OR q''' (also written as '''p ∨ q''', '''p || q''', or '''p + q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p + q
|-
| T || T || T
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

Stated in English, if ''p'', then ''p'' ∨ ''q'' is ''p'', otherwise ''p'' ∨ ''q'' is ''q''.

==Exclusive disjunction==

[[Exclusive disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if one but not both of its operands is true.

The truth table for '''p XOR q''' (also written as '''p + q''', '''p ⊕ q''', or '''p ≠ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Exclusive Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ⊕ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

For two propositions, '''XOR''' can also be written as (p = 1 ∧ q = 0)∨ (p = 0 ∧ q = 1).

[[Image:XOR.jpg]]

==Logical NAND==

The [[logical NAND]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' if and only if both of its operands are true. In other words, it produces a value of ''true'' if and only if at least one of its operands is false.

The truth table for '''p NAND q''' (also written as '''p | q''' or '''p ↑ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NAND'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↑ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || T
|}
 

==Logical NOR==

The [[logical NOR]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are false. In other words, it produces a value of ''false'' if and only if at least one of its operands is true. ↓ is also known as the [[Peirce arrow]] after its inventor, [[Charles Peirce]], and is a [[Sole sufficient operator]].

The truth table for '''p NOR q''' (also written as '''p ⊥ q''' or '''p ↓ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NOR'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↓ q
|-
| T || T || F
|-
| T || F || F
|-
| F || T || F
|-
| F || F || T
|}
 

*[http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#Introduction%20to%20neural%20networks Neural Network Models]
*[http://www.facweb.iitkgp.ernet.in/~niloy/PRESENTATION/ACRI_presentation_97.ppt Cellular Automata Based Authentication]
*MD5 Paper
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1762088 Stochastic model of E. coli AI-2 quorum signal circuit reveals alternative synthesis pathways] Describes a Stochastic Petri Net (SPN) model of AI-2 (Lux), provides XML code and rate constants.

How to break MD5 and other Hash functions.. A paper written by Xiaoyun Wang and her co-authors about how to break MD5 – i.e. how to make collisions occur
http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf
Nostradamus attack – i.e. the bit about predicting who will become president by exploiting MD5
http://www.win.tue.nl/hashclash/Nostradamus/

The following was taken from http://www.freesoft.org/CIE/RFC/1321/4.htm

MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, it need not be a multiple of eight, and it may be arbitrarily large. We imagine the bits of the message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest of the message.

Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)
At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits. Equivalently, this message has a length that is an exact multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the words of the resulting message, where N is a multiple of 16.

Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, low-order bytes first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z. The function F could have been defined using + instead of v since XY and not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.
The functions G, H, and I are similar to the function F, in that they act in "bitwise parallel" to produce their output from the bits of X, Y, and Z, in such a manner that if the corresponding bits of X, Y, and Z are independent and unbiased, then each bit of G(X,Y,Z), H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that the function H is the bit-wise "xor" or "parity" function of its inputs.
This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Step 5. Output
The message digest produced as output is A, B, C, D. That is, we begin with the low-order byte of A, and end with the high-order byte of D.
This completes the description of MD5. A reference implementation in C is given in the appendix.

Summary
The MD5 message-digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the cas Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (XY v XZ v YZ) to (XZ v Y not(Z)) to make g less symmetric.
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

== Engineering agar ==
[http://www.biotech.iastate.edu/lab_protocols/EvoAntiResBact.html A lab for showing antibiotic resistance across Amp concentration gradient]

File:XOR.jpg

2008-05-29T14:22:46Z

JoIgo:

File:XOR2.jpg

2008-05-29T14:20:29Z

JoIgo:

File:XOR1.jpg

2008-05-29T14:00:55Z

JoIgo:

Math Modeling Pages

2008-05-29T14:00:34Z

JoIgo: /* Exclusive disjunction */

This is the place for math modelers to post ideas, papers, examples and computer programs.

Presentation on Sudoku (Aaron and John have seen)

http://www.math-cs.ucmo.edu/~hchen/talks/sudoku.pdf

== Papers ==
[http://www.rfc-archive.org/getrfc.php?rfc=1319 MD2 Message-Digest Algorithm]

==Logical negation==

[[Logical negation]] is an [[logical operation|operation]] on one [[logical value]], typically the value of a [[proposition]], that produces a value of ''true'' if its operand is false and a value of ''false'' if its operand is true.

The truth table for '''NOT p''' (also written as '''~p''' or '''¬p''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:40%"
|+ '''Logical Negation'''
|- style="background:paleturquoise"
! style="width:20%" | p
! style="width:20%" | ¬p
|-
| F || T
|-
| T || F
|}
==Logical conjunction==

[[Logical conjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are true.

The truth table for '''p AND q''' (also written as '''p ∧ q''', '''p & q''', or '''p<math>\cdot</math>q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Conjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p · q
|-
| T || T || T
|-
| T || F || F
|-
| F || T || F
|-
| F || F || F
|-

|}

 

In ordinary language terms, if both ''p'' and ''q'' are true, then the conjunction ''p'' ∧ ''q'' is true. For all other assignments of logical values to ''p'' and to ''q'' the conjunction ''p'' ∧ ''q'' is false.

It can also be said that if ''p'', then ''p'' ∧ ''q'' is ''q'', otherwise ''p'' ∧ ''q'' is ''p''.

[[Logical disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' [[if and only if]] both of its operands are false.

The truth table for '''p OR q''' (also written as '''p ∨ q''', '''p || q''', or '''p + q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p + q
|-
| T || T || T
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

Stated in English, if ''p'', then ''p'' ∨ ''q'' is ''p'', otherwise ''p'' ∨ ''q'' is ''q''.

==Exclusive disjunction==

[[Exclusive disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if one but not both of its operands is true.

The truth table for '''p XOR q''' (also written as '''p + q''', '''p ⊕ q''', or '''p ≠ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Exclusive Disjunction'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ⊕ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || F
|}
 

For two propositions, '''XOR''' can also be written as (p = 1 ∧ q = 0)∨ (p = 0 ∧ q = 1).

[[Image:XOR1.jpg]]

==Logical NAND==

The [[logical NAND]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' if and only if both of its operands are true. In other words, it produces a value of ''true'' if and only if at least one of its operands is false.

The truth table for '''p NAND q''' (also written as '''p | q''' or '''p ↑ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NAND'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↑ q
|-
| T || T || F
|-
| T || F || T
|-
| F || T || T
|-
| F || F || T
|}
 

==Logical NOR==

The [[logical NOR]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if and only if both of its operands are false. In other words, it produces a value of ''false'' if and only if at least one of its operands is true. ↓ is also known as the [[Peirce arrow]] after its inventor, [[Charles Peirce]], and is a [[Sole sufficient operator]].

The truth table for '''p NOR q''' (also written as '''p ⊥ q''' or '''p ↓ q''') is as follows:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Logical NOR'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p ↓ q
|-
| T || T || F
|-
| T || F || F
|-
| F || T || F
|-
| F || F || T
|}
 

*[http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#Introduction%20to%20neural%20networks Neural Network Models]
*[http://www.facweb.iitkgp.ernet.in/~niloy/PRESENTATION/ACRI_presentation_97.ppt Cellular Automata Based Authentication]
*MD5 Paper
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1762088 Stochastic model of E. coli AI-2 quorum signal circuit reveals alternative synthesis pathways] Describes a Stochastic Petri Net (SPN) model of AI-2 (Lux), provides XML code and rate constants.

How to break MD5 and other Hash functions.. A paper written by Xiaoyun Wang and her co-authors about how to break MD5 – i.e. how to make collisions occur
http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf
Nostradamus attack – i.e. the bit about predicting who will become president by exploiting MD5
http://www.win.tue.nl/hashclash/Nostradamus/

The following was taken from http://www.freesoft.org/CIE/RFC/1321/4.htm

MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, it need not be a multiple of eight, and it may be arbitrarily large. We imagine the bits of the message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest of the message.

Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)
At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits. Equivalently, this message has a length that is an exact multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the words of the resulting message, where N is a multiple of 16.

Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, low-order bytes first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z. The function F could have been defined using + instead of v since XY and not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.
The functions G, H, and I are similar to the function F, in that they act in "bitwise parallel" to produce their output from the bits of X, Y, and Z, in such a manner that if the corresponding bits of X, Y, and Z are independent and unbiased, then each bit of G(X,Y,Z), H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that the function H is the bit-wise "xor" or "parity" function of its inputs.
This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Step 5. Output
The message digest produced as output is A, B, C, D. That is, we begin with the low-order byte of A, and end with the high-order byte of D.
This completes the description of MD5. A reference implementation in C is given in the appendix.

Summary
The MD5 message-digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the cas Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (XY v XZ v YZ) to (XZ v Y not(Z)) to make g less symmetric.
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

== Engineering agar ==
[http://www.biotech.iastate.edu/lab_protocols/EvoAntiResBact.html A lab for showing antibiotic resistance across Amp concentration gradient]

Math Modeling Pages

2008-05-22T13:29:08Z

JoIgo: /* Papers */

This is the place for math modelers to post ideas, papers, examples and computer programs.

== Papers ==
[http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1762088 Stochastic model of E. coli AI-2 quorum signal circuit reveals alternative synthesis pathways] Describes a Stochastic Petri Net (SPN) model of AI-2 (Lux), provides XML code and rate constants.

How to break MD5 and other Hash functions.. A paper written by Xiaoyun Wang and her co-authors about how to break MD5 – i.e. how to make collisions occur
http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf
Nostradamus attack – i.e. the bit about predicting who will become president by exploiting MD5
http://www.win.tue.nl/hashclash/Nostradamus/

The following was taken from http://www.freesoft.org/CIE/RFC/1321/4.htm

MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, it need not be a multiple of eight, and it may be arbitrarily large. We imagine the bits of the message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest of the message.

Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)
At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits. Equivalently, this message has a length that is an exact multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the words of the resulting message, where N is a multiple of 16.

Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, low-order bytes first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z. The function F could have been defined using + instead of v since XY and not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.
The functions G, H, and I are similar to the function F, in that they act in "bitwise parallel" to produce their output from the bits of X, Y, and Z, in such a manner that if the corresponding bits of X, Y, and Z are independent and unbiased, then each bit of G(X,Y,Z), H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that the function H is the bit-wise "xor" or "parity" function of its inputs.
This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Step 5. Output
The message digest produced as output is A, B, C, D. That is, we begin with the low-order byte of A, and end with the high-order byte of D.
This completes the description of MD5. A reference implementation in C is given in the appendix.

Summary
The MD5 message-digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the cas Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (XY v XZ v YZ) to (XZ v Y not(Z)) to make g less symmetric.
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

== Engineering agar ==
[http://www.biotech.iastate.edu/lab_protocols/EvoAntiResBact.html A lab for showing antibiotic resistance across Amp concentration gradient]

Wet Lab Pages

2008-05-21T15:20:05Z

JoIgo: /* Registry parts to clone */

This is the space for MWSU and DC wet lab students to create content.
Our part numbers will be in this range only: '''BBa_K091000 to BBa_K091999'''.

# [http://gcat.davidson.edu/GcatWiki/index.php/Davidson_Missouri_W/Davidson_Protocols Davidson Wet Lab Protocols]
#[http://gcat.davidson.edu/GcatWiki/index.php/Davidson_Missouri_W/MWSU_protocols MWSU Wet Lab Protocols]
# [http://www.bio.davidson.edu/courses/Molbio/Protocols/ORIs.html Plasmid Compatability]
# [http://spreadsheets.google.com/pub?key=pw-NamR_FPJOfhl6mDrkZcw Davidson -80 Stocks]
#[http://tools.wikimedia.de/~tangotango/nubio/ FAQs for Wikis]
 
----
== Registry parts to clone ==

'''Composite Parts''':

{| border="1" cellpadding="2"
!width="50"|Part
!width="225"|Description
!width="225"|Student Responsible (DC or MW)
|-
|BBa_F2621|| AHL receiver with lux pR and codes for LuxR || Sven(MW)
|-
|BBa_I15030 || Lux-sender(Autoinducing)Codes for LuxI and LuxR || Kelly Davis (DC) will this send to part BBa_I13263
|-
|BBa_I13263 || Lux Receiver (HSL & R0063 driven)produces YFP || Pallivi Penumetcha (DC)
|-
|BBa_I0426 || Las-reciver(EYFP) || Sven (MW)
|-
|BBa_I0466|| RhlR Protein Generator without LVA || Sven(MW)
|-
|BBa_I0407 || LasI test || Erin Feeney (DC)
|-
|BBa_I0426 || LasR test || Samantha Simpson (DC)
|-
|BBa_#### || Description || Sven(MW)
|-
|}

'''Basic Parts''':

{| border="1" cellpadding="2"
!width="50"|Part
!width="225"|Description
!width="225"|Student Responsible (DC or MW)
|-
|BBa_C0061 || LuxI gene with LVA || later
|-
|BBa_C0161 || LuxI gene without LVA || Xiao Zhu (MW)
|-
|BBa_C0062 || LuxR gene without LVA || John Igo (MW)
|-
|BBa_R0063 || lux pL|| Aaron Lewis (MW)
|-
|BBa_R0062|| lux pR|| Andrew Gordon(MW)
|-
|BBa_C0070|| rhlI gene || Jeff Poet (MW)
|-
|BBa_C0071|| rhlR gene with LVA|| Sven (MW)
|-
|BBa_R0079 || las pR || Todd Eckdahl (MW)
|-
|BBa_C0079 || lasR gene || Robert Cool (MW)
|-
|BBa_C0078 || LasI gene || Alicia Allen (MW)
|-
|BBa_PA3477|| rhlR gene without LVA || Sven (MW)
|-
|BBa_#### || Description || Sven(MW)
|-
|BBa_#### || Description || Sven(MW)
|-
|BBa_#### || Description || Sven(MW)
|-
|BBa_#### || Description || Sven(MW)
|}

Davidson/Missouri Western iGEM2008

2008-04-04T20:55:32Z

JoIgo: /* iGEM 2007 Useful Information */

<center>
Davidson College - Missouri Western State University
</center>
<center>

iGEM 2008
</center>

== iGEM 2007 Useful Information ==
Virginia Tech (2007) Engineering and Epidemic

The use of bacteria to model the spread of a disease. It would appear that cell-to-cell communication is a major part of the design of the project. It is unclear how successful the team was in building parts useful to us. Most of the project seems to be on the mathematical modeling side of things.

University of Waterloo (2007) Half-Adder Logic Gate

The goal of this project is to design a basic device for computing. Our idea was to reproduce a circuit element called a half adder with DNA, which takes in two 1-bit inputs, adds them, and outputs a sum and a carry. Our device responds to two inputs: red light and the chemical tetracycline. The input sensors control a set of genetic switches in order to carry out the computation and fluoresces green, red, or neither, depending on the outcome. Useful for long addition in base-2.

UCSF (2007) Project 1 Protein Scaffolds as a Molecular Breadboard

Using synthetic protein scaffolds to control information flow of a kinase pathway in eukaryotic cells.

Tianjin (2007) Biological diode

In this project, we try to construct a biological device to imitate the function of the diode, one of the most significant parts in the electric integrate circuit. The flow of molecular signal AHL is considered as the current of electric circuit. The generator, amplifiers, blocks and detector cells are constructed with the parts provided by MIT and then are equipped in series in order to establish the cellular and molecular biological diode. Our device, which is a combination of technologies from the field of computer science, molecular biology and chemical engineering, is a breakthrough for the application of mature techniques of chemical engineering to the field of synthetic biology.

http://parts.mit.edu/igem07/index.php/Duke/Projects/bc - bacterial communication with light.

http://parts.mit.edu/igem07/index.php/Cambridge - they talk a little about making a bacterial internet, I have no idea what they mean.

http://parts.mit.edu/igem07/index.php/Tokyo_Tech - They say, “Bistability and cell-cell communication are necessary to realize our model of ‘Balanced differentiation’.”

== iGEM 2006 Useful Information ==

'''The University of Calgary''' 2006 iGEM team is working on the following project. A petri plate is inhabited by two strains of genetically engineered ''E. coli'' bacteria. The first strain---the Senders---have been engineered to emit two chemical signals into the plate environment: Aspartate and Acyl Homoserine Lactone (AHSL). The senders themselves are activated by light. The second strain---the Receivers---have been designed to respond to each of these signals in a different way.
The Receivers express Green Fluorescent Protein in the vicinity of AHSL.
The Receivers also move towards areas of greater Aspartate concentration. The same bacteria also decrease Aspartate levels where they are present, as this is a nutrient and constitutes the reason for why they are attracted to it in the first place.
Our goal is to make the Senders and Receivers create interesting behaviour dynamics visualized by fluorescent patterns.

http://parts.mit.edu/r/parts/partsdb/pgroup.cgi?pgroup=iGEM2006&group=iGEM2006_Calgary

'''Berkeley''': networks of cells communicating via conjugation; demonstrated the transmission of a coded message

http://parts2.mit.edu/wiki/index.php/University_of_California_Berkeley_2006

“We have developed the process of addressable conjugation for communication within a network of E. coli bacteria. Here, bacteria send messages to one another via conjugation of plasmid DNAs, but the message is only meaningful to cells with a matching address sequence. In this way, the Watson Crick base-pairing of addressing sequences replaces the spatial connectivity present in neural systems. To construct this system, we have adapted natural conjugation systems as the communication device. Information contained in the transferred plasmids is only accessable by "unlocking" the message using RNA based 'keys'. The resulting addressable conjugation process is being adapted to construct a network of NAND logic gates in bacterial cultures.”

'''Mexico''': cellular automata

http://parts2.mit.edu/wiki/index.php/IPN_UNAM_2006

“We wish contribute to the iGEM project development various protein based bio-components. We will work along three main lines: complex and reversible dynamical systems and formal languages, that support particles and multiple reactions, related to the molecular transformations.”

“We study two-dimensional cellular automaton, where every cell takes states 0 and 1 and updates its state depending on sum of states of its 8 closest neighbors as follows. Cell in state 0 takes state 1 if there are exactly two neighbors in state 1, otherwise the cell remains in state 0. Cell in state 1 remains in state 1 if there are exactly seven neighbors in state 1, otherwise the cell switches to state 0. CA governed by such cell-state transition rule exhibits reaction-diffusion like pattern dynamics, so we call this Diffusion Rule.”

“Using the diffusion rule we can generate a dynamical pattern over a system, like turn on/off ligth with alive o dead cells that shows a luminescence, examples include fluorescence, bioluminescence and phosphorescence.”
“Starting with any configuration, the cells alive are represented in yellow (the activator) and dead in black (the inhibitor), see figure 4. The system is created defining an inicial state over the base configuration (see figure 3). The luminescence is obtained by the evolution of this initial pattern.”

'''Brown:Bacterial''' Freeze Tag
http://parts.mit.edu/wiki/index.php/Brown:Bacterial_Freeze_Tag#Overview
2006 igem

This project involves programming bacteria to be able to play a game of freeze tag. Bacteria will be engineered to swim around a microfluidics device until they reach a certain proximity to the 'IT' cell and then they will lose their ability to move. This loss of motility will be combined with a change in color from Green to Blue. When another bacterium, which is moving (not the 'IT' cell), reaches a certain proximity to the 'frozen' bacteria it will again regain its ability to move and turn from Blue to Yellow.

TetR promoted with LuxI downstream. LuxI is an enzyme that produces AHL and will produce the red fluorescent protein (RFP). The AHL produced is exported from the cell where it then forms a complex with the LuxR protein that is produced by the AHL sensor within the Receiver cell.

The AHL sensor is TetR promoted and forms the LuxR protein which then forms a complex with AHL. This LuxR and AHL complex then activates the pLuxR promoter. Downstream of the pLuxR promoter is the LacI protein. LacI inhibits the pLac promoter on the "Freeze Machine".

A promoter that is regulated by LacI will promote the production of LasI, MotB, and cI. This will subsequently inhibit the production of CFP and LasR. In the presence of LacI, however, MotB, LasI, and cI will not be produced. CFP will therefore be produced along with LasR and LacI. This results in the "freezing" of the cell.

'''McGill University Split YFP'''
http://parts.mit.edu/wiki/index.php/McGill_University_2006

The idea behind the project is fluorescence complementation, which involves the joining of two leucine zipper proteins, Fos and Jun, each fused to a half terminus of YFP. Originally, the Fos and Jun proteins were fused to a beta gene coding for a membrane protein. The project involved performing a PCR reaction to produce two inserts, the N-terminus and the C-terminus of YFP, and then ligating these inserts into 2 vectors, containing Jun-beta and the Fos-beta respectively. The two fusion proteins (Fos-beta-YFPC and Jun-beta-YFPN) were expressed in the cell membrane of two populations of E. coli. We then allowed these two cell types to combine, resulting—ideally—in the complementary binding of the Jun and Fos proteins when the cells are in close contact. Consequently, the two half YFP fragments bind to form full YFP, and the cells will fluoresce.

'''Penn State'''
http://openwetware.org/wiki/IGEM:PennState/2006

The bacterial relay race takes advantage of an ability to control cellular motility using inducible promoters such as those involved in nutrient catabolism or quorum sensing. “Receiver” bacteria move in response to small-molecule signals either added to the system or originating from motile, “sender” strains. The most significant challenges relating to this project stem from difficulties of tightly controlling the target motility gene motB. Low levels of motB expression result in system failure (constitutive motility), and resolving this issue is essential to developing reliable modular systems that are the hallmark of synthetic biology

'''Tokyo'''
http://parts.mit.edu/wiki/index.php/Tokyo_Alliance:_Conclusion

Our project is to make this Noughts-and-Crosses in vivo.
-1. Inputs
-1. Chemicals
-1. To indicate each square
-1. To be spreaded into all squares.
-1. Outputs
-1. Reporter of SYANAC: GFP
Reporter of Human: RFP

We can say we will expand the number of regulator genes we can use to build logic gates and through this project we made simple constructing method.

== iGEM 2005 Useful Information ==

Main Page

2008-04-04T20:54:45Z

JoIgo:

==This is our first attempt at GCAT Community Wiki.==
This Wiki has been set up for the use of the GCAT community. The intent is that it be maintained by its users.

Please read the [[Guidelines]] for use.

 
== [[Davidson/Missouri Western iGEM2008]] ==

 
== [[MAGIC Tool Development]] ==

 
== [[Nova Southeastern University]] ==

 

== [[Davidson College]]== Small liberal arts college near Charlotte, NC.
A. Malcolm Campbell and Laurie J. Heyer GCAT faculty

* [http://gcat.davidson.edu/GcatWiki/index.php/User:Kahaynes Karmella A. Haynes], Visiting Assitant Professor of Biology

* [[A_Review_of_Synthetic_Biology |A Review of Synthetic Biology - Davidson College Synthetic Biology Seminar (Fall 2007)]]

== [[Next School Here]]==

 
 
 
----
----
 
Please see [http://meta.wikipedia.org/wiki/MediaWiki_i18n documentation on customizing the interface]
and the [http://meta.wikipedia.org/wiki/MediaWiki_User%27s_Guide User's Guide] for usage and configuration help.
 
 
[http://www.bio.davidson.edu/GCAT GCAT Main Page]

http://parts.mit.edu/igem07/index.php/Duke/Projects/bc - bacterial communication with light.

http://parts.mit.edu/igem07/index.php/Cambridge - they talk a little about making a bacterial internet, I have no idea what they mean.

http://parts.mit.edu/igem07/index.php/Tokyo_Tech - They say, “Bistability and cell-cell communication are necessary to realize our model of ‘Balanced differentiation’.”