Application of the Euclidean Algorithm

Euclidean Rhythms
Fields: Number Theory and Algebra
Image Created By: Wouter Hisschemöller
Website: Wouter Hisschemöller

Euclidean Rhythms

This image shows a pattern of music rhythms generated by Euclidean algorithm. To find out the process of generating music rhythms or how it sounds like, go to section Euclidean Rhythms.

Basic Description

For more information about Euclidean algorithm, please click Euclidean Algorithm.

A More Mathematical Explanation

Note: understanding of this explanation requires: *Number Theory, Algebra

[Click to view A More Mathematical Explanation]

What can I do with Euclidean algorithm? Euclidean Algorithm is very important and fundamental in alge [...]

[Click to hide A More Mathematical Explanation]

What can I do with Euclidean algorithm? Euclidean Algorithm is very important and fundamental in algebra, in other number systems, classical mathematical problems, other applied algorithms, computer science and music.

Mathematical Application

Reducing Fractions

If we know the gcd(greatest common divisor) of the numerator and denominator, we can know if they are prime to each other or not and use the gcd to reduce fractions:

By Euclidean algorithm, we know that gcd(168, 64) = 8 as we discussed in Euclidean Algorithm.

$\frac{64}{168} = \frac{8\times8}{21\times8} = \frac{8}{21}$

$\frac{28}{63} = \frac{4\times7}{9\times7} = \frac{4}{9}$

Adding and Comparing Fractions

Simplify $\frac{7}{64} + \frac{5}{168}.$

You can actually use any common denominator and then add the two equations to simplify it, but using the smallest common denominator is the easiest way. To find the smallest common denominator, we need to find the least common multiple(lcm) of the two denominators, which is the product of a and b divided by gcd(a, b) : $lcm(a, b) = \frac{ab}{gcd(a, b)}$

Solution:

By Euclidean algorithm, we know that gcd(168, 64) = 8.

So $lcm(64, 168) = \frac{64 \times 168}{8} = 1344 \quad \quad \quad \quad \frac{7}{64}+ \frac{5}{168} = \frac{7\times21}{64\times21} + \frac{5\times 8}{168\times8} = \frac{147 + 40}{1344} = \frac{187}{1344}$

In this way, you don't need to reduce the fraction anymore because the denominator is the least common multiple of 64 and 168.

Given two fractions ($\frac{5}{64}, \frac{7}{168}$ for instance) lcm(a, b) also helps us determine which fraction is larger:

$\frac{5}{64} = \frac{105}{1344} > \frac{56}{1344} = \frac{7}{168}$

Continued Fractions

How to change a fraction into a continued fraction? Well, we need the help of Euclidean algorithm.

Let $a = b q_0 + r_0$ with $0 \leqslant r_0 < b$, then $\frac{a}{b} = q_0 + \frac{r_0}{b}$.

By analog:

$\frac{a}{b} = q_0 + \frac{r_0}{b}$

$\frac{b}{r_0} = q_1 + \frac{r_1}{r_0}$

$\frac{r_0}{r_1} = q_2 + \frac{r_2}{r_1}$

... ...

$\frac{r_{n-3}}{r_{n-2}} = q_{n-1} + \frac{r_{n-1}}{r_{n-2}}$

$\frac{r_{n-2}}{r_{n-1}} = q_n$

Do they look familiar to you? Don't they share similarities with division equations from Euclidean algorithm? Indeed, Euclidean algorithm is closely related to continued fractions.

As you've probably noticed, the second term on the right-hand side is the inverse of the left-hand side of the next equation, except in the last equation $r_{n-1}$ divides $r_{n-2}$. In that case, we can combine those equations together. Start with the first two equations:

$\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}}$

Next, move on with the third equation. Substitute $\frac{r_1}{r_0}$ with the inverse of the third equation:

$\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}} }$

Every time, the fraction $\frac{r_k}{r_{k-1}}$ could be replaced by the inverse of the next equation. Keep this process till we hit the last equation and we will eventually get a continued fraction:

