Examples of mathematics

(This is the theory behind the ‘Lock Aspect Ratio’ feature.)  Suppose that the user has selected a display region centred on point (midA, midB), with width displayWidth and height displayHeight. Suppose that the viewing window is bitmapWidth pixels wide and bitmapHeight pixels tall. Then we can compute the number of display units per pixel in each direction thus:

    unitsPerPixelX = displayWidth / bitmapWidth

    unitsPerPixelY = displayHeight / bitmapHeight

If unitsPerPixelX is less than unitsPerPixelY, then to preserve the aspect ratio while still showing all of the selected region we must widen the display region so that unitsPerPixelX = unitsPerPixelY. We do this by setting:

     displayWidth = unitsPerPixelY * bitmapWidth

so the display range on the horizontal axis will be midA ± (unitsPerPixelY * bitmapWidth / 2)

If unitsPerPixelX is greater than unitsPerPixelY then we adjust the height in a similar manner.

The Earth Orbit demo renders the earth by wrapping a standard two dimensional Mercator-projection topographical map around a pseudo-spherical three dimensional DirectX object (similarly for the moon).  The demo shows the earth's axis inclined at its real-world value of 23.5° to the ecliptic (and the moon at about 1.5° to its orbital plane).  This is done by supplying appropriate vectors to the DirectX CreateWrap() function.  Here's how:

Suppose that the centre of the earth is located at (x, y, z) = (0, 0, 0)  (all vectors are relative to the earth's reference frame).  Suppose that the reference frame is oriented so that (0, 1, 0) is the "up" direction (this is the way we normally visualise frames).  If we gave our wrap an "up" direction of (0, 1, 0) then the North Pole would be at 90° to the ecliptic - no good.  To get the correct vector, imagine a right angled triangle with a horizontal of length 1 and adjacent angle of 67.5° (i.e. 90° - 23.5°).  You can see that the vertical would have a length of tan(67.5°) (since tan(67.5°) = [length of vertical] / [length of horizontal]).  So when calling CreateWrap() we supply an "up" direction of (x, y, z) = (1, tan(67.5°), 0) (since this is a two-dimensional problem we don't need the z dimension).

 

To cut a long story short, RSA encryption and decryption are done by computing ab mod c, where a is the (encrypted or plaintext) message, c is a special number that is known to all parties (c > a), and b is another special number that is either the public or private key (depending on whether a is encrypted or decrypted).  The trouble is that ab will usually be an incredibly big number that even a computer will not be able to handle in a timely fashion.  Fortunately, there is a trick that enables us to compute ab mod c without needing to compute ab.  In this page we will look at the theory, but you can see the source code for my implementation of a simple 32-bit version here.

The first thing to recognise is that xy mod c = ( x mod c )( y mod c ) mod c.
For example, consider x = 17, y = 8, c = 6:

xy mod c = 136 mod 6 = 4

x mod c = 17 mod 6 = 5

y mod c = 8 mod 6 = 2

( x mod c )( y mod c ) mod c = 5 * 2 mod 6 = 10 mod 6 = 4

Now, let’s break b down into its binary representation.  For example, consider b = 23:

23 = 16 + 4 + 2 + 1 = 2⁴ + 2² + 2¹ + 2⁰ (ie the binary representation is 10111₂)

So a²³ = a^{2^4 + 2^2 + 2^1 + 2^0} = a^{2^4}.a^{2^2}. a^{2^1}. a^{2^0}

Thus a²³ mod c = a^{2^4}.a^{2^2}. a^{2^1}. a^{2^0} mod c

= a^{2^4} mod c . a^{2^2} mod c . a^{2^1} mod c . a mod c

This allows us to deal with each ‘bit’ separately.  To handle bit 2, for example, we must compute a^{2^2} mod c. We can also see that we can ignore the bits that are zero.

Now a^{2^2} = (a²)²

Once again we can break this down, because a^{b^d} mod c = ((a^b mod c) ^d) mod c, so

(a²)² mod c = ((a² mod c)²) mod c

We can handle this as long as we can handle the square of any number < c.

 Now look at a^{2^3} mod c = ((a²)²) ² mod c.

This can be rewritten as (((a² mod c)²) mod c) ² mod c

This includes the term ((a² mod c)²) mod c that we already calculated when handling (a²)², and we can see a pattern emerging:

• To handle the 0^th bit, we compute (a mod c).  Call this residual₀
• To handle the 1^st bit, we compute (residual₀² mod c).  Call this residual₁
• To handle the 2^nd bit, we compute (residual₁² mod c).  Call this residual₂
• To handle the n^th bit, we compute (residual_n-1² mod c).  Call this residual_n

 Then a^b mod c = residual_i . residual_j . residual_k … mod c,

where residual_i , residual_j , etc are the residuals for the non-zero bits of b.  Computing the residuals is an O(log₂ b) operation, and multiplying them together is another O(log₂ b) operation.