Assignments are listed in reverse chronological order, i.e., most recent first, and labeled by the date due.
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 sequencepostion (beginning with $1$) of the current point in the sequence.
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]\phantom{\rule{0.6em}{0ex}}\text{.}$$ What is the smallest number of “tries” that will provide a list of $127$ points for this code sequence?
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:

A message encrypted by a list of pairs of points on an elliptic curve is waiting for you at the url
The El Gamal key for decoding it is 950.
What sequence of points on the curve was encoded?
What is the content of the message?
Reencrypt 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 builtin functions. See also unichr().
Schedule for this class:

What builtin function in Sage will, for a given pair $\left(a,b\right)$ of integers, produce integers $\left(r,s\right)$ such that $\mathrm{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 builtin function. What builtin function can be used for the same task?
Schedule for this class:

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:

Schedule for this class:

Schedule for this class:

Updated student presentation schedule (PDF for printing —classical HTML for terminal window browsing).
Redo 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).
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.
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 sputf8xmlvalid to validate the XHTML+MathML
Updated student presentation schedule (PDF for printing —classical HTML for terminal window browsing).
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?
Morph the separate document type definition hack/hack.dtd into an XML document type definition shadowing it but using lower case names.
Write an sgmlspl script for translating documents under hack/hack.dtd to an XML document type shadowing it but using lower case names.
Use this script to translate hack/hack2.sgml to the XML shadow document type.
Use the program spxmlvalid 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.
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?
Read about the use of sgmlspl for translating SGML (or XML) documents. There is also a chapter on sgmlspl in The LaTeX Web Companion.
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.
Fill in the skeleton script to morph it into an sgmlspl script for translation of hack1.sgml to an HTML document.
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]$.
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$.
$\left[1,4\right]+\left[2,2\right]$
$\left[5,10\right]\left[3,4\right]$
$6\xb7\left[1,2\right]$
Course slides: addelli.xhtml (PDF for printing).
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.)
Exercises:
No LaTeX source is provided for the variant form assgt/tex/assgt2examplea.pdf. Try creating LaTeX source that may be used to generate this variant.
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)
Explore the web for free software that can be used to translate HTML to LaTeX.
Explore the web for free software that purports to translate LaTeX to HTML.
Try using the tex4ht commands htlatex and mzlatex (as found on chern) to translate the documents found in the course web at assgt/tex/.
Try out El Gamal cryptography using the gp code from the file in the course web at assgt/code/elg.
LaTeX
Some introductory things available at the Comprehensive TeX
Archive Network – CTAN (for
which local copies are available):
Cryptography
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 …)
Write one or more functions for gp to facilitate the tasks of two cooperating partners using DiffieHellman key exchange with the multiplicative group of $\mathbf{Z}\u2044p\mathbf{Z}$ (the integers modulo $p$) for a given prime $p$.
Write a function cfas for gp2.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}\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}\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.
Using gp2.3 and the function you wrote in the previous task determine the alternating sum of the ${30}^{\mathrm{th}}$ convergent of $\pi $^{1}
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 automaticallygenerated 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.
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).
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.
(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.
Review my course notes for Math 326 on Continued Fractions. The main points for our purpose here are these:
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$.
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]}\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}\text{when}\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}n>m\phantom{\rule{0.6em}{0ex}}\text{.}$$
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/gp2.3. Read the first 5 sections of the Tutorial, and read § 2.6.1 of the User's Guide.
Write your own gp function for the Syracuse function.
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.
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.
The Syracuse function $s$ is defined for integers $n$ by $$s\left(n\right)=\left\{\begin{array}{cc}\hfill 1& \phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}\text{if}\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}n\le 1\hfill \\ \hfill 3n+1& \phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}\text{if}\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}n>1\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}\text{is odd}\hfill \\ \hfill n\u20442& \phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}\text{if}\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}n>1\phantom{\rule{0.6em}{0ex}}\phantom{\rule{0.6em}{0ex}}\text{is even}\hfill \end{array}\right.$$ The iterates of $s$ are $${s}_{1}\left(n\right)=s\left(n\right),\phantom{\rule{0.6em}{0ex}}{s}_{2}\left(n\right)=s\left(s\left(n\right)\right),\phantom{\rule{0.6em}{0ex}}{s}_{3}\left(n\right)=s\left(s\left(s\left(n\right)\right)\right),\dots \phantom{\rule{0.6em}{0ex}}\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:
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$.
UP  TOP  Department