$\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{q_3 + \cfrac{1}{\ddots + \cfrac{1}{q_n}}}}}$

Example:

Rewrite the fraction $\frac{168}{64}$ as continued fractions.

Apply Euclidean algorithm:

$168 = 2 \times 64 + 40$

$64 = 1 \times 40 + 24$

$40 = 1 \times 24 + 16$

$24 = 1 \times 16 + 8$

$16 = 2 \times 8 + 0$

Therefore we could rewrite the fraction above as:

$\frac{168}{64} = 2 + \cfrac{1}{1+\cfrac{1}{1 + \cfrac{1}{1+ \cfrac{1}{2} } } }$

Linear Diophantine Equations

Suppose a, b and c are integers, linear Diophantine equations take the form ax + by = c and only have integer solutions. The equations honor the Greek mathematician Diophantus around the 3rd century A.D., who was interested in finding integer solutions to various equations in his whole life. See the figure below.

An example of linear Diophantine equation.

Theorem:

The linear Diophantine equation ax + by = c has a solution if and only if gcd(a, b) divides c.

Proof:

Because gcd(a, b) divides a and b, gcd(a, b) divides ax + by for any integer x and y. Thus, assume gcd(a, b) = am + bn, where m and n are both integers, and gcd(a, b) also divides c because c = ax + by.

Therefore, c = c' gcd(a, b) = c'(am + bn) = (c'm)a + (c'n)b.

Therefore, x = c'm, y = c'n are the two coefficients we want.

We could solve for the coefficients in this way by using extended Euclidean algorithm (see the section we talked about before extended Euclidean algorithm ). If c is not the gcd nor is it a multiple of the gcd, then this equation has no solution. So Diophantine equations either have infinite solutions or no solution.

Example:

Now let's find out how to solve a linear Diophantine equation with extended Euclidean algorithm.

$348x + 126y = 6$

First, find out if it has a solution or not. Start by going through the steps of the Euclidean algorithm to show that gcd(348, 126) = 6:

Eq. 1        $348 = 2 \times 126 + 96$

Eq. 2        $126 = 1 \times 96 + 30$

Eq. 3        $96 = 3 \times 30 + 6$

Eq. 4        $30 = 6 \times 5$

Indeed, 6 is the gcd of 348 and 126. The equation has solutions.

Then solve for integers x and y.

According to Eq. 3, $6 = 96 - 3 \times 30$.

According to Eq. 2, $30 = 126 - 1 \times 96$. Substitute it into the previous equation above, and we get

$6 = 96 - 3 \times (126 - 1\times 96)$

$6 = -3 \times 126 + 4 \times 96$

According to Eq. 1, $96 = 348 - 2 \times 126$. Substitute it into the previous equation above, and we get

$6 = -3 \times 126 + 4 \times ( 348 - 2\times 126)$

$\therefore 6 = 4\times 348 - 11\times 126$

Therefore, x = 4 and y = -11.

Summary: In order to get the values of x and y, we need to keep trying to express gcd(348, 126) as an integer linear combination of 348 and 126 using equations from Euclidean algorithm step by step.

Chinese Remainder Theorem

There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?

A problem like this is called Chinese remainder problem, another classical application of Euclidean algorithm. It is posed by a Chinese mathematician, Sun Tsu, in 4th century A.D.

More mathematically, we could rewrite the Chinese remainder theorem in the following way.

Theorem:

$x \equiv a_1 \pmod{m_1}$

$x \equiv a_2 \pmod{m_2}$

$x \equiv a_3 \pmod{m_3}$

... ...

$x \equiv a_n \pmod{m_n}$

where $m_1, m_2, m_3, ... , m_n$ are relatively prime to each other or $(m_i, m_j) = 1$ for $i \ne j$. Then this system of congruences has a unique solution $mod~m_1m_2m_3...m_n$.

Notation:

1. Before we prove this theorem, we need to know the modular arithmetic:

[Show More about Modular Arithmetic][Hide More about Modular Arithmetic]

