Modern Computing for Mathematicians (Math 587)
Assignments

Spring Semester, 2009

Assignments are listed in reverse chronological order, i.e., most recent first, and labeled by the date due.

Tue., May. 5:

Written Assignment No. 5 (PDF for printing —classical HTML for terminal window browsing) is due.

Bring wrap-up questions

Thu., Apr. 30:

Review the Sage code for functions related to the use of the El Gamal technique with an elliptic curve over a prime field ${\mathbf{F}}_p$. Note, however, that the task of writing functions for the actual encryption and decryption of point sequences is left to the reader.

1. Write Sage functions for encrypting and decrypting point sequences on an elliptic curve over ${\mathbf{F}}_p$. For the purpose of being able to compare answers use the provided function randfake, rather than an actual random number generator, with first argument the number of points on the curve and second argument the sequence-postion (beginning with $1$) of the current point in the sequence.

2. With the curve $y^2=x^3+43x+13$ over the prime field of size $1283$ use the provided function codestopoints with $10$ “tries” to generate a point sequence corresponding to the list of ASCII codes $$\left[1,2,3,4,\dots ,126,127\right]\text{.}$$ What is the smallest number of “tries” that will provide a list of $127$ points for this code sequence?

3. Test your functions by encrypting and then decrypting the point sequence obtained in the previous exercise with $10$ “tries” on the curve $y^2=x^3+43x+13$ in the field ${\mathbf{F}}_{1283}$. For this purpose use as base point $b=\left[0,36\right]$ and as secret key the integer $97$.

Schedule for this class:

Time Presenter Topic 4:15 A. L. Singular 4:40 W. H. elliptic El Gamal

Tue., Apr. 28:

Read about the use of El Gamal on Elliptic Curves (PDF for printing —classical HTML for terminal window browsing).

A message encrypted by a list of pairs of points on an elliptic curve is waiting for you at the url

http://math.albany.edu/pers/hammond/course/mat587s2009/assgt/psrt .

The El Gamal key for decoding it is 950.

1. What sequence of points on the curve was encoded?

2. What is the content of the message?

3. Re-encrypt the message relative to $\left[1,338\right]$ as base point using the public key determined by the same secret key, and then decode that.

Note: In Sage the function chr() is inverted by the function ord(). See the Python documentation about built-in functions. See also unichr().

Schedule for this class:

Time Presenter Topic 4:15 A. M. Texmacs 4:40 J. Y. R 5:05 W. H. elliptic El Gamal

Thu., Apr. 23:

Read this primer on group theory in Sage.

What built-in function in Sage will, for a given pair $\left(a,b\right)$ of integers, produce integers $\left(r,s\right)$ such that $\gcd \left(a,b\right)=ra+sb$?

Write a function for Sage that, given a list of integers representing a finite continued fraction, returns the rational number having that continued fraction expansion without using a built-in function. What built-in function can be used for the same task?

Schedule for this class:

Time Presenter Topic 4:15 B. S. Texinfo 4:40 W. H. Sage

Tue., Apr. 21:

Read the third group of 3 sections of the Guided Tour in the online SAGE Tutorial.

Review for the purpose of comparison code for sifting primes (also available as PDF or DVI) smaller than a given bound in the languages of (1) gp and (2) sage.

Schedule for this class:

Time Presenter Topic 4:15 W. K. Octave 4:40 M. G. Kash 5:05 W. H. Sage

Thu., Apr. 16:

Read the second group of 3 sections of the Guided Tour in the online SAGE Tutorial.

Schedule for this class:

Time Presenter Topic 4:15 postponed   4:40 J. P. Maxima 5:05 W. H. Sage

Tue., Apr. 14:

Read the first 3 sections of the Guided Tour in the online SAGE Tutorial.

Schedule for this class:

Time Presenter Topic 4:15 A. B. Open Office math 4:40 K. D'A GAP 5:05 W. H. Sage

Tue., Apr. 7:

Written Assignment No. 4 (PDF for printing —classical HTML for terminal window browsing) is due.

Updated student presentation schedule (PDF for printing —classical HTML for terminal window browsing).

Thu., Apr. 2:

