Cryptography-Digest Digest #905, Volume #9 Sun, 18 Jul 99 07:13:04 EDT
Contents:
Re: Math, Math, Math (David A Molnar)
Re: Math, Math, Math (Peter L. Montgomery)
Re: Math, Math, Math ("Douglas A. Gwyn")
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: Math, Math, Math ("Douglas A. Gwyn")
Re: Math, Math, Math (person)
Re: Math, Math, Math (person)
Re: Math, Math, Math ("Douglas A. Gwyn")
Re: How Big is a Byte? (was: New Encryption Product!) ([EMAIL PROTECTED])
Re: How Big is a Byte? (was: New Encryption Product!) ("Michael D.")
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Math, Math, Math
Date: 18 Jul 1999 07:16:43 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> David A Molnar wrote:
>> Why does geometry help?
> I don't think it's essential, but it can be helpful, since good
> geometric intuition can help with some mathematical problems,
> for example, cluster analysis.
Thanks for pointing this out. I did not know what cluster analysis was,
but a web search is revealing some interesting pages.
> There is another example in a paper
> by Wyllys called "This Matrix Business" that appeared in three
> parts in the NSA Tech. J. (the first two parts are unclassified),
> where a linear-algebra problem is cast in terms of nearest point
> to a plane, etc.
This sounds a good deal like the "geometry of numbers" which I've seen
associated with lattice basis reduction. Should have thought of that.
Thanks for the pointer; I'll see if I can find the article.
Thanks,
-David Molnar
------------------------------
From: [EMAIL PROTECTED] (Peter L. Montgomery)
Subject: Re: Math, Math, Math
Date: Sun, 18 Jul 1999 08:11:08 GMT
In article <[EMAIL PROTECTED]> Person <[EMAIL PROTECTED]> writes:
>I`m a college student... I`m majoring in computer science but I would
>like to specialize in cryptographic algorithms. Thus far, In addition to
>my general education curiculum and computer science courses, I`ve
>completed the following courses at the community college where I go to
>school...
>beginning algebra
>intermediate algebra
>pre-calculus
>calculus I
>calculus II
>In addition to the above courses, I will also complete the following
>courses before I transfer...
>calculus III
>linear algebra
>differential equations
>discrete mathematics
>boolean algebra
Going from beginning algebra to the sophomore-level courses
on your second line is alot to accomplish in the two years
one normally stays at a community college.
>So here is my question. Which mathematics courses should I take in the
>upper division level in order to learn the necessary mathematics to
>study and develop cryptographic algorithms ? I`m probably going to
>atleast get a minor in mathematics. But I may also double major in
>mathematics and computer science. Which mathematics courses should
>I take ?
>
Take abstract algebra (groups, rings, fields) and number theory
early. Be sure your linear algebra course covers theory and proofs,
not simply computing the determinant and inverse of a 3 x 3 matrix.
You need a strong understanding of mathematical induction,
which your discrete mathematics course will partially cover.
Try to take a computational number theory course, but
take numerical analysis or graphics if this is not offered,
to get practice coding mathematical algorithms.
Statistics is useful.
In the computer science department, start with a programming
language. Learn about data structures, such as
linked lists and binary trees. Take an assembly language class
(perhaps named computer organization or computer architecture)
to learn how the machine carries out your programs.
Take analysis of algorithms (perhaps named computational complexity)
so you can estimate how long your
programs will run (e.g., how does the time to encrypt
vary when you switch from a 128-bit key to a 256-bit key?).
Parallel algorithms is desirable.
--
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Math, Math, Math
Date: Sun, 18 Jul 1999 09:27:51 GMT
David A Molnar wrote:
> Thanks for the pointer; I'll see if I can find the [Wyllys] article.
That's most unlikely.. If I ever get my Web site set up, that'll be
one of the documents there.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 18 Jul 1999 05:02:18 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Math, Math, Math
Date: Sun, 18 Jul 1999 10:11:22 GMT
person wrote:
> How applicable is calculus and analysis to cryptography ? If given
> the choice, should I take algebra courses such as advanced linear
> algebra and abstract algebra instead of advanced calculus courses ?
If you're definitely aiming at a career in cryptology, then yes,
by all means concentrate on abstract algebra (rings, fields, etc.)
in preference to advanced calculus ("analysis").
> Why or why not ?
Algebra studies and describes structure. The cryptanalyst tries to
detect, then exploit, the structure of the encryption system.
There is an active field of study called "coding theory"; see the
IEEE Journal of Information Theory for a sample. Much of modern
cryptology and communication system design in general makes use of
coding theory or equivalent methodology. Coding theory is almost
entirely algebraic.
------------------------------
From: person <[EMAIL PROTECTED]>
Subject: Re: Math, Math, Math
Date: Sun, 18 Jul 1999 02:31:36 -0700
Reply-To: [EMAIL PROTECTED]
"Peter L. Montgomery" wrote:
> In article <[EMAIL PROTECTED]> Person <[EMAIL PROTECTED]> writes:
>
> >I`m a college student... I`m majoring in computer science but I would
> >like to specialize in cryptographic algorithms. Thus far, In addition to
> >my general education curiculum and computer science courses, I`ve
> >completed the following courses at the community college where I go to
> >school...
>
> >beginning algebra
> >intermediate algebra
> >pre-calculus
> >calculus I
> >calculus II
>
> >In addition to the above courses, I will also complete the following
> >courses before I transfer...
>
> >calculus III
> >linear algebra
> >differential equations
> >discrete mathematics
> >boolean algebra
>
> Going from beginning algebra to the sophomore-level courses
> on your second line is alot to accomplish in the two years
> one normally stays at a community college.
>
> >So here is my question. Which mathematics courses should I take in the
> >upper division level in order to learn the necessary mathematics to
> >study and develop cryptographic algorithms ? I`m probably going to
> >atleast get a minor in mathematics. But I may also double major in
> >mathematics and computer science. Which mathematics courses should
> >I take ?
> >
> Take abstract algebra (groups, rings, fields) and number theory
> early. Be sure your linear algebra course covers theory and proofs,
> not simply computing the determinant and inverse of a 3 x 3 matrix.
> You need a strong understanding of mathematical induction,
> which your discrete mathematics course will partially cover.
> Try to take a computational number theory course, but
> take numerical analysis or graphics if this is not offered,
> to get practice coding mathematical algorithms.
> Statistics is useful.
>
> In the computer science department, start with a programming
> language. Learn about data structures, such as
> linked lists and binary trees. Take an assembly language class
> (perhaps named computer organization or computer architecture)
> to learn how the machine carries out your programs.
> Take analysis of algorithms (perhaps named computational complexity)
> so you can estimate how long your
> programs will run (e.g., how does the time to encrypt
> vary when you switch from a 128-bit key to a 256-bit key?).
> Parallel algorithms is desirable.
> --
> [EMAIL PROTECTED] Home: San Rafael, California
> Microsoft Research and CWI
Well... as I said, I have completed the following courses and received an A in all
of them....
Beginning algebra
Intermediate algebra
Trigonometry
Pre-Calculus
Calculus I
Calculus II
This is the order in which all students are supposed to take these courses at my
community college as well as every other college that I know of. Before I transfer
I will take the following courses...
Calculus III
Linear Algebra
Differential Equations
Discrete mathematics
Boolean Algebra
Again... I will take these courses in that order as that is how my community
college requres me to take them. And, regarding computer science courses I have
already taken the following courses...
Pascal programming
C programming
C++ programming
Computer Organization and Machine Language
Computer Organization and Assembly Language
And I`ll still take the following courses before I transfer...
Data Structures and Algorithms
Java programming
Software engineering in Java
Notice how these courses reflect exactly your suggestions. But, let me ask you
this. How applicable is calculus and analysis to cryptography ? If given the
choice, should I take algebra courses such as advanced linear algebra and abstract
algebra instead of advanced calculus courses ? Why or why not ?
[EMAIL PROTECTED]
------------------------------
From: person <[EMAIL PROTECTED]>
Subject: Re: Math, Math, Math
Date: Sun, 18 Jul 1999 02:33:38 -0700
Reply-To: [EMAIL PROTECTED]
"Peter L. Montgomery" wrote:
> In article <[EMAIL PROTECTED]> Person <[EMAIL PROTECTED]> writes:
>
> >I`m a college student... I`m majoring in computer science but I would
> >like to specialize in cryptographic algorithms. Thus far, In addition to
> >my general education curiculum and computer science courses, I`ve
> >completed the following courses at the community college where I go to
> >school...
>
> >beginning algebra
> >intermediate algebra
> >pre-calculus
> >calculus I
> >calculus II
>
> >In addition to the above courses, I will also complete the following
> >courses before I transfer...
>
> >calculus III
> >linear algebra
> >differential equations
> >discrete mathematics
> >boolean algebra
>
> Going from beginning algebra to the sophomore-level courses
> on your second line is alot to accomplish in the two years
> one normally stays at a community college.
>
> >So here is my question. Which mathematics courses should I take in the
> >upper division level in order to learn the necessary mathematics to
> >study and develop cryptographic algorithms ? I`m probably going to
> >atleast get a minor in mathematics. But I may also double major in
> >mathematics and computer science. Which mathematics courses should
> >I take ?
> >
> Take abstract algebra (groups, rings, fields) and number theory
> early. Be sure your linear algebra course covers theory and proofs,
> not simply computing the determinant and inverse of a 3 x 3 matrix.
> You need a strong understanding of mathematical induction,
> which your discrete mathematics course will partially cover.
> Try to take a computational number theory course, but
> take numerical analysis or graphics if this is not offered,
> to get practice coding mathematical algorithms.
> Statistics is useful.
>
> In the computer science department, start with a programming
> language. Learn about data structures, such as
> linked lists and binary trees. Take an assembly language class
> (perhaps named computer organization or computer architecture)
> to learn how the machine carries out your programs.
> Take analysis of algorithms (perhaps named computational complexity)
> so you can estimate how long your
> programs will run (e.g., how does the time to encrypt
> vary when you switch from a 128-bit key to a 256-bit key?).
> Parallel algorithms is desirable.
> --
> [EMAIL PROTECTED] Home: San Rafael, California
> Microsoft Research and CWI
Oh yeah... and... just to clarify...
I`ll be starting my fifth year of community college in the fall. :-)
[EMAIL PROTECTED]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Math, Math, Math
Date: Sun, 18 Jul 1999 10:00:26 GMT
person wrote:
> ... what I was thinking of doing was taking a course in linear
> algebra (in addition to the course that I`ll take as a lower
> division course before I transfer), two semesters of advanced
> calculus, real analysis, and complex analysis. Are these classes
> at all applicable to cryptography?
Almost any mathematics has *some* application in cryptology, as
well as in engineering, sciences, etc. However, calculus much
past college freshman level (in the US), real analysis, and
complex analysis don't have a lot of application in cryptology.
> The school that I will be going to also offers number theory,
> two semesters of abstract algebra, combinatorics, and a course
> in discrete dynamical systems and chaos. Should I take these
> courses instead? What type of curriculum would you recommend
> among these courses.
Abstract algebra is very important for cryptology, particularly
the theory of finite fields.
I'm not sure what is taught in a "combinatorics" course, but
certain combinatoric skills are indeed useful in cryptology.
While I think dynamical systems are worth knowing about, their
theory hasn't had a lot of impact on cryptology.
My main advice is to be prepared to learn what you need on
your own, which is facilitated by a good general grounding
in mathematics. For example, if you need to learn about
zero-information proofs, there are numerous articles available,
both on and off the Internet, and a basic knowledge of graph
theory (which may be a component of a topology or combinatorics
course) will help you to understand some of them.
> Also... I`ve never seen alot of those courses you listed
> required for computer science or electrical engineering majors.
> The only courses I`ve seen required are complex analysis and
> signals and communications theory.
I don't think you asked what was recommended for general CS
or EE majors! EEs are expected to find the poles and zeros
of transfer functions of systems, which bear on stability
and other matters of interest, and sometimes complex analysis
is useful there. Also, amplitudes and phases of signals can
be analyzed more readily using complex numbers (phasors), and
this carries over into Fourier analysis. However, specialized
topics like homotopies or rational and meromorphic functions
don't help the cryptologist very much.
You might consider getting a textbook on "mathematical
methods for scientists and engineers", which can serve as a
quick way to come up to speed on most standard techniques,
for example the use of Laplace transforms to solve diffeqs,
or Lagrange undetermined multipliers, etc. Sooner or later
a working cryptomathematician may need to know almost any of
these things, but it's asking too much to learn them all in
advance of encountering real applications for them.
The most important thing is to learn the basics on which
further developments are built, and to develop some facility
in thinking in abstract mathematical terms. As an actual
example, the other day it occurred to me (while reading about
cyclic codes) that there was probably a theorem to the effect
that, when using polynomials to describe systems, any
structural constraint on the whole system expressible as a
polynomial could be used as a "modulus" and the resulting
polynomial descriptions would all continue to work. E.g.,
{whatever} modulo (x^2+1) for complex numbers expressed as
polynomials ax+b. But I was unsure of this until I asked
a professional mathematician, who told me immediately why
this idea works.. He was much better at thinking about
such things!
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.folklore.computers
Subject: Re: How Big is a Byte? (was: New Encryption Product!)
Date: Sun, 18 Jul 99 08:47:56 GMT
In article <jL2k3.3986$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Peter Seebach) wrote:
>In article <[EMAIL PROTECTED]>,
>Natarajan Krishnaswami <[EMAIL PROTECTED]> wrote:
>>On Thu, 15 Jul 1999 22:59:44 GMT, Peter Seebach <[EMAIL PROTECTED]>
wrote:
>>> This is partially because "he" is a gender-neutral pronoun in English,
while
>>> "she" isn't, and "it" is a pronoun for the inanimate. "he" is
correctly used
>>> both for typeless entities and for male entities.
>
>>Quite a few English-language native speakers (and publishers) have
>>rejected that position. (Unlike programming languages, natural ones
>>are in a constant state of flux. ;-) The social context arising from
>>the women's equality movement has precipitated, at least in the US, a
>>dramatic reduction in use of masculine pronouns, compounds of 'man,
>>etc., in generic contexts, and a fairly widespread (if mild) antipathy
>>towards their use as such.
>
>Oh, certainly. However, I disapprove of political changes to languages.
>That change breaks too much existing code. A lot of people have decided
to
>"reject" that position, mostly based on made-up etymologies or false
claims
>about the historical origins of our current set of words.
Yea, working on real stuff isn't the "in" thing these days.
>
>Essentially, I treat these people the same way I treat anyone who tries to
>redefine words to fit a political agenda.
But doesn't it make you feel as if you're trying to stop a
hurricane? I've tried and I couldn't be accused of being a
male chauvinist pig.
>
>>It's not inconceivable that in another 20
>>years, it may be considered poor style ("agrammatical") to use them
>>that way (here).
>
>It would be a shame, though, because we'd lose a lot of very expressive
text.
>"Man's inhumanity to man" is a much more elegant phrase than anything you
can
>do once you lose that usage.
Yup.
>
>In my own work, I mostly use 'he' as a gender-neutral pronoun, but
>in the Hacker FAQ, I switch pronouns every question to keep people on
their
>toes.
Well, that's pain in the ass just in maintenance of a document.
>
>(Curiously, I get flames about this; not on the grounds that "he is gender
>neutral", but on the grounds that "there aren't many female hackers". I
don't
>know, but I'm guessing none of the people complaining are female or over
18.)
There are a lot of people who can't smell a myth when they see one.
/BAH
Subtract a hundred and four for e-mail.
------------------------------
From: "Michael D." <[EMAIL PROTECTED]>
Crossposted-To: alt.folklore.computers
Subject: Re: How Big is a Byte? (was: New Encryption Product!)
Date: Sun, 18 Jul 1999 05:46:16 -0500
I think that a major problem that we all have is that our mothers, yes, mine
as well as yours, taught us that the first number is one(1) rather than
zero(0). It was cute when we were three(3), but now, as a result of that
conditioning, we cannot do math in our heads.
Michael D.
[EMAIL PROTECTED]
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> wtshaw wrote:
> >
> > In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
wrote:
> >
> > >
> > > The IBM 7074 was a decimal based machine. Ours had 10,000 ten digit
> > > signed words. Each of the digits used five bits with a two-out-of-five
> > > coding scheme.
> > >
> > > So perhaps God did mean for us to think in decimal....
> > >
> > Please try not to confuse IBM with God; on the other hand, God is not
apt
> > to be confused, just perplexed.
> >
> > Occasionally, people, individuals, families, have other then ten
fingers;
> > God allows options and gives all of them a chance.
>
> I'm having a real hard time working out base zero arithmetic.
>
> > --
> > Most wrestlers and politicians seem to have pretty the same
> > agenda, seek various kinds of by appearing to do things they are
> > not doing, catering to specialty groups of supporters, and as a
> > result of deals, learn to take falls when they know better. Those
> > who do not go along tend to be excluded and punished.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
