Archive

Archive for October, 2010

Converting from binary to integer

26 October 2010 1 comment

The following is an updated and edited version of my posts to this sage-support thread.

Problem

You have a bitstring as output by

sage.crypto.stream.blum_blum_shub

and you want to convert that bitstring to an integer. Or in general, you want to convert a bit vector to its integer representation.

Solution

Here are two ways, assuming that you want the bits in little-endian order, i.e. you read the bits from right to left in increasing order of powers of 2.

sage: version()
'Sage Version 4.5.3, Release Date: 2010-09-04'
sage: from sage.crypto.stream import blum_blum_shub
sage: b = blum_blum_shub(length=6, lbound=10**4, ubound=10**5); b
100110
sage: type(b)
<class 'sage.monoids.string_monoid_element.StringMonoidElement'>
sage: # read in little-endian order
sage: # conversion using Python's built-in int()
sage: int(str(b), base=2)
38
sage: # conversion using Sage's built-in Integer()
sage: Integer(str(b), base=2)
38

Now assume you read the bitstring as output by blum_blum_shub in big-endian order, i.e. from left to right in increasing order of powers of 2. You simply convert the bitstring to a string, reverse that string, and apply any of the above two methods.

sage: # reversing a string
sage: str(b)
'100110'
sage: str(b)[::-1]
'011001'
sage: # read in big-endian order
sage: int(str(b)[::-1], base=2)
25
sage: Integer(str(b)[::-1], base=2)
25

Or you can do as follows:

sage: b = "100110"
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b))
25
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b[::-1]))
38

Another way is to use Horner’s method. Here’s a Sage function that computes the integer representation of a bit vector read using big-endian order. A usage example is also shown.

sage: def horner(A, x0):
...       # Evaluate the polynomial P(x) at x = x_0.
...       #
...       # INPUT
...       #
...       # - A -- list of coefficients of P where A[i] is the coefficient of
...       #   x_i.
...       # - x0 -- the value x_0 at which to evaluate P(x).
...       #
...       # OUTPUT
...       #
...       # An evaluation of P(x) using Horner's method.
...       i = len(A) - 1
...       b = A[i]
...       i -= 1
...       while i >= 0:
...           b = b*x0 + A[i]
...           i -= 1
...       return b
sage: A = [1, 0, 0, 1, 1, 0]
sage: horner(A, 2)
25

As an exercise, modify the function horner to output the integer representation of a bit vector that is read using little-endian order.

Number theory & RSA public key cryptography

14 October 2010 Leave a comment

I have released version 1.1 of the Sage tutorial “Number theory and the RSA public key cryptosystem”. There is little change in terms of content. However, note that I now use the GNU Free Documentation License v1.3+ for the tutorial. Here are the relevant files you can download for your reading pleasure.

All versions of the tutorial are available from the download page on its website. For the adventurous of heart, I have also made the full \LaTeX source of the document available.

The tutorial is meant to be educational. I don’t pretend that it is complete in any way. Any suggestions and/or criticisms for improving the tutorial are more than welcome. Enjoy and happy Sage’ing.

Numbering exercises/problems using chapter numbers

9 October 2010 1 comment

To typeset a list of exercises or problems in \LaTeX, you could use the enumerate environment. By default, this would only produce numbers of the form n. where n is a positive integer. You could number an exercise using the chapter number to produce numbering of the form c.n. where c is the chapter number. Put the following macro definition in your preamble to get the chapter number to appear.

%% For listing problem sets. Each problem is numbered according to the
%% format
%%
%% chapterNumber.problemNumber.
\newcounter{problemcounter}
\newenvironment{problem}{%
  \setcounter{problemcounter}{1}
  \begin{list}
    {\thechapter.\arabic{problemcounter}.}
    {\usecounter{problemcounter}}
    \let\olditem\item}{%
  \end{list}
}

This could easily be customized to insert the section number instead of the chapter number.

Categories: documentation, LaTeX Tags: ,

Clone, configure, build and test M4RI

7 October 2010 Leave a comment

I’m new to the autotools world, so I was rather helpless when I first looked at M4RI. Say I have patched a file in M4RI. The problem now is figuring out how to configure, build, and test the patched M4RI tree. The solution below was kindly communicated to me by the lead M4RI maintainer Martin Albrecht.

$ hg clone http://bitbucket.org/malb/m4ri
$ cd m4ri/
$ autoreconf --install
$ ./configure 
$ make
$ make check

Optimized parity testing

6 October 2010 Leave a comment

To test the parity of an integer is to determine whether it is even or odd. Letting n = 132469, we can test the parity of n by computing its value modulo 2. This can be done either by using the Sage built-in mod function, the Python modulo operator %, or by using the Python bitwise operator &. The operator & is bitwise conjunction, i.e. it corresponds to multiplication over the Galois field \mathbf{F}_2 of two elements. The integer n = 132469 is odd, hence the result of parity testing via mod, %, and & should each return 1.