The GELLMU Project offers the use of LaTeX-like markup to write for an SGML document type. Begin to become familiar with the Manual (also available as PDF or DVI or classical HTML) and the Introductory User's Guide to Regular GELLMU (also available as PDF or DVI or classical HTML). My honors calculus notes on the Gamma function provide an example. The following files are in the production chain: generalized LaTeX source, equivalent SGML, which should have line-by-line alignment with the source, under this SGML DTD, XML shadow under this XML DTD, spawned XHTML + MathML, spawned LaTeX, and PDF made from the spawned LaTeX.

Re-do the exercise of the previous assignment by preparing a single “regular” GELLMU source file and then, on chern, run the command gellmu on that file.

Demo files used in class on March 31: ghtml (HTML) is in the open directory glm/. ghack4 (hack) is in the open directory hack/. gamma (“regular”) is in the open directory http://math.albany.edu/pers/hammond/course/calcnotes/.

Updated student presentation schedule (PDF for printing —classical HTML for terminal window browsing).

Tue., Mar. 31:

Begin to become familiar with Mathematical Markup Language (MathML). Note that under the current specification, incorporated in an XML document type definition, MathML may be included only in the XML form of HTML and then only using the MathML namespace. (The online form of this assignment sheet is an example.)

1. What elements in the document type definition for hack have yet to receive suitable treatment in the sgmlspl script hack/hack2html.pl? Add text to your copy of hack/hack3.sgml so that these are exercised, and extend the code in the sgmlspl script to accommodate them.

2. Prepare two small documents, one PDF and the other XHTML+MathML that typeset the formula $$\frac{\pi }{2}={\int }_0^1\frac{dx}{\sqrt{1-x^2}}$$ in a display (as here). Be sure to use (on chern) the program sp-utf8-xmlvalid to validate the XHTML+MathML

Updated student presentation schedule (PDF for printing —classical HTML for terminal window browsing).

Thu., Mar. 26:

Examples of SGML/XML processing based on sgmlspl may be found in the GELLMU distribution as well as in the sgmlspl distribution from CPAN that was referenced in the previous assignment.

1. hack/hack2.sgml contains the document instance associated with the previously considered hack/hack1.sgml but with a reference in its prolog to the separate (and expanded) document type definition hack/hack.dtd. What differences do you find in the ESIS output obtained by parsing hack1 and hack2 with onsgmls?

2. Morph the separate document type definition hack/hack.dtd into an XML document type definition shadowing it but using lower case names.

3. Write an sgmlspl script for translating documents under hack/hack.dtd to an XML document type shadowing it but using lower case names.

   1. Use this script to translate hack/hack2.sgml to the XML shadow document type.

   2. Use the program sp-xmlvalid found on chern (or on itsunix) to validate your XML version of hack2 after making sure that the XML version has a SYSTEM reference in its prolog to your XML document type definition.

   3. What modifications would be needed to your sgmlspl script for translation to HTML so that it can be used with your XML version of hack2?

Tue., Mar. 24:

1. Read about the use of sgmlspl for translating SGML (or XML) documents. There is also a chapter on sgmlspl in The LaTeX Web Companion.

2. Use sgmlspl (for example, on chern) with the script hack/skel.pl (from the sgmlspl distribution) to create a skeleton sgmlspl script for translation of the SGML document hack/hack1.sgml.

3. Fill in the skeleton script to morph it into an sgmlspl script for translation of hack1.sgml to an HTML document.

Thu., Mar. 19:

Written Assignment No. 3 (PDF for printing —classical HTML for terminal window browsing) is due.

student presentation (PDF for printing —classical HTML for terminal window browsing) schedule.

Tue., Mar. 17:

Student Presentation Topic Auction

Thu., Mar. 12:

Use gp-2.3 for the following:

1. For the curve $y^2+y=x^3+x^2$ compute the points $kA$ for $2\le k\le 10$ when $A$ is the rational point $A=\left[0,0\right]$.

2. Determine the isomorphism class of the group of points on the curve $y^2=x^3-1$ in the field ${\mathbf{F}}_p$ for the following values of the prime $p$: $11,13,37,47,61,107,109$.

Some of the auxiliary routines in code/ell may be helpful.

Tue., Mar. 10:

Continue reading about the arithmetic on an elliptic curve. Use the native routines available in gp-2.3 to perform the following operations in the arithmetic of the elliptic curve $y^2=x^3-7x+10$:

1. $\left[-1,4\right]+\left[2,2\right]$

2. $\left[5,10\right]-\left[3,4\right]$

3. $6·\left[1,2\right]$

Thu., Mar. 5:

Begin to become familiar with arithmetic on an elliptic curve by looking over these items:

1. Wikipedia article

2. Course slides: addelli.xhtml (PDF for printing).

3. Sections of the Pari/GP Tutorial and User's Guide on elliptic curves. (Copies of the Pari/GP documents may be found on chern in /math/local/doc/apps/pari.)

Tue., Mar. 3:

Written Assignment No. 2 (PDF for printing —classical HTML for terminal window browsing) is due.

Thu., Feb. 26:

LaTeX-related examples for study in connection with Written Assignment No. 2 may be found in the course web at assgt/tex/ in the items having names that begin with “assgt2-example”. (The XHTML + MathML files were made from LaTeX source using mzlatex.)

Exercises:

1. No LaTeX source is provided for the variant form assgt/tex/assgt2-examplea.pdf. Try creating LaTeX source that may be used to generate this variant.

2. Use gp to assist with investigations of the iterative behavior of certain generalizations of the Syracuse function described in this handout: assgt/linmadecoprime.xhtml (or assgt/linmadecoprime.pdf)

Tue., Feb. 24:

Tasks:

1. Explore the web for free software that can be used to translate HTML to LaTeX.

2. Explore the web for free software that purports to translate LaTeX to HTML.

3. Try using the tex4ht commands htlatex and mzlatex (as found on chern) to translate the documents found in the course web at assgt/tex/.

4. Try out El Gamal cryptography using the gp code from the file in the course web at assgt/code/elg.

Thu., Feb. 12:

Reading about (1) LaTeX and (2) topics in cryptography:

1. LaTeX
   Some introductory things available at the Comprehensive TeX Archive Network – CTAN (for which local copies are available):

   Very short guide

   Formatting information

   Not so short introduction

2. Cryptography

   Diffie Hellman key exchange (at Wikipedia)

   El Gamal encryption (at Wikipedia)

Tasks:

1. Rewrite your HTML response to assignment no. 1 in LaTeX. Then (a) use the program latex, e.g., on chern, to make a DVI file (viewable with a DVI reader such as xdvi) and (b) use the program pdflatex to make a PDF file (viewable with, as available, xpdf, or gpdf, or Adobe Reader™, or …)

2. Write one or more functions for gp to facilitate the tasks of two cooperating partners using Diffie-Hellman key exchange with the multiplicative group of $\mathbf{Z}⁄p\mathbf{Z}$ (the integers modulo $p$) for a given prime $p$.

Tue., Feb. 10:

Written Assignment No. 1 Submit this assignment through your University at Albany web site at the (relative) URL mat587s09/assgt1.html. (Make sure that it is a valid HTML document.) The HTML body should consist of an ordered list (i.e., ol) with two items (i.e., two li's) corresponding to the two assigned tasks.

1. Write a function cfas for gp-2.3 (the command line interface to Pari/gp, version 2.3) that, given a rational number, returns the alternating sum of the integers in its finite continued fraction expansion. More precisely, if $r$ is the given rational number and $$r=a_1+\frac{1}{a_2+\frac{1}{a_3+\dots +\frac{1}{a_n}}}$$ its (finite) continued fraction expansion, the function will return the integer $$a_1-a_2+a_3-+\dots +{\left(-1\right)}^{n+1}{a}_n\text{.}$$

   Once your code is working correctly, for your submitted response to this task place the listing of your code for cfas verbatim in assgt1.html using the HTML pre element.

2. Using gp-2.3 and the function you wrote in the previous task determine the alternating sum of the ${30}^{\mathrm{th}}$ convergent of $\pi$¹

   Comment on 6 Feb: I've had several questions about this second task. My intention is that you determine the ${30}^{\mathrm{th}}$ convergent of $\pi$ (a rational number) explicitly – see, for example, the fourth task in the assignment for Jan. 29 – and then feed it to cfas. Unlike the first task that only asks for a listing of (working) code, your work on this task should be written up as a math problem solution with an explanation of what you did.

Thu., Feb. 5:

Tasks:

• Become familiar with the W3C reference document on HTML 4.01, which is classic HTML.

• If you have not already done so, open a web site under your University at Albany user account (the top page may be visibly blank or otherwise publicly useless if you wish).

• Place a translation, whether automatically-generated or “manually written” of the SGML document tinc.sgml in your web site at the (relative) URL mat587s09/tinc.html. Make sure that it is a valid HTML document.

Note 1: The document on using the math network (also available as PDF or DVI) in this course have been revised.

Note 2: Because the understanding of markup languages is a topic in this course it is not appropriate at this stage to use a program other than a plain text editor for this task. Moreover, one also should not attempt to use a “word processor” since sometimes, even when creating “plain text”, such programs do not generate plain text correctly.

Tue., Feb. 3:

Reading:

• Read through the slides on computing basics (also available as PDF).

• Read through the slides on HTML, SGML, and XML (also available as PDF).

• Read this document on SGML and XML (also available as PDF or DVI).

Exercises:

1. Of documents that can be found on the web claiming to be W3C HTML 4.01, find 3 examples that are valid and also find 3 examples that are not valid. For this task retrieve the underlying HTML files, and use the command “validhtml” found in the unix network.

   A version of “validhtml” suitable for this task can be downloaded to your computer from

   http://math.albany.edu/~hammond/gellmu/gvalidhtml-0.9.tgz

   (It will require you to have OpenSP, which can be found at the web site of OpenJade; you do not need to download OpenJade. Note also that OpenSP is packaged for various systems that have software distributed in packages.)

2. (Challenging at this point) Write a program in whatever language for translating the SGML document type represented by art.dtd to HTML 4.01 document type and then use that program to translate the document tinc.sgml to an HTML 4.01 document.

Thu., Jan. 29:

Tasks:

1. Review my course notes for Math 326 on Continued Fractions. The main points for our purpose here are these:

   1. Every rational number has a finite continued fraction expansion that may be represented by a finite sequence $\left[a_1,a_2,\dots ,a_n\right]$ of integers with $a_i>0$ for $i>1$.

   2. The rational number represented by a given finite sequence is determined by a backward recursion where $a=\left[a\right]$ and $$\left[a_m,\dots ,a_n\right]=a_m+\frac{1}{\left[a_{m+1},\dots ,a_n\right]}\text{when}n>m\text{.}$$

2. Become familiar with the computer algebra system Pari/GP. (Pari is the name of a library; the user application is GP.) Either acquire a personal copy or learn how to use it on the campus math network (also available as PDF or DVI) (where it may be found as /math/local/solaris/bin/gp-2.3. Read the first 5 sections of the Tutorial, and read § 2.6.1 of the User's Guide.

3. Write your own gp function for the Syracuse function.

4. Write your own gp function that when given a finite vector of integers, representing the continued fraction expansion of a rational number, computes the rational number it represents.

Tue., Jan. 27:

Tasks:

1. Read the Wikipedia page on Maple, and in a Maple session work through the code examples found there. Note that Maple is available at many public computing stations on campus and also through remote login to itsunix.albany.edu.

2. The Syracuse function $s$ is defined for integers $n$ by $$s\left(n\right)=\left\{\begin{array}{cc}\hfill 1& \text{if}n\le 1\hfill \\ \hfill 3n+1& \text{if}n>1\text{is odd}\hfill \\ \hfill n⁄2& \text{if}n>1\text{is even}\hfill \end{array}\right.$$ The iterates of $s$ are $$s_1\left(n\right)=s\left(n\right),s_2\left(n\right)=s\left(s\left(n\right)\right),s_3\left(n\right)=s\left(s\left(s\left(n\right)\right)\right),\dots \text{.}$$ For example, $s_1\left(6\right)=s\left(6\right)=3$, $s_2\left(6\right)=s\left(3\right)=10$, $s_3\left(6\right)=s\left(10\right)=5$, $s_4\left(6\right)=s\left(5\right)=16$, $s_5\left(6\right)=s\left(16\right)=8$, $s_6\left(6\right)=s\left(8\right)=4$, $s_7\left(6\right)=s\left(4\right)=2$, $s_8\left(6\right)=s\left(2\right)=1$. Since the $8$th iterate of $s$ applied to $6$ is $1$, all higher iterates of $s$ applied to $6$ are $1$.

   The Syracuse function may be defined in Maple with a “one line” procedure definition as follows:

   syr := n -> piecewise(n <= 1, 1, modp(n, 2) = 0, 1/2 n, 3 n + 1);

   Use Maple to find the 5 smallest values of $n$ for which the first $2n+1$ iterations of $s$ applied to $n$ fail to yield $1$.

Thu., Jan. 22:

First meeting: No assignment.

UP  |   TOP  |   Department

Footnotes

1. * The (rational) value of the initial segment of length $30$ in the (infinite) continued fraction expansion of $\pi$.