λ calculus

definition:
–λ formal-parameter. function-body
define an anonymous function

–λ formal-parameter. function-body actual-parameter
replace all the formal-parameter in the function body with the actual-parameters.

some time it is difficult to separate the function body and the actual-parameter, use (): (λ formal-parameter. function-body) (actual-parameter)

eg:
–(λf.f 3)(λx.x + 2)
–where (λf.f 3) means an anonymous function λ(f){f 3}
–so (λf.f 3)(λx.x + 2) means {(λx.x + 2) 3}
–then {(λx.x + 2) 3} means (3 + 2)

–[λf g.(f (g 3))](λx.x + 2)
–where [λf g.(f (g 3))] means an anonymous function λ(f,g){f[g(3)]}
–so [λf g.(f (g 3))](λx.x + 2) means λg.{(λx.x + 2) (g 3)}
–then λg.{(λx.x + 2) (g 3)} means λg.(g(3) + 2)

(λx.x x)(λx.x x) means: use the later (λx.x x) to substitute the (x x) in the former (λx.x x), you get (λx.x x) (λx.x x) again.

(λx.x x x)(λx.x x x) means: use the later (λx.x x x) to substitute the (x x x) in the former (λx.x x x), you get (λx.x x x)(λx.x x x)(λx.x x x), next time you will get (λx.x x x)(λx.x x x)(λx.x x x)(λx.x x x)(λx.x x x)(λx.x x x)…

note: (λx y.x y) (λy.F y) means (λy.(λy.F y)y) <==> (λy.(λz.F z)y) <==> (λy.F y). The scope of formal parameter is local.

Fixed point combinator:

A fixed point combinator (or fixed-point operator) is a higher-order function which computes a fixed point of other functions.

e.g. Suppose “fix” is a fixed point combinator which fix(g) is a fixed point of function g, thus g(fix(g)) = fix(g).

One well-known (and perhaps the simplest) fixed point combinator in the untyped lambda calculus is called the Y combinator. It was discovered by Haskell B. Curry, and is defined as:

Y = λf.(λx.f(x x))(λx.f(x x))

Note that the Y combinator is intended for the call-by-name evaluation strategy, since (Y g) diverges (for any g) in call-by-value settings.