sage: n = 132469
sage: mod(n, 2).lift()
1
sage: mod(n, 2)
1
sage: n % 2
1
sage: n & 1
1

However, the test using the bitwise operator & is the fastest of all:

sage: %timeit mod(n, 2).lift()
625 loops, best of 3: 42.2 micro second per loop
sage: %timeit mod(n, 2)
625 loops, best of 3: 42.2 micro second per loop
sage: %timeit n % 2
625 loops, best of 3: 1.22 micro second per loop
sage: %timeit n & 1
625 loops, best of 3: 1.02 micro second per loop

The program below demonstrates how to do parity testing using C.

#include <stdio.h>

/* Parity testing using bitwise AND.
 */
static void parity_and(int n)
{
    if (n & 1)
        printf("%i is odd\n", n);
    else
        printf("%i is even\n", n);
}

/* Parity testing using the modulus operator.
 */
static void parity_mod(int n)
{
    if (n % 2)
        printf("%i is odd\n", n);
    else
        printf("%i is even\n", n);
}

int main(void)
{
    int n = 132469;
    int m = 132470;

    printf("Parity testing using modulus operator\n");
    parity_mod(n);
    parity_mod(m);
    printf("Parity testing using bitwise AND\n");
    parity_and(n);
    parity_and(m);

    return 0;
}

The output of the program is:

Parity testing using modulus operator
132469 is odd
132470 is even
Parity testing using bitwise AND
132469 is odd
132470 is even

Tools for C development

2 October 2010 5 comments

This post collects free and open source software tools that are useful when you do software development in C. For a survey of software development tools for scientific computation, see A Survey of C and C++ Software Tools for Computational Science by D.J. Worth, C. Greenough and L.S. Chin. See The Art, Science, and Engineering of Software Development by Steve McConnell for some best practices.

Lint tools

  • Cppcheck: A tool for static C/C++ code analysis.
  • Splint: Annotation-assisted lightweight static checking.

Documentation generators

  • Natural Docs: documentation generator for multiple programming languages.
  • ROBODoc
  • Sphinx: A tool that makes it easy to create intelligent and beautiful documentation.

Testing tools

See A Survey of Software Testing Tools for Computational Science by L.S. Chin, D.J. Worth and C. Greenough.

  • CUnit: Unit testing framework for C.
  • gcov: A test coverage program. See ggcov for a GUI replacement of gcov.

Profiling & debugging tools

  • DDD: Graphical front-end for command-line debuggers such as GDB, etc.
  • GDB: The GNU Project debugger.
  • google-perftools: Fast, multi-threaded malloc() and nifty performance analysis tools.
  • gprof: The GNU profiler. For a tutorial on this tool, see Profiling Tutorial: A simple program by DJ Worth, LS Chin, and C Greenough.
  • OProfile: Profiler for Linux systems, capable of profiling all running code at low overhead.
  • RATS: Rough Auditing Tool for Security.
  • Solaris Studio: Formerly Sun Studio, but is now called Oracle Solaris Studio.
  • Valgrind: Instrumentation framework for building dynamic analysis tools.

Lateral thinking: A textbook of creativity

2 October 2010 1 comment

Lateral thinking can be paraphrased as the generation of alternatives, looking beyond the adequate to obtain something better, and to free oneself from cliche patterns. The book Lateral Thinking: A Textbook of Creativity by Edward de Bono [1] offers an alternative thinking process called lateral thinking. The two thinking processes of lateral and vertical thinking can be distinguished by how they handle information. Vertical thinking is associated with logical and mathematical thinking and, as the epithet suggests, vertical thinking is used to establish and build up an idea. At each step of the way, the previous step must be logically connected to the current step. No logical error is permitted at any stage in the process of vertical thinking. Contrast that with lateral thinking whose use is in generating ideas for the sake of generating ideas. Each step is not constricted by logic for logic plays a minimal role in lateral thinking. Despite the above differences between lateral and vertical thinking, both of these thinking processes are complementary. For example, in problem solving we might first use lateral thinking to generate a variety of possible solutions and alternative ways of looking at the problem. We then use vertical thinking to establish the validity of each alternative.