• Modular arithmetic is an abstraction of a method of counting. For example, if I tell you today is Thursday, you know that it will be Wednesday in 20 days. Because $20 = 7 \times 2 + 6$, you just need to count 6 days beginning from Friday. Mathematically, we denote: $a~mod~b = r$, when a = qb + r, where q is the quotient and r is the remainder upon dividing integers a by b. Hence, $9~ mod~7 = 2, ~ ( 9 = 7 \times 1 + 2 )$; $57~ mod~ 8 = 1, ~( 57 = 8 \times 7 + 1 )$.

• In general, if a and b are both integers and n is a positive integer, then$a~ mod ~n = b~ mod~ n$ if and only if n divides a - b. Usually, we denote it as $a \equiv b \pmod{n}$. So $x \equiv a_n \pmod{m_n}$ means $m_n$ divides $x$ and $a_n$ or $x$ and $a_n$ have the same remainder if divided by $m_n$.

• The operation of modular arithmetic is, as what you probably expect, the same as regular operations: addition, subtraction, multiplication, and division. For example: if $x \equiv 1 \pmod{n}$ and $y \equiv 2x$, then $y \equiv 2x \equiv 2 \cdot 1 \pmod{n} \equiv 2 \pmod{n}$. Most of the time, we omit $\pmod{n}$ if it is the same one in a continued equaity and just keep one at the end of this equality. So we could rewrite y as $y \equiv 2x \equiv 2 \cdot 1 \equiv 2 \pmod{n}$.

2. Let $l_k$ represents the product of all m's $m_1m_2m_3\cdots m_n$ EXCEPT $m_k$, where k is any integer that is not greater than n. For example, $l_3$ = $m_1m_2m_4m_5m_6m_7m_8$.

Proof:

$l_k = m_1m_2 \cdots m_{k-1}m_{k+1} \cdots m_n$. Thus, $l_k$ is prime to $m_k$, $(l_k, m_k) = 1$. By extended Euclidean algorithm , there exist integers $s_k$ and $t_k$, such that $s_kl_k + t_km_k = 1$. In terms of congruence, $s_kl_k \equiv 1 \pmod{m_k}.$ We assume

Eq. 5        $x \equiv a_1l_1s_1 + a_2l_2s_2 + \cdots + a_nl_ns_n$

and we are going to prove that it is correct.