Obviously: Y g = (λx.g(x x))(λx.g(x x)) = g((λx.g(x x)(λx.g(x x)) = g(Y g)
Thus Y g = g(Y g) = g(g(Y g)) = g(g(g(Y g))) …

Factorial function n!, we would simply call g(Y g) n
Where g := λf n. (1, if n = 0; and n·f(n-1), if n > 0).
So g(Y g) = λn. (1, if n = 0; and n·((Y g)(n-1)), if n > 0)
and g(Y g)n = (1, if n = 0; and n·((Y g)(n-1)), if n > 0)
for n = 5:
g(Y g)5 = 5·((Y g)(5-1)) = 5·((Y g)4) = 5·(g(Y g)4) = 5·4·((Y g)3) = 5·4·(g(Y g)3)= … = 5·4·3·2·1

Every recursively defined function can be seen as a fixed point of some other suitable function, and therefore, using Y, every recursively defined function can be expressed as a lambda expression.

A quick sort λ expression:
suppose we have sizeof and pl and pg function
sizeof(array) returns the size of the array.
pl(array) and pg(array) makes a complete partition of the array, where each element in pl(array) is less than each element in pg(array).

q := λs a. a, if sizeof(a)<=1; and s(pl(a)) s(pg(a)), if sizeof(a)>1

q(Y q)
= λa.a, if sizeof(a)<=1; and (Y q)(pl(a)) (Y q)(pg(a))
= λa.a, if sizeof(a)<=1; and (q(Y q))(pl(a)) (q(Y q))(pg(a))

q(Y q)a
= a, if sizeof(a)<=1; and (q(Y q))(pl(a)) (q(Y q))(pg(a))

q(Y q)a is the λ expression of the quick sort function.

Because that Y can calculate the fixed point of any function g, so any recursive function can be represented as per replacing the recursion point with g(Y g):

h(x) := (F(h))(x)
F is some high order function, F(fun) returns a function composed with fun, here we use it to represent the recursive form of function h. This is not a λ expression, because there is an explicit recursion.

let g := λH x.(F(H))(x) then
g(Y g) = λx.(F(Y g))(x) = λx.(F(g(Y g)))(x) ..now this is a valid λ expression.

so
h := g(Y g)
= (λH x.(F(H))(x))(Y (λH x.(F(H))(x)))
= (λH x.(F(H))(x))((λf.(λx.f(x x))(λx.f(x x)))(λH x.(F(H))(x)))
is the λ expression definition for function h

ref:
http://en.wikipedia.org/wiki/Fixed_point_combinator
http://en.wikipedia.org/wiki/Lambda_calculus

My idea about EC point embedding

To encrypt message in ECC, we have to embed the message into a EC point inefficiently.
I have a new idea about avoiding embed the message.

The old scheme of ECC is: G is the base point, P = k*G as public key. M is the point that M.x contain the message m. But not all x are valid coordination of a EC point, so M.x always something larger than m, say 32 bits longer than m, to make sure a valid coordination that contains m can be found.

The sender send (A, B) = (r*G, M+r*P), r is a random number
The receiver calculate M = B – k*A

My idea is: try some different random number r, to find a r, that makes ((r*P).x)⊕m is a valid x coordinate in EC, then make the x coordinate of M is just ((r*P).x)⊕m. The receiver first calculate M, and then m = M.x⊕(k*A).x.

One thing should be proved: For each possible message m, there are pretty much point on EC whose x coordinate plus m will also make a x coordinate of some EC point.

Finding all paths from source to destination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
AllPathsFromSourceToDestination(s, d) {
    push s into path vector
    InCurrentPathTags[s] = true
    for each vertex v adjacent to s {
        if(v == d) {
            Output the path vector;
        } else {
            if(InCurrentPathTags[v] == false) {
                AllPathsFromSourceToDestination(v, d)
            }
        }
    }
    pop s from path vector
    InCurrentPathTags[s] = false
}

Origins of the universe: Stephen Hawking’s J. Robert Oppenheimer Lecture

http://www.berkeley.edu/news/media/releases/2007/03/16_hawking_text.shtml

Note the bold font segment.

The is the text of the J. Robert Oppenheimer Lecture in Physics, delivered March 13, 2007, by Stephen Hawking, the Lucasian professor of mathematics at Cambridge University. Hawking spoke at Zellerbach Hall on the campus of the University of California, Berkeley.

Can you hear me?

According to the Boshongo people of central Africa, in the beginning there was only darkness, water, and the great god Bumba. One day Bumba, in pain from a stomach ache, vomited up the sun. The sun dried up some of the water, leaving land. Still in pain, Bumba vomited up the moon, the stars, and then some animals. The leopard, the crocodile, the turtle, and, finally man.

This creation myth, like many others, tries to answer the questions we all ask. Why are we here? Where did we come from? The answer generally given, was that humans were of comparatively recent origin, because it must have been obvious, even at early times, that the human race was improving in knowledge and technology. So it can’t have been around that long, or it would have progressed even more. For example, according to Bishop Usher, the Book of Genesis placed the creation of the world at 9 in the morning, on October the 27th, 4,004 BC. On the other hand, the physical surroundings, like mountains and rivers, change very little in a human life time. They were therefore thought to be a constant background, and either to have existed for ever as an empty landscape, or to have been created at the same time as the humans.

Not everyone however, was happy with the idea that the universe had a beginning. For example, Aristotle, the most famous of the Greek philosophers, believed the universe had existed for ever. Something eternal, is more perfect than something created. He suggested the reason we see progress, was that floods, or other natural disasters, had repeatedly set civilization back to the beginning. The motivation for believing in an eternal universe, was the desire to avoid invoking divine intervention, to create the universe, and set it going. Conversely, those who believed the universe had a beginning, used it as an argument for the existence of God, as the first cause, or prime mover of the universe.

If one believed that the universe had a beginning, the obvious question was, What happened before the beginning? What was God doing before He made the world? Was He preparing Hell for people who asked such questions? The problem of whether or not the universe had a beginning, was a great concern to the German philosopher, Immanuel Kant. He felt there were logical contradictions, or Antimonies, either way. If the universe had a beginning, why did it wait an infinite time before it began? He called that the thesis. On the other hand, if the universe had existed for ever, why did it take an infinite time to reach the present stage? He called that the anti thesis. Both the thesis, and the anti thesis, depended on Kant’s assumption, along with almost everyone else, that time was Absolute. That is to say, it went from the infinite past, to the infinite future, independently of any universe that might or might not exist in this background.

This is still the picture in the mind of many scientists today. However in 1915, Einstein introduced his revolutionary General Theory of Relativity. In this, space and time were no longer Absolute, no longer a fixed background to events. Instead, they were dynamical quantities that were shaped by the matter and energy in the universe. They were defined only within the universe, so it made no sense to talk of a time before the universe began. It would be like asking for a point south of the South Pole. It is not defined.

If the universe was essentially unchanging in time, as was generally assumed before the 1920s, there would be no reason that time should not be defined arbitrarily far back. Any so-called beginning of the universe, would be artificial, in the sense that one could extend the history back to earlier times. Thus it might be that the universe was created last year, but with all the memories and physical evidence, to look like it was much older. This raises deep philosophical questions about the meaning of existence. I shall deal with these by adopting what is called, the positivist approach. In this, the idea is that we interpret the input from our senses in terms of a model we make of the world. One can not ask whether the model represents reality, only whether it works. A model is a good model, if first it interprets a wide range of observations, in terms of a simple and elegant model. And second, if the model makes definite predictions that can be tested, and possibly falsified, by observation.

In terms of the positivist approach, one can compare two models of the universe. One in which the universe was created last year, and one in which the universe existed much longer. The model in which the universe existed for longer than a year, can explain things like identical twins, that have a common cause more than a year ago. On the other hand, the model in which the universe was created last year, can not explain such events. So the first model is better. One can not ask whether the universe really existed before a year ago, or just appeared to. In the positivist approach, they are the same.

In an unchanging universe, there would be no natural starting point. The situation changed radically however, when Edwin Hubble began to make observations with the hundred inch telescope on Mount Wilson, in the 1920s.

Hubble found that stars are not uniformly distributed throughout space, but are gathered together in vast collections called galaxies.

By measuring the light from galaxies, Hubble could determine their velocities. He was expecting that as many galaxies would be moving towards us, as were moving away. This is what one would have in a universe that was unchanging with time. But to his surprise, Hubble found that nearly all the galaxies were moving away from us. Moreover, the further galaxies were from us, the faster they were moving away. The universe was not unchanging with time, as everyone had thought previously. It was expanding. The distance between distant galaxies, was increasing with time.

The expansion of the universe, was one of the most important intellectual discoveries of the 20th century, or of any century. It transformed the debate about whether the universe had a beginning. If galaxies are moving apart now, they must have been closer together in the past. If their speed had been constant, they would all have been on top of one another, about 15 billion years ago. Was this, the beginning of the universe.

Many scientists were still unhappy with the universe having a beginning, because it seemed to imply that physics broke down. One would have to invoke an outside agency, which for convenience, one can call God, to determine how the universe began. They therefore advanced theories in which the universe was expanding at the present time, but didn’t have a beginning. One was the Steady State theory, proposed by Bondi, Gold, and Hoyle in 1948.

In the Steady State theory, as galaxies moved apart, the idea was that new galaxies would form from matter that was supposed to be continually being created throughout space. The universe would have existed for ever, and would have looked the same at all times. This last property had the great virtue, from a positivist point of view, of being a definite prediction, that could be tested by observation. The Cambridge radio astronomy group, under Martin Ryle, did a survey of weak radio sources in the early 1960s. These were distributed fairly uniformly across the sky, indicating that most of the sources, lay outside our galaxy. The weaker sources would be further away, on average.

The Steady State theory predicted the shape of the graph of the number of sources, against source Strength. But the observations showed more faint sources than predicted, indicating that the density sources was higher in the past. This was contrary to the basic assumption of the Steady State theory, that everything was constant in time. For this, and other reasons, the Steady State theory was abandoned.

Another attempt to avoid the universe having a beginning, was the suggestion that there was a previous contracting phase, but because of rotation and local irregularities, the matter would not all fall to the same point. Instead, different parts of the matter would miss each other, and the universe would expand again, with the density remaining finite. Two Russians, Lifshitz and Khalatnikov, actually claimed to have proved that a general contraction without exact symmetry, would always lead to a bounce, with the density remaining finite. This result was very convenient for Marxist Leninist dialectical materialism, because it avoided awkward questions about the creation of the universe. It therefore became an article of faith for Soviet scientists.

When Lifshitz and Khalatnikov published their claim, I was a 21–year-old research student, looking for something to complete my PhD thesis. I didn’t believe their so-called proof, and set out with Roger Penrose to develop new mathematical techniques to study the question. We showed that the universe couldn’t bounce. If Einstein’s General Theory of Relativity is correct, there will be a singularity, a point of infinite density and space-time curvature, where time has a beginning.

Observational evidence to confirm the idea that the universe had a very dense beginning, came in October 1965, a few months after my first singularity result, with the discovery of a faint background of microwaves throughout space. These microwaves are the same as those in your microwave oven, but very much less powerful. They would heat your pizza only to minus 271 point 3 degrees centigrade, not much good for defrosting the pizza, let alone cooking it. You can actually observe these microwaves yourself. Set your television to an empty channel. A few percent of the snow you see on the screen, will be caused by this background of microwaves. The only reasonable interpretation of the background, is that it is radiation left over from an early very hot and dense state. As the universe expanded, the radiation would have cooled until it is just the faint remnant we observe today.

Although the singularity theorems of Penrose and myself, predicted that the universe had a beginning, they didn’t say how it had begun. The equations of General Relativity would break down at the singularity. Thus Einstein’s theory can not predict how the universe will begin, but only how it will evolve once it has begun. There are two attitudes one can take to the results of Penrose and myself. One is to that God chose how the universe began for reasons we could not understand. This was the view of Pope John Paul. At a conference on cosmology in the Vatican, the Pope told the delegates that it was OK to study the universe after it began. but they should not inquire into the beginning itself, because that was the moment of creation, and the work of God. I was glad he didn’t realize I had presented a paper at the conference, suggesting how the universe began. I didn’t fancy the thought of being handed over to the Inquisition, like Galileo.

The other interpretation of our results, which is favored by most scientists, is that it indicates that the General Theory of Relativity, breaks down in the very strong gravitational fields in the early universe. It has to be replaced by a more complete theory.. One would expect this anyway, because General Relativity does not take account of the small scale structure of matter, which is governed by quantum theory. This does not matter normally, because the scale of the universe, is enormous compared to the microscopic scales of quantum theory. But when the universe is the Planck size, a billion trillion trillionth of a centimeter, the two scales are the same, and quantum theory has to be taken into account.

In order to understand the Origin of the universe, we need to combine the General Theory of Relativity, with quantum theory. The best way of doing so, seems to be to use Feynman’s idea of a sum over histories. Richard Feynman was a colorful character, who played the bongo drums in a strip joint in Pasadena, and was a brilliant physicist at the California Institute of Technology. He proposed that a system got from a state A, to a state B, by every possible path or history.

Each path or history, has a certain amplitude or intensity, and the probability of the system going from A- to B, is given by adding up the amplitudes for each path. There will be a history in which the moon is made of blue cheese, but the amplitude is low, which is bad news for mice.

The probability for a state of the universe at the present time, is given by adding up the amplitudes for all the histories that end with that state. But how did the histories start. This is the Origin question in another guise. Does it require a Creator to decree how the universe began. Or is the initial state of the universe, determined by a law of science.

In fact, this question would arise even if the histories of the universe went back to the infinite past. But it is more immediate if the universe began only 15 billion years ago. The problem of what happens at the beginning of time, is a bit like the question of what happened at the edge of the world, when people thought the world was flat. Is the world a flat plate, with the sea pouring over the edge. I have tested this experimentally. I have been round the world, and I have not fallen off.

As we all know, the problem of what happens at the edge of the world, was solved when people realized that the world was not a flat plate, but a curved surface. Time however, seemed to be different. It appeared to be separate from space, and to be like a model railway track. If it had a beginning, there would have to be someone to set the trains going.

Einstein’s General Theory of Relativity, unified time and space as space-time, but time was still different from space, and was like a corridor, which either had a beginning and end, or went on for ever. However, when one combines General Relativity with Quantum Theory, Jim Hartle and I, realized that time can behave like another direction in space under extreme conditions. This means one can get rid of the problem of time having a beginning, in a similar way in which we got rid of the edge of the world. Suppose the beginning of the universe, was like the south pole of the Earth , with degrees of latitude, playing the role of time. The universe would start as a point at the South Pole. As one moves north, the circles of constant latitude, representing the size of the universe, would expand. To ask what happened before the beginning of the universe, would become a meaningless question, because there is nothing south of the South Pole.

Time, as measured in degrees of latitude, would have a beginning at the South Pole, but the South Pole is much like any other point, at least so I have been told. I have been to Antarctica, but not to the South Pole.

The same laws of Nature hold at the South Pole, as in other places. This would remove the age-old objection to the universe having a beginning, that it would be a place where the normal laws broke down. The beginning of the universe, would be governed by the laws of science.

The picture Jim Hartle and I developed, of the spontaneous quantum creation of the universe, would be a bit like the formation of bubbles of steam in boiling water.
The idea is that the most probable histories of the universe, would be like the surfaces of the bubbles. Many small bubbles would appear, and then disappear again. These would correspond to mini universes that would expand, but would collapse again while still of microscopic size. They are possible alternative universes, but they are not of much interest since they do not last long enough to develop galaxies and stars, let alone intelligent life. A few of the little bubbles, however, with grow to a certain size at which they are safe from recollapse. They will continue to expand at an ever increasing rate, and will form the bubbles we see. They will correspond to universes that would start off expanding at an ever increasing rate. This is called inflation, like the way prices go up every year.

The world record for inflation, was in Germany after the First World War. Prices rose by a factor of ten million in a period of 18 months. But that was nothing compared to inflation in the early universe. The universe expanded by a factor of million trillion trillion in a tiny fraction of a second. Unlike inflation in prices, inflation in the early universe was a very good thing. It produced a very large, and uniform universe, just as we observe. However, it would not be completely uniform. In the sum over histories, histories that are very slightly irregular, will have almost as high probabilities as the completely uniform and regular history.. The theory therefore predicts that the early universe is likely to be slightly non-uniform. These irregularities would produce small variations in the intensity of the microwave background from different directions. The microwave background has been observed by the Map satellite, and was found to have exactly the kind of variations predicted. So we know we are on the right lines.

The irregularities in the early universe, will mean that some regions will have slightly higher density than others. The gravitational attraction of the extra density, will slow the expansion of the region, and can eventually cause the region to collapse to form galaxies and stars. So look well at the map of the microwave sky. It is the blue print for all the structure in the universe. We are the product of quantum fluctuations in the very early universe. God really does play dice.

We have made tremendous progress in cosmology in the last hundred years. The General Theory of Relativity, and the discovery of the expansion of the universe, shattered the old picture of an ever existing, and ever lasting universe. Instead, general relativity predicted that the universe, and time itself, would begin in the big bang. It also predicted that time would come to an end in black holes. The discovery of the cosmic microwave background, and observations of black holes, support these conclusions. This is a profound change in our picture of the universe, and of reality itself.

Although the General Theory of Relativity, predicted that the universe must have come from a period of high curvature in the past, it could not predict how the universe would emerge from the big bang. Thus general relativity on its own, can not answer the central question in cosmology, Why is the universe, the way it is. However, if general relativity is combined with quantum theory, it may be possible to predict how the universe would start. It would initially expand at an ever increasing rate. During this so called inflationary period, the marriage of the two theories predicted that small fluctuations would develop, and lead to the formation of galaxies, stars, and all the other structure in the universe. This is confirmed by observations of small non uniformities in the cosmic microwave background, with exactly the predicted properties. So it seems we are on our way to understanding the origin of the universe, though much more work will be needed. A new window on the very early universe, will be opened when we can detect gravitational waves by accurately measuring the distances between space craft. Gravitational waves propagate freely to us from earliest times, unimpeded by any intervening material. By contrast, light is scattered many times by free electrons. The scattering goes on until the electrons freeze out, after 300,000 years.

Despite having had some great successes, not everything is solved. We do not yet have a good theoretical understanding, of the observations that the expansion of the universe, is accelerating again, after a long period of slowing down. Without such an understanding, we can not be sure of the future of the universe. Will it continue to expand forever? Is inflation a law of Nature? Or will the universe eventually collapse again? New observational results, and theoretical advances, are coming in rapidly. Cosmology is a very exciting and active subject. We are getting close to answering the age old questions. Why are we here? Where did we come from?

Thank you for listening to me.

Sorting network

The following is network-sorting algorithm for less than 33 elements.

What is Sorting Network? -> http://en.wikipedia.org/wiki/Sorting_network

List of sorting networks:
From: http://pages.ripco.net/~jgamble/nw.html
Input the number n (maximum 32)
Algorithm choices: “Best”
Click [Take a look] button.


-static const unsigned int network02[][2] = {
- { 0, 1},
-};
-static const unsigned int network03[][2] = {
- { 1, 2},
- { 0, 2},
- { 0, 1},
-};
-static const unsigned int network04[][2] = {
- { 0, 1}, { 2, 3},
- { 0, 2}, { 1, 3},
- { 1, 2},
-};
-static const unsigned int network05[][2] = {
- { 0, 1}, { 3, 4},
- { 2, 4},
- { 2, 3}, { 1, 4},
- { 0, 3},
- { 0, 2}, { 1, 3},
- { 1, 2},
-};
-static const unsigned int network06[][2] = {
- { 1, 2}, { 4, 5},
- { 0, 2}, { 3, 5},
- { 0, 1}, { 3, 4}, { 2, 5},
- { 0, 3}, { 1, 4},
- { 2, 4}, { 1, 3},
- { 2, 3},
-};
-static const unsigned int network07[][2] = {
- { 1, 2}, { 3, 4}, { 5, 6},
- { 0, 2}, { 3, 5}, { 4, 6},
- { 0, 1}, { 4, 5}, { 2, 6},
- { 0, 4}, { 1, 5},
- { 0, 3}, { 2, 5},
- { 1, 3}, { 2, 4},
- { 2, 3},
-};
-static const unsigned int network08[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7},
- { 0, 2}, { 1, 3}, { 4, 6}, { 5, 7},
- { 1, 2}, { 5, 6}, { 0, 4}, { 3, 7},
- { 1, 5}, { 2, 6},
- { 1, 4}, { 3, 6},
- { 2, 4}, { 3, 5},
- { 3, 4},
-};
-static const unsigned int network09[][2] = {
- { 0, 1}, { 3, 4}, { 6, 7},
- { 1, 2}, { 4, 5}, { 7, 8},
- { 0, 1}, { 3, 4}, { 6, 7}, { 2, 5},
- { 0, 3}, { 1, 4}, { 5, 8},
- { 3, 6}, { 4, 7}, { 2, 5},
- { 0, 3}, { 1, 4}, { 5, 7}, { 2, 6},
- { 1, 3}, { 4, 6},
- { 2, 4}, { 5, 6},
- { 2, 3},
-};
-static const unsigned int network10[][2] = {
- { 4, 9}, { 3, 8}, { 2, 7}, { 1, 6}, { 0, 5},
- { 1, 4}, { 6, 9}, { 0, 3}, { 5, 8},
- { 0, 2}, { 3, 6}, { 7, 9},
- { 0, 1}, { 2, 4}, { 5, 7}, { 8, 9},
- { 1, 2}, { 4, 6}, { 7, 8}, { 3, 5},
- { 2, 5}, { 6, 8}, { 1, 3}, { 4, 7},
- { 2, 3}, { 6, 7},
- { 3, 4}, { 5, 6},
- { 4, 5},
-};
-static const unsigned int network11[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
- { 1, 3}, { 5, 7}, { 0, 2}, { 4, 6}, { 8,10},
- { 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 3, 7},
- { 1, 5}, { 6,10}, { 4, 8},
- { 5, 9}, { 2, 6}, { 0, 4}, { 3, 8},
- { 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
- { 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
- { 2, 4}, { 7, 9}, { 5, 6},
- { 3, 4}, { 7, 8},
-};
-static const unsigned int network12[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11},
- { 1, 3}, { 5, 7}, { 9,11}, { 0, 2}, { 4, 6}, { 8,10},
- { 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 7,11},
- { 1, 5}, { 6,10}, { 3, 7}, { 4, 8},
- { 5, 9}, { 2, 6}, { 0, 4}, { 7,11}, { 3, 8},
- { 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
- { 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
- { 2, 4}, { 7, 9}, { 5, 6},
- { 3, 4}, { 7, 8},
-};
-static const unsigned int network13[][2] = {
- { 1, 7}, { 9,11}, { 3, 4}, { 5, 8}, { 0,12}, { 2, 6},
- { 0, 1}, { 2, 3}, { 4, 6}, { 8,11}, { 7,12}, { 5, 9},
- { 0, 2}, { 3, 7}, {10,11}, { 1, 4}, { 6,12},
- { 7, 8}, {11,12}, { 4, 9}, { 6,10},
- { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, { 1, 7},
- { 2, 6}, { 9,11}, { 1, 3}, { 4, 7}, { 8,10}, { 0, 5},
- { 2, 5}, { 6, 8}, { 9,10},
- { 1, 2}, { 3, 5}, { 7, 8}, { 4, 6},
- { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
- { 3, 4}, { 5, 6},
-};
-static const unsigned int network14[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
- { 0, 2}, { 4, 6}, { 8,10}, { 1, 3}, { 5, 7}, { 9,11},
- { 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, { 3, 7},
- { 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13},
- { 5,10}, { 6, 9}, { 3,12}, { 7,11}, { 1, 2}, { 4, 8},
- { 1, 4}, { 7,13}, { 2, 8}, { 5, 6}, { 9,10},
- { 2, 4}, {11,13}, { 3, 8}, { 7,12},
- { 6, 8}, {10,12}, { 3, 5}, { 7, 9},
- { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
- { 6, 7}, { 8, 9},
-};
-static const unsigned int network15[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
- { 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11},
- { 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7},
- { 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14},
- { 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
- { 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
- { 2, 4}, {11,13}, { 3, 8}, { 7,12},
- { 6, 8}, {10,12}, { 3, 5}, { 7, 9},
- { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
- { 6, 7}, { 8, 9},
-};
-static const unsigned int network16[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15},
- { 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11}, {13,15},
- { 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7}, {11,15},
- { 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14}, { 7,15},
- { 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
- { 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
- { 2, 4}, {11,13}, { 3, 8}, { 7,12},
- { 6, 8}, {10,12}, { 3, 5}, { 7, 9},
- { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
- { 6, 7}, { 8, 9},
-};
-static const unsigned int network17[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {15,16},
- { 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {14,16},
- { 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {14,15}, {13,16},
- { 1, 5}, { 2, 6}, {12,15}, {11,16},
- { 1, 4}, { 3, 6}, {12,14}, {13,15}, { 7,16},
- { 2, 4}, { 3, 5}, {13,14}, {10,15},
- { 3, 4}, { 8,13}, { 9,14}, {11,15},
- { 8,12}, { 9,13}, {11,14}, { 6,15},
- { 9,12}, {10,13}, { 5,14}, { 7,15},
- {10,12}, {11,13}, { 0, 9}, { 7,14},
- {11,12}, { 0, 8}, { 1,10}, { 4,13},
- { 1, 9}, { 2,11}, { 3,12}, { 5,13},
- { 1, 8}, { 3,11}, { 2, 9}, { 6,13},
- { 2, 8}, { 3,10}, { 7,13}, { 6,11},
- { 3, 9}, { 5,10}, { 7,12},
- { 3, 8}, { 4, 9}, { 7,11},
- { 4, 8}, { 5, 9}, { 7,10},
- { 5, 8}, { 6, 9},
- { 6, 8}, { 7, 9},
- { 7, 8},
-};
-static const unsigned int network18[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17},
- { 0, 2}, { 1, 3}, { 6, 8}, { 9,11}, {10,12}, {15,17},
- { 1, 2}, { 6, 7}, { 5, 8}, {10,11}, {15,16}, {14,17},
- { 4, 7}, { 3, 8}, {13,16}, {12,17},
- { 4, 6}, { 5, 7}, {13,15}, {14,16}, { 8,17},
- { 5, 6}, { 2, 7}, {14,15}, {11,16},
- { 0, 5}, { 1, 6}, { 3, 7}, { 9,14}, {10,15}, {12,16},
- { 0, 4}, { 1, 5}, { 3, 6}, { 9,13}, {10,14}, {12,15}, { 7,16},
- { 1, 4}, { 2, 5}, {10,13}, {11,14}, { 0, 9}, { 6,15}, { 8,16},
- { 2, 4}, { 3, 5}, {11,13}, {12,14}, { 1,10}, { 7,15},
- { 3, 4}, {12,13}, { 1, 9}, { 2,11}, { 5,14}, { 8,15},
- { 3,12}, { 2, 9}, { 4,13}, { 7,14},
- { 3,11}, { 5,13}, { 8,14},
- { 3,10}, { 6,13},
- { 3, 9}, { 7,13}, { 5,10}, { 6,11},
- { 8,13}, { 4, 9}, { 7,12},
- { 5, 9}, { 8,12}, { 7,11},
- { 8,11}, { 6, 9}, { 7,10},
- { 8,10}, { 7, 9},
- { 8, 9},
-};
-static const unsigned int network19[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {12,13}, {14,15}, {17,18},
- { 0, 2}, { 1, 3}, { 6, 8}, {11,13}, {16,18},
- { 1, 2}, { 6, 7}, { 5, 8}, {11,12}, {10,13}, {16,17}, {15,18},
- { 4, 7}, { 3, 8}, { 9,12}, {14,17}, {13,18},
- { 4, 6}, { 5, 7}, { 9,11}, {10,12}, {14,16}, {15,17}, { 8,18},
- { 5, 6}, { 2, 7}, {10,11}, {15,16}, { 9,14}, {12,17},
- { 0, 5}, { 1, 6}, { 3, 7}, {10,15}, {11,16}, {13,17},
- { 0, 4}, { 1, 5}, { 3, 6}, {10,14}, {12,16}, { 7,17},
- { 1, 4}, { 2, 5}, {13,16}, {11,14}, {12,15}, { 0,10}, { 8,17},
- { 2, 4}, { 3, 5}, {13,15}, {12,14}, { 0, 9}, { 1,11}, { 6,16},
- { 3, 4}, {13,14}, { 1,10}, { 2,12}, { 5,15}, { 7,16},
- { 1, 9}, { 3,13}, { 2,10}, { 4,14}, { 8,16}, { 7,15},
- { 3,12}, { 2, 9}, { 5,14}, { 8,15},
- { 3,11}, { 6,14},
- { 3,10}, { 7,14}, { 6,11},
- { 3, 9}, { 8,14}, { 5,10}, { 7,12},
- { 4, 9}, { 8,13}, { 7,11},
- { 5, 9}, { 8,12}, { 7,10},
- { 8,11}, { 6, 9},
- { 8,10}, { 7, 9},
- { 8, 9},
-};
-static const unsigned int network20[][2] = {
- { 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {15,16}, {18,19},
- { 2, 4}, { 7, 9}, {12,14}, {17,19},
- { 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {17,18}, {16,19},
- { 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {14,19},
- { 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {15,17}, {16,18}, { 9,19},
- { 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {16,17}, {10,15}, {13,18},
- { 1, 6}, { 2, 7}, { 4, 8}, {11,16}, {12,17}, {14,18}, { 0,10},
- { 1, 5}, { 3, 7}, {11,15}, {13,17}, { 8,18},
- { 4, 7}, { 2, 5}, { 3, 6}, {14,17}, {12,15}, {13,16}, { 1,11}, { 9,18},
- { 4, 6}, { 3, 5}, {14,16}, {13,15}, { 1,10}, { 2,12}, { 7,17},
- { 4, 5}, {14,15}, { 3,13}, { 2,10}, { 6,16}, { 8,17},
- { 4,14}, { 3,12}, { 5,15}, { 9,17}, { 8,16},
- { 4,13}, { 3,11}, { 6,15}, { 9,16},
- { 4,12}, { 3,10}, { 7,15},
- { 4,11}, { 8,15}, { 7,12},
- { 4,10}, { 9,15}, { 6,11}, { 8,13},
- { 5,10}, { 9,14}, { 8,12},
- { 6,10}, { 9,13}, { 8,11},
- { 9,12}, { 7,10},
- { 9,11}, { 8,10},
- { 9,10},
-};
-static const unsigned int network21[][2] = {
- { 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {16,17}, {19,20},
- { 2, 4}, { 7, 9}, {12,14}, {15,17}, {18,20},
- { 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {15,16}, {18,19}, {17,20},
- { 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {16,19}, {14,20},
- { 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {17,19}, {16,18}, { 9,20},
- { 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {17,18}, {10,16}, {13,19},
- { 1, 6}, { 2, 7}, { 4, 8}, {10,15}, {11,17}, {12,18}, {14,19},
- { 1, 5}, { 3, 7}, {11,16}, {13,18}, { 8,19},
- { 4, 7}, { 2, 5}, { 3, 6}, {11,15}, {14,18}, {13,16}, { 9,19},
- { 4, 6}, { 3, 5}, {12,15}, {14,17}, { 0,11}, { 7,18},
- { 4, 5}, {14,16}, {13,15}, { 0,10}, { 1,12}, { 6,17}, { 8,18},
- {14,15}, { 1,11}, { 2,13}, { 5,16}, { 9,18}, { 8,17},
- { 1,10}, { 3,14}, { 4,15}, { 6,16}, { 9,17},
- { 4,14}, { 3,13}, { 2,10}, { 7,16},
- { 4,13}, { 3,11}, { 8,16},
- { 4,12}, { 3,10}, { 9,16}, { 7,13}, { 8,14},
- { 4,11}, { 6,12}, { 9,15}, { 8,13},
- { 4,10}, { 5,11}, { 9,14},
- { 5,10}, { 6,11}, { 9,13},
- { 6,10}, { 8,11}, { 9,12},
- { 7,10}, { 9,11},
- { 8,10},
- { 9,10},
-};
-static const unsigned int network22[][2] = {
- { 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21},
- { 2, 4}, { 5, 7}, { 8,10}, {13,15}, {16,18}, {19,21},
- { 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {13,14}, {12,15}, {16,17}, {19,20}, {18,21},
- { 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {16,19}, {17,20}, {15,21},
- { 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {11,13}, {12,14}, {18,20}, {17,19}, {10,21},
- { 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {12,13}, {18,19}, {11,17}, {14,20},
- { 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {11,16}, {12,18}, {13,19}, {15,20},
- { 1, 6}, { 3, 8}, {12,17}, {14,19}, { 0,11}, { 9,20},
- { 1, 5}, { 4, 8}, { 3, 6}, {12,16}, {15,19}, {14,17}, {10,20},
- { 2, 5}, { 4, 7}, {13,16}, {15,18}, { 1,12}, { 8,19},
- { 4, 6}, { 3, 5}, {15,17}, {14,16}, { 1,11}, { 2,13}, { 7,18}, { 9,19},
- { 4, 5}, {15,16}, { 3,14}, { 2,11}, { 6,17}, {10,19},
- { 4,15}, { 3,13}, { 5,16}, { 7,17}, {10,18},
- { 4,14}, { 3,12}, { 6,16}, { 9,17},
- { 4,13}, { 3,11}, { 7,16}, {10,17},
- { 4,12}, { 8,16}, { 7,13},
- { 4,11}, { 9,16}, { 6,12}, { 8,14},
- {10,16}, { 5,11}, { 7,12}, { 9,15},
- { 6,11}, {10,15}, { 9,14},
- { 7,11}, {10,14}, { 9,12},
- { 8,11}, {10,13},
- {10,12}, { 9,11},
- {10,11},
-};
-static const unsigned int network23[][2] = {
- { 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {12,13}, {15,16}, {18,19}, {21,22},
- { 2, 4}, { 5, 7}, { 8,10}, {11,13}, {14,16}, {17,19}, {20,22},
- { 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {11,12}, {14,15}, {13,16}, {17,18}, {20,21}, {19,22},
- { 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {12,15}, {17,20}, {18,21}, {16,22},
- { 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {13,15}, {12,14}, {19,21}, {18,20}, {11,17}, {10,22},
- { 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {13,14}, {19,20}, {12,18}, {15,21},
- { 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {13,19}, {12,17}, {14,20}, {16,21},
- { 1, 6}, { 3, 8}, {13,18}, {15,20}, { 0,12}, { 9,21},
- { 1, 5}, { 4, 8}, { 3, 6}, {13,17}, {16,20}, {15,18}, { 0,11}, {10,21},
- { 2, 5}, { 4, 7}, {14,17}, {16,19}, { 1,13}, { 8,20},
- { 4, 6}, { 3, 5}, {16,18}, {15,17}, { 1,12}, { 2,14}, { 7,19}, { 9,20},
- { 4, 5}, {16,17}, { 1,11}, { 3,15}, { 6,18}, {10,20},
- { 4,16}, { 3,14}, { 2,11}, { 5,17}, { 7,18}, {10,19},
- { 4,15}, { 3,12}, { 6,17}, { 9,18},
- { 4,14}, { 3,11}, { 7,17}, {10,18},
- { 4,13}, { 8,17},
- { 4,12}, { 9,17}, { 7,13}, { 8,14},
- { 4,11}, {10,17}, { 6,12}, { 9,15},
- { 5,11}, { 7,12}, {10,16}, { 9,14},
- { 6,11}, {10,15}, { 9,12},
- { 7,11}, {10,14},
- { 8,11}, {10,13},
- {10,12}, { 9,11},
- {10,11},
-};
-static const unsigned int network24[][2] = {
- { 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {22,23},
- { 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23},
- { 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {21,22}, {20,23},
- { 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,21}, {19,22}, {17,23},
- { 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {20,22}, {19,21}, {12,18}, {11,23},
- { 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {20,21}, {13,19}, {16,22}, { 0,12},
- { 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {14,20}, {13,18}, {15,21}, {17,22},
- { 2, 7}, { 4, 9}, {14,19}, {16,21}, { 1,13}, {10,22},
- { 2, 6}, { 5, 9}, { 4, 7}, {14,18}, {17,21}, {16,19}, { 1,12}, {11,22},
- { 3, 6}, { 5, 8}, {15,18}, {17,20}, { 2,14}, { 9,21},
- { 5, 7}, { 4, 6}, {17,19}, {16,18}, { 2,13}, { 3,15}, { 8,20}, {10,21},
- { 5, 6}, {17,18}, { 2,12}, { 4,16}, { 7,19}, {11,21},
- { 5,17}, { 4,15}, { 3,12}, { 6,18}, { 8,19}, {11,20},
- { 5,16}, { 4,13}, { 7,18}, {10,19},
- { 5,15}, { 4,12}, { 8,18}, {11,19},
- { 5,14}, { 9,18},
- { 5,13}, {10,18}, { 8,14}, { 9,15},
- { 5,12}, {11,18}, { 7,13}, {10,16},
- { 6,12}, { 8,13}, {11,17}, {10,15},
- { 7,12}, {11,16}, {10,13},
- { 8,12}, {11,15},
- { 9,12}, {11,14},
- {11,13}, {10,12},
- {11,12},
-};
-static const unsigned int network25[][2] = {
- { 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {21,22}, {23,24},
- { 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23}, {22,24},
- { 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {22,23}, {20,24},
- { 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,22}, {19,23}, {17,24},
- { 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {18,21}, {20,23}, {11,24},
- { 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {19,21}, {20,22}, {16,23},
- { 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {20,21}, {12,19}, {15,22}, {17,23},
- { 2, 7}, { 4, 9}, {12,18}, {13,20}, {14,21}, {16,22}, {10,23},
- { 2, 6}, { 5, 9}, { 4, 7}, {14,20}, {13,18}, {17,22}, {11,23},
- { 3, 6}, { 5, 8}, {14,19}, {16,20}, {17,21}, { 0,13}, { 9,22},
- { 5, 7}, { 4, 6}, {14,18}, {15,19}, {17,20}, { 0,12}, { 8,21}, {10,22},
- { 5, 6}, {15,18}, {17,19}, { 1,14}, { 7,20}, {11,22},
- {16,18}, { 2,15}, { 1,12}, { 6,19}, { 8,20}, {11,21},
- {17,18}, { 2,14}, { 3,16}, { 7,19}, {10,20},
- { 2,13}, { 4,17}, { 5,18}, { 8,19}, {11,20},
- { 2,12}, { 5,17}, { 4,16}, { 3,13}, { 9,19},
- { 5,16}, { 3,12}, { 4,14}, {10,19},
- { 5,15}, { 4,12}, {11,19}, { 9,16}, {10,17},
- { 5,14}, { 8,15}, {11,18}, {10,16},
- { 5,13}, { 7,14}, {11,17},
- { 5,12}, { 6,13}, { 8,14}, {11,16},
- { 6,12}, { 8,13}, {10,14}, {11,15},
- { 7,12}, { 9,13}, {11,14},
- { 8,12}, {11,13},
- { 9,12},
- {10,12},
- {11,12},
-};
-static const unsigned int network26[][2] = {
- { 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21}, {22,23}, {24,25},
- { 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {19,21}, {22,24}, {23,25},
- { 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {16,17}, {15,18}, {19,20}, {23,24}, {21,25},
- { 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,16}, {14,17}, {19,23}, {20,24}, {18,25},
- { 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {15,17}, {14,16}, {19,22}, {21,24}, {12,25},
- { 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {15,16}, {20,22}, {21,23}, {17,24},
- { 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {21,22}, {13,20}, {16,23}, {18,24},
- { 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {13,19}, {14,21}, {15,22}, {17,23}, {11,24},
- { 2, 8}, { 1, 6}, { 5,10}, {15,21}, {14,19}, {18,23}, { 0,13}, {12,24},
- { 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {17,21}, {18,22}, { 1,14}, {10,23},
- { 2, 6}, { 3, 7}, { 5, 8}, {15,19}, {16,20}, {18,21}, { 1,13}, { 9,22}, {12,23},
- { 3, 6}, { 5, 7}, {16,19}, {18,20}, { 2,15}, { 8,21}, {10,22},
- { 4, 6}, {17,19}, { 2,14}, { 3,16}, { 7,20}, {11,22},
- { 5, 6}, {18,19}, { 2,13}, { 4,17}, { 8,20}, {12,22}, {11,21},
- { 5,18}, { 4,16}, { 3,13}, { 6,19}, {10,20}, {12,21},
- { 5,17}, { 4,14}, { 7,19}, {12,20},
- { 5,16}, { 4,13}, { 8,19},
- { 5,15}, { 9,19},
- { 5,14}, {10,19}, { 8,15}, { 9,16},
- { 5,13}, {11,19}, { 7,14}, {10,17},
- {12,19}, { 6,13}, { 8,14}, {10,16}, {11,18},
- { 7,13}, {12,18}, {11,16}, {10,14},
- { 8,13}, {12,17}, {11,15},
- {12,16}, { 9,13},
- {10,13}, {12,15},
- {11,13}, {12,14},
- {12,13},
-};
-static const unsigned int network27[][2] = {
- { 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {16,17}, {18,19}, {21,22}, {23,24}, {25,26},
- { 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {17,19}, {20,22}, {23,25}, {24,26},
- { 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {17,18}, {15,19}, {20,21}, {24,25}, {22,26},
- { 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,17}, {14,18}, {20,24}, {21,25}, {19,26},
- { 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {13,16}, {15,18}, {20,23}, {22,25}, {12,26},
- { 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {14,16}, {15,17}, {21,23}, {22,24}, {13,20}, {18,25},
- { 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {15,16}, {22,23}, {14,21}, {17,24}, {19,25},
- { 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {15,22}, {14,20}, {16,23}, {19,24}, {11,25},
- { 2, 8}, { 1, 6}, { 5,10}, {15,21}, {17,23}, { 0,14}, {12,25},
- { 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {18,23}, {17,21}, { 0,13}, {10,24},
- { 2, 6}, { 3, 7}, { 5, 8}, {19,23}, {16,20}, {18,22}, { 1,15}, {12,24},
- { 3, 6}, { 5, 7}, {17,20}, {19,22}, { 2,16}, { 1,13}, { 9,23},
- { 4, 6}, {18,20}, {19,21}, { 2,15}, { 3,17}, { 8,22}, {10,23},
- { 5, 6}, {19,20}, { 2,14}, { 4,18}, { 7,21}, {11,23},
- { 2,13}, { 5,19}, { 4,17}, { 3,14}, { 6,20}, { 8,21}, {12,23}, {11,22},
- { 5,18}, { 3,13}, { 4,15}, { 7,20}, {10,21}, {12,22},
- { 5,17}, { 4,13}, { 8,20}, {12,21},
- { 5,16}, { 9,20},
- { 5,15}, {10,20}, { 9,16},
- { 5,14}, {11,20}, { 8,15}, {10,17},
- { 5,13}, {12,20}, { 7,14}, {10,16}, {11,18},
- { 6,13}, { 8,14}, {12,19}, {11,16},
- { 7,13}, {12,18}, {10,14}, {11,15},
- { 8,13}, {12,17},
- {12,16}, { 9,13},
- {10,13}, {12,15},
- {11,13}, {12,14},
- {12,13},
-};
-static const unsigned int network28[][2] = {
- { 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {22,23}, {24,25}, {26,27},
- { 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {24,26}, {25,27},
- { 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {21,22}, {25,26}, {23,27},
- { 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {21,25}, {22,26}, {20,27},
- { 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {21,24}, {23,26}, {13,27},
- { 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {22,24}, {23,25}, {14,21}, {19,26},
- { 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {23,24}, {15,22}, {18,25}, {20,26}, { 0,14},
- { 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,23}, {15,21}, {17,24}, {20,25}, {12,26},
- { 2, 8}, { 4,10}, {16,22}, {18,24}, { 1,15}, {11,25}, {13,26},
- { 2, 7}, { 5,10}, { 4, 8}, {16,21}, {19,24}, {18,22}, { 1,14}, {13,25},
- { 6,10}, { 3, 7}, { 5, 9}, {20,24}, {17,21}, {19,23}, { 2,16},
- { 4, 7}, { 6, 9}, {18,21}, {20,23}, { 2,15}, { 3,17}, {10,24},
- { 5, 7}, { 6, 8}, {19,21}, {20,22}, { 2,14}, { 4,18}, { 9,23}, {11,24},
- { 6, 7}, {20,21}, { 4,17}, { 5,19}, { 3,14}, { 8,22}, {12,24},
- { 6,20}, { 5,17}, { 4,15}, { 7,21}, { 9,22}, {13,24}, {12,23},
- { 6,19}, { 4,14}, { 5,16}, { 8,21}, {11,22}, {13,23},
- { 6,18}, { 5,14}, { 9,21}, {13,22},
- { 6,17}, {10,21},
- { 6,16}, {11,21}, {10,17},
- { 6,15}, {12,21}, { 9,16}, {11,18},
- { 6,14}, {13,21}, { 8,15}, {11,17}, {12,19},
- { 7,14}, { 9,15}, {13,20}, {12,17},
- { 8,14}, {13,19}, {11,15}, {12,16},
- { 9,14}, {13,18},
- {13,17}, {10,14},
- {11,14}, {13,16},
- {12,14}, {13,15},
- {13,14},
-};
-static const unsigned int network29[][2] = {
- { 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28},
- { 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {22,24}, {25,27}, {26,28},
- { 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {22,23}, {26,27}, {21,25}, {24,28},
- { 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {22,26}, {23,27}, {20,28},
- { 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {22,25}, {24,27}, {13,28},
- { 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {23,25}, {24,26}, {14,22}, {19,27},
- { 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {24,25}, {14,21}, {15,23}, {18,26}, {20,27},
- { 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,24}, {15,21}, {17,25}, {20,26}, {12,27},
- { 2, 8}, { 4,10}, {16,23}, {18,25}, { 0,15}, {11,26}, {13,27},
- { 2, 7}, { 5,10}, { 4, 8}, {16,22}, {19,25}, { 0,14}, {13,26},
- { 6,10}, { 3, 7}, { 5, 9}, {16,21}, {20,25}, {18,22}, {19,23},
- { 4, 7}, { 6, 9}, {17,21}, {20,24}, { 1,16}, {10,25},
- { 5, 7}, { 6, 8}, {18,21}, {20,23}, { 2,17}, { 1,14}, { 9,24}, {11,25},
- { 6, 7}, {19,21}, {20,22}, { 2,16}, { 3,18}, { 8,23}, {12,25},
- {20,21}, { 2,15}, { 4,19}, { 7,22}, { 9,23}, {13,25}, {12,24},
- { 2,14}, { 4,18}, { 5,20}, { 6,21}, { 8,22}, {11,23}, {13,24},
- { 6,20}, { 5,18}, { 3,14}, { 4,15}, { 9,22}, {13,23},
- { 6,19}, { 4,14}, { 5,16}, {10,22},
- { 6,18}, { 5,14}, {11,22},
- { 6,17}, {12,22}, {10,18}, {11,19},
- { 6,16}, {13,22}, { 9,17}, {11,18}, {12,20},
- { 6,15}, { 8,16}, {13,21}, {12,18},
- { 6,14}, { 7,15}, { 9,16}, {13,20},
- { 7,14}, { 9,15}, {13,19}, {12,16},
- { 8,14}, {13,18}, {11,15},
- { 9,14}, {13,17},
- {10,14}, {13,16},
- {11,14}, {13,15},
- {12,14},
- {13,14},
-};
-static const unsigned int network30[][2] = {
- { 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29},
- { 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {18,20}, {19,21}, {22,24}, {23,25}, {26,28}, {27,29},
- { 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {15,16}, {19,20}, {17,21}, {23,24}, {27,28}, {22,26}, {25,29},
- { 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {15,19}, {16,20}, {23,27}, {24,28}, {21,29},
- { 0, 3}, { 2, 5}, { 8,11}, {10,13}, {15,18}, {17,20}, {23,26}, {25,28}, {14,29},
- { 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {16,18}, {17,19}, {24,26}, {25,27}, {15,23}, {20,28},
- { 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {17,18}, {25,26}, {15,22}, {16,24}, {19,27}, {21,28},
- { 2,10}, { 1, 7}, { 3,11}, { 6,12}, {17,25}, {16,22}, {18,26}, {21,27}, { 0,15}, {13,28},
- { 2, 9}, { 4,11}, {17,24}, {19,26}, { 1,16}, {12,27}, {14,28},
- { 2, 8}, { 5,11}, {17,23}, {20,26}, { 1,15}, {14,27},
- { 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {17,22}, {21,26}, {19,23}, {20,24},
- { 3, 7}, { 6,10}, {18,22}, {21,25}, { 2,17}, {11,26},
- { 4, 7}, { 6, 9}, {19,22}, {21,24}, { 2,16}, { 3,18}, {10,25}, {12,26},
- { 5, 7}, { 6, 8}, {20,22}, {21,23}, { 2,15}, { 4,19}, { 9,24}, {13,26},
- { 6, 7}, {21,22}, { 4,18}, { 5,20}, { 3,15}, { 8,23}, {10,24}, {14,26},
- { 6,21}, { 5,18}, { 4,16}, { 7,22}, {10,23}, {13,24}, {14,25},
- { 6,20}, { 4,15}, { 5,17}, { 8,22}, {12,23}, {14,24},
- { 6,19}, { 5,15}, { 9,22}, {14,23},
- { 6,18}, {10,22},
- { 6,17}, {11,22}, {10,18},
- { 6,16}, {12,22}, { 9,17}, {11,19},
- { 6,15}, {13,22}, { 8,16}, {10,17}, {12,20},
- {14,22}, { 7,15}, {10,16}, {12,19}, {13,21},
- { 8,15}, {14,21}, {13,19}, {12,16},
- { 9,15}, {14,20}, {13,17},
- {10,15}, {14,19},
- {11,15}, {14,18},
- {12,15}, {14,17},
- {13,15}, {14,16},
- {14,15},
-};
-static const unsigned int network31[][2] = {
- { 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28}, {29,30},
- { 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {16,18}, {19,21}, {20,22}, {23,25}, {24,26}, {27,29}, {28,30},
- { 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {16,17}, {20,21}, {15,19}, {18,22}, {24,25}, {28,29}, {23,27}, {26,30},
- { 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {16,20}, {17,21}, {24,28}, {25,29}, {15,23}, {22,30},
- { 0, 3}, { 2, 5}, { 8,11}, {10,13}, {16,19}, {18,21}, {24,27}, {26,29}, {14,30},
- { 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {17,19}, {18,20}, {25,27}, {26,28}, {16,24}, {21,29},
- { 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {18,19}, {26,27}, {16,23}, {17,25}, {20,28}, {22,29},
- { 2,10}, { 1, 7}, { 3,11}, { 6,12}, {18,26}, {17,23}, {19,27}, {22,28}, { 0,16}, {13,29},
- { 2, 9}, { 4,11}, {18,25}, {20,27}, { 0,15}, { 1,17}, {12,28}, {14,29},
- { 2, 8}, { 5,11}, {18,24}, {21,27}, { 1,15}, {14,28},
- { 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {18,23}, {22,27}, {20,24}, {21,25},
- { 3, 7}, { 6,10}, {19,23}, {22,26}, { 2,18}, {11,27},
- { 4, 7}, { 6, 9}, {20,23}, {22,25}, { 2,17}, { 3,19}, {10,26}, {12,27},
- { 5, 7}, { 6, 8}, {21,23}, {22,24}, { 2,16}, { 4,20}, { 9,25}, {13,27},
- { 6, 7}, {22,23}, { 2,15}, { 4,19}, { 5,21}, { 8,24}, {10,25}, {14,27},
- { 6,22}, { 5,19}, { 3,15}, { 4,16}, { 7,23}, {10,24}, {13,25}, {14,26},
- { 6,21}, { 4,15}, { 5,17}, { 8,23}, {12,24}, {14,25},
- { 6,20}, { 5,15}, { 9,23}, {14,24},
- { 6,19}, {10,23},
- { 6,18}, {11,23},
- { 6,17}, {12,23}, {10,18}, {11,19},
- { 6,16}, {13,23}, { 9,17}, {12,20},
- { 6,15}, {14,23}, { 8,16}, {10,17}, {12,19}, {13,21},
- { 7,15}, {10,16}, {14,22}, {13,19},
- { 8,15}, {14,21}, {12,16}, {13,17},
- { 9,15}, {14,20},
- {10,15}, {14,19},
- {11,15}, {14,18},
- {12,15}, {14,17},
- {13,15}, {14,16},
- {14,15},
-};
-static const unsigned int network32[][2] = {
- { 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29}, {30,31},
- { 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {12,14}, {13,15}, {16,18}, {17,19}, {20,22}, {21,23}, {24,26}, {25,27}, {28,30}, {29,31},
- { 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {13,14}, { 8,12}, {11,15}, {17,18}, {21,22}, {16,20}, {19,23}, {25,26}, {29,30}, {24,28}, {27,31},
- { 1, 5}, { 2, 6}, { 9,13}, {10,14}, { 0, 8}, { 7,15}, {17,21}, {18,22}, {25,29}, {26,30}, {16,24}, {23,31},
- { 1, 4}, { 3, 6}, { 9,12}, {11,14}, {17,20}, {19,22}, {25,28}, {27,30}, { 0,16}, {15,31},
- { 2, 4}, { 3, 5}, {10,12}, {11,13}, { 1, 9}, { 6,14}, {18,20}, {19,21}, {26,28}, {27,29}, {17,25}, {22,30},
- { 3, 4}, {11,12}, { 1, 8}, { 2,10}, { 5,13}, { 7,14}, {19,20}, {27,28}, {17,24}, {18,26}, {21,29}, {23,30},
- { 3,11}, { 2, 8}, { 4,12}, { 7,13}, {19,27}, {18,24}, {20,28}, {23,29}, { 1,17}, {14,30},
- { 3,10}, { 5,12}, {19,26}, {21,28}, { 1,16}, { 2,18}, {13,29}, {15,30},
- { 3, 9}, { 6,12}, {19,25}, {22,28}, { 2,16}, {15,29},
- { 3, 8}, { 7,12}, { 5, 9}, { 6,10}, {19,24}, {23,28}, {21,25}, {22,26},
- { 4, 8}, { 7,11}, {20,24}, {23,27}, { 3,19}, {12,28},
- { 5, 8}, { 7,10}, {21,24}, {23,26}, { 3,18}, { 4,20}, {11,27}, {13,28},
- { 6, 8}, { 7, 9}, {22,24}, {23,25}, { 3,17}, { 5,21}, {10,26}, {14,28},
- { 7, 8}, {23,24}, { 3,16}, { 5,20}, { 6,22}, { 9,25}, {11,26}, {15,28},
- { 7,23}, { 6,20}, { 4,16}, { 5,17}, { 8,24}, {11,25}, {14,26}, {15,27},
- { 7,22}, { 5,16}, { 6,18}, { 9,24}, {13,25}, {15,26},
- { 7,21}, { 6,16}, {10,24}, {15,25},
- { 7,20}, {11,24},
- { 7,19}, {12,24},
- { 7,18}, {13,24}, {11,19}, {12,20},
- { 7,17}, {14,24}, {10,18}, {13,21},
- { 7,16}, {15,24}, { 9,17}, {11,18}, {13,20}, {14,22},
- { 8,16}, {11,17}, {15,23}, {14,20},
- { 9,16}, {15,22}, {13,17}, {14,18},
- {10,16}, {15,21},
- {11,16}, {15,20},
- {12,16}, {15,19},
- {13,16}, {15,18},
- {14,16}, {15,17},
- {15,16},
-};
-
-typedef struct {
- const unsigned int comparators;
- const unsigned int (*pNetwork)[2];
-} Network;
-
-#define elemof(ary) (sizeof(ary)/sizeof(ary[0]))
-#define NETWORK(n) {elemof(network##n), network##n}
-
-static const Network networks[] = {
- {0, NULL},
- {0, NULL},
- NETWORK(02),
- NETWORK(03),
- NETWORK(04),
- NETWORK(05),
- NETWORK(06),
- NETWORK(07),
- NETWORK(08),
- NETWORK(09),
- NETWORK(10),
- NETWORK(11),
- NETWORK(12),
- NETWORK(13),
- NETWORK(14),
- NETWORK(15),
- NETWORK(16),
- NETWORK(17),
- NETWORK(18),
- NETWORK(19),
- NETWORK(20),
- NETWORK(21),
- NETWORK(22),
- NETWORK(23),
- NETWORK(24),
- NETWORK(25),
- NETWORK(26),
- NETWORK(27),
- NETWORK(28),
- NETWORK(29),
- NETWORK(30),
- NETWORK(31),
- NETWORK(32),
-};
-#undef NETWORK
-
-static const size_t cutoff = elemof(networks);
-
-template < typename Elem &gt
-inline void shortSort(Elem *p, size_t n) {
- const unsigned int (* pNetwork)[2], (* pEnd)[2];
- Elem *p0, *p1;
- assert(n < elemof(networks));
- pNetwork = networks[n].pNetwork;
- pEnd = pNetwork + networks[n].comparators;
- for(; pNetwork < pEnd; pNetwork++) {
- p0 = p + (*pNetwork)[0];
- p1 = p + (*pNetwork)[1];
- if(*p1 < *p0) exchange(p0, p1);
- }
-}

About component assembling

User scenario of the component user (unnecessary be an end user without explicitly mention)

A. Background

We shall provide the library as a toolkit. The toolkits contains a collection of tools or sub-toolkits or item references. Each tool is an independent component, which has self-support informations.

The organization of the toolkits is a tree. Each item in a toolkits has a identity called tool-tag. We tag an item when we add it into a toolkit.

Each tool, as a component, has 2 sets of connector: provided connectors and required connectors.

Each connector has an interface specification as its type. A required connector can accept a provided connector if the type of the later can satisfy the type of the former.

If and only if the type D is a sub-type of type B, then D can satisfy B. The relationship between types and their identities are organized by the interface packages.

Interface packages are released before the components which implement them. A interface package organizes the hierarchy of the interfaces through their identities. The interface packages will not exposed directly to the user. We shall use them just for checking the legality of the assembly of the connectors.

Actually, the interface package is not for providing the interface specification information such as the function signatures, but for providing the list of identities of the base interfaces which this interface inherits from. And also provide the service for checking if one interface can satisfy another.

In the following discussion, we use following conventions:
“{SomeInterface}” : an interface called “SomeInterface”
“[SomeComponent]” : a component called “SomeComponent”
“{A} <: {B}" : {A} is a subtype of {B}
“x: [C]” : x is an object instance of [C]
“x.someMember” : a member of object x called “someMember”
“x := y” : assign x with the value y

B.User scenario

——————-

1. User reads the manual of the toolkit to learn the following information:
__1.the list of the tools, the literal name of the tool-tags.
__2.for each tool, the function include provided services and required services, the connectors and their identities, the interface specification of the connectors.

2. User use tool-tags to select the tools needed. Say [SecSha1] (a software {Sha1} implementation) & [SecHmac] (a software {Hmac} implementation).
__[SwSha1] has
____provided service connectors:
______sha1: {Sha1}, where {Sha1} derives from {Hash}
____required service connectors:
______none.
__[SwHmac] has
____provided service connectors:
______setKey: {HmacSetKey}, where {HmacSetKey} derives from {SetKey}
______hmac: {Hmac}, where {Hmac} derives from {Hash}
____required service connectors:
______hash: {Hash}

3. User create object instance from the tool-components selected. Say:
__swSha1: [SwSha1]
__swHmac: [SwHmac]

4. User assembles the objects through connecting their connectors together. During connecting, the interface matching will be checked.
__connect(swHmac.hash, swSha1.sha1)

or user can assemble the objects with a composite object
__swHmacSha1: [LegoComposite]
__enum Id {HMAC, SHA1};
__swHmacSha1.addComponent(HMAC, swHmac);
__swHmacSha1.addComponent(SHA1, swHmac);
__swHmacSha1.connect(
____swHmacSha1.component(HMAC).hash,
____swHmacSha1.component(SHA1).sha1
__)

5. User setup the objects, this step can also be done before assembling the objects.

user can use setKey method
__hmacKey: [SizedOctetString]
__swHmac.setKey(hmacKey)

or user can use common parameter binding
__hmacKey: [SizedOctetString]
__hmacKeyValue: [valueTree]
__hmacKeyValue.addNode(hmacKey)
__swHmac.bind(hmacKeyValue)

6. Now the state of the object is ready to provide the
——————-

List of Sorting Networks

What is Sorting Network? -> http://en.wikipedia.org/wiki/Sorting_network

From: http://pages.ripco.net/~jgamble/nw.html
Input the number n (maximum 32)
Algorithm choices: “Best”
Click [Take a look] button.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
n: comparators, parallels
1: 0, 0

2: 1, 1
[[0,1]]

3: 3, 3
[[1,2]]
[[0,2]]
[[0,1]]

4: 5, 3
[[0,1],[2,3]]
[[0,2],[1,3]]
[[1,2]]

5: 9, 6
[[0,1],[3,4]]
[[2,4]]
[[2,3],[1,4]]
[[0,3]]
[[0,2],[1,3]]
[[1,2]]

6: 12, 6
[[1,2],[4,5]]
[[0,2],[3,5]]
[[0,1],[3,4],[2,5]]
[[0,3],[1,4]]
[[2,4],[1,3]]
[[2,3]]

7: 16, 7
[[1,2],[3,4],[5,6]]
[[0,2],[3,5],[4,6]]
[[0,1],[4,5],[2,6]]
[[0,4],[1,5]]
[[0,3],[2,5]]
[[1,3],[2,4]]
[[2,3]]

8: 19, 7
[[0,1],[2,3],[4,5],[6,7]]
[[0,2],[1,3],[4,6],[5,7]]
[[1,2],[5,6],[0,4],[3,7]]
[[1,5],[2,6]]
[[1,4],[3,6]]
[[2,4],[3,5]]
[[3,4]]

9: 25, 9
[[0,1],[3,4],[6,7]]
[[1,2],[4,5],[7,8]]
[[0,1],[3,4],[6,7],[2,5]]
[[0,3],[1,4],[5,8]]
[[3,6],[4,7],[2,5]]
[[0,3],[1,4],[5,7],[2,6]]
[[1,3],[4,6]]
[[2,4],[5,6]]
[[2,3]]

10: 29, 9
[[4,9],[3,8],[2,7],[1,6],[0,5]]
[[1,4],[6,9],[0,3],[5,8]]
[[0,2],[3,6],[7,9]]
[[0,1],[2,4],[5,7],[8,9]]
[[1,2],[4,6],[7,8],[3,5]]
[[2,5],[6,8],[1,3],[4,7]]
[[2,3],[6,7]]
[[3,4],[5,6]]
[[4,5]]

11: 35, 9
[[0,1],[2,3],[4,5],[6,7],[8,9]]
[[1,3],[5,7],[0,2],[4,6],[8,10]]
[[1,2],[5,6],[9,10],[0,4],[3,7]]
[[1,5],[6,10],[4,8]]
[[5,9],[2,6],[0,4],[3,8]]
[[1,5],[6,10],[2,3],[8,9]]
[[1,4],[7,10],[3,5],[6,8]]
[[2,4],[7,9],[5,6]]
[[3,4],[7,8]]

12: 39, 9
[[0,1],[2,3],[4,5],[6,7],[8,9],[10,11]]
[[1,3],[5,7],[9,11],[0,2],[4,6],[8,10]]
[[1,2],[5,6],[9,10],[0,4],[7,11]]
[[1,5],[6,10],[3,7],[4,8]]
[[5,9],[2,6],[0,4],[7,11],[3,8]]
[[1,5],[6,10],[2,3],[8,9]]
[[1,4],[7,10],[3,5],[6,8]]
[[2,4],[7,9],[5,6]]
[[3,4],[7,8]]

13: 45, 10
[[1,7],[9,11],[3,4],[5,8],[0,12],[2,6]]
[[0,1],[2,3],[4,6],[8,11],[7,12],[5,9]]
[[0,2],[3,7],[10,11],[1,4],[6,12]]
[[7,8],[11,12],[4,9],[6,10]]
[[3,4],[5,6],[8,9],[10,11],[1,7]]
[[2,6],[9,11],[1,3],[4,7],[8,10],[0,5]]
[[2,5],[6,8],[9,10]]
[[1,2],[3,5],[7,8],[4,6]]
[[2,3],[4,5],[6,7],[8,9]]
[[3,4],[5,6]]

14: 51, 10
[[0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,13]]
[[0,2],[4,6],[8,10],[1,3],[5,7],[9,11]]
[[0,4],[8,12],[1,5],[9,13],[2,6],[3,7]]
[[0,8],[1,9],[2,10],[3,11],[4,12],[5,13]]
[[5,10],[6,9],[3,12],[7,11],[1,2],[4,8]]
[[1,4],[7,13],[2,8],[5,6],[9,10]]
[[2,4],[11,13],[3,8],[7,12]]
[[6,8],[10,12],[3,5],[7,9]]
[[3,4],[5,6],[7,8],[9,10],[11,12]]
[[6,7],[8,9]]

15: 56, 10
[[0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,13]]
[[0,2],[4,6],[8,10],[12,14],[1,3],[5,7],[9,11]]
[[0,4],[8,12],[1,5],[9,13],[2,6],[10,14],[3,7]]
[[0,8],[1,9],[2,10],[3,11],[4,12],[5,13],[6,14]]
[[5,10],[6,9],[3,12],[13,14],[7,11],[1,2],[4,8]]
[[1,4],[7,13],[2,8],[11,14],[5,6],[9,10]]
[[2,4],[11,13],[3,8],[7,12]]
[[6,8],[10,12],[3,5],[7,9]]
[[3,4],[5,6],[7,8],[9,10],[11,12]]
[[6,7],[8,9]]

16: 60, 10
[[0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,13],[14,15]]
[[0,2],[4,6],[8,10],[12,14],[1,3],[5,7],[9,11],[13,15]]
[[0,4],[8,12],[1,5],[9,13],[2,6],[10,14],[3,7],[11,15]]
[[0,8],[1,9],[2,10],[3,11],[4,12],[5,13],[6,14],[7,15]]
[[5,10],[6,9],[3,12],[13,14],[7,11],[1,2],[4,8]]
[[1,4],[7,13],[2,8],[11,14],[5,6],[9,10]]
[[2,4],[11,13],[3,8],[7,12]]
[[6,8],[10,12],[3,5],[7,9]]
[[3,4],[5,6],[7,8],[9,10],[11,12]]
[[6,7],[8,9]]

17: 81, 20
[[0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,13],[15,16]]
[[0,2],[1,3],[4,6],[5,7],[8,10],[9,11],[14,16]]
[[1,2],[5,6],[0,4],[3,7],[9,10],[14,15],[13,16]]
[[1,5],[2,6],[12,15],[11,16]]
[[1,4],[3,6],[12,14],[13,15],[7,16]]
[[2,4],[3,5],[13,14],[10,15]]
[[3,4],[8,13],[9,14],[11,15]]
[[8,12],[9,13],[11,14],[6,15]]
[[9,12],[10,13],[5,14],[7,15]]
[[10,12],[11,13],[0,9],[7,14]]
[[11,12],[0,8],[1,10],[4,13]]
[[1,9],[2,11],[3,12],[5,13]]
[[1,8],[3,11],[2,9],[6,13]]
[[2,8],[3,10],[7,13],[6,11]]
[[3,9],[5,10],[7,12]]
[[3,8],[4,9],[7,11]]
[[4,8],[5,9],[7,10]]
[[5,8],[6,9]]
[[6,8],[7,9]]
[[7,8]]

18: 90, 20
[[0,1],[2,3],[4,5],[7,8],[9,10],[11,12],[13,14],[16,17]]
[[0,2],[1,3],[6,8],[9,11],[10,12],[15,17]]
[[1,2],[6,7],[5,8],[10,11],[15,16],[14,17]]
[[4,7],[3,8],[13,16],[12,17]]
[[4,6],[5,7],[13,15],[14,16],[8,17]]
[[5,6],[2,7],[14,15],[11,16]]
[[0,5],[1,6],[3,7],[9,14],[10,15],[12,16]]
[[0,4],[1,5],[3,6],[9,13],[10,14],[12,15],[7,16]]
[[1,4],[2,5],[10,13],[11,14],[0,9],[6,15],[8,16]]
[[2,4],[3,5],[11,13],[12,14],[1,10],[7,15]]
[[3,4],[12,13],[1,9],[2,11],[5,14],[8,15]]
[[3,12],[2,9],[4,13],[7,14]]
[[3,11],[5,13],[8,14]]
[[3,10],[6,13]]
[[3,9],[7,13],[5,10],[6,11]]
[[8,13],[4,9],[7,12]]
[[5,9],[8,12],[7,11]]
[[8,11],[6,9],[7,10]]
[[8,10],[7,9]]
[[8,9]]

19: 100, 21
[[0,1],[2,3],[4,5],[7,8],[9,10],[12,13],[14,15],[17,18]]
[[0,2],[1,3],[6,8],[11,13],[16,18]]
[[1,2],[6,7],[5,8],[11,12],[10,13],[16,17],[15,18]]
[[4,7],[3,8],[9,12],[14,17],[13,18]]
[[4,6],[5,7],[9,11],[10,12],[14,16],[15,17],[8,18]]
[[5,6],[2,7],[10,11],[15,16],[9,14],[12,17]]
[[0,5],[1,6],[3,7],[10,15],[11,16],[13,17]]
[[0,4],[1,5],[3,6],[10,14],[12,16],[7,17]]
[[1,4],[2,5],[13,16],[11,14],[12,15],[0,10],[8,17]]
[[2,4],[3,5],[13,15],[12,14],[0,9],[1,11],[6,16]]
[[3,4],[13,14],[1,10],[2,12],[5,15],[7,16]]
[[1,9],[3,13],[2,10],[4,14],[8,16],[7,15]]
[[3,12],[2,9],[5,14],[8,15]]
[[3,11],[6,14]]
[[3,10],[7,14],[6,11]]
[[3,9],[8,14],[5,10],[7,12]]
[[4,9],[8,13],[7,11]]
[[5,9],[8,12],[7,10]]
[[8,11],[6,9]]
[[8,10],[7,9]]
[[8,9]]

20: 106, 21
[[0,1],[3,4],[5,6],[8,9],[10,11],[13,14],[15,16],[18,19]]
[[2,4],[7,9],[12,14],[17,19]]
[[2,3],[1,4],[7,8],[6,9],[12,13],[11,14],[17,18],[16,19]]
[[0,3],[5,8],[4,9],[10,13],[15,18],[14,19]]
[[0,2],[1,3],[5,7],[6,8],[10,12],[11,13],[15,17],[16,18],[9,19]]
[[1,2],[6,7],[0,5],[3,8],[11,12],[16,17],[10,15],[13,18]]
[[1,6],[2,7],[4,8],[11,16],[12,17],[14,18],[0,10]]
[[1,5],[3,7],[11,15],[13,17],[8,18]]
[[4,7],[2,5],[3,6],[14,17],[12,15],[13,16],[1,11],[9,18]]
[[4,6],[3,5],[14,16],[13,15],[1,10],[2,12],[7,17]]
[[4,5],[14,15],[3,13],[2,10],[6,16],[8,17]]
[[4,14],[3,12],[5,15],[9,17],[8,16]]
[[4,13],[3,11],[6,15],[9,16]]
[[4,12],[3,10],[7,15]]
[[4,11],[8,15],[7,12]]
[[4,10],[9,15],[6,11],[8,13]]
[[5,10],[9,14],[8,12]]
[[6,10],[9,13],[8,11]]
[[9,12],[7,10]]
[[9,11],[8,10]]
[[9,10]]

21: 118, 23
[[0,1],[3,4],[5,6],[8,9],[10,11],[13,14],[16,17],[19,20]]
[[2,4],[7,9],[12,14],[15,17],[18,20]]
[[2,3],[1,4],[7,8],[6,9],[12,13],[11,14],[15,16],[18,19],[17,20]]
[[0,3],[5,8],[4,9],[10,13],[15,18],[16,19],[14,20]]
[[0,2],[1,3],[5,7],[6,8],[10,12],[11,13],[17,19],[16,18],[9,20]]
[[1,2],[6,7],[0,5],[3,8],[11,12],[17,18],[10,16],[13,19]]
[[1,6],[2,7],[4,8],[10,15],[11,17],[12,18],[14,19]]
[[1,5],[3,7],[11,16],[13,18],[8,19]]
[[4,7],[2,5],[3,6],[11,15],[14,18],[13,16],[9,19]]
[[4,6],[3,5],[12,15],[14,17],[0,11],[7,18]]
[[4,5],[14,16],[13,15],[0,10],[1,12],[6,17],[8,18]]
[[14,15],[1,11],[2,13],[5,16],[9,18],[8,17]]
[[1,10],[3,14],[4,15],[6,16],[9,17]]
[[4,14],[3,13],[2,10],[7,16]]
[[4,13],[3,11],[8,16]]
[[4,12],[3,10],[9,16],[7,13],[8,14]]
[[4,11],[6,12],[9,15],[8,13]]
[[4,10],[5,11],[9,14]]
[[5,10],[6,11],[9,13]]
[[6,10],[8,11],[9,12]]
[[7,10],[9,11]]
[[8,10]]
[[9,10]]

22: 125, 23
[[0,1],[3,4],[6,7],[9,10],[11,12],[14,15],[17,18],[20,21]]
[[2,4],[5,7],[8,10],[13,15],[16,18],[19,21]]
[[2,3],[1,4],[5,6],[8,9],[7,10],[13,14],[12,15],[16,17],[19,20],[18,21]]
[[0,3],[5,8],[6,9],[4,10],[11,14],[16,19],[17,20],[15,21]]
[[0,2],[1,3],[7,9],[6,8],[11,13],[12,14],[18,20],[17,19],[10,21]]
[[1,2],[7,8],[0,6],[3,9],[12,13],[18,19],[11,17],[14,20]]
[[0,5],[1,7],[2,8],[4,9],[11,16],[12,18],[13,19],[15,20]]
[[1,6],[3,8],[12,17],[14,19],[0,11],[9,20]]
[[1,5],[4,8],[3,6],[12,16],[15,19],[14,17],[10,20]]
[[2,5],[4,7],[13,16],[15,18],[1,12],[8,19]]
[[4,6],[3,5],[15,17],[14,16],[1,11],[2,13],[7,18],[9,19]]
[[4,5],[15,16],[3,14],[2,11],[6,17],[10,19]]
[[4,15],[3,13],[5,16],[7,17],[10,18]]
[[4,14],[3,12],[6,16],[9,17]]
[[4,13],[3,11],[7,16],[10,17]]
[[4,12],[8,16],[7,13]]
[[4,11],[9,16],[6,12],[8,14]]
[[10,16],[5,11],[7,12],[9,15]]
[[6,11],[10,15],[9,14]]
[[7,11],[10,14],[9,12]]
[[8,11],[10,13]]
[[10,12],[9,11]]
[[10,11]]

23: 133, 24
[[0,1],[3,4],[6,7],[9,10],[12,13],[15,16],[18,19],[21,22]]
[[2,4],[5,7],[8,10],[11,13],[14,16],[17,19],[20,22]]
[[2,3],[1,4],[5,6],[8,9],[7,10],[11,12],[14,15],[13,16],[17,18],[20,21],[19,22]]
[[0,3],[5,8],[6,9],[4,10],[11,14],[12,15],[17,20],[18,21],[16,22]]
[[0,2],[1,3],[7,9],[6,8],[13,15],[12,14],[19,21],[18,20],[11,17],[10,22]]
[[1,2],[7,8],[0,6],[3,9],[13,14],[19,20],[12,18],[15,21]]
[[0,5],[1,7],[2,8],[4,9],[13,19],[12,17],[14,20],[16,21]]
[[1,6],[3,8],[13,18],[15,20],[0,12],[9,21]]
[[1,5],[4,8],[3,6],[13,17],[16,20],[15,18],[0,11],[10,21]]
[[2,5],[4,7],[14,17],[16,19],[1,13],[8,20]]
[[4,6],[3,5],[16,18],[15,17],[1,12],[2,14],[7,19],[9,20]]
[[4,5],[16,17],[1,11],[3,15],[6,18],[10,20]]
[[4,16],[3,14],[2,11],[5,17],[7,18],[10,19]]
[[4,15],[3,12],[6,17],[9,18]]
[[4,14],[3,11],[7,17],[10,18]]
[[4,13],[8,17]]
[[4,12],[9,17],[7,13],[8,14]]
[[4,11],[10,17],[6,12],[9,15]]
[[5,11],[7,12],[10,16],[9,14]]
[[6,11],[10,15],[9,12]]
[[7,11],[10,14]]
[[8,11],[10,13]]
[[10,12],[9,11]]
[[10,11]]

24: 138, 24
[[1,2],[4,5],[7,8],[10,11],[13,14],[16,17],[19,20],[22,23]]
[[0,2],[3,5],[6,8],[9,11],[12,14],[15,17],[18,20],[21,23]]
[[0,1],[3,4],[2,5],[6,7],[9,10],[8,11],[12,13],[15,16],[14,17],[18,19],[21,22],[20,23]]
[[0,3],[1,4],[6,9],[7,10],[5,11],[12,15],[13,16],[18,21],[19,22],[17,23]]
[[2,4],[1,3],[8,10],[7,9],[0,6],[14,16],[13,15],[20,22],[19,21],[12,18],[11,23]]
[[2,3],[8,9],[1,7],[4,10],[14,15],[20,21],[13,19],[16,22],[0,12]]
[[2,8],[1,6],[3,9],[5,10],[14,20],[13,18],[15,21],[17,22]]
[[2,7],[4,9],[14,19],[16,21],[1,13],[10,22]]
[[2,6],[5,9],[4,7],[14,18],[17,21],[16,19],[1,12],[11,22]]
[[3,6],[5,8],[15,18],[17,20],[2,14],[9,21]]
[[5,7],[4,6],[17,19],[16,18],[2,13],[3,15],[8,20],[10,21]]
[[5,6],[17,18],[2,12],[4,16],[7,19],[11,21]]
[[5,17],[4,15],[3,12],[6,18],[8,19],[11,20]]
[[5,16],[4,13],[7,18],[10,19]]
[[5,15],[4,12],[8,18],[11,19]]
[[5,14],[9,18]]
[[5,13],[10,18],[8,14],[9,15]]
[[5,12],[11,18],[7,13],[10,16]]
[[6,12],[8,13],[11,17],[10,15]]
[[7,12],[11,16],[10,13]]
[[8,12],[11,15]]
[[9,12],[11,14]]
[[11,13],[10,12]]
[[11,12]]

25: 154, 27
[[1,2],[4,5],[7,8],[10,11],[13,14],[16,17],[19,20],[21,22],[23,24]]
[[0,2],[3,5],[6,8],[9,11],[12,14],[15,17],[18,20],[21,23],[22,24]]
[[0,1],[3,4],[2,5],[6,7],[9,10],[8,11],[12,13],[15,16],[14,17],[18,19],[22,23],[20,24]]
[[0,3],[1,4],[6,9],[7,10],[5,11],[12,15],[13,16],[18,22],[19,23],[17,24]]
[[2,4],[1,3],[8,10],[7,9],[0,6],[14,16],[13,15],[18,21],[20,23],[11,24]]
[[2,3],[8,9],[1,7],[4,10],[14,15],[19,21],[20,22],[16,23]]
[[2,8],[1,6],[3,9],[5,10],[20,21],[12,19],[15,22],[17,23]]
[[2,7],[4,9],[12,18],[13,20],[14,21],[16,22],[10,23]]
[[2,6],[5,9],[4,7],[14,20],[13,18],[17,22],[11,23]]
[[3,6],[5,8],[14,19],[16,20],[17,21],[0,13],[9,22]]
[[5,7],[4,6],[14,18],[15,19],[17,20],[0,12],[8,21],[10,22]]
[[5,6],[15,18],[17,19],[1,14],[7,20],[11,22]]
[[16,18],[2,15],[1,12],[6,19],[8,20],[11,21]]
[[17,18],[2,14],[3,16],[7,19],[10,20]]
[[2,13],[4,17],[5,18],[8,19],[11,20]]
[[2,12],[5,17],[4,16],[3,13],[9,19]]
[[5,16],[3,12],[4,14],[10,19]]
[[5,15],[4,12],[11,19],[9,16],[10,17]]
[[5,14],[8,15],[11,18],[10,16]]
[[5,13],[7,14],[11,17]]
[[5,12],[6,13],[8,14],[11,16]]
[[6,12],[8,13],[10,14],[11,15]]
[[7,12],[9,13],[11,14]]
[[8,12],[11,13]]
[[9,12]]
[[10,12]]
[[11,12]]

26: 163, 27
[[1,2],[4,5],[7,8],[9,10],[11,12],[14,15],[17,18],[20,21],[22,23],[24,25]]
[[0,2],[3,5],[6,8],[9,11],[10,12],[13,15],[16,18],[19,21],[22,24],[23,25]]
[[0,1],[3,4],[2,5],[6,7],[10,11],[8,12],[13,14],[16,17],[15,18],[19,20],[23,24],[21,25]]
[[0,3],[1,4],[6,10],[7,11],[5,12],[13,16],[14,17],[19,23],[20,24],[18,25]]
[[2,4],[1,3],[6,9],[8,11],[15,17],[14,16],[19,22],[21,24],[12,25]]
[[2,3],[7,9],[8,10],[4,11],[15,16],[20,22],[21,23],[17,24]]
[[8,9],[0,7],[3,10],[5,11],[21,22],[13,20],[16,23],[18,24]]
[[0,6],[1,8],[2,9],[4,10],[13,19],[14,21],[15,22],[17,23],[11,24]]
[[2,8],[1,6],[5,10],[15,21],[14,19],[18,23],[0,13],[12,24]]
[[2,7],[4,8],[5,9],[15,20],[17,21],[18,22],[1,14],[10,23]]
[[2,6],[3,7],[5,8],[15,19],[16,20],[18,21],[1,13],[9,22],[12,23]]
[[3,6],[5,7],[16,19],[18,20],[2,15],[8,21],[10,22]]
[[4,6],[17,19],[2,14],[3,16],[7,20],[11,22]]
[[5,6],[18,19],[2,13],[4,17],[8,20],[12,22],[11,21]]
[[5,18],[4,16],[3,13],[6,19],[10,20],[12,21]]
[[5,17],[4,14],[7,19],[12,20]]
[[5,16],[4,13],[8,19]]
[[5,15],[9,19]]
[[5,14],[10,19],[8,15],[9,16]]
[[5,13],[11,19],[7,14],[10,17]]
[[12,19],[6,13],[8,14],[10,16],[11,18]]
[[7,13],[12,18],[11,16],[10,14]]
[[8,13],[12,17],[11,15]]
[[12,16],[9,13]]
[[10,13],[12,15]]
[[11,13],[12,14]]
[[12,13]]

27: 173, 28
[[1,2],[4,5],[7,8],[9,10],[11,12],[14,15],[16,17],[18,19],[21,22],[23,24],[25,26]]
[[0,2],[3,5],[6,8],[9,11],[10,12],[13,15],[16,18],[17,19],[20,22],[23,25],[24,26]]
[[0,1],[3,4],[2,5],[6,7],[10,11],[8,12],[13,14],[17,18],[15,19],[20,21],[24,25],[22,26]]
[[0,3],[1,4],[6,10],[7,11],[5,12],[13,17],[14,18],[20,24],[21,25],[19,26]]
[[2,4],[1,3],[6,9],[8,11],[13,16],[15,18],[20,23],[22,25],[12,26]]
[[2,3],[7,9],[8,10],[4,11],[14,16],[15,17],[21,23],[22,24],[13,20],[18,25]]
[[8,9],[0,7],[3,10],[5,11],[15,16],[22,23],[14,21],[17,24],[19,25]]
[[0,6],[1,8],[2,9],[4,10],[15,22],[14,20],[16,23],[19,24],[11,25]]
[[2,8],[1,6],[5,10],[15,21],[17,23],[0,14],[12,25]]
[[2,7],[4,8],[5,9],[15,20],[18,23],[17,21],[0,13],[10,24]]
[[2,6],[3,7],[5,8],[19,23],[16,20],[18,22],[1,15],[12,24]]
[[3,6],[5,7],[17,20],[19,22],[2,16],[1,13],[9,23]]
[[4,6],[18,20],[19,21],[2,15],[3,17],[8,22],[10,23]]
[[5,6],[19,20],[2,14],[4,18],[7,21],[11,23]]
[[2,13],[5,19],[4,17],[3,14],[6,20],[8,21],[12,23],[11,22]]
[[5,18],[3,13],[4,15],[7,20],[10,21],[12,22]]
[[5,17],[4,13],[8,20],[12,21]]
[[5,16],[9,20]]
[[5,15],[10,20],[9,16]]
[[5,14],[11,20],[8,15],[10,17]]
[[5,13],[12,20],[7,14],[10,16],[11,18]]
[[6,13],[8,14],[12,19],[11,16]]
[[7,13],[12,18],[10,14],[11,15]]
[[8,13],[12,17]]
[[12,16],[9,13]]
[[10,13],[12,15]]
[[11,13],[12,14]]
[[12,13]]

28: 179, 28
[[1,2],[3,4],[5,6],[8,9],[10,11],[12,13],[15,16],[17,18],[19,20],[22,23],[24,25],[26,27]]
[[0,2],[3,5],[4,6],[7,9],[10,12],[11,13],[14,16],[17,19],[18,20],[21,23],[24,26],[25,27]]
[[0,1],[4,5],[2,6],[7,8],[11,12],[9,13],[14,15],[18,19],[16,20],[21,22],[25,26],[23,27]]
[[0,4],[1,5],[7,11],[8,12],[6,13],[14,18],[15,19],[21,25],[22,26],[20,27]]
[[0,3],[2,5],[7,10],[9,12],[14,17],[16,19],[21,24],[23,26],[13,27]]
[[1,3],[2,4],[8,10],[9,11],[0,7],[5,12],[15,17],[16,18],[22,24],[23,25],[14,21],[19,26]]
[[2,3],[9,10],[1,8],[4,11],[6,12],[16,17],[23,24],[15,22],[18,25],[20,26],[0,14]]
[[2,9],[1,7],[3,10],[6,11],[16,23],[15,21],[17,24],[20,25],[12,26]]
[[2,8],[4,10],[16,22],[18,24],[1,15],[11,25],[13,26]]
[[2,7],[5,10],[4,8],[16,21],[19,24],[18,22],[1,14],[13,25]]
[[6,10],[3,7],[5,9],[20,24],[17,21],[19,23],[2,16]]
[[4,7],[6,9],[18,21],[20,23],[2,15],[3,17],[10,24]]
[[5,7],[6,8],[19,21],[20,22],[2,14],[4,18],[9,23],[11,24]]
[[6,7],[20,21],[4,17],[5,19],[3,14],[8,22],[12,24]]
[[6,20],[5,17],[4,15],[7,21],[9,22],[13,24],[12,23]]
[[6,19],[4,14],[5,16],[8,21],[11,22],[13,23]]
[[6,18],[5,14],[9,21],[13,22]]
[[6,17],[10,21]]
[[6,16],[11,21],[10,17]]
[[6,15],[12,21],[9,16],[11,18]]
[[6,14],[13,21],[8,15],[11,17],[12,19]]
[[7,14],[9,15],[13,20],[12,17]]
[[8,14],[13,19],[11,15],[12,16]]
[[9,14],[13,18]]
[[13,17],[10,14]]
[[11,14],[13,16]]
[[12,14],[13,15]]
[[13,14]]

29: 191, 30
[[1,2],[3,4],[5,6],[8,9],[10,11],[12,13],[15,16],[17,18],[19,20],[21,22],[23,24],[25,26],[27,28]]
[[0,2],[3,5],[4,6],[7,9],[10,12],[11,13],[14,16],[17,19],[18,20],[21,23],[22,24],[25,27],[26,28]]
[[0,1],[4,5],[2,6],[7,8],[11,12],[9,13],[14,15],[18,19],[16,20],[22,23],[26,27],[21,25],[24,28]]
[[0,4],[1,5],[7,11],[8,12],[6,13],[14,18],[15,19],[22,26],[23,27],[20,28]]
[[0,3],[2,5],[7,10],[9,12],[14,17],[16,19],[22,25],[24,27],[13,28]]
[[1,3],[2,4],[8,10],[9,11],[0,7],[5,12],[15,17],[16,18],[23,25],[24,26],[14,22],[19,27]]
[[2,3],[9,10],[1,8],[4,11],[6,12],[16,17],[24,25],[14,21],[15,23],[18,26],[20,27]]
[[2,9],[1,7],[3,10],[6,11],[16,24],[15,21],[17,25],[20,26],[12,27]]
[[2,8],[4,10],[16,23],[18,25],[0,15],[11,26],[13,27]]
[[2,7],[5,10],[4,8],[16,22],[19,25],[0,14],[13,26]]
[[6,10],[3,7],[5,9],[16,21],[20,25],[18,22],[19,23]]
[[4,7],[6,9],[17,21],[20,24],[1,16],[10,25]]
[[5,7],[6,8],[18,21],[20,23],[2,17],[1,14],[9,24],[11,25]]
[[6,7],[19,21],[20,22],[2,16],[3,18],[8,23],[12,25]]
[[20,21],[2,15],[4,19],[7,22],[9,23],[13,25],[12,24]]
[[2,14],[4,18],[5,20],[6,21],[8,22],[11,23],[13,24]]
[[6,20],[5,18],[3,14],[4,15],[9,22],[13,23]]
[[6,19],[4,14],[5,16],[10,22]]
[[6,18],[5,14],[11,22]]
[[6,17],[12,22],[10,18],[11,19]]
[[6,16],[13,22],[9,17],[11,18],[12,20]]
[[6,15],[8,16],[13,21],[12,18]]
[[6,14],[7,15],[9,16],[13,20]]
[[7,14],[9,15],[13,19],[12,16]]
[[8,14],[13,18],[11,15]]
[[9,14],[13,17]]
[[10,14],[13,16]]
[[11,14],[13,15]]
[[12,14]]
[[13,14]]

30: 198, 30
[[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[16,17],[18,19],[20,21],[22,23],[24,25],[26,27],[28,29]]
[[0,2],[3,5],[4,6],[7,9],[8,10],[11,13],[12,14],[15,17],[18,20],[19,21],[22,24],[23,25],[26,28],[27,29]]
[[0,1],[4,5],[2,6],[8,9],[12,13],[7,11],[10,14],[15,16],[19,20],[17,21],[23,24],[27,28],[22,26],[25,29]]
[[0,4],[1,5],[8,12],[9,13],[6,14],[15,19],[16,20],[23,27],[24,28],[21,29]]
[[0,3],[2,5],[8,11],[10,13],[15,18],[17,20],[23,26],[25,28],[14,29]]
[[1,3],[2,4],[9,11],[10,12],[0,8],[5,13],[16,18],[17,19],[24,26],[25,27],[15,23],[20,28]]
[[2,3],[10,11],[0,7],[1,9],[4,12],[6,13],[17,18],[25,26],[15,22],[16,24],[19,27],[21,28]]
[[2,10],[1,7],[3,11],[6,12],[17,25],[16,22],[18,26],[21,27],[0,15],[13,28]]
[[2,9],[4,11],[17,24],[19,26],[1,16],[12,27],[14,28]]
[[2,8],[5,11],[17,23],[20,26],[1,15],[14,27]]
[[2,7],[6,11],[4,8],[5,9],[17,22],[21,26],[19,23],[20,24]]
[[3,7],[6,10],[18,22],[21,25],[2,17],[11,26]]
[[4,7],[6,9],[19,22],[21,24],[2,16],[3,18],[10,25],[12,26]]
[[5,7],[6,8],[20,22],[21,23],[2,15],[4,19],[9,24],[13,26]]
[[6,7],[21,22],[4,18],[5,20],[3,15],[8,23],[10,24],[14,26]]
[[6,21],[5,18],[4,16],[7,22],[10,23],[13,24],[14,25]]
[[6,20],[4,15],[5,17],[8,22],[12,23],[14,24]]
[[6,19],[5,15],[9,22],[14,23]]
[[6,18],[10,22]]
[[6,17],[11,22],[10,18]]
[[6,16],[12,22],[9,17],[11,19]]
[[6,15],[13,22],[8,16],[10,17],[12,20]]
[[14,22],[7,15],[10,16],[12,19],[13,21]]
[[8,15],[14,21],[13,19],[12,16]]
[[9,15],[14,20],[13,17]]
[[10,15],[14,19]]
[[11,15],[14,18]]
[[12,15],[14,17]]
[[13,15],[14,16]]
[[14,15]]

31: 206, 31
[[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18],[19,20],[21,22],[23,24],[25,26],[27,28],[29,30]]
[[0,2],[3,5],[4,6],[7,9],[8,10],[11,13],[12,14],[15,17],[16,18],[19,21],[20,22],[23,25],[24,26],[27,29],[28,30]]
[[0,1],[4,5],[2,6],[8,9],[12,13],[7,11],[10,14],[16,17],[20,21],[15,19],[18,22],[24,25],[28,29],[23,27],[26,30]]
[[0,4],[1,5],[8,12],[9,13],[6,14],[16,20],[17,21],[24,28],[25,29],[15,23],[22,30]]
[[0,3],[2,5],[8,11],[10,13],[16,19],[18,21],[24,27],[26,29],[14,30]]
[[1,3],[2,4],[9,11],[10,12],[0,8],[5,13],[17,19],[18,20],[25,27],[26,28],[16,24],[21,29]]
[[2,3],[10,11],[0,7],[1,9],[4,12],[6,13],[18,19],[26,27],[16,23],[17,25],[20,28],[22,29]]
[[2,10],[1,7],[3,11],[6,12],[18,26],[17,23],[19,27],[22,28],[0,16],[13,29]]
[[2,9],[4,11],[18,25],[20,27],[0,15],[1,17],[12,28],[14,29]]
[[2,8],[5,11],[18,24],[21,27],[1,15],[14,28]]
[[2,7],[6,11],[4,8],[5,9],[18,23],[22,27],[20,24],[21,25]]
[[3,7],[6,10],[19,23],[22,26],[2,18],[11,27]]
[[4,7],[6,9],[20,23],[22,25],[2,17],[3,19],[10,26],[12,27]]
[[5,7],[6,8],[21,23],[22,24],[2,16],[4,20],[9,25],[13,27]]
[[6,7],[22,23],[2,15],[4,19],[5,21],[8,24],[10,25],[14,27]]
[[6,22],[5,19],[3,15],[4,16],[7,23],[10,24],[13,25],[14,26]]
[[6,21],[4,15],[5,17],[8,23],[12,24],[14,25]]
[[6,20],[5,15],[9,23],[14,24]]
[[6,19],[10,23]]
[[6,18],[11,23]]
[[6,17],[12,23],[10,18],[11,19]]
[[6,16],[13,23],[9,17],[12,20]]
[[6,15],[14,23],[8,16],[10,17],[12,19],[13,21]]
[[7,15],[10,16],[14,22],[13,19]]
[[8,15],[14,21],[12,16],[13,17]]
[[9,15],[14,20]]
[[10,15],[14,19]]
[[11,15],[14,18]]
[[12,15],[14,17]]
[[13,15],[14,16]]
[[14,15]]

32: 211, 31
[[0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,13],[14,15],[16,17],[18,19],[20,21],[22,23],[24,25],[26,27],[28,29],[30,31]]
[[0,2],[1,3],[4,6],[5,7],[8,10],[9,11],[12,14],[13,15],[16,18],[17,19],[20,22],[21,23],[24,26],[25,27],[28,30],[29,31]]
[[1,2],[5,6],[0,4],[3,7],[9,10],[13,14],[8,12],[11,15],[17,18],[21,22],[16,20],[19,23],[25,26],[29,30],[24,28],[27,31]]
[[1,5],[2,6],[9,13],[10,14],[0,8],[7,15],[17,21],[18,22],[25,29],[26,30],[16,24],[23,31]]
[[1,4],[3,6],[9,12],[11,14],[17,20],[19,22],[25,28],[27,30],[0,16],[15,31]]
[[2,4],[3,5],[10,12],[11,13],[1,9],[6,14],[18,20],[19,21],[26,28],[27,29],[17,25],[22,30]]
[[3,4],[11,12],[1,8],[2,10],[5,13],[7,14],[19,20],[27,28],[17,24],[18,26],[21,29],[23,30]]
[[3,11],[2,8],[4,12],[7,13],[19,27],[18,24],[20,28],[23,29],[1,17],[14,30]]
[[3,10],[5,12],[19,26],[21,28],[1,16],[2,18],[13,29],[15,30]]
[[3,9],[6,12],[19,25],[22,28],[2,16],[15,29]]
[[3,8],[7,12],[5,9],[6,10],[19,24],[23,28],[21,25],[22,26]]
[[4,8],[7,11],[20,24],[23,27],[3,19],[12,28]]
[[5,8],[7,10],[21,24],[23,26],[3,18],[4,20],[11,27],[13,28]]
[[6,8],[7,9],[22,24],[23,25],[3,17],[5,21],[10,26],[14,28]]
[[7,8],[23,24],[3,16],[5,20],[6,22],[9,25],[11,26],[15,28]]
[[7,23],[6,20],[4,16],[5,17],[8,24],[11,25],[14,26],[15,27]]
[[7,22],[5,16],[6,18],[9,24],[13,25],[15,26]]
[[7,21],[6,16],[10,24],[15,25]]
[[7,20],[11,24]]
[[7,19],[12,24]]
[[7,18],[13,24],[11,19],[12,20]]
[[7,17],[14,24],[10,18],[13,21]]
[[7,16],[15,24],[9,17],[11,18],[13,20],[14,22]]
[[8,16],[11,17],[15,23],[14,20]]
[[9,16],[15,22],[13,17],[14,18]]
[[10,16],[15,21]]
[[11,16],[15,20]]
[[12,16],[15,19]]
[[13,16],[15,18]]
[[14,16],[15,17]]
[[15,16]]

Reinvent wheels, my quick sort implementation, just for fun

Not optimized yet.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
initial state:
 p                                                                 #
_p_                                                                #
 p_                                                               _p
 |-----------------------------------------------------------------#
 ..................................................................#


state after choosing pivot:
 p                                                                 #
 _p_                                                               #
 p_                                                               _p
 ||----------------------------------------------------------------#
 =.................................................................#


the middle state during partitioning:
 p                                                                 #
 |                       _p_                                       #
 |           p_           |                           _p           #
 |-----------|------------|----------------------------|-----------#
 <<<<<<<<<<<<=============.............................>>>>>>>>>>>>#


the final state after partition:
 p                                                                 #
 |                                                _p_              #
 |                  p_                            _p               #
 |------------------|------------------------------|---------------#
 <<<<<<<<<<<<<<<<<<<===============================>>>>>>>>>>>>>>>>#

Then, recurse.
Note: the pointer p_ will always point to a pivot element after choosing pivot step.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
template<typename Elem, typename OtherSort, size_t Threshold>
class QuickSort {
public:
    static void go(Elem p[], size_t n) {
        Elem *p_, *_p_, *_p;
        assert(typeid(OtherSort)!=typeid(QuickSort));
        do {
            // recursion exit, use other sort algorithm to process small array
            if(n < Threshold) {
                OtherSort::go(p, n);
                return;
            }

            p_ = p;
            _p_ = p;
            _p = p+n;

            // choosing pivot element
            swap(p_, pivot(p, n));
            _p_++;

            // partitioning
            while(_p_ < _p) {
                while((*p_ == *_p_) && (_p_ < _p)) ++_p_;
                while((*p_ < *_p_) && (_p_ < _p)) {
                    --_p;
                    swap(_p_, _p);
                }
                while((*_p_ < *p_) && (_p_ < _p)) {
                    swap(p_, _p_);
                    ++p_;
                    ++_p_;
                }
            }

            // recursion only for the partition with less elements
            if((p_ - p) < (n - (_p - p))) {
                go(p, p_ - p);
                n = n - (_p - p);
                p = _p;
            } else {
                go(_p, n - (_p - p));
                n = p_ - p;
            }

            // tail recursion elimination
        } while(true);
    }
private:
    static Elem *pivot(Elem p[], size_t n) {
        if(n < 10) return p + n/2;
        else return p + random(n);
        // random(n) should return a uniformly distributed random number in [0, n)
    }
};

About stream interface usage


-bool Buffering::process(IBuff *pi, OBuff *po) {
- forever {
- // put as much as possible
- po->put(&ctBuff_, ctBuff_.gSize());
- // get as much as possible
- pi->get(&ptBuff_, ptBuff_.pSize());
- if(ptBuff_->isFull() && ctBuff_->isEmpty()) {
- // now, the plaintext buff is fullfilled
- // the ciphertext buff is empty.
- processor_.process(ptBuff, ctBuff);
- // now, the plaintext buff is empty,
- // the ciphertext buff is fullfilled.
- } else {
- break;
- }
- }
- return true;
-}

About applicating hash algorithms with data encryption

Generate hash code and attach it with the message before encryption to achieve both encryption and authentication, what is the security requirement of the hash function?

If the security requirement is as simple as other normal error-checking-code, we can apply some simple hash algorithms, such as CRC algorithm.

Using such simple hash code generators, the performance may get some significant improvement. Especially you can always apply hash function with counter operation mode parallelly.

Dependency management

How to management the dependency between the software modules? Is there any GNU tool to do this?

How can we collect units from some symbol entries together? I mean how can I start with some symbols, collect all the code units that these symbols directly or indirectly depend on, to make a single library file which contains all these symbols and all dependencies.

Aspect management

Each component of a component system may has more than one aspect.

The relationship between aspect and component mostly is orthogonal.

Sometime we may add some new aspect, sometime we may add some new component. But it is not necessary to implement every aspect for every component. If a component don’t provide some aspect, the service that associated with the aspect may not applicable for that component, but the component should be still executable with its implemented aspects.

We can just use a matrix to trace the implemented aspects of each component we have.

By the way, matrix method can also applied to trace the platform depend components for the cross-platform component project. In this scenario, the matrix record the supported platform for each component we have.

Assembling component model: composite component.

Manually assemble the independent component together by hand-coding, is not flexible and lack of management.

Sometime some component can play a manager role when you assemble it with some other components. You can let this component take the responsibility of registering and destroying all the components that it depends on.

But in most cases it’s not a good practice. This makes many components have to burden with the management code. Even worse, sometime the assembling relationship of the whole component system is not tree-formed, some times, it’s a network-like graph.

We need some manager for organize some component sub-system. This can be achieved through creating a common purpose component in assembling component model. We call it a composite component.

A composite component provide following features:

1.registering all the sub-components.
2.recording all the assembling relationships between sub-components.
3.forwarding the service invocation to the corresponding sub-components.
4.destroying all the sub-components before destroyed.

And a composite component may also provides some service such like serialization for saving the assembling relationship of the sub-components.

In practice, composite component sometimes has to manage some external dependency, such some component which may not managed by the current composite component. In this case, the component should register the identity of the external dependency. This identity can be resolved by some higher-level component registry.

(to be continued…)

Assembling component model in software design, my considerations.

Different from other component models, assembling component model explicitly separates the two type of the service port of a component: service provider and service consumer.

Each port references a specification which specify the syntax and semantics of the service, we call it interface specification.

A service provider port, provides service to the customer through a given specification.

A service consumer port, consumes service from the customer through a given specification.

When a service provider of some component can satisfy the service consumer of some component, then when you create objects as instances of the components at runtime, you can simply connect the ports of the objects together, which called assembling. You can assemble many components together to make a complex component system and provide high level services, just like assemble a set of Lego bricks.

How a service provider satisfy a service consumer? If and only if the service provider’s interface specification is a sub-type of the service consumer’s interface specification.

Therefore, it’s not necessary that the provider and the consumer have the exactly same interface specification.

In such an assembling component model, the benefit is you can easily assemble things together, just like to assemble the standardized computer devices. But the draw back is, each time if you want to provide some new independent services, you have to define the syntax and the semantics for the services first, after that you can implement the components which can provide or consume the services. This step will slow down the the response time for the requirement, but reduce the coupling between components, all coupling will just take place between the components and the interface specifications.

In such component model, interfaces are no more auxiliaries of the components, actually they are the central concepts of a system.

RSA blind算法--让RSA抵抗时间分析攻击

对于了解RSA算法并且也了解密码算法时间分析攻击的人,可以跳过A,B两部分。

A.先大致说一下RSA算法:

公开密钥(n,e),私有密钥(n,d)
其中n = p*q,p,q是两个随机选择的巨型素数(必须保密),d,e满足d*e≡1 (mod(p-1)(q-1))

—-====以下公式中,如果不加特殊说明,所有运算都是(mod n)的运算====—-

于是根据Fermat小定理,x^(d*e) = x

假设明文为m,密文为c,那么

利用公钥(n,e)的加密过程:c = m^e
利用私钥(n,e)的解密过程:m = c^d = (m^e)^d = m^(e*d),根据Fermat小定理,m^(e*d)刚好等于m。

当然,RSA算法真实实现比这要复杂很多,需要用到大素数的随机生成算法、强素数的生成算法、中国剩余定理、快速的模幂运算等,但这些对与我们要讨论的RSA blind没有什么关系,因此不再深入了。

B.再大致介绍一下时间分析攻击:

时间分析攻击,实际上是选择密文攻击的一种,利用了一种边带(side channel)信息的泄漏

B.1先说说选择密文攻击:

所谓选择密文攻击,是指攻击者能够获取解密服务,但不知道密钥的情况下,对系统进行的一种攻击。

例如,一个职员,在任职期间可以得到其主管机器的解密服务,因此可以阅读主管收到的加密邮件并且代主管回复邮件,但并不知道主管的密钥。但该职员离职之后,该解密服务随即停止。因此该职员不再能够继续阅读主管的邮件,因为他没有主管的密钥。如果该职员在任职期间,利用职务的便利,通过精心构造一批密文,并且使用主管机器提供的解密服务,根据这批密文的解密结果(注意,解密结果不一定仅仅包括明文信息,解密指定密文所消耗的时间,系统产生的热量,此类信息都术语解密结果信息)设法确定了主管的密钥,那么他就可以在离职之后继续读取主管的邮件。这个职员的攻击方法就被称作选择密文攻击。

稍微正式一点地描述选择密文攻击:攻击者精心设计一组密文ci,使用能够获取到的解密服务对密文ci进行解密,假设每个ci对应的解密结果所包含的信息是ri,那么我们就得到了这组ci和ri的之间的关系Rk:
ri = Rk(ci)。Rk与密钥k之间肯定是有关系的,通过这个Rk确定密钥k的过程就是选择密文攻击。

如果对于一个算法,Rk与k之间的关系并不复杂,有办法在可接受的时间内由Rk确定密钥k,那么就说这个算法对于选择密文攻击是脆弱的。

B.2再说说时间攻击:

所谓时间(分析)攻击,所利用的解密结果信息就是解密服务解密密文ci所用的时间ti。如果精心设计密文,获取了ci和ti的关系Tk:
ti = Tk(ci),通过分析Tk和密钥k之间的关系来确定密钥的方法,就是所谓的时间分析攻击。

一个非密码学的时间分析攻击的例子:如果我要窃取你在键盘上输入的口令,我不一定非要看到敲击口令的过程,我只要在旁边听你相邻两次击键的时间间隔,就可以得到一些信息:间隔短的两次击键,很可能意味着两个键的距离比较近,间隔长的两次击键,很可能意味着两个键的距离比较远。如果我有机会尝试攻击你的口令,我可以仅仅尝试哪些在时间间隔模式上跟我窃听到的你的击键过程的时间间隔很相似的口令,这样我所需要进行尝试的数量就会远小于完全的暴力攻击。

对于RSA算法,数学上的攻击,至少在目前来说,没有已知的特别高效的攻击手段。但是,对于一个具体的RSA算法实现,只要我知道算法的具体代码,我就可以给出解密一个指定密文ci所需要的时间ti,与密钥每个bit的值之间的函数关系。这样我只要精心构造出一组密文ci,并测量时间ti,就可以把密钥的每个bit作为未知数,建立一组方程把每个密钥bit求出来。这个方程甚至很可能是线性的。

有人可能怀疑解密时间可能不能精确测量,那么这种攻击是否还能奏效呢?当然可以,首先,时间不精确可以重复多次地对同一个密文进行解密取平均值而得到。其次,即便测量不精确,不能唯一地确定密钥,至少也可以只试探那些最可能的密钥,大大缩小密钥搜索空间。

注意,这种攻击并不仅仅是理论上未来可能出现的攻击,有一些密码学家已经成功地利用此类攻击攻破了一些密码算法。

之所以这种攻击也属于边带信息或者带外信息泄漏的一种,就是因为这种攻击并非对RSA的数学结构进行攻击,而是对RSA具体实现过程中软硬件特性所泄漏的密钥信息进行攻击,而这些信息在RSA算法本身所建立的安全信道之外,是一种经常被”忽视”的信道。在此类信道上的信息泄漏,常常可以称为边带信息泄漏或者带外信息泄漏。

知道了时间分析攻击,能量分析攻击就简单了,就是通过测量密码系统在解密一个特定密文的时候的发热量,来猜测密钥信息的方法。由于发热量的测量相对于时间来说更加不准确,而且实际情况中常常难以对系统的能量进行测量,因此一般来说这种攻击比时间攻击更难实施,效率也更低,但一旦能够实施这种攻击,仍然比暴力搜索要快若干数量级(别忘了,系统发热量虽然不能准确测量,但我仍然可以对一个密文重复测量1000000次取平均)。

为了防范时间分析攻击,一种容易想到的方法就是设法确定算法在最坏情况下所消耗的时间,然后任何一次解密,如果没有达到最坏时间,都不输出结果。这样做一个是估计最坏时间很麻烦,而且与平台相关,同时也大大降低算法效率。而且即便这种方法能够阻止时间分析攻击,也难以阻止能量分析攻击,因为等待到最坏时间的过程,毕竟跟计算过程不同,因此所消耗的能量也不同。为了防止能量分析攻击,容易想到的方法是对硬件做功率补偿控制,永远让系统消耗恒定功率。这些容易想到的方法成本都很高。

C.RSA blind算法
在解密密文c之前(这个密文c可能是攻击者精心构造出来用来刺探时间信息的密文),我们生成一个均匀分布于[0,n)之间的随机数r(必须是密码学意义上安全的随机数或者伪随机数),对r进行加密并且与c相乘得到变换后的密文s:
s = r^e * c(注意,这里往后的运算还是都要对n取模的)
(这一步很快,因为RSA加密指数e总是很小,因此这一步的速度常常比解密过程快几十倍)

这里要说一句:r是一个[0,n)之间均匀分布的随机变量,可以断言r^e以及s
= r^e * c也都是这样的随机变量,只是三者不是相互独立的。但任何一个单独来看,都仍然是一个密码学意义上安全的随机数。

这个过程涉及到公钥中的加密指数e,由于这个过程中并没有涉及到私钥中的解密指数d,因此不必担心任何信息的泄漏。

然后对s进行解密并且除以r,就可以得到明文m:(别忘了(mod n)运算!)
m = s^d / r
因为s^d / r = (r^e * c)^d / r = r^(e*d) * c^d / r = r * c^d / r = c^d = m

注意,这个过程中,s^d运算与d的值相关,让我们来分析一下是否可能会泄漏d的信息。

密文c可能是攻击者精心构造用来刺探解密指数d的信息的数据,那么攻击者只要建立了解密时间t与密文c之间的关系t=t(c),就可能以此获取私钥d的信息。

但由于s是一个密码学意义上安全的随机数,那么可以肯定的是,无论攻击者如何精心地构造了c,最终使用d进行解密的都是随机数s,于是攻击者实际上无法建立解密时间t与密文c之间的关系,解密时间t实际上是一个与密文c完全无关的随机变量s相关的时间。最后还有一个除法,这个除法所需要的时间跟r有关,但r也是一个与密文c完全独立的随机变量。

于是在整个过程中,攻击者得不到ti和ci的关系t,因此时间攻击也就无法奏效。

说实话,前面的讨论中我打了一个马虎眼。第一步s = r^e * c过程,所需要的时间与随机数r的值也有关系,因此这一步的时间可能会与随机数r的值相关。但即便这一步的时间被单独测量了,所得到的关于r的信息也是很少的,因为花费同样时间的不同r值太多了(简并度太大:D)。而且最关键的是,r值是每次系统解密的时候重新随机生成的,用过就丢,因此不能通过多次精心设计的刺探过程来积累有关某一次使用过的r值的信息(前提是r确实是一个密码学安全的随机数或者伪随机数),虽然信息可能会泄漏一点点,但无论过多长时间都无法积累到危险的程度。

Consistency, for me, is the only thing reliable to judge truth or mistake.

We can’t talk the correctness without the relationship between things. If we say something is correct, actually means it is consistent with some preset background, not means something can be correct without any precondition. Consistency is the only reliable thing for me to judge the correctness.

First, every relevant relationship must be consistent if a thing is correct. Second, there must be some relevant relationship is inconsistent if a thing is incorrect. It sounds just like some superfluous words, but I think it is just because consistency is the primitive meaning of correctness in nature language.

So the word “correct” should be the synonym of “every relevant relationship is consistent”. The word “incorrect” should be the synonym of “there must be some relevant relationship is inconsistent”.

I think, the essentiality of science is just pursuing consistency, nothing more, nothing less.

Any live logical contradiction and violation with the fact is unacceptable in science, must be solved sooner or later.

It is so simple and elegant, isn’t it?

关于电子自旋和量子态的简单科普

电子自旋与经典的自转不同。你可以在任何方向上测量电子的自旋。但是无论你选择什么方向,你测量的结果只能是两种,可以用(与该方向相关的)↑和↓来表示。在你不进行测量的时候,电子的自旋可以处于该方向的↑和↓两种状态的“相干叠加态”。

实际上,只有当你选定了一个测量方向,你才能测得电子自旋。在这个方向上,能够测得的两种状态↑和↓被称为“该方向上电子自旋的本征态”。注意,称一个状态为本征态,并不是指这个状态比其他的状态更“基本”。这个本征态之所以是本征态,仅仅是因为你选定了一个方向。所以。实际上在任何一个方向上,电子自旋都有两个本征态。一个方向上所确定的电子自旋的两个本征态,对于另外一个不同方向来说,就变成了·相干叠加态·。

如果你想要同时测量电子自旋在两个相互不同方向上的分量来确定电子“自转轴”的空间指向,在量子力学的理论框架中是绝对做不到的。你只能先在一个方向上测量,然后在另外一个方向上测量。但是如果你先在一个方向上测量,那么测量本身就会迫使电子自旋进入该方向的↑和↓两个状态之一(这通常被称为波函数的坍塌),此时如果你紧接着进行另一个方向的测量,就相当于你把先前的测量结果按照量子相干叠加的方式分解到新方向的↑和↓两个本征态上,你仍然只能测得新方向的两个本征态之一。也就是说,你想要通过测量两个方向电子自旋的方向来确定电子自旋的取向,在量子力学的框架中完全是徒劳的。

至于这个相干叠加态,简称叠加态,跟通常概率统计意义上按概率分布的多种状态是完全不同的。如果我不知道桌子底下的一个硬币是正面还是反面,我可以说这个硬币处于正面和反面的概率分别是多少多少。但这仅仅是因为我不知道硬币的状态,实际上这个硬币当然必定处于正面或者反面两种情况之一,·根本没有·处于正面和反面的某种“叠加态”上。在量子力学中,把这种由于不知道系统所处的状态而导致的多种状态按照概率的分布,叫做“混合态”,而不叫做叠加态。而把叠加态(叠加态包括本征态)叫做“纯态”,叠加态实际上是一个精确的状态,并不是多个不同状态的混合。混合态才是多个纯态按照概率分布的混合。混合态之中,各个纯态的概率之和必须是1。而任何一个纯态则可以在指定了测量方式之后,被唯一地分解到对应该测量方式的若干本征态上去,但是分解之后的各个本征态系数是复数。这些复数的模的平方和必须是1,而它们自身的和并不一定是1。例如电子可以处于(1/√2)↑ + (1/√2)↓或者(1/√2)↑ – (1/√2)↓或者(1/2)i↑ + (√3/2)↓等等。无论是叠加态还是本征态,都是纯态,他们的区别仅仅是你所选择的表达量子态的基底不同造成的,就好像建立坐标系的时候选用的基向量不同一样。实际上基向量和其他向量之间并没有本质的区别,完全可以随意选择。你可以说一个叠加态是若干个本征态的叠加,你也可以把一个本征态表示为某些叠加态的某种叠加。只不过后者由于不代表具体测量值,因而不太方便。

一旦你对量子系统选定了一个(可以实际操作的)测量手段,那么你就确定了一组本征态(相当于向量空间的一组基底)。这时候你对一个量子系统进行测量,你就只能得到这些本征态之一,而且测量操作也将立即迫使系统进入你所测得的本征态。对于一个叠加态,你的测量结果是某个本征态的概率,等于该叠加态在这个本征态上投影系数的模的平方。

principle, law, rule在学科中的含义解释

principle:原理、原则。

principle 作为原理,往往是指一个理论最基本的假定,有时候也可以叫作基本定律(basic law)。一个理论以原理为基本假设,推导出一些导出结论而构建起来。例如相对论的原理,量子力学的原理,经济学的原理。原理在一个理论中是用来解释和推 导其他内容的,其本身不能在理论内部得到解释。有时候,A理论的一些原理在B理论中可能是导出结论,而B理论的一些原理也可能在A理论中作为导出结论。特 别地,随着理论的发展,往往会出现这种情况:原来以为很基本的原理,在新理论中不再基本;而原来的导出结果,在新理论被认为更加基本而作为原理。

principle 作为原则,往往指一些先入为主的规则。例如,你做人坚决不说谎,而且根本不管这是为什么,反正就是不说谎,丝毫没得商量。这种情况下可以认为不说谎是你做 人的原则。但是这和原理的含义实际上是有差别的,一个东西作为理论的原理,在理论内部是不能得到解释的,这一点跟原则的含义相似。但这不等于这些原理不能 被解释,也不等于这些原理不能被放弃。前面说了在B理论中A理论的部分原理变成了导出结论,那么实际上B理论就对A理论的这些原理给出了解释。当理论和事 实冲突的时候,我们更相信事实,而不是原理。而原则和现实利益相互冲突的时候,一些人会选择坚持原则。有时候盲目坚持原则会带来好处,因为某些你不清楚原 因的原则并不是真的没有原因。但有时候盲目坚持原则会带来恶果,因为你可能不知道这个原则的适用情况而滥用了这个原则。

law:定律(法律这个意思我就不提了)。

law 作为定律,大部分情况应该是指通过对试验数据进行分析而得到的一些经验规律,但是却能够经受广泛严格的试验检验。例如理想气体定律,安培定律,万有引力定 律,能量守恒定律。当一个定律在某个理论框架中得到了解释,在这个理论框架中这个定律就作为一个导出结论而存在。例如,机械能守恒在牛顿理论中作为一个导 出结论。但是,能量守恒(包括机械能守恒)在热力学中变成了原理(基本定律)。现在看来,能量守恒定律是比牛顿运动定律更加基本的规律,因此在后来的理论 中往往也被拿来作为理论的原理。

rule:规律、规则。

rule作为规则,就是指制定出来的必须遵守的一些约定。例如数学推导规则,语法规则,游戏规则,交通规则等。

对 于人制定的规则,既然是人的约定,实际上就存在任意性,例如交通规则的右侧通行或者左侧通行,数学推导中使用什么符号,语法规则中的语序等。虽然有任意 性,但是也不能不做约定,否则就无法解决混乱。但是在若干都能够解决混乱的约定之间做出选择,就是比较随意的事情了。例如,为了解决人和人之间交流思想的 问题,世界上出现了大量不同的语言;为了保证交通秩序,世界上出现了许多不同的交通规则。他们都能够解决特定领域的混乱,相互间往往很难比较孰优孰劣,但 是却互不兼容。

rule作为规律,我猜其最原始的含义应该是“造物主所制定的用于指导宇宙运转的规则”,实际上也是规则。但这个规则不是 人制定的,而这个宇宙事实上却按照这个规则运转。到底是不是造物主制定的我们根本不用关心,但是作为规律,这个词的含义往往是指一个领域所研究的对象所遵 循的·事实·上的关系。例如经济规律,物理规律,化学规律。

有时候如果一个理论经过大量检验后被认为是准确有效的,我们往往也会把这个理 论的各种结论称为规律。但这仅仅是在这个理论的预言与观察结果一致的情况下。如果在某些情况下与事实不一致,那么至少在这些情况下,我们就不能再称之为规 律。如果发现某些事实没有现有理论能够解释,可以称这个地方有我们尚未发现的规律。