Vertical and lateral thinking has a common basis in how our mind works. In chapter 1 “The way the mind works,” de Bono offers a model of the operation of the mind. Communication is the transfer of information and an efficient means of communication makes use of codes. We can think of a code as embodying a collection of information in the same way that a catalogue number completely describes a book. Knowing the catalogue number allows us to locate the book and know its content. Without knowing the code, we could still conjure up the relevant package of information by describing some part of that information. A catalogue number completely describes a book, but we also recognize a book by knowing the name(s) of its author(s) or the subject of the book. An analogous system is language where a word has its attendant rich nuances of meanings and uses. We may recognize a code heading in an environment irrespective of whether it was deposited there by purpose or inadvertence. Contrast the situation of semaphore used in the navy as opposed to biblical exegesis by means of Bible codes [2]. A code is likened to a preset pattern and to communicate with codes or preset patterns requires the build-up of a collection of patterns.

The mind is capable of making and recognizing patterns. It is a passive self-organizing system that takes no active role in how patterns are formed. We can think of the mind as an environment where bits of incoming information self-organize themselves into patterns. The fundamental twin characteristics of the passive self-organizing system that is the mind is the limited attention span and the self-maximizing tendency. Limited attention span means that the activated area at any time is a coherent area and the more easily activated an area is the more familiar it becomes. The characteristic of self-maximizing tends to integrate and assimilate incoming information into existing patterns. The self-maximizing tendency works against itself upon the arrival of an anomalous piece of information. A self-maximizing system works in tandem with the order in which information arrives for the sequence of arrival determines how information is arranged. The mind is hard-pressed to incorporate the anomaly into an existing pattern. Situations like this requires a rearrangement of existing patterns, a questioning of that which have been taken for granted, bringing into question long-held assumptions, requiring some insight as to how to handle the anomaly. Lateral thinking is adept at handling anomalies, rearranging patterns, or creating new patterns.

Thus even though one had been correct at each stage one would still have to restructure the situation before being able to proceed. … The trouble with a self-maximizing system that must make sense at each moment is that the sequence of arrival of information determines the way it is to be arranged. For this reason the arrangement of information is always less than the best possible arrangement [sic] for the best possible arrangement would be quite independent of the sequence of arrival of the pieces of information [1, p.33].

A switch over from one arrangement to another requires insight or humour. A temporary switch over gives rise to humour and a permanent switch over, insight. In a preset pattern information system, patterns tend to become ever more rigid once they are established. Any incoming piece of information tends to be assimilated into an existing pattern. Once a pattern is established, it becomes difficult to change that pattern or to reuse the information comprising one pattern in the context of another pattern. An established pattern gets ever larger. Anything that bears resemblance to a standard pattern is construed as the pattern itself, a phenomenon called “centering”. Through division the mind creates patterns. A slight divergence at one moment has lasting repercussions. The order in which information arrives plays an all too important role in how the information is used. There is a tendency to snap transition from pattern to pattern, instead of a smooth change from one to the other. Faced with a choice between two competing patterns, there is a tendency to choose one pattern and ignore the other. There is also the tendency to polarize, to move to either extremes instead of maintaining some balance between the two. “The mind is a cliche making and cliche using system” [1, p.36]. To overcome these limitations of a preset pattern information system, lateral thinking provides means for restructuring patterns, escaping established patterns, combining patterns in new ways to generate new ideas.

The mind handles information in a characteristic way. This way is very effective and it has huge practical advantages. But it also has limitations. In particular the mind is good at establishing concept patterns but not at restructuring them to bring them up to date. It is from these inherent limitations that the need for lateral thinking arises [1, p.36].

In chapter 2 “Difference between lateral and vertical thinking,” de Bono draws a clear distinction between the two modes of thinking. A precis of his argument can be summarized in the following key points:

  • “Vertical thinking is selective, lateral thinking is generative” [1, p.37].
  • “Vertical thinking moves only if there is a direction in which to move, lateral thinking moves in order to generate a direction” [1, p.38].
  • “Vertical thinking is analytical, lateral thinking is provocative” [1, p.39].
  • “Vertical thinking is sequential, lateral thinking can make jumps” [1,p.39].
  • “With vertical thinking one has to be correct at every step, with lateral thinking one does not have to be” [1, p.40].
  • “With vertical thinking one uses the negative in order to block off certain pathways. With lateral thinking there is no negative” [1, p.40].
  • “With vertical thinking one concentrates and excludes what is irrelevant, with lateral thinking one welcomes chance intrusions” [1, p.41].
  • “With vertical thinking categories, classifications and labels are fixed, with lateral thinking they are not” [1, p.41].
  • “Vertical thinking follows the most likely paths, lateral thinking explores the least likely” [1, p.42].
  • “Vertical thinking is a finite process, lateral thinking is a probabilistic one” [1, p.42].

The differences between lateral and vertical thinking are very
fundamental. The processes are quite distinct. It is not a matter of
one process being more effective than the other for both are
necessary. It is a matter of realizing the differences in order to be
able to use both effectively.

With vertical thinking one uses information for its own sake in order
to move forward to a solution.

With lateral thinking one uses information not for its own sake but
provocatively in order to bring about
repatterning [1, p.43].