Now $mod ~ m_k$ all the terms in Eq. 5, meaning that we divide the terms with $m_k$ and obtaining the remainder. We only get $a_kl_ks_k$ because$m_k$ could divide other terms, which eventually turn to 0, but not the k-th term $($ the k-th term doesn't have $m_k$, so it is not a multiple of $m_k$). Therefore according to the operation of modular arithmetic:

Eq. 6        $x \equiv a_kl_ks_k \pmod{m_k}$

Because $s_kl_k \equiv 1 \pmod{m_k}$

$x \equiv a_k \cdot 1 \equiv a_k \pmod{m_k}$.

Because k is no greater than n, Eq. 6 matches with the last equation from the description of the theorem $x \equiv a_n \pmod{m_n}$. This shows that x is, indeed, a solution to the system of congruence and we even have a formula for x, which is  :

Eq. 5        $x \equiv a_1l_1s_1 + a_2l_2s_2 + \cdots + a_nl_ns_n$.

Then we need to prove that it is the only solution to the congruence. Suppose there is another solution y.

$y \equiv a_1 \pmod{m_1}$

$y \equiv a_2 \pmod{m_2}$

$y \equiv a_3 \pmod{m_3}$

... ...

$y \equiv a_n \pmod{m_n}$

Compared with x, we will find that $x \equiv a_k \equiv y \pmod{m_k}$. Thus, $x- y \equiv 0 \pmod{m_k}$.

Then $m_k$ divides $(x-y)$, or $(x-y)$ is a multiple of all the m's.

Thus, the least common multiple(lcm) of m's divides $(x-y)$, denoted as $\left [m_1m_2m_3\cdots m_n \right ]\mid (x-y)$.

Because the m's are relatively prime, the least common multiples of all m's are actually the product of all m's, so we get $\left [m_1m_2m_3\cdots m_n \right ] = m_1m_2m_3 \cdots m_n$.

Hence, $m_1m_2m_3 \cdots m_n \mid (x-y)$ or $x \equiv y \pmod{m_1m_2m_3\cdots m_n}$ .

Here, we know that x and y are the same solution. Therefore, there is one unique solution to the congruence: $mod ~ m_1m_2m_3\cdots m_n$.

Example:

Go back to the original Chinese Remainder problem. Solve

$x \equiv 2 \pmod{3}$

$x \equiv 3 \pmod{5}$

$x \equiv 2 \pmod{7}$.

___________________________________________________________

The famous Chinese remainder problem: There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number? This figure shows that 23 is one possible answer.

Since 3, 5 and 7 are pairwise relatively prime, there is only one solution $mod~3\times5\times7$, which is $mod~105$.

As we did in the proof, we need to construct the formula for x:$x \equiv a_1l_1s_1 + a_2l_2s_2 + a_3l_3s_3$.

We know $a_1 = 2, a_2 = 3$ and $a_3 = 2$, so let's find $l_k$ and $s_k$.

$l_1 = m_2 \times m_3 = 5 \times 7 = 35.$

$l_2 = m_1 \times m_3 = 3 \times 7 = 21.$

$l_3 = m_1 \times m_2 = 3 \times 5= 15.$.

Because $l_1s_1 \equiv 1\pmod{m_1}$

Therefore $35 s_1 \equiv 1\pmod{3}$

To fin the value of integer $s_1$, try each integer starting with 1 until we get the remainder 1 when we divide ($35 s_1$) by 3.

We find that $\quad s_1 = 2$.

Similarly, $21 \times 1 \equiv 1 \pmod{5}, 15 \times 1 \equiv 1 \pmod{7}$. We find that $s_2 = 1, s_3 =1$. Thus,

$x \equiv a_1l_1s_1 + a_2l_2s_2 + a_3l_3s_3$

$x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 \equiv 233$

$233 = 105 \times 2 + 23$, therefore $233 \equiv 23 \pmod{105}$.

$233 = 105 \times 1 + 128$, therefore $233 \equiv 128 \pmod{105}$.

Therefore, the number is 23 or 128. See the right figure to check the smaller number 23.

Gaussian Integers

Gaussian integers are complex numbers a + bi, where a and b are real integers and i is the imaginary integer. The formal set of Gaussian integers is

$Z[i] = \left\{ a + bi \mid a, b \in Z \right\}$.

Gaussian integers satisfy the analog of Fundamental Theorem of ArithmeticEvery integer has a unique prime factorization (up to reordering factors and multiplying by +1, -1). For example, factorize 180 and any one could get $180 = 2^2 \times 3^2 \times 5.$ There is no other way to prime factorize 180. by applying the analog of the Euclidean algorithm. In other words, a Gaussian integer has a unique factorization with certain prime factors multiplied together just as a natural integer does.

To prove that natural integers satisfy the fundamental theorem of arithmetic, we use Euclidean algorithm to find the gcd and list all the prime factors. We use the same method to show unique factorization of Gaussian integers. Please note, Euclidean algorithm is not the only effective way to prove this property, but it is the most convenient method.

First, denote $\alpha, \beta$ as two Gaussian integers just as we denote a and b for two normal integers. Then, we start the process as we did for Euclidean algorithm: subtracting the smaller integer from the bigger one and obtaining a remainder that is strictly smaller than its predecessor from each step until it is 0. The general equation is the same,

$r_{n -2} = k_{n - 1}r_{n -1} + r_n$

lattice points in the complex plane

but the quotients and remainders are complex numbers, starting with$r_{n - 2}= \alpha, r_{n - 1} = \beta$. You can treat those complex numbers separately as two parts, the real part and imaginary part. Then, we round the real and imaginary parts to the nearest integers. For example: $\alpha = 2 + 3i, \beta = 1 + i$.

$\frac{a}{b} = \frac{2 + 3i}{1+ i} = \frac{(2 + 3i)(1 - i)}{(1+ i)(1 - i)} = \frac{2 + 3i - 2i - 3i^2}{1 - i^2} = \frac{2 + i + 3}{1 + 1} = \frac{5 + i}{2} = \frac{5}{2} + \frac{1}{2} i$.

By rounding $\frac{5}{2}$ to $2$ and $\frac{1}{2}$ to $0$, we know that the quotient of $\frac{a}{b}$ is $2 + 0\times i = 2 + 0 = 2$. Thus, the remainder is $2 + 3i - (1 + i)\times 2 = i$. Repeat this step by applying Euclidean algorithm in this way and we will get the gcd($\alpha, \beta$), which is the last nonzero remainder. Note that there is going to be four greatest common divisor of $\alpha$ and $\beta$ up to multiplication by +1, - 1, + i, - i.

For normal integers, it is easy to know which one is bigger. How do we compare Gaussian integers to see which one is bigger and which one is smaller when they are complex numbers? Graphically, we represent Gaussian integers with lattice points in the complex plane (a, b). We take the norm of every Gaussian integer $\left\vert Z \right\vert = \sqrt{a^2 + b^2}$, converting complex numbers to normal integers. See the right figure. The norm of the remainder decreases after each step of the Euclidean algorithm, meaning that it is getting closer to the origin. Therefore, we compare the distance from the point to the origin to see which Gaussian integer is smaller.

We can solve other applications and problems of the Euclidean algorithm for Gaussian integers as well, not only for normal integers. Applications like Chinese remainder theorem and linear Diophantine equations we discussed just now also work for complex numbers.

Musical Application

Euclidean Rhythms

In addition to those applications of various mathematical problems and computer science, Euclidean algorithm could be used to generate a large number of traditional musical rhythms efficiently.

Generally, binary sequences are used to represent musical rhythms. Each bit is considered as one unit of time; a one bit “x” means an onset of a note whereas an unaccented note “.” means a silence. Given a certain amount of notes, we will get a pattern if we distribute the notes as evenly as possible in a certain period. For example: assume that the time interval is 12 and there are four notes to be played, then this is how we note them:

x . . x . . x . . x . .

This is a very basic pattern since it gives you one note in every three steps. What if the time interval could not be divided exactly? Let’s say we want to play 5 notes during the time interval 12 instead of 4. Since $12 - 5\times2 = 2$. First, we are going to start with a sequence of putting the same notes together:

x x x x x . . . . . . .

Then place a period after each x, which leaves 2 periods at the end:

[x . ] [x . ] [x . ] [x . ] [x . ] . .

We now have five paired bits “x .” and a remainder of two single bits each. Next, put the remaining 2 periods after each “x .” sequence:

[x . . ] [x . . ] [x . ] [x . ] [x . ]

We now have two sequences of bits “x . .” and a remainder of three paired bits "x . " . Next, put the remaining 3 bits after each “x . .” sequence:

[x . . x . ] [x . . x . ] [x . ]

This gives us only one remainder of “x . “ with two sequences of bits “x . . x . ". Although we could continue the distribution by putting “x . ” in the middle of “x . . x . ” and “x . . x . ”, it doesn’t matter because the sequence is cyclic (according to Bjorklund’s stopping rule). Therefore, the final sequence of 5 notes in an interval of 12 is:

x . . x . x . . x . x .

Did you find Euclidean algorithm lying in this process? When applying the Euclidean algorithm, we basically try to subtract the smaller number from the greater one again and again. The remainder is subtracted from the smaller number each time, generating a new remainder smaller than the quotient. We stop until the new remainder is zero. Let's go back to the process of finding a certain pattern of musical rhythms we did just now. When we pair up the 5 x’s and 7 periods and leave the two periods alone, we are doing the same thing as subtracting 5 (smaller number) from 12 (bigger number) twice and obtaining a remainder 2. This process mentioned above is actually called Bjorklund’s algorithm named after its creator. Bjorklund’s algorithm has the same principle and structure as Euclidean algorithm, so we now usually call these rhythms Euclidean rhythms.

Try this pattern by knocking on the table and you will probably find that it is not so regular compared with patterns whose notes divide evenly into the interval. Combine several different patterns to find their own beauty of showing unique musical rhythms. Go to Wouter’s website to generate your own rhythms with a cool flash application or watch the video of some beautiful rhythms Wouter has made!

RSA Algorithm and Modular Multiplication Inverse

RSA algorithm is invented by and named after Ron Rivest, Adi Shamir and Leonard Adleman in 1977. It is a widely used public key algorithm for encryption and digital signatures. It gets its security from integer factorization.

RSA

Operation

RSA algorithm has three steps: key generation, encryption and decryption. See the right figure.

Key Generation

We need a public key and a private key to do RSA algorithm. A public key, used for encrypting messages, is known to everyone. A private key, used for decrypting messages, is only known to the consignee. Messages encrypted with the public key can only be decrypted using the private key. This key generation is performed a single time for each person with the public and private keys.

1. Pick any two different prime integers: $p, q$.
2. Get the modulus $n$: $n = p \times q$.
3. According to Euler's totient function, we have $\phi (n) = (p - 1) \times (q - 1)$. It is because $n$, the product of $p$ and $q$, is bigger than $\phi(n)$ and it is prime to $n$ because prime numbers, $p$ and $q$, have no common positive factors with $p - 1$ and $q - 1$ other than $1$.
4. Take any integer $e$, such that $gcd(\phi(n), e) = 1$ where $1 < e < \phi(n)$, which means that $e$ and $\phi$ are relatively prime. Now $e$ is the public key component. $(n, e)$ is the public key, used for encryption.
5. Let $d = e^{-1} mod~\phi(n)$. It is usually found by extended Euclidean algorithm, which we will talk about in the next section. Now $d$ is the private key component; you cannot give it to the public. The private key is $(n, d)$, used for decryption.

Imagine you have the public key and private key now. You only give the public key to your friend A and A wants to send a secret message to you. This is what A should do.

Encryption

1. Turn the message into an integer $m$ with $0 < m < n.$
2. Compute $t$, where $t = m^e ~ (mod~n).$
3. $t$ is the encrypted message A gives to you. If you want to know what A wants to tell you, use the private key $(n, d)$ to decrypt the code.

Decryption

1. Compute $m$, where $m = t^d ~ (mod~n).$
2. You are able to recover the original message $m$ now. This is the RSA algorithm.

Too hard to understand? No worries! There is going to be an example later.

RSA and extended Euclidean algorithm

This will give you a better understanding of how important extended Euclidean algorithm means to RSA algorithm. Modular multiplicative inverse, used to get the value of the private key, is an essential step in RSA, and extended Euclidean algorithm helps us solve modular multiplicative inverse.

How should we get d using extended Euclidean algorithm?

$d = e^{-1} mod~\phi(n)$

Here, it is complicated to solve the inverse of e directly, so we apply modular multiplicative inverse. The modular multiplicative inverse of an integer a modulo m is an integer x such that $a^{-1} \equiv x ~(mod~m)$. This is equivalent to $a a^{-1} \equiv a x \equiv 1~(mod~m)$.

[show more][hide]

( Note that the sign $\equiv$ means equivalent. When terms on both sides are modulo m, the sign $\equiv$ has the same function as the equal sign $=$. To help you understand better about modular multiplicative inverse, we can rewrite those equations above, though mathematically inappropriate, as:

Because $a^{-1} = x, a^{-1} a = 1,$ so $a x = 1.$ )

In this case, denote $x$ as the remainder of $e^{-1}$ modulo m, such that $e^{-1} \equiv x~(mod~\phi(n) )$, so

$d \equiv e^{-1} \equiv x~mod~\phi(n)$.

Now we just need to know $x$'s value to get the value of $d$. According to modular multiplicative inverse, $e^{-1} \equiv x~(mod~\phi(n) )$, hence

$e e^{-1} \equiv ex \equiv 1~(mod~\phi(n)).$

By the definition of congruence, it means that we divide $ex$ with $\phi(n)$ and get a remainder 1. This could be noted as

$ex - \phi(n) y = 1$ where $x$ and $y$ are integers.

Recall that $e$ and $\phi(n)$ are coprime integers, so $gcd(e, \phi(n)) = 1$. Therefore,

$ex - \phi(n)y = gcd(e, \phi(n)).$

Recall that our goal is to find the value of $x$. Does this equation look familiar to you? Yes, it is in the form of Bézout's identity. In section extended Euclidean algorithm, we know that extended Euclidean algorithm can solve for the two coefficients x, y of Bézout's identity:

$ax + by = gcd(a, b)$.

Solve $ex + \phi(n) (- y) = gcd(e, \phi(n))$ for$x$ using extended Euclidean algorithm, and then we will know the value of d. Now we can tell that extended Euclidean algorithm is very important for RSA algorithm.

Security

RSA algorithm is pretty secure. If people want to attack RSA, they have to fix the problem of factoring large numbers and the RSA problem. We won't talk about these two problems in detail, but what is worth mentioning is that full decryption of the RSA ciphertext is infeasible because there hasn't been an efficient way of solving the two problems so far.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

About the Creator of this Image

As he said in his webpage, Wouter Hisschemöller is interested in lots of different aspects of audio, music and (ActionScript) programming: Manipulating existing sounds (like samplers do), generating new sounds (like synthesizers), capturing and storing musical data (as used in composition, sequencers and MIDI) etc.

References

[1] Loy, Jim. Euclid's Algorithm. Retrieved from http://www.jimloy.com/number/euclids.htm.

[2] Artmann, Benno. (1999) ‘‘ Euclid-the creation of mathematics.’’ New York: Springer-Verlag.

[3] Weisstein, Eric W. Euclidean Algorithm. From MathWorld--A Wolfram Web Resource. Retrieved from http://mathworld.wolfram.com/EuclideanAlgorithm.html.

[4] Klappenecker, Andreas. Euclid's Algorithm. Retrieved from http://faculty.cs.tamu.edu/klappi/alg/euclid.pdf.

[5] Wikipedia (Linear Diophatine Equation). (n.d.). Linear Diophantine Equation. Retrieved from http://en.wikipedia.org/wiki/Linear_diophantine_equation.

[6] W. H. Freeman and Company. The Euclidean Algorithm and Linear Diophantine Equations. Retrieved from http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/euclid.html.

[7] Gallian, Joseph A. (2010) Contemporary Abstract Algebra Seventh Edition. Belmont: Brooks/Cole, Cengage Learning.

[8] Bogomolny, Alexander. Chinese Remainder Theorem. Retrieved from http://www.cut-the-knot.org/blue/chinese.shtml.

[9] Ikenaga, Bruce. The Chinese Remainder Theorem. Retrieved from http://marauder.millersville.edu/~bikenaga/numbertheory/chinese-remainder/chinese-remainder.html.

[10] Wikipedia(Gaussian Integer). (n.d.). Gaussian Integer. Retrieved from http://en.wikipedia.org/wiki/Gaussian_integer.

[11] Toussaint, Godfried. The Euclidean Algorithm Generates Traditional Musical Rhythms. Retrieved from http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf.

[12] Hisschemöller, Wouter. Euclidean Rhythms. Retrieved from http://www.hisschemoller.com/2011/euclidean-rhythms/comment-page-1/#comment-4509.

[13] Voytko, Jake. Why Does RSA Work? Retrieved from http://www.jakevoytko.com/blog/2008/01/06/why-does-rsa-work/#totient.

[14] Wikipedia(RSA). (n. d.). RSA. Retrieved from http://en.wikipedia.org/wiki/RSA.

Future Directions for this Page

1. Application about knot theory.
2. Anything you think necessary for this page.
   

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.

  [[Description::This image shows a pattern of music rhythms generated by Euclidean algorithm. To find out the process of generating music rhythms or how it sounds like, go to section  Euclidean Rhythms.|]]