In the first post on greatest common divisor we saw that is the largest positive integer such that and . There are in fact multiple ways of characterizing the GCD of two integers. In this post I will present another way of looking at GCD. This characterization says that is the least positive integer that is a linear combination of and , i.e. a number for . The proof uses the well-ordering property which says that every non-empty subset of positive integers has a least element (this can be taken as an axiom of the integers). The proof will also use the division algorithm and facts about divisibility. Here is the theorem:
Theorem: The greatest common divisor of the integers and , not both zero, is the least positive integer that is a linear combination of and .
Proof: Suppose is the least positive integer such that for some integers . We know that the set of the set of positive integers is nonempty because we may take either or , so our exists by the well-ordering property. By the division algorithm we have that for some integers where , and so
So is a linear combination of and but . If this would contradict our assumption that is the least such positive integer, so it must be that case that . So in fact , so . Similarly we may show that . This shows is a common divisor of and . It remains to show it is the greatest common divisor. Suppose and and . Then so , but this implies a contradiction. So is indeed the greatest common divisor.
In sage the
xgcd(a,b) command gives a tuple with three entries:
(d,m,n) where as in the proof above.
The Sieve of Eratosthenes is the classic example of a number sieve. But before explaining this algorithm, here is a particularly elegant description of sieve theory by Dr. Terrance Tao(blog):
The idea is to try to uncover the primes as a set in aggregate. The primes you can think of as some sort of sculpture buried inside the integers. So the natural numbers: 1,2,3,4,5… you can think of as some sort of block of granite and you’re trying to carve out the primes out of this block of granite. So what you do is you take this big mallet and you’re gonna wack off big chunks off of this granite sculpture and then after a while you take away your mallet and you take a chisel and you chisel off some smaller pieces and then you put away your chisel and you take a needle and make little tiny adjustments, and then eventually you get the primes.
The sieve of Eratosthenes is an algorithm for finding all of the prime numbers up to a given positive integer . Here is the algorithm:
- List all numbers (one is not a prime)
- Starting with the first element of the list, , remove all multiples of from the list.
- Move to the next element of (modified) list and remove all multiples of that number from the list.
- Repeat this process until all multiples of are removed from the list.
- The final list contains all the primes less than .
The reason we only need to check up to , follows from the fact that every number up to and including has prime factors not exceeding . For suppose were composite, then for . If then , a contradiction. Thus we only need to remove numbers from the list with divisors (are multiples of) numbers up to .
What makes this idea so good is that each time the list gets smaller and so on each iteration you need to check less and less numbers, analogous to Dr. Tao’s description of sculpting a block of granite. On the first iteration you hit the block with a large mallet by removing all multiples of two, half of the numbers in the list. Subsequent iterations involve knocking off relatively smaller chunks of numbers.
Now for some code.
The general starting point for cryptography is to consider a person Alice who wants to send a secure message to another person Bob. First Alice writes out her message, called the plaintext. Then she encrypts the message to produce the cyphertext. She send this to Bob who subsequently decrypts it to reveal the plaintext. We may also suppose the existence of an eavesdropper named Eve. She may have various goals such as decrypting a single encrypted message, or to discover the encryption/decryption key in order to read all future messages. Maybe Eve wants to communicate with Bob as if she were Alice.
There are four main ways Eve might be able to attack the secure communication system between Alice and Bob.
- Cyphertext-only: Here Eve only has access to cyphertext that she intercepted.
- Known-plaintext: Here Eve has access to cyphertext as well as the corresponding plaintext, called the crib.
- Chosen-cyphertext: Eve is able to create an arbitrary string of cyphertext and decrypt using an unknown decryption key it and find the corresponding plaintext.
- Chosen-plaintext: Where Eve can make an arbitrary string of plaintext and encrypt it with an unknown encryption key to find the cyphertext.
Classical cyphers were vulnerable to these types of attacks but more modern cyphers attempt to be resistant to all of them. I will refer back to this list in future posts on specific cyphers.
Two’s complement is a way of writing signed integers, that is both positive and negative, using binary digits. This notation simplifies computer arithmetic as we will see. For an integer such that , its two’s complement is written using bits as follows. If is positive the leftmost bit is and the remaining bits are the binary expansion of . If is negative the leftmost bit is and the remaining bits are the binary expansion of .
Example: and .
Here is some sage code to test this out:
Proposition: If is an integer with two's complement representation , then
Proof: If then , so
Otherwise we have trivially that
Proposition: Given the twos's complement representation of an integer , to find the two's complement representation of just flip the bits and add 1. In other words, .
Proof: Clearly we must flip the first bit to change the sign of the number. If is positive then we have
One way of interpreting this equation is that if 's two's complement representation has bits, then the first is zero, and the remaining bits are either or . The bits are what constitute . If we take all the remaining bits and flip them on then we get Thus if we flip the bits in the two's complement of then we will get , which is one less than what we want. So just add one and we get the two's complement of . Now if then we have the equation
Using the same logic as above we see that the method still works.
I have written some code to add two numbers in arbitrary bases with arbitrary digits. Scroll to the bottom to perform your own additions.
For more information on integer representation read this post.
The most common bases to work with in computing are 2 (binary), 8 (octal), 10 (decimal), and 16 (hexadecimal). In particular it is very easy to convert between 2 and 8 or 2 and 16.
Recall that an octal number is a string consisting of the digits . A number in octal is written as such:
Now each octal digit consists of at most three bits (binary digits), so we make the following conversion table:
So to convert an octal number to binary just replace each octal digit with the three corresponding binary digits. Conversion between binary and hexadecimal is similar except each hex digit corresponds to four bits. Here is the conversion table:
In general, to convert between base- and base-, make a conversion table where every base- digit is represented as an -digit base- number. Then substitute the numbers in the table to make the desired conversion.
Converting between various number bases is easy in sagemath:
SageMath is an open-source mathematics software package that has many cool features. I like SageMath because it is all open-source. In fact it is an amalgam of many other open-source software packages. One feature is called SageMathCell and it allows for embedding a code box directly into a website which can then be executed and the output displayed. This is just what I have been looking for. I look forward to using this extensively in my future blog posts.
Here is an example:
Here is another:
When the “Evaluate” button is pressed, the code is sent to the SageMath servers and executed, and the output is sent back to the website. It is possible to set up your own server, which will be a fun project for me in the next few months.