In chapter 3 “Attitudes towards lateral thinking,” de Bono lists various standard objections/attitudes towards lateral thinking. These standard objections are listed below accompanied by de Bono’s responses.

  • “Although one appreciates the effectiveness of insight solutions and the value of new ideas there is no practical way these can be brought about. One can only wait for them and recognize them after they have happened” [1, p.44]. Insight comes about from rearranging existing patterns. To view insight as a chance occurrence does not explain why some people have a consistent outpouring of insights. Lateral thinking offers a process conducive to insights.
  • “Whenever a solution is said to have been reached by lateral thinking there is always a logical pathway by which the solution could have been reached. Hence what is supposed to be lateral thinking is no more than a plea for better logical thinking” [1, p.44]. Lateral thinking is a process, not a description of a result. Once a solution is known, we can with hindsight trace out a logical path from the problem to the solution. A characteristic of insights and new ideas is that once they are known they become obvious, a demonstration of how inadequate logical thinking is. If logical thinking were enough to generate insights and new ideas, we should be able to generate them by the bucket loads.
  • “Since all effective thinking is really logical thinking then lateral thinking is just a part of logical thinking” [1, p.45]. This seems to be a question of semantics. It is irrelevant whether lateral thinking is distinct from vertical thinking, or that lateral thinking is part of vertical thinking. A main point is that one understands the nature of lateral thinking. If this objection takes account of how the mind works, then it is logical to be illogical.
  • “Lateral thinking is the same as inductive logic” [1, p.46]. A basis of this objection is the distinction between deductive and inductive logic. Both deductive and inductive logic are conducive to forming patterns. In contrast, lateral thinking breaks up existing patterns in order to restructure patterns.
  • “Lateral thinking is not a deliberate way of thinking at all but a creative gift which some people have and others do not” [1, p.46]. Lateral thinking can be learnt and practiced, akin to the situation of learning and practicing mathematical skills.

Chapter 4 “Basic nature of lateral thinking” characterizes lateral thinking in its own right instead of juxtaposing it with vertical thinking. De Bono’s characterization of lateral thinking follows:

  • “Lateral thinking is concerned with changing patterns” [1, p.48].
  • “In a self-maximizing system with a memory the arrangement of information must always be less than the best possible arrangement” [1, p.48].
  • “Lateral thinking is both an attitude and a method of using information” [1, p.49].
  • “Lateral thinking is directly related to the information handling behaviour of mind” [1, p.51].

In chapter 5 “The use of lateral thinking,” de Bono provides many uses for lateral thinking. Chief among these uses are:

  • To generate new ideas.
  • For problem solving. De Bono distinguishes between three types of problems. First are problems that require the collection of more information or better techniques for dealing with information. This type of problem can be solved by means of vertical thinking. Second are problems that require no new information, but an insight restructuring of available information. The third type of problem is characterized as the “problem of no problem,” where we do not realize that there is a better arrangement than what is currently available. Both the second and third types of problems are amenable to lateral thinking.
  • For processing perceptual choice. In the first stage of information processing, information is parcelled up into packages that can be efficiently handled by vertical thinking. Instead of accepting these packages as they are, lateral thinking can be used to process the packages themselves.
  • For deliberate and unjustified periodic reassessment.
  • For preventing sharp divisions and polarizations. Lateral thinking as an attitude can prevent these.

The topic of generating alternatives is taken up in chapter 7 “The generation of alternatives.” We deliberately generate alternatives for their own sake. Even if in the course of doing so we arrive at a promising alternative, we keep on generating alternatives. As a practical routine, we could place a quota on the number of alternatives to generate. A quota should indicate the minimum number of alternatives to generate, but this quota should not prevent us from generating further alternatives.

Chapter 8 discusses the use of challenging assumptions. In solving a problem we can unconsciously bind ourselves with assumptions that are not part of the problem. Making those assumptions known and questioning them help us to see a solution.

The technique of suspending judgement is discussed in chapter 10. At each step of the way we need not judge whether something is right or wrong. We suspend judgement and go ahead with generating possible steps toward a solution.

The remaining chapters deal with practical techniques for developing and exercising skills in lateral thinking:

  • Design
  • Dominant ideas and crucial factors
  • Fractionation
  • The reversal method
  • Brainstorming
  • Analogies
  • Entry points and attention area
  • Random stimulation
  • Concepts, divisions, polarization
  • The word “po” as a means to go beyond yes and no
  • Breaking out of the domination of openness
  • Description, problem solving, design

[1] E. de Bono. Lateral Thinking: A Textbook of Creativity. Pelican Books, 1977.

[2] B. McKay. In search of mathematical miracles, accessed 22nd August 2010.

Follow

Get every new post delivered to your Inbox.